On supersaturation for oddtown and eventown
Preprint
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 $s\le n-4$. 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 $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 problem of eventown. Previously, the correctness of this conjecture was only verified for $s=1$ and $2$. We further provide a twice weaker lower bound in this conjecture for eventown, that is $op(\mathcal{A})\ge s\cdot 2^{\lfloor n/2\rfloor-2}$ for general $n$ and $s$ by using discrete Fourier analysis. Finally, some asymptotic results for the lower bounds of $op(\mathcal A)$ are given when $s$ is large for both problems.
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- A short note on supersaturation for oddtown and eventownDiscrete Applied Mathematics, 2023
- A Note on k-Wise Oddtown ProblemsGraphs and Combinatorics, 2022
- Exact k-Wise Intersection TheoremsGraphs and Combinatorics, 2005
- Set Systems with few Disjoint PairsCombinatorica, 2003
- Extremal Set Systems with Weakly Restricted IntersectionsCombinatorica, 1999
- Extremal Systems with Upper-Bounded Odd IntersectionsGraphs and Combinatorics, 1997
- On Subsets with Cardinalities of Intersections Divisible by a Fixed IntegerEuropean Journal of Combinatorics, 1983
- Supersaturated graphs and hypergraphsCombinatorica, 1983
- Boolean designs and self-dual matroidsLinear Algebra and its Applications, 1975
- Ein Satz ber Untermengen einer endlichen MengeMathematische Zeitschrift, 1928