Thresholds and spread in set systems of bounded VC-dimension
Abstract
Let pc(ℱ), q(ℱ), and qf(ℱ) denote the threshold, expectation threshold, and fractional expectation threshold of a family ℱ of nonempty subsets of a finite set, respectively. We prove that there is an absolute constant C>0 such that, if ℱ has VC dimension at most d≥1, then pc(ℱ)≤ Cq(ℱ)log(d+1). More generally, for every 0<ε≤1/2, a binomial random set of density min{1,Cq(ℱ)log((d+1)/ε)} contains a member of ℱ with probability at least 1−ε. Consequently, qf(ℱ)≤ Cq(ℱ)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/k)log((d+1)/ε)} contains a member of its support with probability at least 1−ε. In both random-containment results, the factor log((d+1)/ε) 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−1log((d+1)/ε))n members contains a (p,ε)-robust sunflower. In particular, every such family with more than (Crlog(d+1))n members contains an r-sunflower, improving the recent bound (Crd)n of Ge, Wang, Xu, and Zhao.
Related
- A dimension-free comparison between expectation thresholds and fractional expectation thresholds
- Minimum-degree thresholds beyond bounded colourability
- Bounded VC-dimension implies the Erdős--Rado sunflower conjecture
- Finite Borel asymptotic dimension of bounded-to-one commutative monoid actions
- Largest Sperner families with bounded VC-dimension
BibTeX
@misc{shangguan2026thresholds,
title = {{Thresholds and spread in set systems of bounded VC-dimension}},
author = {Chong Shangguan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.30263},
eprint = {2609.30263},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30263},
}
RIS
TY - UNPB
TI - Thresholds and spread in set systems of bounded VC-dimension
AU - Chong Shangguan
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.30263
UR - https://arxiv.org/abs/2609.30263
AB - Let p_c(ℱ), q(ℱ), and q_f(ℱ) denote the threshold, expectation threshold, and fractional expectation threshold of a family ℱ of nonempty subsets of a finite set, respectively. We prove that there is an absolute constant C>0 such that, if ℱ has VC dimension at most d≥1, then p_c(ℱ)≤ Cq(ℱ)log(d+1). More generally, for every 0<ε≤1/2, a binomial random set of density min{1,Cq(ℱ)log((d+1)/ε)} contains a member of ℱ with probability at least 1−ε. Consequently, q_f(ℱ)≤ Cq(ℱ)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/k)log((d+1)/ε)} contains a member of its support with probability at least 1−ε. In both random-containment results, the factor log((d+1)/ε) 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^−1log((d+1)/ε))^n members contains a (p,ε)-robust sunflower. In particular, every such family with more than (Crlog(d+1))^n members contains an r-sunflower, improving the recent bound (Crd)^n of Ge, Wang, Xu, and Zhao.
ER -