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 $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$.
Keywords
All Related Versions
This publication has 17 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
- Kleitman's conjecture about families of given size minimizing the number of k-chainsAdvances in Mathematics, 2018
- 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
- 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