Pith. sign in

REVIEW 4 cited by

Maxmum Size of a Uniform Family with Bounded VC-dimension

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2508.14334 v1 pith:U4QHPK3P submitted 2025-08-20 math.CO

Maxmum Size of a Uniform Family with Bounded VC-dimension

classification math.CO
keywords binomboundchoosesizeuniformuppervc-dimensionconstructed
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
Share X Bluesky LinkedIn Reddit HN
read the original abstract

In 1984, Frankl and Pach proved that, for positive integers $n$ and $d$, the maximum size of a $(d+1)$-uniform set family $\mathcal{F}$ on an $n$-element set with VC-dimension at most $d$ is at most ${n\choose d}$; and they suspected that ${n\choose d}$ could be replaced by ${n-1\choose d}$, which would generalize the famous Erd\H{o}s-Ko-Rado theorem and was mentioned by Erd\H{o}s as Frankl--Pach conjecture. However, Ahlswede and Khachatrian in 1997 constructed $(d+1)$-uniform families on an $n$-element set with VC-dimension at most $d$ and size exactly $\binom{n-1}{d}+\binom{n-4}{d-2}$, and Mubayi and Zhao in 2007 constructed more such families. It has since been an open question to narrow the gap between the lower bound $\binom{n-1}{d}+\binom{n-4}{d-2}$ and the upper bound ${n\choose d}$. In a recent breakthrough, Chao, Xu, Yip, and Zhang reduced the upper bound $\binom{n }{d}$ to $ \binom{n-1}{d}+O( n^{d-1-\frac{1}{4d-2}})$. In this paper, we further reduce the upper bound to $\binom{n-1}{d} + O(n^{d-2})$, asymptotically matching the lower bound $\binom{n-1}{d}+\binom{n-4}{d-2}$.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. A disproof of the uniform witness conjecture

    math.CO 2026-06 unverdicted novelty 8.0

    Disproves the uniform witness conjecture via explicit construction of larger families than the bound binom(n-1,d) for d≥4 and ceil((d+2)/2)≤s≤d-1.

  2. Beating the Ahlswede--Khachatrian bound for the Erd\H{o}s--Frankl--Pach problem

    math.CO 2026-06 unverdicted novelty 8.0

    New explicit constructions yield (d+1)-uniform VC-d families larger than the Ahlswede-Khachatrian size for d≥3, disproving the Mubayi-Zhao conjecture.

  3. Recursive Lifting Beyond the Ahlswede--Khachatrian Construction

    math.CO 2026-07 accept novelty 6.5

    For every d≥3 and n≥d+3, M_d(n) ≥ binom(n-1,d)+binom(n-4,d-2)+M_{d-3}(n-5), beating the Ahlswede–Khachatrian/Mubayi–Zhao lower bound via recursive lifting.

  4. A Single-Exponential Erd\H{o}s--Hajnal Bound for Graphs of Bounded VC-Dimension

    math.CO 2026-07 accept novelty 6.0

    Every n-vertex graph of VC-dimension ≤ d has a homogeneous set of size at least n^{(C d)^{-d}} for an absolute constant C.