Non-representability of finite projective planes by convex sets
HTML articles powered by AMS MathViewer
- by Martin Tancer PDF
- Proc. Amer. Math. Soc. 138 (2010), 3285-3291 Request permission
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
- N. Alon, Expanders, sorting in rounds and superconcentrators of limited depth, Proc. 17th ACM Sympos. on Theory of Comput., 1985, pp. 98–102.
- N. Alon, Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory, Combinatorica 6 (1986), no. 3, 207–219. MR 875289, DOI 10.1007/BF02579382
- 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.
- Noga Alon, Gil Kalai, Jiří Matoušek, and Roy Meshulam, Transversal numbers for hypergraphs arising in geometry, Adv. in Appl. Math. 29 (2002), no. 1, 79–101. MR 1921545, DOI 10.1016/S0196-8858(02)00003-9
- Ludwig Danzer, Branko Grünbaum, and Victor Klee, Helly’s theorem and its relatives, Proc. Sympos. Pure Math., Vol. VII, Amer. Math. Soc., Providence, R.I., 1963, pp. 101–180. MR 0157289
- Jürgen Eckhoff, Helly, Radon, and Carathéodory type theorems, Handbook of convex geometry, Vol. A, B, North-Holland, Amsterdam, 1993, pp. 389–448. MR 1242986
- P. Erdos and Robert Steinberg, Problems and Solutions: Advanced Problems: Solutions: 4065, Amer. Math. Monthly 51 (1944), no. 3, 169–171. MR 1525919, DOI 10.2307/2303021
- E. Helly, Über mengen konvexer Körper mit gemeinschaftlichen Punkten, Jahresber. Deustch. Math.-Verein. 32 (1923), 175–176.
- L. M. Kelly, A resolution of the Sylvester-Gallai problem of J.-P. Serre, Discrete Comput. Geom. 1 (1986), no. 2, 101–104. MR 834051, DOI 10.1007/BF02187687
- Jiří Matoušek, Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212, Springer-Verlag, New York, 2002. MR 1899299, DOI 10.1007/978-1-4613-0039-7
- Jiří Matoušek and Jaroslav Ne et il, Invitation to discrete mathematics, The Clarendon Press, Oxford University Press, New York, 1998. MR 1668997
- Jiří Matoušek and Martin Tancer, Dimension gaps between representability and collapsibility, Discrete Comput. Geom. 42 (2009), no. 4, 631–639. MR 2556459, DOI 10.1007/s00454-008-9091-9
- János Pach, A Tverberg-type result on multicolored simplices, Comput. Geom. 10 (1998), no. 2, 71–76. MR 1614605, DOI 10.1016/S0925-7721(97)00022-9
- R. Michael Tanner, Explicit concentrators from generalized $N$-gons, SIAM J. Algebraic Discrete Methods 5 (1984), no. 3, 287–293. MR 752035, DOI 10.1137/0605030
- Gerd Wegner, $d$-collapsing and nerves of families of convex sets, Arch. Math. (Basel) 26 (1975), 317–321. MR 375333, DOI 10.1007/BF01229745
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
- Email: tancer@kam.mff.cuni.cz
- 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
- © Copyright 2010
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Proc. Amer. Math. Soc. 138 (2010), 3285-3291
- MSC (2010): Primary 52A35, 52A20; Secondary 05B25, 05E45
- DOI: https://doi.org/10.1090/S0002-9939-10-10463-8
- MathSciNet review: 2653958