The extremal number of Venn diagrams

Abstract

We show that there exists an absolute constant $C>0$ such that any family $\mathcal{F}\subset \{0,1{\}}^n$ of size at least $C{n}^3$ has dual VC-dimension at least 3. Equivalently, every family of size at least $C{n}^3$ contains three sets such that all eight regions of their Venn diagram are non-empty. This improves upon the $C{n}^{3.75}$ bound of Gupta, Lee and Li and is sharp up to the value of the constant.

11 pages