Collapsibility of simplicial complexes of graphs and hypergraphs

Seminar
Speaker
Alan Lew (Technion)
Date
17/11/2019 - 15:30 - 14:00Add to Calendar 2019-11-17 14:00:00 2019-11-17 15:30:00 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. Room 201, Math and CS Building (Bldg. 216) אוניברסיטת בר-אילן - Department of Mathematics mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Room 201, Math and CS Building (Bldg. 216)
Abstract

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.

Last Updated Date : 11/11/2019