On supersaturation for oddtown and eventown

MaRDI QIDQ6426149zbMATH OpenFDO

Authors Xin Wei, Yuhao Zhao, Xian De Zhang, Gennian Ge

Publication date 10 February 2023

Abstract: We study the supersaturation problems of oddtown and eventown. Given a family $mathcalA$ of subsets of an $n$ element set, let $op(mathcalA)$ denote the number of distinct pairs $A,BinmathcalA$ for which $|AcapB|$ is odd. We show that if $mathcalA$ consists of $n+s$ odd-sized subsets, then $op(mathcalA)geqs+2$, which is tight when $ngeqs+4$. This disproves a conjecture by O'Neill on the supersaturation oddtown. For the supersaturation eventown, we show that for large enough $n$, if $mathcalA$ consists of $2^{lfloorfracn2floor}+s$ even-sized subsets, then $op(mathcalA)gescdot{2}^{lfloorfracn2floor-1}$ for any positive integer $slefrac{2}^{lfloorfracn8floor}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$.

This page was built for publication: On supersaturation for oddtown and eventown

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6426149)