The extremal number of Venn diagrams
| Autor: | Keevash, Peter, Leader, Imre, Long, Jason, Wagner, Adam Zsolt |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 11 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|