Combinatorica Вычислительная математика
Sunflowers in Set Systems with Small VC-Dimension
Аннотация
Abstract A family of r distinct sets $$\{A_1,\ldots , A_r\}$$ { A 1 , … , A r } is an r -sunflower if for all $$1 \leqslant i < j\leqslant r$$ 1 ⩽ i < j ⩽ r and $$1 \leqslant i' < j'\leqslant r$$ 1 ⩽ i ′ < j ′ ⩽ r , we have $$A_i\cap A_j = A_{i'}\cap A_{j'}$$ A i ∩ A j = A i ′ ∩ A j ′ . Erdős and Rado conjectured in 1960 that every family $$\mathcal {H}$$ H of $$\ell $$ ℓ -element sets of size at least $$K(r)^\ell $$ K ( r ) ℓ contains an r -sunflower, where K ( r ) is some function that depends only on r . We prove that if $$\mathcal {H}$$ H is a family of $$\ell $$ ℓ -element sets of VC-dimension at most d and $$|\mathcal H| > (C r(\log d+\log ^*\ell ))^\ell $$ | H | > ( C r ( log d + log ∗ ℓ ) ) ℓ for some absolute constant $$C > 0$$ C > 0 , then $$\mathcal {H}$$ H contains an r -sunflower. This improves a recent result of Fox, Pach, and Suk. When $$d=1$$ d = 1 , we obtain a sharp bound, namely that $$|\mathcal H| > (r-1)^\ell $$ | H | > ( r - 1 ) ℓ 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.