NON-REPRESENTABILITY OF FINITE PROJECTIVE PLANES BY CONVEX SETS

作者：Tancer Martin^*

来源：Proceedings of the American Mathematical Society, 2010, 138(9): 3285-3291.

DOI：10.1090/S0002-9939-10-10463-8

• Convex set
• intersection pattern
• d-representable
• d-collapsible
• finite projective plane

We prove that there is no d such that all finite projective planes can be represented by convex sets in R(d), answering a question of Alon, Kalai, Matousek, and Meshulam. Here, if P is a projective plane with lines l(1), . . . , l(n,) a representation of P by convex sets in R(d) is a collection of convex sets C(1), . . . , C(n), subset of R(d) such that C(i1), C(i2), . . . , C(ik) have a common point if and only if the corresponding lines l(1,) ... , l(ik) Pik have a common point in 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 Matousek and the author.

• 出版日期2010-9