On Supersaturation for Oddtown and Eventown
Authors:
- 24 November 2025
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 39 (4) , 2311-2327
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.Keywords
All Related Versions
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:
- A Note on k-Wise Oddtown ProblemsGraphs and Combinatorics, 2022
- The minimum number of disjoint pairs in set systems and related problemsCombinatorica, 2016
- Exact k-Wise Intersection TheoremsGraphs and Combinatorics, 2005
- The Theory of Finite Groups2004
- Set Systems with few Disjoint PairsCombinatorica, 2003
- Extremal Systems with Upper-Bounded Odd IntersectionsGraphs and Combinatorics, 1997
- A generalization of the ray‐chaudhuri‐wilson theoremJournal of Combinatorial Designs, 1995
- On functions of strengthtCombinatorica, 1983
- Supersaturated graphs and hypergraphsCombinatorica, 1983
- Ein Satz ber Untermengen einer endlichen MengeMathematische Zeitschrift, 1928