Collapsibility of simplicial complexes of graphs and hypergraphs

Let X be a simplicial complex. Given a simplex σ ∈ X of dimension at most d − 1 that is contained in a unique maximal face of X, the operation of removing σ and all the simplices that contain it from X is called an elementary d-collapse. We say that X is d-collapsible if it can be reduced to the void complex by performing a sequence of elementary d-collapses. The collapsibility of X is the minimal d such that X is d-collapsible. The notion of d-collapsibility was introduced by Wegner, who applied it in the study of intersection patterns of convex sets in R^d .

We study the collapsibility of simplicial complexes associated to different properties of graphs and hypergraphs, and present several topological and combinatorial applications. We discuss some of the tools that we use for bounding the collapsibility of a complex. In particular, we present a useful and easy to apply bound, generalizing a method due to Matoušek and Tancer.

The talk is partly based on joint work with Minki Kim.