Slide 1Slide 2Slide 3TriangulationSimplicization of [0,1]n?1st Step: Division into Cubelets2nd Step: Simplicization of each CubeletGeneralization to n-dimensionsSimplicizationCycle of a SimplexSlide 11Legal Coloring in 2-dLegal ColoringLegal Coloring (3-d)Slide 15Sperner’s LemmaSlide 17Slide 18Slide 19Slide 20Original ColoringThe Canonically Colored EnvelopeEnvelope construction in 3-dEnvelope construction in Many DimensionsSlide 25WalkSlide 27Starting SimplexSlide 29The Proof of Sperner’s LemmaProof of SpernerOdd number of panchromatic simplices?Abstractly…Proofs constructs a graph with degree ≤ 2Slide 35Towards a more constructive argumentDirection of the walkDirection of the walkDirection of the walkDirection of the walkInteresting Properties ofInteresting Properties ofInteresting Properties ofInteresting Properties ofInteresting Properties of6.896: Topics in Algorithmic Game TheoryLecture 6Constantinos DaskalakisSperner’ s Lemma in n dimensionsA. Canonical Triangulation of [0,1]nTriangulationHigh-dimensional analog of triangle?in 2 dimensions: a triangle in n dimensions: an n-simplexi.e. the convex hull of n+1 points in general positionSimplicization of [0,1]n?1st Step: Division into CubeletsDivide each dimension into integer multiples of 2-m, for some integer m.2nd Step: Simplicization of each Cubeletnote that all tetrahedra in this division use the corners 000 and 111 of the cubein 3 dimensions…Generalization to n-dimensionsFor a permutation of the coordinates, define: 0 0 0 0 0…0 0 0 0 1…0 0 0 1 1…0 0 1 1 1…1 1 1 1 1……Claim 1: The unique integral corners of are the following n+1 points:SimplicizationClaim 2: is a simplex.Claim 3: Theorem: is a triangulation of [0,1]n.Apply the above simplicization to each cubelet.Claim 4: If two cubelets share a face, their simplicizations agree on a common simplicization of the face.Cycle of a SimplexLetting denote the unit vector along dimension i, and we can cycle around the corners of as follows:…Claim: Hamming weight is increasing from to .the 0n corner of the cubeletthe 1n corner of the cubeletB. Legal ColoringLegal Coloring in 2-dno redno blueno yellow2-dimensional Spernern-dimensional SpernerLegal Coloring3 colors: blue (1), red (2), yellow (0)(P2): None of the vertices on the left (x1=0) side of the square uses blue, no vertex on the bottom side (x2=0) uses red, and no vertex on the other two sides uses yellow.n colors: 0, 1, …, n(Pn): For all i {1,…, ∈ n}, none of the vertices on the face xi = 0 of the hypercube uses color i; moreover, color 0 is not used by any vertex on a face xi = 1, for some i {1,…, ∈ n}.Legal Coloring (3-d)no use of 0no use of 1no use of 3no use of 2C. Statement of Sperner’s LemmaSperner’s Lemma(Pn): For all i {1,…, ∈ n}, none of the vertices on the face xi = 0 uses color i; moreover, color 0 is not used by any vertex on a face xi = 1, for some i {1,…, ∈ n}. Suppose that the vertices of the canonical simplicization of the hypercube [0,1]n are colored with colors 0,1, …, n so that the following property is satisfied by the coloring on the boundary. Then there exists a panchromatic simplex in the simplicization. In fact, there is an odd number of those.Theorem [Sperner 1928]:pan: from ancient Greek πᾶν = all, everychromatic: from ancient Greek χρῶμα.= colorRemarks:1. We need not restrict ourselves to the canonical simplicization of the hypercube shown above (that is, divide the hypercube into cubelets, and divide each cubelet into simplices in the canonical way shown above). The conclusion of the theorem is true for any partition of the cube into n-simplices, as long as the coloring on the boundary satisfies the property stated above. The reason we state Sperner’s lemma in terms of the canonical triangulation is in an effort to provide an algorithmically-friendly version of the computational problem related to Sperner, in which the triangulation and its simplices are easy to define, the neighbors of a simplex can be computed efficiently etc. We follow-up on this in the next lecture. Moreover, our setup allows us to make all the steps in the proof of Sperner’s lemma “constructive” (except for the length of the walk, see below).Sperner’s Lemma was originally stated for a coloring of a triangulation of the n-simplex, (rather than the cube shown above). In that setting, we color the vertices of any triangulation of the n-simplex---a convex combination of points in general position---with n colors, 0,1,…,n, so that the facet not containing vertex does not use color i. Then Sperner’s lemma states that there exists a panchromatic simplex in the simplicization.2.Our coloring of the n-dimensional cube with n+1 colors is essentially mimicking the coloring of a simplex whose facets (except one) correspond to the facets of the cube around the corner 0n, while the left-out facet corresponds to the “cap” of the hypercube around 1n.Proof of n-dimensional Sperner’s Lemmageneralizing the proof of the 2-d case1. Envelope ConstructionOriginal Coloringno redno blueno yellowThe Canonically Colored EnvelopeFor convenience introduce an outer boundary, that does not create new tri-chromatic triangles.Envelope construction in 3-dno use of 0no use of 1no use of 3no use of 2use color 1, except for the boundary with x1=0111use color 2, except for the boundary with x2= 0use color 0use color 3, except for the boundary with x3= 0Envelope construction in Many Dimensionswhere 0 is disallowed, color with 1, except for boundary with x1=0;where 1 is disallowed, color with 2, except for boundary with x2=0;where i is disallowed, color with i+1, except for boundary with xi+1=0;where n is disallowed, color with 0.……Introduce an extra layer off of the boundary of the hypercube and color the vertices of this extra layer legally, but according to the very canonical/greedy way defined below:Claim: No new panchromatic tetrahedra were introduced during the envelope construction.2. Definition of the WalkWalkLike we did in the 2-d case, we show that a panchromatic simplex exists by defining a walk that jumps from simplex to simplex of our simplicization, starting at some fixed simplex (independent of the coloring) and guaranteed to conclude at a panchromatic one. - The simplices in our walk (except