{"id":"arxiv/2609.30263","url":"https://arxiv.org/abs/2609.30263","tags":["math.CO"],"score":0,"title":"Thresholds and spread in set systems of bounded VC-dimension","domain":"math.CO","source":"arxiv","authors":["Chong Shangguan"],"reviews":0,"subject":"math.CO","summary":"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\\ge1$, then $p_c(\\mathcal F)\\le Cq(\\mathcal F)\\log(d+1)$. More generally, for every $0<\\varepsilon\\le1/2$, a binomial random set of density $\\min\\{1,Cq(\\mathcal F)\\log((d+1)/\\varepsilon)\\}$ contains a member of $\\mathcal F$ with probability at least $1-\\varepsilon$.…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{}}