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" [1].
It was first experimentally found by Descartes who wrote it down in a secret notebook [2].
As described well in a dialog called "proofs and refutations", the philosopher
Lakatos explains in [3] 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 [5]. 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 [1] 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 [4].
D.S. Richeson, Euler's Gem, Princeton, 2008
A. Aczel, Descartes secret notebook, Broadway books, 2005
I. Lakatos, Proofs and Refutations, Cambrdige, 1976
B. Gruenbaum, Convex Polytopes, Springer, 2003
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.
