Skip to content
DraconiticResearch
Search Sources API
201,642 studies31 sourcesUpdated 55 min ago
PreprintCC BY 4.0arXiv

Largest Sperner families with bounded VC-dimension

  • Gennian Ge
  • Hanyu Wang
  • Zixiang Xu
  • Yixuan Zhang
Open at sourcePDFDOICite

Abstract

A conjecture of Frankl proposed in the 1980s states that for n≥2d, every Sperner family ℱ⊆ 2[n] of VC-dimension at most d has at most binomnd members. We prove this conjecture for every fixed d and large n, and show that equality holds only when ℱ is binom[n]d or binom[n]n−d.

Related

  1. The second-order term for the largest r-fork-free families
    Yiyan Zhan, Mei Lu, Xiamiao Zhao
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  2. On partitions with bounded multiplicity restrictions on even parts and with the largest part being odd
    Gaurab Bardhan, Nipen Saikia
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  3. Bounded VC-dimension implies the Erdős--Rado sunflower conjecture
    Gennian Ge, Jian Wang, Zixiang Xu +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Finite Borel asymptotic dimension of bounded-to-one commutative monoid actions
    Ruijun Wang
    arXivPreprintCC BY 4.0Full textLogic & foundationsarXiv
  5. Intrinsic-dimension empirical Bernstein inequalities for bounded self-adjoint operators
    Diego Martinez-Taboada, Aaditya Ramdas
    arXivPreprintarXiv licenceFull textStatisticsarXiv

Cite

BibTeXRIS
BibTeX
@misc{ge2026largest,
  title = {{Largest Sperner families with bounded VC-dimension}},
  author = {Gennian Ge and Hanyu Wang and Zixiang Xu and Yixuan Zhang},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.06860},
  eprint = {2611.06860},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.06860},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Largest Sperner families with bounded VC-dimension
AU  - Gennian Ge
AU  - Hanyu Wang
AU  - Zixiang Xu
AU  - Yixuan Zhang
PY  - 2026
DA  - 2026/11/04
PB  - arXiv
DO  - 10.48550/arxiv.2611.06860
UR  - https://arxiv.org/abs/2611.06860
AB  - A conjecture of Frankl proposed in the 1980s states that for n≥2d, every Sperner family ℱ⊆ 2^[n] of VC-dimension at most d has at most binomnd members. We prove this conjecture for every fixed d and large n, and show that equality holds only when ℱ is binom[n]d or binom[n]n−d.
ER  -