Way back during the 1700's
Leonhard Euler, born in Basel, Switzerland, on April 15, 1707, was one of top mathematicians of the eighteenth century and the greatest mathematician to come out of Switzerland. He made numerous contributions to almost every mathematics field and was the most prolific mathematics writer of all time. It was said that "Euler calculated without apparent effort, as men breathe...." He was dubbed "Analysis Incarnate" by his peers for his incredible ability.
Flash to the 1970's
The Euler formula: for any convex polyhedron, the number of vertices and faces together is exactly two more than the number of edges. Symbolically V-E+F=2.
There also seems to be a potential connection to binomials: if one defines a polynomial p(t) = 1+Vt+Et2+Ft3+t4, the Euler formula can be interpreted as saying that p(t) is divisible by 1+t. But for simplices of any dimension, p(t)=(1+t)d+1 by the binomial formula.
A binary space partition is a data structure commonly used for computer graphics and other geometric searching problems. It's formed by cutting space by a hyperplane, then recursively partitioning each of the two resulting halfspaces. The result is a hierarchical decomposition of space into convex cells.
In 1974, Helge Tverberg showed that, given any convex polytope K, one can find a binary space partition that decomposes K into simplices. This is obvious for two dimensional polytopes (just repeatedly cut along polygon diagonals); the general proof proceeds by induction on dimension and number of faces:
We assume K is not a simplex or we would already be done.
If K has a vertex P incident to more than d facets, then (by induction on dimension) we can partition K by hyperplanes through P into smaller polytopes each of which has exactly d facets incident to P. The number of facets not incident to P in each of these polytopes is at most the same as in K, so each smaller polytope has fewer facets than K. By induction on number of facets, we can recursively partition the smaller polytopes into simplices.
On the other hand suppose that each vertex of K has only d incident facets. Let P be a vertex of K that is not adjacent to some two facets F1 and F2 (we can find P, F1, and F2 by induction on dimension if K has a non-simplicial facet; if all facets of K are simplices, let F1 and F2 be two adjacent facets and P be any vertex other than the d+1 vertices shared by F1 and F2). Let L be the hyperline contained in the hyperplanes through F1 and F2, and cut K by a hyperplane through P and L. Then each of the two pieces avoids one of the facets Fi, but has a new facet on the cut plane, so its number of facets is not increased. One can show that each piece either has more than d facets at P (in which case we can apply the previous case), or avoids an additional facet of K (in which case we can apply induction on the number of facets), so either way we can partition each piece recursively.
The number of cuts in this partition may be exponential in the number of facets, but this seems unavoidable due to examples like the hypercube which have few facets but require many cuts.
Tverberg then proves that the Euler characteristic X(K) (as defined more precisely for the shelling proof) is always zero, by induction on dimension and on the number of cuts in the binary space partition:
If K is a simplex, the number of faces of any dimension is counted by a binomial coefficient, and the identity X(K)=0 is just the application of the binomial theorem to the evaluation of (1+x)d at x = -1.
Otherwise, let the top level cut of the binary space partition split K into two polytopes K1 and K2. Let K3 be the convex hull of the set of vertices of K that are contained in the cutting hyperplane, and let K4 be the intersection of K with the cutting hyperplane. Then we have the formula
X(K) = X(K1) + X(K2) + 2 X(K3) - 3 X(K4),
since each face of K is either contained in the cutting hyperplane (contributing to all four terms X(Ki)), split by the cutting hyperplane (forming a face of one lower dimension in K1, K2, and K4, and contributing a negated term to each of these three polytopes' Euler characteristics), or is contained in one of the two halfspaces (and contributes only to X(K1) or X(K2)).
K1 and K2 have smaller binary space partitions, and K3 and K4 have lower dimension, so by induction all have zero Euler characteristic. Therefore, X(K) is also zero.
Flash to the Present
Now wait till you see what we did with 3.5 maps using all this crap and not understanding any of it.