Frankl's chain-free conjecture for families with bounded VC-dimension

About 1 year old · traced to

Let n,d,ℓn,d,\ell be positive integers satisfying

n+ℓ≥2(d+1),n+\ell\ge 2(d+1),

and let F⊆2[n]\mathcal{F}\subseteq 2^{[n]} be a family whose VC-dimension is at most dd and which contains no chain of length ℓ+1\ell+1.

Frankl's chain-free conjecture.

∣F∣≤∑i=d−ℓd(ni).|\mathcal{F}|\le \sum_{i=d-\ell}^{d}{n\choose i}.

This extends the Sperner-family problem from antichains to families with bounded chain length while retaining bounded VC-dimension. The source presents it as an open conjecture of Frankl.

References

Primary source

Tianchi Yang and Xingxing Yu, “Maxmum Size of a Uniform Family with Bounded VC-dimension”, arXiv:2508.14334 (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.