On Supersaturation for Oddtown and Eventown

Authors:

Abstract
We study the supersaturation problems of oddtown and eventown. Given a family [Formula: see text] of subsets of an [Formula: see text]-element set, let [Formula: see text] denote the number of distinct pairs [Formula: see text] for which [Formula: see text] is odd. We show that if [Formula: see text] consists of [Formula: see text] odd-sized subsets, then [Formula: see text], which is tight when [Formula: see text]. This disproves a conjecture by O’Neill on the supersaturation problem of oddtown. For the supersaturation problem of eventown, we show that for large enough [Formula: see text], if [Formula: see text] consists of [Formula: see text] even-sized subsets, then [Formula: see text] for any positive integer [Formula: see text]. This partially proves a conjecture by O’Neill on the supersaturation problem of eventown. Previously, the correctness of this conjecture was only verified for [Formula: see text] and 2. We further provide a lower bound which is a factor of two away from the conjectured bound for eventown, that is, [Formula: see text] for general [Formula: see text] and [Formula: see text] by using discrete Fourier analysis. Finally, some asymptotic results for the lower bounds of [Formula: see text] are given when [Formula: see text] is large for both problems.
Funding Information
  • National Key Research and Development Program of China (2020YFA0712100, 2018YFA0704703, 2020YFA0713100)
  • Beijing Scholars Program
  • Innovation Program for Quantum Science and Technology (2021ZD0302902)
  • National Natural Science Foundation of China (11971325, 12171452, 12231014)

This publication has 25 references indexed in Scilit: