A short note on supersaturation for oddtown and eventown

Abstract

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. For $s\in \{1,2\}$, we prove $\text{op}(\mathcal{A})\ge s\cdot 2^{\lfloor n/2\rfloor -1}$ for any collection $\mathcal{A}$ of $2^{\lfloor n/2\rfloor }+s$ even-sized subsets of an $n$ element set. We also prove $\text{op}(\mathcal{A})\ge 3$ for any collection $\mathcal{A}$ of $n+1$ odd-sized subsets of an $n$ element set that. Moreover, we show that both of these results are best possible. We then consider larger collections of odd-sized and even-sized sets respectively and explore the connection to minimizing the number of pairwise intersections of size exactly $k-2$ amongst collections of size $k$ subsets from an $n$ element set.

arXiv commentsome typos fixed and new remarks on corresponding problem for forbidden intersection problem