Abstract
We study the supersaturation problems of oddtown and eventown. Given a family $\mathcal A$ of subsets of an $n$ element set, let $op(\mathcal A)$ denote the number of distinct pairs $A,B\in \mathcal A$ for which $|A \cap B|$ is odd. We show that if $\mathcal A$ consists of $n+s$ odd-sized subsets, then $op(\mathcal A)\geq s+2$, which is tight when $n\geq s+4$. This disproves a conjecture by O'Neill on the supersaturation oddtown. For the supersaturation eventown, we show that for large enough $n$, if $\mathcal A$ consists of $2^ {\lfloor \frac n 2 \rfloor}+s$ even-sized subsets, then $op(\mathcal A)\ge s\cdot2^{\lfloor \frac n 2\rfloor-1} $ for any positive integer $s\le \frac {2^{\lfloor\frac n 8\rfloor}} n$. This partially proves a conjecture by O'Neill on the supersaturation eventown. Previously, the correctness of this conjecture was only verified for $s=1$ and $2$.

This publication has 17 references indexed in Scilit: