Shellability

Every connected planar graph can be created by successive addition of edges while preserving connectedness. This leads to the famous Euler’s formula and its many interesting consequences: The non-planarity of \(K_5\) and \(K_{3,3}\); the fact that every planar triangulation with \(n\) vertices has \(3n-6\) edges and many others.

However, if we increase the dimension, the situation changes dramatically. Not all connected \(2\)-dimensional simplicial complexes can be built by successively gluing triangles together along edges. Those complexes that can be built in such a way are called shellable. They form a higher-dimensional analog of planar graphs and share many properties with them.

In this talk we look at some of the properties of shellable complexes: Euler’s formula extends to Dehn-Sommerville’s relations, we have the Upper and Lower Bound theorem for the number of triangles and edges in a shellable triangulation of the space and some others.

We also show that deciding whether a complex is shellable or not is an \(\mathsf{NP}\)-complete problem.

Recording