# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

On 6.6.2013 at 12:20 in S6, there is the following noon lecture:

# Recognition of collapsible complexes is NP-complete

## Martin Tancer

## Abstract

A simplicial complex K is collapsible if there is a sequence of elementary collapses collapsing K to a point. By an elementary collapse we mean the removal of all proper superfaces of some face which is contained in exactly one maximal proper superface. Elementary collapses preserve the homotopy type; thus, collapsible complexes form an important subclass of contractible complexes--describable by a combinatorial condition.

We sketch a proof that it is NP-complete to decide whether a given (3-dimensional) simplicial complex is collapsible. This work extends a result of Malgouyres and Francés showing that it is NP-complete to decide whether a given simplicial complex collapses to a 1-complex.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 2020 | newer lectures)

Webmaster: kamweb.mff.cuni.cz Archive page