Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
Mobile Device Pairing
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(e) ISSN 0002-9939(p)

     

Non-representability of finite projective planes by convex sets

Author(s): Martin Tancer
Journal: Proc. Amer. Math. Soc. 138 (2010), 3285-3291.
MSC (2010): Primary 52A35, 52A20; Secondary 05B25, 05E45
Posted: April 30, 2010
MathSciNet review: 2653958
Retrieve article in: 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:

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
Email: tancer@kam.mff.cuni.cz

DOI: 10.1090/S0002-9939-10-10463-8
PII: S 0002-9939(10)10463-8
Keywords: Convex set, intersection pattern, $d$-representable, $d$-collapsible, finite projective plane
Received by editor(s): August 28, 2009
Posted: 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 of article: Copyright 2010, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.




AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia