Largest Sperner families with bounded VC-dimension

Source: arxiv.org/abs/2611.06860

Gennian Ge, Hanyu Wang, Zixiang Xu, Yixuan Zhang

arXivarxiv/2611.06860Nov 4, 2026math.COscore 0

A conjecture of Frankl proposed in the 1980s states that for $n\ge2d$, every Sperner family $\mathcal{F}\subseteq 2^{[n]}$ of VC-dimension at most $d$ has at most $\binom{n}{d}$ members. We prove this conjecture for every fixed $d$ and large $n$, and show that equality holds only when $\mathcal{F}$ is $\binom{[n]}{d}$ or $\binom{[n]}{n-d}$.

JSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2611.06860
curl -X POST /api/v1/records/arxiv/2611.06860/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.06860/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'