Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Non-representability of finite projective planes by convex sets

Author: Martin Tancer
Journal: Proc. Amer. Math. Soc. 138 (2010), 3285-3291
MSC (2010): Primary 52A35, 52A20; Secondary 05B25, 05E45
Published electronically: April 30, 2010
MathSciNet review: 2653958
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We prove that there is no $ d$ such that all finite projective planes can be represented by convex sets in $ \mathbb{R}^d$, answering a question of Alon, Kalai, Matoušek, and Meshulam. Here, if $ \mathbb{P}$ is a projective plane with lines $ \ell_1,\ldots,\ell_n$, a representation of $ \mathbb{P}$ by convex sets in $ \mathbb{R}^d$ is a collection of convex sets $ C_1,\ldots,C_n \subseteq \mathbb{R}^d$ such that $ C_{i_1},C_{i_2},\ldots,C_{i_k}$ have a common point if and only if the corresponding lines $ \ell_{i_1},\ldots,\ell_{i_k}$ have a common point in $ \mathbb{P}$. The proof combines a positive-fraction selection lemma of Pach with a result of Alon on ``expansion'' of finite projective planes. As a corollary, we show that for every $ d$ there are 2-collapsible simplicial complexes that are not $ d$-representable, strengthening a result of Matoušek and the author.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 52A35, 52A20, 05B25, 05E45

Retrieve articles in all journals with MSC (2010): 52A35, 52A20, 05B25, 05E45

Additional Information

Martin Tancer
Affiliation: Department of Applied Mathematics and Institute for Theoretical Computer Science, Faculty of Mathematics and Physics, Charles University, Malostranské nám. 25, 118 00 Prague, Czech Republic

Keywords: Convex set, intersection pattern, $d$-representable, $d$-collapsible, finite projective plane
Received by editor(s): August 28, 2009
Published electronically: April 30, 2010
Additional Notes: The author was partially supported by project GAUK 49209. He was also supported by project 1M0545 of The Ministry of Education of the Czech Republic
Communicated by: Jonathan I. Hall
Article copyright: © Copyright 2010 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society