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.

12 pages