2026/07/24 by Gennian Ge, Zixiang Xu, Xiaochen Zhao
#math.CO
Let L be a fixed set of positive integers. A family F⊆ 2[n] is called L-differencing if | A∖ B|∈ L for every ordered pair of distinct members A,B\inF. A longstanding conjecture of Frankl, proposed in 1985, asserts that every L-differencing family has size at most \binomn|L|. 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≠ [s] and n is large, then every L-differencing family satisfies | F| ≤ ((s)/(s+1)+oL(1))\binomns. (2) If L=[s] and n≥ 2s-1, then | F|≤\binomns, with equality only for \binom[n]s and \binom[n]n-s. 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.