Supersaturation for Eventown via Generator Switching

Abstract

An eventown family is a family of even-sized subsets of $[n]$ in which every two distinct members have an even-sized intersection. A classical theorem of Berlekamp and Graver shows that the maximum size of such a family is $2^{\lfloor n/2\rfloor}$. The supersaturation problem for eventown asks how many odd-intersection pairs must occur when this extremal bound is exceeded. For a family $\mathcal F$ of even-sized subsets of $[n]$, let $e(\mathcal F)$ denote the number of unordered pairs whose intersection size is odd. O'Neill conjectured that if $|\mathcal F|=2^{\lfloor n/2\rfloor}+s$, then $e(\mathcal F)\ge s\,2^{\lfloor n/2\rfloor-1}$ for \[ 1\le s\le 2^{\lfloor n/2\rfloor}-2^{\lfloor n/4\rfloor}. \] Previously, the conjecture was known for $s=1,2$, and, for $s\le 2^{\lfloor n/8\rfloor}/n$ with $n$ sufficiently large. We prove the conjectured bound for \[ 1\le s\le \frac{2^{\lfloor n/2\rfloor}}{26}, \] extending the known range to a fixed positive proportion of the extremal eventown size. The bound is sharp throughout this range. As further consequences, we derive a lower bound valid for arbitrary excess $s$, which improves the previously known estimate in an additional range. We also establish stability and removal results for families of extremal size satisfying $e(\mathcal F)<2^{\lfloor n/2\rfloor-1}$, showing that such a family is close to an extremal eventown family and can be made eventown by deleting a small number of its members.

Disclosure

“nteresting to determine whether switching arguments involving several cosets outside the generator can extend Theorem 1.2 to a larger part of the range in Conjecture 1.1. Declarations During the development of this work, the authors used OpenAI GPT-5.5 as a research-assistance tool to explore possible improvements of the argument of Wei, Zhao, Zhang and Ge. In particular, GPT-5.5 was used at an intermediate stage to investigate whether their range s ≤ 2⌊n/8⌋ /n could be extended, and thi”

PDF page 11

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T05:19:12.624987Z

Structural counts