Noon lecture

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

On 06.06.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 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010