Towards supersaturation for oddtown and eventown

Jason O'Neill

Published 2021-09-21Version 1

Given a collection $\mathcal{A}$ of subsets of an $n$ element set, let $\text{op}(\mathcal{A})$ denote the number of distinct pairs $A,B \in \mathcal{A}$ for which $|A \cap B|$ is odd. Using linear algebra arguments, we prove that for any collection $\mathcal{A}$ of $2^{\lfloor n/2 \rfloor}+1$ even-sized subsets of an $n$ element set that $\text{op}(\mathcal{A}) \geq 2^{\lfloor n/2 \rfloor-1}$. We also prove that for any collection $\mathcal{A}$ of $n+1$ odd-sized subsets of an $n$ element set that $\text{op}(\mathcal{A}) \geq 3$, and that both of these results are best possible. We also consider the problem for larger collections of odd-sized and even-sized sets respectively.