On balanced subfamilies of maximum complement-free families in the middle layer of the Boolean lattice

Abstract

We study balanced subfamilies of the middle layer $\left(\genfrac{}{}{0ex}{}{[2n]}{n}\right)$ of the Boolean lattice $2^{[2n]}$. A family $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[2n]}{n}\right)$ is said to be balanced if every element in $[2n]$ appears in the same number of members of $\mathcal{F}$. A balanced subfamily of size 2 is exactly a complementary pair $\{A,[2n]\setminus A\}$, and therefore a family with no balanced subfamily of size $2$ has at most $\frac{1}{2}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ members. We show that for every $k\ge 1$ and all sufficiently large $n$, this maximum size is compatible with delaying the smallest size of a balanced subfamily until $2k+2$. More precisely, there exists a family $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[2n]}{n}\right)$ of size $\frac{1}{2}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ with no balanced subfamilies of sizes $2,4,\dots ,2k$, but with a balanced subfamily of size $2k+2$. The proof is constructive and is obtained by lifting Taylor-Zwicker trade-robust magic-square games to self-dual selectors in the middle layer. This proves a recent conjecture of Moss and Pedersen.

Changed title, fixed typos, 9 pages