M A T H 2 1 B
Mathematics Math21b Spring 2018
Linear Algebra and Differential Equations
Exhibit: Polyhedra
Office: SciCtr 432

# Polyhedra: polishing the Gem

In the first homework, you worked with polyhedra. The notion of polyhedron is a bit tricky because various incompatible definitions have been used in the past. The beautiful polyhedron formula v-e+f=2 of Euler is also called "Euler's Gem" . It was first experimentally found by Descartes who wrote it down in a secret notebook . As described well in a dialog called "proofs and refutations", the philosopher Lakatos explains in  how the polyhedron formula was shown again and again to be "wrong". It is a bit embarrassing for mathematics, which deals with eternal truth, where theorems turn out to be false. But as it turns out the mathematicians did not really prove wrong theorems, they worked with terminology which are ambiguous . Even for regular Kepler polyhedra the formula can fails. Then there are more general polyhedra (see the Morpheus building below) where v-e+f is different from 2. In higher dimensions again the formula has to be modified depending on what "polyhedron" means. The book  explains this well. How can one handle this elegantly? One thing to try is to borrow surfaces from continuum geometry and triangulate them. Also this opens a Pandora's box of difficulties as the notion of "triangulation" is also used in various different and incompatible ways. Some authors have limited themselves to convex polyhedra or polytopes .
1. D.S. Richeson, Euler's Gem, Princeton, 2008
2. A. Aczel, Descartes secret notebook, Broadway books, 2005
3. I. Lakatos, Proofs and Refutations, Cambrdige, 1976
4. B. Gruenbaum, Convex Polytopes, Springer, 2003
5. B. Gruenbaum, Are your polyhedra the same as my polyhedra? Disc. and Comp. Geom., 2003
Some slides, proof, and PDF, honoring Euler's day 2/7/18. An elegant approach is remain within combinatorics and define what a sphere is without referring ever to Euclidean space. The language of graph theory is intuitive and suitable to do that. Here is an elegant approach which has first been formulated by a mathematician called Evako in the 90ies at MIT. Other approaches using graphs are discrete Morse approaches by Forman or Fisk. A graph is a finite collection of nodes together with a finite collection of edges, where an edge joins two different nodes. The unit sphere S(x) of a node x is the sub graph formed by all vertices connected to x. First we define what a contractible graph is. The definition is inductive: the 1-point graph is contractible. A graph G is declared to be contractible if there exists a vertex x such that the unit sphere S(x) and G-x, the graph in which x and connections to x were removed, are both contractible. Now we define what a sphere is. This is also inductive. The empty graph 0 is declared to be a sphere of dimension -1. A graph G is called a d-sphere, if for every of its vertices x, the unit sphere S(x) is a (d-1)-dimensional sphere and if there exists a vertex x, such that G-x is contractible. Finally, the Euler characteristic of a graph is defined as X(G) = ∑_K (-1)dim(K)-1, where the sum is over all complete subgraphs K of G and dim(K)=|K|-1 is the number of nodes |K| minus 1. For the (-1)-sphere, the sum is empty and gives 0. A complete subgraph is is collection of nodes in the graph which are all connected to each other. Here is the theorem:

 Gem formula: if G is a d-dimensional sphere, then X(G)=1+(-1)d.

 Proof. First we prove by induction that a contractible graph G has Euler characteristic X(G)=1. It is true for the one point graph, as there is only a vertex x and dim(x)=0. To make the induction step, assume we know X(G)=1 for all contractible graphs with n nodes. Take a graph G with n+1 nodes. As it is contractible, there exists a vertex x for which both S(x) and G-x are contractible. As both S(x) and G-x have less than n+1 nodes we know from the induction assumption that X(S(x)) =1 and X(G-x)=1. Now use that for any two subgraphs A,B the valuation property X(A ∪ B) = X(A)+X(B) - X(A ∩ B) holds. Using this for A=B(x), the unit ball of x, and B=G-x, we have A ∩ B = S(x) and A &cup B=G. Then X(G) = X(B(x)) + X(G-x) - X(S(x)). As all these graphs B(x),G-x,S(x) are contractible, we have X(G)=1+1-1=1. Now, we can prove the formula for spheres. Also this is done by induction, but now with respect to the dimension of the sphere. For d=-1, the claim is X(G)=0 which is true. Now assume we have proven it for spheres of dimension d. Take a sphere of dimension d+1. By assumption there is a vertex x for which G-x is contractible. Now, we know that the unit sphere S(x) is a d-sphere. By induction, we have X(S(x))=1+(-1)d. We have again X(G) = X(B(x)) + X(G-x) - X(S(x)) = 1+1- (1+(-1)d) = 1-(-1)d = 1+(-1)d+1 which is the formula for d+1.

Here are some slides done on Euler's day 2/7/18:
 By assumption a 0-dimensional sphere has unit sphere to be a -1 sphere and such that removing one vertex renders the rest contractible. The assumption that every unit sphere is a -1 sphere means that there are no edges in the graph. It is just a collection of nodes, none of which are connected to each other. If there are two or more nodes then this can not be contractible as the unit sphere of a single disconnected node is the empty graph which is not contractible. As removing one node must lead to a contractible graph, G must have two nodes. There is only one 0-dimensional sphere. It has two nodes and no edges. Its Euler characteristic is 2. Now lets look at one dimensional spheres. By definition, every unit sphere must now have exactly two disconnected nodes. This in particular implies that there are no triangles in such a graph and that it must be a collection of closed loops. As removing one vertex must render the graph contractible, the sphere is one circular graph. The Euler characteristic is the number of vertices minus the number of edges. As they are the same, we have X(G)=0. This matches the theorem. For 2-dimensional spheres every unit sphere of a node must be a circular graph of length 4 or higher. Examples are the Octahedron or the Icosahedron. A tetrahedron is not a sphere as every unit sphere is a triangle and not a 1-sphere. The cube and the dodecahedron are not spheres as the unit spheres are zero dimensional and not one-dimensional circular graphs. The Euler characteristic of a 2-sphere is the number of vertices minus the number of edges plus the number of triangles. This is v-e+f. And the formula gives for d=2 the answer 2. Lets look at a triangulation of a torus. Why is this not a sphere? We can triangulate in such a way that every unit sphere is a 1-sphere. The problem is that if we take a torus and take a point away, we don't get a contractible graph. You can do that when fixing your bike tube the next time. After punching a hole into the tube, it is not contractible. On the other hand, if you punch a hole into a balloon, then the balloon is rest is contractible. How can one see that the punctured torus is not contractible? We can use the theorem! If it were, then the Euler characteristic of the torus would be 2. But we can count just vertices v, edges e and faces f to see that v-e+f = 0 in the case of a torus. For three dimensional spheres, every unit sphere has to be a two dimensional sphere. n example is the 600 cell. In this case, the number of vertices and edges and faces and three dimensional cells t are related by the formula v-e+f-t=0. This formula has been formulated first by Schlaefli. In the case of the 600 cell there are v=120 vertices, e=720 edges, f=1200 triangles and t=600 tetrahedra. All unit spheres are icosahedra. Here is a building called Morpheus, Macau, the City of Dreams on the Cotai Strip. The building was designed by Zaha Hadid Architects in Macau, China. Opend in 2017. Images by Zaha Hadid Architects and 2014 Melco Crown Entertainment Limited. The building basic structure can be modeled as a graph. If you look not all the unit spheres are not all spheres. The architect would have had to put more connections to achieve that. It is also far from a sphere. Even if we would complete the triangulation, there are three holes. The building is not simply connected. Indeed, every d-sphere as defined above is simply connected: every closed one dimensional circular graph can be deformed to a point as when puncturing the sphere, we have a contractible rest. The other direction is highly non-trivial and was one of the millenium problems: it is the Poincare conjecture. The continuum proof implies directly an analogue statement discrete case. Define a d-graph to be a graph in which every unit sphere is a (d-1) sphere in the above sense. Theorem of Perelmann implies that every d-graph which is simply connected is a sphere. To see this in the discrete, one just has to notice that every d-graph produces defines a d-manifold in the continuum. Simply connectedness in the discrete goes over to simply connectedness in the continuum.   