Sunflowers in set systems with small VC-dimension
<|reference_start|>Sunflowers in set systems with small VC-dimension: A family of $r$ distinct sets $\{A_1,\ldots, A_r\}$ is an $r$-sunflower if for all $1 \leqslant i < j \leqslant r$ and $1 \leqslant i' < j' \leqslant r$, we have $A_i \cap A_j = A_{i'} \cap A_{j'}$. Erd\H{o}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}| > (C r (\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.<|reference_end|>
@article{balogh2024sunflowers,
    title={Sunflowers in set systems with small VC-dimension},
    author={J'ozsef Balogh, Anton Bernshteyn, Michelle Delcourt, Asaf Ferber, Huy
  Tuan Pham},
    journal={arXiv preprint arXiv:2408.04165},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.04165},
    primaryClass={math.CO cs.DM math.PR}
}