The beginnings of Shellability

A finite abstract simplicial complex $G$ is a finite set of non-empty sets closed under the operation of taking finite non-empty subsets. The sets in G are also called simplices or faces. A complex $G$ is {\bf pure} if the maximal simplices all have the same dimension $d$. Inductively, a pure complex is shellable if there is an ordering $x_1,x_2, \dots, x_n$ of the maximal simplices such that the complex $G_k$ generated by $\{x_1, \dots, x_k\}$ and the complex $X_k$ generated by $\{x_k\}$ have the property that $G_k \cap X_k$ is a $(d-1)$ dimensional shellable complex. The induction foundation is that every 0-dimensional complex is shellable. It is important that all this is purely combinatorial and does not depend on any Euclidean realization.

There are variants of the above definition. The just given definition uses a the formulation of Bruggesser and Mani in 1971 given in Definition 1 of their paper. That paper cites a paper of Mary Ellen Rudin from 1958 with the title “An unshellable triangulation of a tetrahedron”. Rudin, in a remarkable 2 page paper calls a triangulation of $G$ shellable if there exists an ordering of the maximal simplices such that the $G_k$ are all homeomorphic to $G$. This is different, as it refers to Euclidean realizations. Rudin cites D.E. Sanderson, a paper from 1957 who calls a d-manifold with boundary shellable if there is an ordered cellular decomposition into d-cells with disjoint interior such that $x_k$ is free in $G_k$. A $d$-cell is free $G_k$ if the intersection with the boundary of $G_k$ is homeomorphic to a $d-1$ cell. Note that also this definition makes uses of homeomorphism and so Euclidean embeddings. Sanderson actually works with what we today call the PL manifolds. Sanderson shows that for any triangulation, there is as a shellable subdivision. The Sanderson paper cites a paper of R.H. Bing from 1951 who looks at a “partitioning” into mutually exclusive open sets in Euclidean space whose sum is dense. R.H. Bing, who is an acacemic brother of M.E. Rudin, looks at ordered sequence of these sets and asks that $G_k$ intersected with $X_k$ is a connected set. It appears therefore that the paper of Bruggisser and Mani is the first which gives a definition of shellability which is combinatorial. Bing started his career by proving the Kline sphere characterization: in 1949: (a locally connected metric continuum that is separated by a simple closed curve but not by a pair of points is the two sphere). By the way, the Bing house can be thickened and triangulated to be unshellable even so the thickened house is a 3-ball.

The paper of Heinz Bruggisser and Peter Mani is a landmark in combinatorial topology. They wrote the paper while affiliated at the University of Bern. There is a long tradition of geometry in Bern, starting of course with Ludwig Schlaefli, one of the geometry giants who made the first steps in higher dimensional geometry. Schlaefli was the first to prove the Euler gem formula $\chi(G) = (1+(-1)^d)$ for d-dimensional spheres. Bruggesser and Mani are related in a connected part of the academic family tree containing other formidable mathematicians. (Also mentioned is Hans Giger who was a referee of mine, when I competed in a competition SJF.

David Hilbert
  |
Kurt Fueter     -> Walter Nef  -> Heinz Bruggesser
  |
Willy Scherrer  -> Hans Giger
  |
Hugo Hadwiger
  |
Peter Mani

After his dissertation on polyhedra in 1975, Heinz Bruggisser followed a more computer science related career, working partly at the university of Bern but also working at IBM as a specialist in the APL language which had been produced by Ken Iverson in the 50 ies at Harvard University (Iverson worked with Aiken who had developed the Harvard Mark 1 and with Wassily Leontief, who with his Input-Output analysis won the Nobel prize in 1973 and who would work on the Harvard Mark 2). APL is still used in AI and finance and has a GNU implementation. By the way, the GNU guru, Richard Stallman wrote once a texteditor in APL as a high school student.

Peter Mani who is a student of Hugo Hadwiger, remained at the university of Bern and is there Emeritus since 2004. Mani wrote his PhD in 1967 on combinatorial theorems close to the Sperner, Tucker, Fan results. In Kalai blog entri, there is a story about the proof about the conjecture that the dual graph of a combinatorial d-polytop determines the polytop. This had been conjectured by Perles in the 70ies and was proven in 1987 by Blind and Mani.

The 19’th century proofs of the Euler theorem had used the assumption that one can build up the d-polytop recursively by attaching d-dimensional simplices. This is shellability. That this is justified for convex polytopes was first proved by Bruggesser and Mani in 1970. Still according to that blog entry, Peter Mani found a crucial ingredient of the proof in a dream.