Sunflowers in set systems of bounded dimension

Abstract

Given a family $\mathcal{F}$ of $k$-element sets, $S_1,\dots ,S_r\in \mathcal{F}$ form an {\em $r$-sunflower} if $S_i\cap S_j=S_{i^{\prime }}\cap S_{j^{\prime }}$ for all $i\ne j$ and $i^{\prime }\ne j^{\prime }$. According to a famous conjecture of Erd\H os and Rado (1960), there is a constant $c=c(r)$ such that if $|\mathcal{F}|\ge c^k$, then $\mathcal{F}$ contains an $r$-sunflower. We come close to proving this conjecture for families of bounded {\em Vapnik-Chervonenkis dimension}, VC-dim$(\mathcal{F})\le d$. In this case, we show that $r$-sunflowers exist under the slightly stronger assumption $|\mathcal{F}|\ge 2^{10k(dr{)}^{2{\log }^{\ast }k}}$. Here, ${\log }^{\ast }$ denotes the iterated logarithm function. We also verify the Erd\H os-Rado conjecture for families $\mathcal{F}$ of bounded {\em Littlestone dimension} and for some geometrically defined set systems.