Non-representability of finite projective planes by convex sets

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.