Largest Sperner families with bounded VC-dimension

arXiv:2611.06860 · math.CO · Submitted 2026-11-04 · Read on arXiv

math.CO

Submitted: 2026-11-04

Updated: 2026-11-04

Comments: 14 pages

License: http://creativecommons.org/licenses/by/4.0/

The gist: A conjecture of Frankl proposed in the 1980s states that for n at least2d, every Sperner family F 2[n] of VC-dimension at most d has at most d members.

Terminology

Abstract

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

Sources

Related papers