Pavel Paták, 25 Apr 2022

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.