Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar Talk Information |

**Date and Time**: Wednesday, May 20, 2009, 12:15 pm

**Duration**: This information is not available in the database

**Location**: CAB G51

**Speaker**: Martin Tancer (Charles Univ., Prague)

It is well known that a finite projective plane cannot be represented by lines in R^d. We prove a similar result when we consider a representation by convex sets (for projective planes that arise from a finite field).

More precisely, we show that for every positive integer d there is a positive integer q_0 with the following property. Let us have a projective plane which arises over GF(q) for q \geq q_0 with the set of lines L. Then there are no convex sets C_l in d-space for lines l from L such that for every l_1,...,l_k the sets C_{l_1},...,C_{l_k} intersect if and only if the lines l_1,...,l_k meet in a point of the projective plane.

If I have enough time I will also explain the main motivation of this problem: a simplicial complex is d-representable if it is the nerve of a collection of convex sets in R^d. A simplicial complex is d-collapsible if it can be reduced to an empty complex by repeatedly removing (collapsing) a face of dimension at most d-1 that is contained in a unique maximal face. Every d-representable simplicial complex is d-collapsible. Alon, Kalai, Matoušek and Meshulam asked whether there is a function f(d) such that every d-collapsible complex is f(d)-representable. Our result on projective planes implies that no such f exists for d > 1.

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

Previous talks by year: 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