Largest Sperner families with restricted differences

Abstract

Let $L$ be a fixed set of positive integers. A family $\mathcal{F}\subseteq 2^{[n]}$ is called $L$-differencing if $|A\setminus B|\in L$ for every ordered pair of distinct members $A,B\in \mathcal{F}$. A longstanding conjecture of Frankl, proposed in 1985, asserts that every $L$-differencing family has size at most $\left(\genfrac{}{}{0ex}{}{n}{|L|}\right)$. We resolve this conjecture asymptotically for every fixed $L$, and obtain the exact answer in the only case in which the conjectured bound could be tight. (1) If $L\ne [s]$ and $n$ is large, then every $L$-differencing family satisfies $|\mathcal{F}|\le \left(\frac{s}{s+1}+o_L(1)\right)\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. (2) If $L=[s]$ and $n\ge 2s-1$, then $|\mathcal{F}|\le \left(\genfrac{}{}{0ex}{}{n}{s}\right)$, with equality only for $\left(\genfrac{}{}{0ex}{}{[n]}{s}\right)$ and $\left(\genfrac{}{}{0ex}{}{[n]}{n-s}\right)$. The first result follows by reducing directed differences to restricted Hamming distances. For the exact result, we develop a new homogeneous polynomial method, which might be of independent interest.

11 pages