Unformatted text preview:

6.896 Topics in Algorithmic Game Theory February 22, 2010Lecture 6Lecturer: Constantinos Daskalakis Scribe: Jason Biddle, Debmalya PanigrahiNOTE: The content of these notes has not been formally reviewed by thelecturer. It is recommended that they are read critically.In our last lecture, we proved Nash’s Theorem using Broweur’s Fixed Point Theorem. We alsoshowed Brouwer’s Theorem via Sperner’s Lemma in 2-d using a limiting argument to go from thediscrete combinatorial problem to the topological one. In this lecture, we present a multidimensionalgeneralization of the proof from last time. Our proof differs from those typically found in the literature.In particular, we will insist that each step of the proof be constructive. Using constructive arguments,we shall be able to pin down the complexity-theoretic nature of the proof and make the steps algorithmicin subsequent lectures. In the first part of our lecture, we present a framework for the multidimensionalgeneralization of Sperner’s Lemma.• A Canonical Triangulation of the Hypercube• A Legal Coloring RuleIn the second part, we formally state Sperner’s Lemma in n dimensions and prove it using thefollowing constructive steps:• Colored Envelope Construction• Definition of the Walk• Identification of the Starting Simplex• Direction of the Walk1 FrameworkRecall that in the 2-dimensional case we had a square which was divided into triangles. We had alsodefined a legal coloring scheme for the triangle vertices lying on the boundary of the square. Now let usextend those concepts to higher dimensions.1.1 Canonical Triangulation of the HypercubeWe begin by introducing the n-simplex as the n-dimensional analog of the triangle in 2 dimensions asshown in Figure 1. The n-simplex is simply the n-dimensional polytope formed by the convex hull ofn + 1 points in general position.Next we introduce the hypercube [0, 1]nas the n-dimensional analog of our original square in 2dimensions. We divide the hypercube into cubelets of equal size. That is, we divide each dimension ofthe hypercube [0, 1]ninto integer multiples of 2−mfor some positive integer m as shown in Figure 2.This division into cubelets provides us with a set of vertices for the hypercube, namely all points in thehypercube whose coordinates are multiples of 2−m.Now we define a simplicization of the hypercube on these vertices by splitting each cubelet intosimplices. We define our simplicization of the cubelets such that if two cubelets share a facet, thesimplicization defined in the two cubelets coincides on that facet. We do this by ensuring all simplicesof the cubelet use the vertices [0]nand [1]n. An example simplicization for a cubelet in 3 dimensionswhere all tetrahedra share the vertices (0, 0, 0) and (1, 1, 1) is shown in Figure 3.Formally, every simplex corresponds to a permutation of the coordinates. The points contained ineach simplex are all of the points inside the hypercube which satisfy the following definition:6-1Triangulation High-dimensional analog of triangle? in 2 dimensions: a triangle in n dimensions: an n-simplex i.e. the convex hull of n+1 points in general position Figure 1: The n-simplex as the high-dimensional analog of the triangle.Divide each dimension into integer multiples of 2-m, for some integer m. Figure 2: Dividing the hypercube into cubelets.Definition 1. For a permutation π : [n] → [n],Tπ:= {x ∈ [0, 1]n| xπ(1)≤ xπ(2)≤ ... ≤ xπ(n)}.Claim 1. The unique integral corners of Tπare the following n + 1 points:xπ(1)xπ(2). . . xπ(n−2)xπ(n−1)xπ(n)vπ1= 0 0 . . . 0 0 0vπ2= 0 0 . . . 0 0 1vπ3= 0 0 . . . 0 1 1vπ4= 0 0 . . . 1 1 1...vπn= 0 1 . . . 1 1 1vπn+1= 1 1 . . . 1 1 1Proof: Any other integral point in the hypercube that does not respect the ordering must violate theinequality in Definition 1. Suppose vertex v of the hypercube [0, 1]nbelongs to set Tπand is not listed6-2note that all tetrahedra in this division use the corners 000 and 111 of the cube in 3 dimensions… Figure 3: Simplicization of a 3-dimensional cub elet.above. Vertex v must necessarily contain vπ(i)= 1 and vπ(i+1)= 0 for some i ∈ {1, ..., n − 1} whichimplies vπ(i)6≤ vπ(i+1), a contradiction. Therefore, vertex v cannot belong to set Tπ. Claim 2. Tπis a simplex.Proof: We can easily express any point x ∈ Tπas a convex combination of the integral cornersvπ1, vπ1, ..., vπn+1of Tπvia the following procedure:Let y = xαn+1= yin+1≥ 0 where in+1= arg miniyiy ← y − αn+1vπn+1αn= yin≥ 0 where in= arg mini /∈{in+1}yiy ← y − αnvπn...α2= yi2≥ 0 where i2= arg mini /∈{i3,i4,...,in+1}yiy ← y − α2vπ2α1= 1 −n+1Xj=2αj⇒n+1Xj=1αjvπj= x wheren+1Xj=1αj= 1 ⇒ Tπis a simplex. Claim 3.[πTπ= [0, 1]n.Proof: Trivially, any point x ∈ [0, 1]nsatisfies at least one of the permutations, each of which is asimplex from Claim 2; therefore, the union of simplices equals the hypercube. 6-3Theorem 1. {Tπ}πis a triangulation of [0, 1]n.Proof: A triangulation of [0, 1]nis a collection of simplices with disjoint interiors whose union equalsthe hypercube. We demonstrated the latter in Claim 3. To show our simplices have disjoint interiors,we must argue no simplices can intersect at internal point. Obviously, any internal point must strictlysatisfy the inequalities from Definition 1. There is no way an internal point can satisfy more than oneset of strict inequalities on the permutations of the coordinates. For example, in the 2-dimensional caseif an internal point (x1, x2) satisfies x1< x2then it cannot also satisfy x2< x1. We apply this triangulation to every cubelet in our hypercube division. We can think of each cubeletas living in [0, 1]n, and we can scale and translate the cubelet to the corresponding location in thehypercube division. In order for our simplicization of cubelets to be a simplicization of the entirehypercube, the following property must hold:Figure 4: Projection of simplicies in the lower cubelet (black) onto its top face and projection of simplicies in the uppercubelet (blue) onto its bottom face.Claim 4. If two cubelets share a face, their simplicizations agree on a common simplicization of theface.Proof: Suppose cubelets C1and C2share a facet. WLOG we can think of each cubelet as living in[0, 1]nand assume that their shared face is xn= 0 for C1and xn= 1 for C2. The projections of then-simplices of C1onto the face xn= 0 produce the (n − 1)–simplicesT1π0= {x ∈ [0, 1]n| xn= 0,


View Full Document

MIT 6 896 - Canonical Triangulation of the Hypercube

Download Canonical Triangulation of the Hypercube
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Canonical Triangulation of the Hypercube and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Canonical Triangulation of the Hypercube 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?