The extremal number of Venn diagrams
Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:HY3XPBRSrecord.jsonopen to challenge →
classification
math.CO
keywords
leastconstantfamilysizevennabsoluteboundcontains
read the original 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 $Cn^3$ has dual VC-dimension at least 3. Equivalently, every family of size at least $Cn^3$ contains three sets such that all eight regions of their Venn diagram are non-empty. This improves upon the $Cn^{3.75}$ bound of Gupta, Lee and Li and is sharp up to the value of the constant.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.