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?)

  • 1. N. Alon, Expanders, sorting in rounds and superconcentrators of limited depth, Proc. 17th ACM Sympos. on Theory of Comput., 1985, pp. 98-102.
  • 2. N. Alon, Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory, Combinatorica 6 (1986), no. 3, 207-219. MR 875289 (88g:05090)
  • 3. N. Alon, D. Haussler, and E. Welzl, Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension, Proc. 3rd ACM Sympos. on Computational Geometry, 1987, pp. 331-340.
  • 4. N. Alon, G. Kalai, J. Matoušek, and R. Meshulam, Transversal numbers for hypergraphs arising in geometry, Adv. in Appl. Math. 130 (2002), 2509-2514. MR 1921545 (2003g:52004)
  • 5. L. Danzer, B. Grünbaum, and V. Klee, Helly's theorem and its relatives, Proc. Sympos. Pure Math., vol. 7 (Convexity), American Mathematical Society, Providence, RI, 1963, pp. 101-180. MR 0157289 (28:524)
  • 6. J. Eckhoff, Helly, Radon and Carathéodory type theorems, Handbook of Convex Geometry (P. M. Gruber and J. M. Wills, eds.), North-Holland, Amsterdam, 1993, pp. 389-448. MR 1242986 (94k:52010)
  • 7. T. Gallai, Solution of problem 4065, Amer. Math. Monthly 51 (1944), 169-171. MR 1525919
  • 8. E. Helly, Über mengen konvexer Körper mit gemeinschaftlichen Punkten, Jahresber. Deustch. Math.-Verein. 32 (1923), 175-176.
  • 9. L.M. Kelly, A resolution of the Sylvester-Gallai problem of J.-P. Serre, Discrete Comput. Geom. 1 (1986), no. 1, 101-104. MR 834051 (87k:14047)
  • 10. J. Matoušek, Lectures on discrete geometry, Springer-Verlag New York, Inc., 2002. MR 1899299 (2003f:52011)
  • 11. J. Matoušek and J. Nešetřil, Invitation to discrete mathematics, Oxford University Press, Oxford, 1998. MR 1668997
  • 12. J. Matoušek and M. Tancer, Dimension gaps between representability and collapsibility, Discrete Comput. Geom. 42 (2009), no. 4, 631-639. MR 2556459
  • 13. J. Pach, A Tverberg-type result on multicolored simplices, Comput. Geom. 10 (1998), 71-76. MR 1614605 (99a:52006)
  • 14. R. M. Tanner, Explicit concentrators from generalized n-gons, SIAM J. Algebraic Discrete Methods 5 (1984), no. 3, 287-293. MR 752035 (85k:68080)
  • 15. G. Wegner, $ d$-collapsing and nerves of families of convex sets, Arch. Math. 26 (1975), 317-321. MR 0375333 (51:11528)

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