Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

Date and Time: Tuesday, May 06, 2008, 12:15 pm

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Martin Tancer (Charles Univ., Prague)

On the complexity of recognition of d-collapsible complexes

A simplicial complex K is d-collapsible if it can be reduced to an empty complex by repeatedly removing a face of dimension at most d-1 that is contained in a unique maximal face. The motivation for this notion is that the set of d-collapsible complexes is known to be a superset of the set of complexes that are the nerves of collections of convex sets in R^d. We sketch the proof that the problem of recognition of d-collapsible complexes is polynomial for d at most 2, and NP-complete for d greater or equal to 4.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login