Thresholds and spread in set systems of bounded VC-dimension

Let $p_c(\mathcal{F})$, $q(\mathcal{F})$, and $q_f(\mathcal{F})$ denote the threshold, expectation threshold, and fractional expectation threshold of a family $\mathcal{F}$ of nonempty subsets of a finite set, respectively. We prove that there is an absolute constant $C>0$ such that, if $\mathcal{F}$ has VC dimension at most $d\ge 1$, then $p_c(\mathcal{F})\le Cq(\mathcal{F})\log (d+1)$. More generally, for every $0<\epsilon \le 1\mathrm{/}2$, a binomial random set of density $\min \{1,Cq(\mathcal{F})\log ((d+1)\mathrm{/}\epsilon )\}$ contains a member of $\mathcal{F}$ with probability at least $1-\epsilon$. Consequently, $q_f(\mathcal{F})\le Cq(\mathcal{F})\log (d+1)$, verifying Talagrand’s integral–fractional conjecture for families of any fixed VC dimension. We also prove that if a $k$-spread probability measure has support of VC dimension at most $d$, then a binomial random set of density $\min \{1,(C\mathrm{/}k)\log ((d+1)\mathrm{/}\epsilon )\}$ contains a member of its support with probability at least $1-\epsilon$. In both random-containment results, the factor $\log ((d+1)\mathrm{/}\epsilon )$ is optimal up to absolute constants. As an application of the spread theorem, we prove that every $n$-uniform family of VC dimension at most $d$ with more than $(C{p}^{-1}\log ((d+1)\mathrm{/}\epsilon ){)}^n$ members contains a $(p,\epsilon )$-robust sunflower. In particular, every such family with more than $(Cr\log (d+1){)}^n$ members contains an $r$-sunflower, improving the recent bound $(Crd{)}^n$ of Ge, Wang, Xu, and Zhao.