Venn diagrams as forbidden hypergraph traces

Abstract

We study the maximum size of a set system that contains no $k$-Venn diagram, denoted by $VD_k$, as a trace. For every fixed $k\ge 3$, we prove $\text{ex}_{tr}(n,VD_k)=O_k(n^{2^k-2k+1})$, improving the direct Sauer-Shelah bound $O_k(n^{2^k-1})$. In particular, for $k=4$ the exponent decreases from $15$ to $9$. The proof starts from the theorem of Keevash, Leader, Long and Wagner for $VD_3$ and uses induction on $k$ in which two new Venn regions are forced for free at each added edge. We also record lower-bound constructions for Venn diagrams in fixed uniformity, explicit bounds for the $4$-uniform $3$-Venn problem, and a fixed uniformity trace result for the loose triangle.

Disclosure

“a-Curie grant agreement No. 823748. It was carried out during the DIMACS REU in 2024 under the guidance of Bhargav Narayanan and Milan Haiman. We thank them for many helpful meetings and discussions. Declaration of AI use The authors used OpenAI’s ChatGPT for proofreading and stylistic improvements of the text. All the mathematical ideas and proofs are due to the authors. References [1] R. P. Anstee and A. Sali. A survey of forbidden configuration results. The Electronic Journal of”

PDF page 9

Classification

Proofreading, grammar, or spelling

Multiplier

1

Verified

2026-08-23T18:58:04.190295Z

Structural counts