Non-representability of finite projective planes by convex sets

Details Non-representability of finite projective planes by convex sets Non-representability of finite projective planes by convex sets

2009-08-27

arxiv.org/abs/0908.4038v1

Mathematics

Combinatorics

8 pages, 4 figures

Scientific paper

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 in R^d such that C_{i_1},...,C_{i_k} have a common point if and only if the corresponding lines l_{i_1},...,l_{i_k} 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.

Affiliated with

Also associated with

No associations

Rating

Non-representability of finite projective planes by convex sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Non-representability of finite projective planes by convex sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Non-representability of finite projective planes by convex sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-411878