2019/11/01 by Keevash, Peter, Leader, Imre, Long, Jason +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1911.00487
We show that there exists an absolute constant C>0 such that any family F⊂ \0,1\n of size at least Cn3 has dual VC-dimension at least 3. Equivalently, every family of size at least Cn3 contains three sets such that all eight regions of their Venn diagram are non-empty. This improves upon the Cn3.75 bound of Gupta, Lee and Li and is sharp up to the value of the constant.