Overflow conjecture for families of bounded diameter

About 1 year old · traced to

Let [n]={1,…,n}[n]=\{1,\ldots,n\} and let 2[n]2^{[n]} denote its power set. For a family F⊂2[n]\mathcal{F}\subset 2^{[n]}, write

δ(F)=max⁡{∣A△B∣:A,B∈F}\delta(\mathcal{F})=\max\{|A\triangle B|:A,B\in\mathcal{F}\}

and define its diametral overflow by

κu(F)=min⁡{∣F∖KA(n,u)∣:A⊂[n]},\kappa_u(\mathcal{F})=\min\{|\mathcal{F}\setminus\mathcal{K}_A(n,u)|:A\subset[n]\},

where KA(n,u)\mathcal{K}_A(n,u) is a Kleitman extremal family of diameter uu. Let uu be a positive integer, and write u=2du=2d or u=2d+1u=2d+1 according to its parity. Overflow conjecture. There exists an absolute constant cc such that, whenever δ(F)≤u\delta(\mathcal{F})\leq u and n>cun>cu,

κu(F)≤(n−2d−1)if u=2d,\kappa_u(\mathcal{F})\leq\binom{n-2}{d-1}\quad\text{if }u=2d,

while

κu(F)≤2(n−3d−1)if u=2d+1.\kappa_u(\mathcal{F})\leq2\binom{n-3}{d-1}\quad\text{if }u=2d+1.

The bounds are motivated by the examples B(n,2d)\mathcal{B}(n,2d) and G(n,2d+1)\mathcal{G}(n,2d+1), for which the corresponding overflows attain these values; the conjecture asserts that these examples give universal upper bounds when nn is sufficiently larger than uu.

References

Primary source

Peter Frankl and Jian Wang, “The overflow in the Katona Theorem”, arXiv:2506.05704 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.