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

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

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

Mittagsseminar Talk Information

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

Duration: This information is not available in the database

Location: OAT S15/S16/S17

Speaker: Martin Tancer (Charles Univ., Prague)

Non-representability of finite projective planes by convex sets

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:   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