Sunflowers in set systems with small VC-dimension

Abstract

A family of $r$ distinct sets $\{A_1,\dots ,A_r\}$ is an $r$-sunflower if for all $1⩽i<j⩽r$ and $1⩽i^{\prime }<j^{\prime }⩽r$, we have $A_i\cap A_j=A_{i^{\prime }}\cap A_{j^{\prime }}$. Erdős and Rado conjectured in 1960 that every family $\mathcal{H}$ of $\ell$-element sets of size at least $K(r{)}^{\ell }$ contains an $r$-sunflower, where $K(r)$ is some function that depends only on $r$. We prove that if $\mathcal{H}$ is a family of $\ell$-element sets of VC-dimension at most $d$ and $|\mathcal{H}|>(Cr(\log d+{\log }^{\ast }\ell ){)}^{\ell }$ for some absolute constant $C>0$, then $\mathcal{H}$ contains an $r$-sunflower. This improves a recent result of Fox, Pach, and Suk. When $d=1$, we obtain a sharp bound, namely that $|\mathcal{H}|>(r-1{)}^{\ell }$ is sufficient. Along the way, we establish a strengthening of the Kahn-Kalai conjecture for set families of bounded VC-dimension, which is of independent interest.

16 pages, 1 figure