|
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 such that all finite projective planes can be represented by convex sets in , answering a question of Alon, Kalai, Matoušek, and Meshulam. Here, if is a projective plane with lines , a representation of by convex sets in is a collection of convex sets such that have a common point if and only if the corresponding lines have a common point in . 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 there are 2-collapsible simplicial complexes that are not -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,
-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.
|