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.[1] It states that every Sperner coloring (described below) of a triangulation of an n {\displaystyle n} -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.
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.
In one dimension, Sperner's Lemma can be regarded as a discrete version of the intermediate value theorem. In this case, it essentially says that if a discrete function takes only the values 0 and 1, begins at the value 0 and ends at the value 1, then it must switch values an odd number of times.
The two-dimensional case is the one referred to most frequently. It is stated as follows:
Subdivide a triangle ABC arbitrarily into a triangulation consisting of smaller triangles meeting edge to edge. Then a Sperner coloring of the triangulation is defined as an assignment of three colors to the vertices of the triangulation such that
Then every Sperner coloring of every triangulation has at least one "rainbow triangle", a smaller triangle in the triangulation that has its vertices colored with all three different colors. More precisely, there must be an odd number of rainbow triangles.
In the general case the lemma refers to a n-dimensional simplex:
Consider any triangulation T, a disjoint division of A {\displaystyle {\mathcal {A}}} into smaller n-dimensional simplices, again meeting face-to-face. Denote the coloring function as:
where S is the set of vertices of T. A coloring function defines a Sperner coloring when:
A i 1 A i 2 … … --> A i k + 1 {\displaystyle A_{i_{1}}A_{i_{2}}\ldots A_{i_{k+1}}}
are colored only with the colors
i 1 , i 2 , … … --> , i k + 1 . {\displaystyle i_{1},i_{2},\ldots ,i_{k+1}.}
Then every Sperner coloring of every triangulation of the n-dimensional simplex has an odd number of instances of a rainbow simplex, meaning a simplex whose vertices are colored with all n + 1 colors. In particular, there must be at least one rainbow simplex.
We shall first address the two-dimensional case. Consider a graph G built from the triangulation T as follows:
Note that on the interval AB there is an odd number of borders colored 1-2 (simply because A is colored 1, B is colored 2; and as we move along AB, there must be an odd number of color changes in order to get different colors at the beginning and at the end). On the intervals BC and CA, there are no borders colored 1-2 at all. Therefore, the vertex of G corresponding to the outer area has an odd degree. But it is known (the handshaking lemma) that in a finite graph there is an even number of vertices with odd degree. Therefore, the remaining graph, excluding the outer area, has an odd number of vertices with odd degree corresponding to members of T.
It can be easily seen that the only possible degree of a triangle from T is 0, 1, or 2, and that the degree 1 corresponds to a triangle colored with the three colors 1, 2, and 3.
Thus we have obtained a slightly stronger conclusion, which says that in a triangulation T there is an odd number (and at least one) of full-colored triangles.
A multidimensional case can be proved by induction on the dimension of a simplex. We apply the same reasoning, as in the two-dimensional case, to conclude that in a n-dimensional triangulation there is an odd number of full-colored simplices.
Here is an elaboration of the proof given previously, for a reader new to graph theory.
This diagram numbers the colors of the vertices of the example given previously. The small triangles whose vertices all have different numbers are shaded in the graph. Each small triangle becomes a node in the new graph derived from the triangulation. The small letters identify the areas, eight inside the figure, and area i designates the space outside of it.
As described previously, those nodes that share an edge whose endpoints are numbered 1 and 2 are joined in the derived graph. For example, node d shares an edge with the outer area i, and its vertices all have different numbers, so it is also shaded. Node b is not shaded because two vertices have the same number, but it is joined to the outer area.
One could add a new full-numbered triangle, say by inserting a node numbered 3 into the edge between 1 and 1 of node a, and joining that node to the other vertex of a. Doing so would have to create a pair of new nodes, like the situation with nodes f and g.
Andrew McLennan and Rabee Tourky presented a different proof, using the volume of a simplex. It proceeds in one step, with no induction.[2][3]
Suppose there is a d-dimensional simplex of side-length N, and it is triangulated into sub-simplices of side-length 1. There is a function that, given any vertex of the triangulation, returns its color. The coloring is guaranteed to satisfy Sperner's boundary condition. How many times do we have to call the function in order to find a rainbow simplex? Obviously, we can go over all the triangulation vertices, whose number is O(Nd), which is polynomial in N when the dimension is fixed. But, can it be done in time O(poly(log N)), which is polynomial in the binary representation of N?
This problem was first studied by Christos Papadimitriou. He introduced a complexity class called PPAD, which contains this as well as related problems (such as finding a Brouwer fixed point). He proved that finding a Sperner simplex is PPAD-complete even for d=3. Some 15 years later, Chen and Deng proved PPAD-completeness even for d=2.[4] It is believed that PPAD-hard problems cannot be solved in time O(poly(log N)).
Suppose that each vertex of the triangulation may be labeled with multiple colors, so that the coloring function is F : S → 2[n+1].
For every sub-simplex, the set of labelings on its vertices is a set-family over the set of colors [n + 1]. This set-family can be seen as a hypergraph.
If, for every vertex v on a face of the simplex, the colors in f(v) are a subset of the set of colors on the face endpoints, then there exists a sub-simplex with a balanced labeling – a labeling in which the corresponding hypergraph admits a perfect fractional matching. To illustrate, here are some balanced labeling examples for n = 2:
This was proved by Shapley in 1973.[5] It is a combinatorial analogue of the KKMS lemma.
Suppose that we have a d-dimensional polytope P with n vertices. P is triangulated, and each vertex of the triangulation is labeled with a label from {1, …, n}. Every main vertex i is labeled i. A sub-simplex is called fully-labeled if it is d-dimensional, and each of its d + 1 vertices has a different label. If every vertex in a face F of P is labeled with one of the labels on the endpoints of F, then there are at least n – d fully-labeled simplices. Some special cases are:
The general statement was conjectured by Atanassov in 1996, who proved it for the case d = 2.[6] The proof of the general case was first given by de Loera, Peterson, and Su in 2002.[7] They provide two proofs: the first is non-constructive and uses the notion of pebble sets; the second is constructive and is based on arguments of following paths in graphs.
Meunier[8] extended the theorem from polytopes to polytopal bodies, which need not be convex or simply-connected. In particular, if P is a polytope, then the set of its faces is a polytopal body. In every Sperner labeling of a polytopal body with vertices v1, …, vn, there are at least:
fully-labeled simplices such that any pair of these simplices receives two different labelings. The degree degB(P)(vi) is the number of edges of B(P) to which vi belongs. Since the degree is at least d, the lower bound is at least n – d. But it can be larger. For example, for the cyclic polytope in 4 dimensions with n vertices, the lower bound is:
Musin[9] further extended the theorem to d-dimensional piecewise-linear manifolds, with or without a boundary.
Asada, Frick, Pisharody, Polevy, Stoner, Tsang and Wellner[10] further extended the theorem to pseudomanifolds with boundary, and improved the lower bound on the number of facets with pairwise-distinct labels.
Suppose that, instead of a simplex triangulated into sub-simplices, we have an n-dimensional cube partitioned into smaller n-dimensional cubes.
Harold W. Kuhn[11] proved the following lemma. Suppose the cube [0,M]n, for some integer M, is partitioned into Mn unit cubes. Suppose each vertex of the partition is labeled with a label from {1, …, n + 1}, such that for every vertex v: (1) if vi = 0 then the label on v is at most i; (2) if vi=M then the label on v is not i. Then there exists a unit cube with all the labels {1, …, n + 1} (some of them more than once). The special case n = 2 is: suppose a square is partitioned into sub-squares, and each vertex is labeled with a label from {1,2,3}. The left edge is labeled with 1 (= at most 1); the bottom edge is labeled with 1 or 2 (= at most 2); the top edge is labeled with 1 or 3 (= not 2); and the right edge is labeled with 2 or 3 (= not 1). Then there is a square labeled with 1,2,3.
Another variant, related to the Poincaré–Miranda theorem,[12] is as follows. Suppose the cube [0,M]n is partitioned into Mn unit cubes. Suppose each vertex is labeled with a binary vector of length n, such that for every vertex v: (1) if vi = 0 then the coordinate i of label on v is 0; (2) if vi = M then coordinate i of the label on v is 1; (3) if two vertices are neighbors, then their labels differ by at most one coordinate. Then there exists a unit cube in which all 2n labels are different. In two dimensions, another way to formulate this theorem is:[13] in any labeling that satisfies conditions (1) and (2), there is at least one cell in which the sum of labels is 0 [a 1-dimensional cell with (1,1) and (-1,-1) labels, or a 2-dimensional cells with all four different labels].
Wolsey[14] strengthened these two results by proving that the number of completely-labeled cubes is odd.
Musin[13] extended these results to general quadrangulations.
Suppose that, instead of a single labeling, we have n different Sperner labelings. We consider pairs (simplex, permutation) such that, the label of each vertex of the simplex is chosen from a different labeling (so for each simplex, there are n! different pairs). Then there are at least n! fully labeled pairs. This was proved by Ravindra Bapat[15] for any triangulation. A simpler proof, which only works for specific triangulations, was presented later by Su.[16]
Another way to state this lemma is as follows. Suppose there are n people, each of whom produces a different Sperner labeling of the same triangulation. Then, there exists a simplex, and a matching of the people to its vertices, such that each vertex is labeled by its owner differently (one person labels its vertex by 1, another person labels its vertex by 2, etc.). Moreover, there are at least n! such matchings. This can be used to find an envy-free cake-cutting with connected pieces.
Asada, Frick, Pisharody, Polevy, Stoner, Tsang and Wellner[10] extended this theorem to pseudomanifolds with boundary.
More generally, suppose we have m different Sperner labelings, where m may be different than n. Then:[17]: Thm 2.1
Both versions reduce to Sperner's lemma when m = 1, or when all m labelings are identical.
See [18] for similar generalizations.
Brown and Cairns[19] strengthened Sperner's lemma by considering the orientation of simplices. Each sub-simplex has an orientation that can be either +1 or -1 (if it is fully-labeled), or 0 (if it is not fully-labeled). They proved that the sum of all orientations of simplices is +1. In particular, this implies that there is an odd number of fully-labeled simplices.
As an example for n = 3, suppose a triangle is triangulated and labeled with {1,2,3}. Consider the cyclic sequence of labels on the boundary of the triangle. Define the degree of the labeling as the number of switches from 1 to 2, minus the number of switches from 2 to 1. See examples in the table at the right. Note that the degree is the same if we count switches from 2 to 3 minus 3 to 2, or from 3 to 1 minus 1 to 3.
Musin proved that the number of fully labeled triangles is at least the degree of the labeling.[20] In particular, if the degree is nonzero, then there exists at least one fully labeled triangle.
If a labeling satisfies the Sperner condition, then its degree is exactly 1: there are 1-2 and 2-1 switches only in the side between vertices 1 and 2, and the number of 1-2 switches must be one more than the number of 2-1 switches (when walking from vertex 1 to vertex 2). Therefore, the original Sperner lemma follows from Musin's theorem.
There is a similar lemma about finite and infinite trees and cycles.[21]
Mirzakhani and Vondrak[22] study a weaker variant of a Sperner labeling, in which the only requirement is that label i is not used on the face opposite to vertex i. They call it Sperner-admissible labeling. They show that there are Sperner-admissible labelings in which every cell contains at most 4 labels. They also prove an optimal lower bound on the number of cells that must have at least two different labels in each Sperner-admissible labeling. They also prove that, for any Sperner-admissible partition of the regular simplex, the total area of the boundary between the parts is minimized by the Voronoi partition.
Sperner colorings have been used for effective computation of fixed points. A Sperner coloring can be constructed such that fully labeled simplices correspond to fixed points of a given function. By making a triangulation smaller and smaller, one can show that the limit of the fully labeled simplices is exactly the fixed point. Hence, the technique provides a way to approximate fixed points. A related application is the numerical detection of periodic orbits and symbolic dynamics.[23] Sperner's lemma can also be used in root-finding algorithms and fair division algorithms; see Simmons–Su protocols.
Sperner's lemma is one of the key ingredients of the proof of Monsky's theorem, that a square cannot be cut into an odd number of equal-area triangles.[24]
Sperner's lemma can be used to find a competitive equilibrium in an exchange economy, although there are more efficient ways to find it.[25]: 67
Fifty years after first publishing it, Sperner presented a survey on the development, influence and applications of his combinatorial lemma.[26]
There are several fixed-point theorems which come in three equivalent variants: an algebraic topology variant, a combinatorial variant and a set-covering variant. Each variant can be proved separately using totally different arguments, but each variant can also be reduced to the other variants in its row. Additionally, each result in the top row can be deduced from the one below it in the same column.[27]
هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (يناير 2023) مركبة الاستطلاع القتالية طراز 87 النوع مركبة قتالية مدرعة بلد الأصل اليابان تاريخ الاستخدام المستخدمون اليابان قوة الدفاع الذاتي البرية اليابانية تاري…
Gresya Amanda MaaliwugaLahir27 Mei 1995 (umur 28)Ternate, MalukuTinggi175 cm (5 ft 9 in)Pemenang kontes kecantikanGelarPuteri Indonesia Pariwisata 2015Warna rambutHitamWarna mataHitamKompetisiutamaPuteri Indonesia 2015(Runner-up 2)(Puteri Kepulauan Sulawesi)Miss Supranational 2015(30 Besar)(Best National Costume) Gresya Amanda Maaliwuga (lahir 27 Mei 1995) adalah seorang model Indonesia yang menjadi runner-up 2 atau Puteri Indonesia Pariwisata dalam kontes Puteri Indonesia 20…
ثالوث فيرخوف التاريخ سُمي باسم رودلف فيرخوف تعديل مصدري - تعديل ثلاثي فيرشو يصف ثالوث فيرشوف أو ثالوث فيرخوف (بالإنجليزية: Virchow's triad) أو مثلث فيرشوف وهوَ يُعبر عن العوامل الثلاثة التي تسهم في تخثر الدم.[1] فرط التخثر التغيرات الدورة الدموية (ركود، الاضطراب) إصابة ا
American football player (born 1980) American football player Jabar GaffneyGaffney during the Redskins training camp in 2011No. 86, 10Position:Wide receiverPersonal informationBorn: (1980-12-01) December 1, 1980 (age 43)San Antonio, Texas, U.S.Height:6 ft 2 in (1.88 m)Weight:200 lb (91 kg)Career informationHigh school:William M. Raines(Jacksonville, Florida)College:FloridaNFL Draft:2002 / Round: 2 / Pick: 33Career history Houston Texans (2002–2…
Xin hãy đóng góp cho bài viết này bằng cách phát triển nó. Nếu bài viết đã được phát triển, hãy gỡ bản mẫu này. Thông tin thêm có thể được tìm thấy tại trang thảo luận. Liverpool F.C. tại các giải đấu châu ÂuCúp vô địch châu Âu Liverpool giành được vào năm 2005Câu lạc bộLiverpool F.C.Tham dự lần đầuCúp C1 châu Âu 1964-65Tham dự gần nhấtUEFA Champions League 2020-21Danh hiệuChampions League/Cúp …
Опис Хрест-пам’ятник на честь перемоги над французами в Вітчизняній війні 1812 року в селі Городно, Волинська область в селі Городно, Волинська область Джерело http://www.vv-orthodox.org/index.php?articleID=174 Час створення невідомий Автор зображення Невідомий Ліцензія Ця робота є невільною …
Jen Simmons Información personalNacimiento Siglo XX EducaciónEducada en Universidad de Temple (M.F.A. en Arte de los nuevos medios)Gordon College (B.A. en Sociología; hasta 1991) Información profesionalOcupación Desarrollador web, diseñadora gráfica y podcaster Empleador Mozilla Sitio web jensimmons.com [editar datos en Wikidata] Jen Simmons es una diseñadora gráfica, desarrolladora web, educadora y conferencista estadounidense conocida por su experiencia en estánda…
اضغط هنا للاطلاع على كيفية قراءة التصنيف خبزية الكامانسي المرتبة التصنيفية نوع التصنيف العلمي النطاق: حقيقيات النوى المملكة: نباتات الشعيبة: بذريات غير مصنف: كاسيات البذور غير مصنف: ثنائيات الفلقة الطائفة: الوردانية غير مصنف: الوردانيات غير مصنف: الوردونات الرتبة: ال…
Віллі ван де Керкгоф Віллі ван де Керкгоф Особисті дані Повне ім'я Вільгельмус Антоніус ванде Керкгоф Народження 16 вересня 1951(1951-09-16) (72 роки) Гелмонд, Нідерланди Зріст 182 см Вага 78 кг Громадянство Нідерланди Позиція півзахисник Інформація про клуб Поточний клуб…
Uto宇土市 CiudadBanderaEscudo UtoLocalización de Uto en Japón Uto en la prefectura de KumamotoCoordenadas 32°41′17″N 130°39′35″E / 32.688, 130.65977777778Entidad Ciudad • País JPN • Región Kyūshū • Isla Kyūshū • Prefectura KumamotoSuperficie • Total 74,30 km²[1]Población (1 de marzo de 2021) • Total 35 947 hab. • Densidad 484,53 hab/km²Huso horario JST (UTC+9)Código posta…
Arzachena Alzachèna, AltzaghènaKomuneComune di ArzachenaLokasi Arzachena di Provinsi SassariNegara ItaliaWilayah SardiniaProvinsiSassari (SS)Pemerintahan • Wali kotaRoberto RagneddaLuas • Total230,85 km2 (89,13 sq mi)Ketinggian85 m (279 ft)Populasi (2016) • Total13,650[1]Zona waktuUTC+1 (CET) • Musim panas (DST)UTC+2 (CEST)Kode pos07020-21Kode area telepon0789Situs webhttp://www.comunearzachena.it/ Arzac…
Institut français du Proche-OrientHistoireFondation 2003Prédécesseurs Institut français d’études arabes de Damas (d), Institut français d’archéologie du Proche-Orient (d), Centre d'études et de recherches sur le Moyen-Orient contemporain (d)CadreCode UAR 3135Zone d'activité Proche-OrientType Centre de rechercheForme juridique UMIFREPays FranceOrganisationDirection Myriam CatusseSite web www.ifporient.orgmodifier - modifier le code - modifier Wikidata L’Institut français du …
2 Kings, chapter 11 2 Kings 11← chapter 10chapter 12 →The pages containing the Books of Kings (1 & 2 Kings) Leningrad Codex (1008 CE).BookSecond Book of KingsHebrew Bible partNevi'imOrder in the Hebrew part4CategoryFormer ProphetsChristian Bible partOld TestamentOrder in the Christian part12 2 Kings 11 is the eleventh chapter of the second part of the Books of Kings in the Hebrew Bible or the Second Book of Kings in the Old Testament of the Christian Bible.[1][2]…
American satirical punk rock band This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: The Dead Milkmen – news · newspapers · books · scholar · JSTOR (September 2020) (Learn how and when to remove this template message) The Dead MilkmenThe reunited Dead Milkmen perform in Philadelphia in 2010Background informationOr…
Korean-American model and beauty queen Emma BroylesBornEmma Leigh Broyles (2001-07-25) July 25, 2001 (age 22)Anchorage, Alaska, USEducationArizona State University (current)Known forFirst Miss Alaska to win the Miss America titleTitleMiss Anchorage's Outstanding Teen 2017Miss Alaska's Outstanding Teen 2017Distinguished Young Woman of Alaska 2019Miss Alaska 2021Miss America 2022TermDecember 16, 2021 – December 15, 2022PredecessorCamille SchrierSuccessorGrace Stanke Emma Leigh Broyles …
Place in Cáceres, SpainArroyomolinos de la Vera SealCountrySpainAutonomous communityCáceresArea • Total23.19 km2 (8.95 sq mi)Elevation617 m (2,024 ft)Population (2018)[1] • Total444 • Density19/km2 (50/sq mi)Time zoneUTC+1 (CET) • Summer (DST)UTC+2 (CEST)Websitehttp://www.arroyomolinosdelavera.es/ You can help expand this article with text translated from the corresponding article in Spanish. (Augus…
Dewan Perwakilan Rakyat Daerah Kabupaten Bogor ᮓᮦᮝᮔ᮪ ᮕᮀᮝᮊᮤᮜ᮪ ᮛᮠᮚᮒ᮪ ᮓᮆᮛᮂ ᮊᮘᮥᮕᮒᮦᮔ᮪ ᮘᮧᮌᮧᮁDéwan Pangwakil Rahayat Daérah Kabupatén BogorDewan Perwakilan RakyatKabupaten Bogor2019-2024JenisJenisUnikameral SejarahSesi baru dimulai27 Agustus 2019PimpinanKetuaRudy Susmanto, S.Si. (Gerindra) sejak 24 September 2019 Wakil Ketua IH. Agus Salim, Lc. (PKS) sejak 24 September 2019 Wakil Ketua IIH. Wawan Hikal Kurdi (Golkar) sej…
List of characters in The Witcher series This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (May 2011) (Learn how and when to remove this template message) This list is incomplete; you can help by adding missing items. (December 2022) The fictional universe of The Witcher Saga was created by Polish writer Andrzej Sapkowski. The following is a list of notable charact…
《福布斯》杂志标识 2010年福布斯中國名人榜榜單(英語:Forbes China Celebrity 100)是《福布斯》雜誌中文版在2010年4月28日揭曉。這是福布斯第七次發佈中國名人榜。[1]。 评选流程 《福布斯》雜誌中文版根據年收入、媒体曝光及专业性评选出100名当年中国最有影响力的演员、歌手、主持人、运动员等公众人物。 榜单人选 綜合排名 姓名 收入(萬元人民幣) 收入排名 1 成龍…
Subdiscipline of civil engineering focused on construction and operations This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Construction engineering – news · newspapers · books · scholar · JSTOR (June 2017) (Learn how and when to remove this template message) Construction engineering, also known as construction o…
Lokasi Pengunjung: 3.143.22.249