Speaker: Jozsef Balogh (UIUC)
Title: Sunflowers in set systems with small VC-dimension
Abstract Text:
A family of r distinct sets {A_1,...,A_r} is an r-sunflower if for all 1⩽i<j⩽r and 1⩽i′<j′⩽r, we have A_i ∩ A_j = A_i′ ∩ A_j′. Erdős and Rado conjectured in 1960 that every family H of ℓ-element sets of size at least K(r)^ℓ contains an r-sunflower, where K(r) is some function that depends only on r. We prove that if H is a family of ℓ-element sets of VC-dimension at most d and |H|>(Cr(logd+log∗ℓ))^ℓ for some absolute constant C>0, then 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 |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.
It is joint work with Anton Bernshteyn, Michelle Delcourt,Huy Tuan Pham, Asaf Ferber.