Sperner's lemma (original) (raw)

About DBpedia

Das Lemma von Sperner, oft Spernersches Lemma genannt, englisch Sperner’s Lemma, ist ein mathematisches Resultat aus dem Teilgebiet der Topologie. Es geht zurück auf den deutschen Mathematiker Emanuel Sperner, der es im Jahr 1928 veröffentlicht hat. Die Bedeutung des Lemmas liegt darin, dass mit seiner Hilfe – und damit lediglich mittels elementarer kombinatorischer Methoden – eine ganze Anzahl wichtiger mathematischer Lehrsätze zu beweisen sind, wie der brouwersche Fixpunktsatz und verwandte Resultate oder auch der Satz von der Invarianz der offenen Menge und nicht zuletzt der Pflastersatz von Lebesgue.

thumbnail

Property Value
dbo:abstract Das Lemma von Sperner, oft Spernersches Lemma genannt, englisch Sperner’s Lemma, ist ein mathematisches Resultat aus dem Teilgebiet der Topologie. Es geht zurück auf den deutschen Mathematiker Emanuel Sperner, der es im Jahr 1928 veröffentlicht hat. Die Bedeutung des Lemmas liegt darin, dass mit seiner Hilfe – und damit lediglich mittels elementarer kombinatorischer Methoden – eine ganze Anzahl wichtiger mathematischer Lehrsätze zu beweisen sind, wie der brouwersche Fixpunktsatz und verwandte Resultate oder auch der Satz von der Invarianz der offenen Menge und nicht zuletzt der Pflastersatz von Lebesgue. (de) En mathématiques, le lemme de Sperner, dû à Emanuel Sperner, est un analogue combinatoire du théorème du point fixe de Brouwer. Le lemme de Sperner affirme que chaque coloriage de Sperner d'une triangulation d'un simplexe de dimension n contient une cellule colorée de toutes les n + 1 couleurs. Le premier résultat de ce type fut démontré par Emanuel Sperner en 1928, en relation avec des preuves du théorème de l'invariance du domaine. Les coloriages de Sperner ont été utilisés pour des déterminations effectives de points fixes, dans des algorithmes de résolution d'équations, et sont employés dans des procédures de partage équitable. (fr) In mathematics, Sperner's lemma is a combinatorial result on colorings of triangulations, analogous to the Brouwer fixed point theorem, which is equivalent to it. It states that every Sperner coloring (described below) of a triangulation of an -dimensional simplex contains a cell whose vertices all have different colors. The initial result of this kind was proved by Emanuel Sperner, in relation with proofs of invariance of domain. Sperner colorings have been used for effective computation of fixed points and in root-finding algorithms, and are applied in fair division (cake cutting) algorithms. Finding a Sperner coloring or equivalently a Brouwer fixed point is now believed to be an intractable computational problem, even in the plane, in the general case. The problem is PPAD-complete, a complexity class invented by Christos Papadimitriou. According to the Soviet Mathematical Encyclopaedia (ed. I.M. Vinogradov), a related 1929 theorem (of Knaster, Borsuk and Mazurkiewicz) had also become known as the Sperner lemma – this point is discussed in the English translation (ed. M. Hazewinkel). It is now commonly known as the Knaster–Kuratowski–Mazurkiewicz lemma. (en) Il lemma di Sperner è un teorema della teoria dei grafi che ha delle importanti applicazioni in topologia; in particolare, permette quella che è forse la dimostrazione più elementare del teorema del punto fisso di Brouwer. (it) Лемма Шпернера — комбинаторный аналог теоремы Брауэра о неподвижной точке, один из основных результатов комбинаторной топологии. Утверждает, что при любой Шпернеровской раскраске вершин в триангуляции n-мерного симплекса найдётся ячейка триангуляции, вершины которой покрашены во все цвета. Первый результат подобного типа был доказан . (ru)
dbo:thumbnail wiki-commons:Special:FilePath/Sperner2d.svg?width=300
dbo:wikiPageExternalLink https://michael-lemberger.itch.io/sperners-lemma-2d http://nrich.maths.org/1383 http://www.cut-the-knot.org/Curriculum/Geometry/SpernerLemma.shtml
dbo:wikiPageID 465067 (xsd:integer)
dbo:wikiPageLength 28591 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1117725085 (xsd:integer)
dbo:wikiPageWikiLink dbr:Root-finding_algorithm dbr:Monsky's_theorem dbc:Lemmas dbc:Triangulation_(geometry) dbc:Fixed_points_(mathematics) dbr:Cycle_(graph_theory) dbr:Cyclic_polytope dbr:Invariance_of_domain dbr:Pseudomanifold dbr:Topological_combinatorics dbc:Articles_containing_proofs dbr:Analogy dbr:Matching_in_hypergraphs dbr:Mathematics dbr:Christos_Papadimitriou dbr:Emanuel_Sperner dbr:Envy-free_cake-cutting dbr:Function_(mathematics) dbr:Graph_(discrete_mathematics) dbr:Equidissection dbr:Lloyd_Shapley dbr:Simplex dbr:Stefan_Mazurkiewicz dbr:Combinatorics dbr:Competitive_equilibrium dbr:Complexity_class dbr:Francis_Su dbr:Krassimir_Atanassov dbr:Ravindra_Bapat dbr:Polygon dbr:Bronisław_Knaster dbr:Tree_(graph_theory) dbc:Combinatorics dbc:Topology dbc:Fair_division dbr:Cut-the-knot dbr:Fixed_point_(mathematics) dbr:Fair_division dbr:Graph_theory dbr:Symbolic_dynamics dbr:Handshaking_lemma dbr:Harold_W._Kuhn dbr:Hypergraph dbr:KKMS_lemma dbr:Karol_Borsuk dbr:Triangle dbr:Triangulation_(geometry) dbr:Piecewise_linear_manifold dbr:Poincaré–Miranda_theorem dbr:Intermediate_value_theorem dbr:Knaster–Kuratowski–Mazurkiewicz_lemma dbr:Exchange_economy dbr:Polytope dbr:Simmons–Su_protocols dbr:PPAD_(complexity) dbr:Brouwer_fixed_point_theorem dbr:I.M._Vinogradov dbr:Quadrangulation dbr:Periodic_orbit dbr:Voronoi_partition dbr:File:An_illustration_of_the_proof_of_Sperner's_lemma_in_2D.png dbr:File:Sperner1d.svg dbr:File:Spernergraph.svg dbr:File:Spernerlemma.svg dbr:File:Sperner2d.svg
dbp:wikiPageUsesTemplate dbt:Anchor dbt:For dbt:Math dbt:Mvar dbt:Overline dbt:Reflist dbt:Rp dbt:Short_description dbt:Sub dbt:Sup dbt:Analogous_fixed-point_theorems
dct:subject dbc:Lemmas dbc:Triangulation_(geometry) dbc:Fixed_points_(mathematics) dbc:Articles_containing_proofs dbc:Combinatorics dbc:Topology dbc:Fair_division
gold:hypernym dbr:Analog
rdf:type yago:WikicatLemmas yago:WikicatTheoremsInCombinatorics yago:Abstraction100002137 yago:Communication100033020 yago:Lemma106751833 yago:Message106598915 yago:Proposition106750804 dbo:Drug yago:Statement106722453 yago:Theorem106752293
rdfs:comment Das Lemma von Sperner, oft Spernersches Lemma genannt, englisch Sperner’s Lemma, ist ein mathematisches Resultat aus dem Teilgebiet der Topologie. Es geht zurück auf den deutschen Mathematiker Emanuel Sperner, der es im Jahr 1928 veröffentlicht hat. Die Bedeutung des Lemmas liegt darin, dass mit seiner Hilfe – und damit lediglich mittels elementarer kombinatorischer Methoden – eine ganze Anzahl wichtiger mathematischer Lehrsätze zu beweisen sind, wie der brouwersche Fixpunktsatz und verwandte Resultate oder auch der Satz von der Invarianz der offenen Menge und nicht zuletzt der Pflastersatz von Lebesgue. (de) En mathématiques, le lemme de Sperner, dû à Emanuel Sperner, est un analogue combinatoire du théorème du point fixe de Brouwer. Le lemme de Sperner affirme que chaque coloriage de Sperner d'une triangulation d'un simplexe de dimension n contient une cellule colorée de toutes les n + 1 couleurs. Le premier résultat de ce type fut démontré par Emanuel Sperner en 1928, en relation avec des preuves du théorème de l'invariance du domaine. Les coloriages de Sperner ont été utilisés pour des déterminations effectives de points fixes, dans des algorithmes de résolution d'équations, et sont employés dans des procédures de partage équitable. (fr) Il lemma di Sperner è un teorema della teoria dei grafi che ha delle importanti applicazioni in topologia; in particolare, permette quella che è forse la dimostrazione più elementare del teorema del punto fisso di Brouwer. (it) Лемма Шпернера — комбинаторный аналог теоремы Брауэра о неподвижной точке, один из основных результатов комбинаторной топологии. Утверждает, что при любой Шпернеровской раскраске вершин в триангуляции n-мерного симплекса найдётся ячейка триангуляции, вершины которой покрашены во все цвета. Первый результат подобного типа был доказан . (ru) In mathematics, Sperner's lemma is a combinatorial result on colorings of triangulations, analogous to the Brouwer fixed point theorem, which is equivalent to it. It states that every Sperner coloring (described below) of a triangulation of an -dimensional simplex contains a cell whose vertices all have different colors. (en)
rdfs:label Lemma von Sperner (de) Lemme de Sperner (fr) Lemma di Sperner (it) Sperner's lemma (en) Лемма Шпернера (ru)
owl:sameAs freebase:Sperner's lemma yago-res:Sperner's lemma wikidata:Sperner's lemma dbpedia-de:Sperner's lemma dbpedia-fa:Sperner's lemma dbpedia-fr:Sperner's lemma dbpedia-he:Sperner's lemma dbpedia-hu:Sperner's lemma dbpedia-it:Sperner's lemma dbpedia-ru:Sperner's lemma https://global.dbpedia.org/id/4uFqQ
prov:wasDerivedFrom wikipedia-en:Sperner's_lemma?oldid=1117725085&ns=0
foaf:depiction wiki-commons:Special:FilePath/An_illustration_of_the_proof_of_Sperner's_lemma_in_2D.png wiki-commons:Special:FilePath/Sperner1d.svg wiki-commons:Special:FilePath/Sperner2d.svg wiki-commons:Special:FilePath/Spernergraph.svg wiki-commons:Special:FilePath/Spernerlemma.svg
foaf:isPrimaryTopicOf wikipedia-en:Sperner's_lemma
is dbo:knownFor of dbr:Emanuel_Sperner
is dbo:wikiPageRedirects of dbr:Sperner's_Lemma dbr:Polytopal_Sperner_lemma dbr:Sperner_coloring dbr:Sperner_lemma
is dbo:wikiPageWikiLink of dbr:List_of_general_topology_topics dbr:Monsky's_theorem dbr:List_of_graph_theory_topics dbr:Index_of_combinatorics_articles dbr:List_of_lemmas dbr:Topological_combinatorics dbr:Emanuel_Sperner dbr:Equidissection dbr:Chore_division dbr:Combinatorial_Geometry_in_the_Plane dbr:Hall's_marriage_theorem dbr:Krassimir_Atanassov dbr:Brouwer_fixed-point_theorem dbr:Parity_of_zero dbr:Daniel_I._A._Cohen dbr:Discrete_geometry dbr:Fractional_Pareto_efficiency dbr:Kakutani_fixed-point_theorem dbr:Lemma_(mathematics) dbr:List_of_PPAD-complete_problems dbr:Hall-type_theorems_for_hypergraphs dbr:Handshaking_lemma dbr:Sperner's_theorem dbr:Rainbow-independent_set dbr:Knaster–Kuratowski–Mazurkiewicz_lemma dbr:List_of_unsolved_problems_in_fair_division dbr:Sperner's_Lemma dbr:Fisher_market dbr:Fixed-point_theorems dbr:Simmons–Su_protocols dbr:Polytopal_Sperner_lemma dbr:Sperner_coloring dbr:Sperner_lemma
is dbp:knownFor of dbr:Emanuel_Sperner
is foaf:primaryTopic of wikipedia-en:Sperner's_lemma