pith. sign in

arxiv: 2501.13850 · v2 · submitted 2025-01-23 · 🧮 math.CO

Uniform set systems with small VC-dimension

Ting-Wei Chao , Zixiang Xu , Chi Hoi Yip , Shengtong Zhang This is my paper

Pith reviewed 2026-05-23 04:44 UTC · model grok-4.3

classification 🧮 math.CO
keywords uniform set systemsVC-dimensionextremal set theoryFrankl-Pach boundErdős-Frankl-Pach conjecturecombinatorial countingset families
0
0 comments X

The pith

For large n the maximum size of a (d+1)-uniform family with VC-dimension at most d is at most binom(n-1,d) plus an error of order n to the power d-1 minus 1 over 4d-2.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper improves the Frankl-Pach upper bound of binom(n,d) on the largest (d+1)-uniform set system on n points that has VC-dimension at most d. It shows that the bound can be sharpened to binom(n,d) minus binom(n-1,d-1) plus a smaller-order error term, which equals binom(n-1,d) plus O_d of n to the power d-1 minus 1 over 4d-2. This removes the dominant term from the previous gap to the known lower bound of binom(n-1,d) plus binom(n-4,d-2). The same combinatorial argument also disproves the original Erdős-Frankl-Pach conjecture and supports a refined version.

Core claim

The paper claims that for all sufficiently large n the extremal size is at most binom(n,d) minus binom(n-1,d-1) plus an error term O_d(n^{d-1 - 1/(4d-2)}), which is equal to binom(n-1,d) plus the same error. The proof uses a purely combinatorial counting argument that cancels the binom(n-1,d-1) term while controlling the remaining error. The result also shows that the Erdős-Frankl-Pach conjecture is false and verifies several cases of a proposed refinement.

What carries the argument

A purely combinatorial counting argument that cancels the binom(n-1,d-1) term while bounding the error term of order n to the power d-1 minus 1 over 4d-2.

If this is right

  • The main term binom(n-1,d-1) is removed from the gap between the previous upper and lower bounds.
  • The original Erdős-Frankl-Pach conjecture is false.
  • A refined conjecture relating VC-dimension to the Erdős-Ko-Rado theorem is proposed and verified in several cases.
  • The new bound gives fresh structural information on uniform families with small VC-dimension.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar counting methods might determine the exact extremal size for fixed d when n is large enough.
  • The refined conjecture could connect VC-dimension bounds more tightly to intersecting-family theorems.
  • For each fixed d the extremal families for large n must be close in structure to the complete d-uniform star.
  • The error exponent 1 over 4d-2 may be improvable by refining the counting argument.

Load-bearing premise

The purely combinatorial counting argument succeeds in cancelling the binom(n-1,d-1) term while controlling the remaining error for all sufficiently large n.

What would settle it

A construction of a (d+1)-uniform family on n points with VC-dimension at most d whose size exceeds binom(n-1,d) plus C times n to the power d-1 minus 1 over 4d-2 for arbitrarily large n would falsify the upper bound.

read the original abstract

We investigate the longstanding problem of determining the maximum size of a $(d+1)$-uniform set system with VC-dimension at most $d$. Since the seminal 1984 work of Frankl and Pach, which established the elegant upper bound $\binom{n}{d}$, this question has resisted significant progress. The best-known lower bound is $\binom{n-1}{d} + \binom{n-4}{d-2}$, obtained by Ahlswede and Khachatrian, leaving a substantial gap of $\binom{n-1}{d-1}-\binom{n-4}{d-2}$. Despite decades of effort, improvements to the Frankl--Pach bound have been incremental at best: Mubayi and Zhao introduced an $\Omega_d(\log{n})$ improvement for prime powers $d$, while Ge, Xu, Yip, Zhang, and Zhao achieved a gain of 1 for general $d$. In this work, we provide a purely combinatorial approach that significantly sharpens the Frankl--Pach upper bound. Specifically, for large $n$, we demonstrate that the Frankl--Pach bound can be improved to $\binom{n}{d} - \binom{n-1}{d-1} + O_d(n^{d-1 - \frac{1}{4d-2}})=\binom{n-1}{d}+O_d(n^{d-1 - \frac{1}{4d-2}})$. This result completely removes the main term $\binom{n-1}{d-1}$ from the previous gap between the known lower and upper bounds. It also offers fresh insights into the combinatorial structure of uniform set systems with small VC-dimension. In addition, the original Erd\H{o}s--Frankl--Pach conjecture, which sought to generalize the EKR theorem in the 1980s, has been disproven. We propose a new refined conjecture that might establish a sturdier bridge between VC-dimension and the EKR theorem, and we verify several specific cases of this conjecture, which is of independent interest.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript claims a purely combinatorial argument that improves the Frankl-Pach upper bound on the maximum size of a (d+1)-uniform set system on [n] with VC-dimension at most d, showing that for sufficiently large n the size is at most binom(n,d) - binom(n-1,d-1) + O_d(n^{d-1 - 1/(4d-2)}), equivalently binom(n-1,d) + O_d(n^{d-1 - 1/(4d-2)}). It further states that this removes the leading binom(n-1,d-1) term from the previous gap to the Ahlswede-Khachatrian lower bound, disproves the Erdős–Frankl–Pach conjecture, and proposes a refined conjecture whose specific cases are verified.

Significance. If the claimed combinatorial counting argument holds, the result would constitute a substantial advance in extremal set theory by closing most of the longstanding gap between the Frankl-Pach upper bound and known constructions, while supplying direct combinatorial structure insights. The purely combinatorial character of the proof (no external analytic or algebraic tools) is a clear strength, as is the explicit disproof of the prior conjecture together with the proposal of a new refined version linking VC-dimension to EKR-type statements.

minor comments (3)
  1. [Theorem 1.1 (or equivalent)] The main theorem statement should replace the informal phrase 'for large n' with an explicit lower bound on n in terms of d (e.g., n ≥ n_0(d)).
  2. [Abstract and §2] The O_d notation in the error term should be accompanied by a brief remark on whether the implied constant is effective or merely existential.
  3. [§6] The new refined conjecture is stated only informally; a precise formulation (including the exact extremal function conjectured) would aid readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive and encouraging report, which recognizes the combinatorial nature of our argument, the improvement over the Frankl–Pach bound, the disproof of the Erdős–Frankl–Pach conjecture, and the proposed refinement. We appreciate the recommendation for minor revision.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper presents its central improvement as a direct, self-contained combinatorial counting argument that cancels the binom(n-1,d-1) term while controlling a lower-order error, without any fitted parameters relabeled as predictions, self-definitional steps, or load-bearing reliance on prior self-citations for the uniqueness or validity of the new bound. The derivation chain is independent of external benchmarks or author-specific theorems and does not reduce any claimed prediction to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claimed result rests on standard binomial identities and double-counting arguments in extremal set theory; no free parameters, new entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • standard math Binomial coefficient identities and basic double-counting hold for uniform set families.
    Invoked implicitly when comparing sizes of (d+1)-uniform families.

pith-pipeline@v0.9.0 · 5919 in / 1333 out tokens · 22058 ms · 2026-05-23T04:44:59.275715+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages · 1 internal anchor

  1. [1]

    Ahlswede and L

    R. Ahlswede and L. H. Khachatrian. Counterexample to the Frankl-Pach conjecture for uniform, dense families. Combinatorica, 17(2):299–301, 1997

    work page 1997

  2. [2]

    Alweiss, S

    R. Alweiss, S. Lovett, K. Wu, and J. Zhang. Improved bound s for the sunflower lemma. Ann. of Math. (2) , 194(3):795–815, 2021

    work page 2021

  3. [3]

    Balogh, A

    J. Balogh, A. Bernshteyn, M. Delcourt, A. Ferber, and H. T . Pham. Sunflowers in set systems with small VC-dimension. arXiv preprint, arXiv: 2408.04165, 2024

    work page arXiv 2024

  4. [4]

    T. Bell, S. Chueluecha, and L. Warnke. Note on sunflowers. Discrete Math. , 344(7):Paper No. 112367, 3, 2021

    work page 2021

  5. [5]

    Chao and H.-H

    T.-W. Chao and H.-H. H. Yu. Tight bound and structural the orem for joints. arXiv preprint , arXiv: 2307.15380, 2023

    work page arXiv 2023

  6. [6]

    Ellis, N

    D. Ellis, N. Keller, and N. Lifshitz. Stability for the co mplete intersection theorem, and the forbidden intersection problem of Erd˝ os and S´ os.J. Eur. Math. Soc. (JEMS) , 26(5):1611–1654, 2024

    work page 2024

  7. [7]

    P. Erd˝ os. On some problems in graph theory, combinatori al analysis and combinatorial number theory. In Graph theory and combinatorics (Cambridge, 1983) , pages 1–17. Academic Press, London, 1984

    work page 1983

  8. [8]

    Erd˝ os, C

    P. Erd˝ os, C. Ko, and R. Rado. Intersection theorems for s ystems of finite sets. Quart. J. Math. Oxford Ser. (2) , 12:313–320, 1961

    work page 1961

  9. [9]

    Erd˝ os and R

    P. Erd˝ os and R. Rado. Intersection theorems for systems of sets. J. London Math. Soc. , 35:85–90, 1960

    work page 1960

  10. [10]

    J. Fox, J. Pach, and A. Suk. Erd˝ os-Hajnal conjecture fo r graphs with bounded VC-dimension. Discrete Comput. Geom. , 61(4):809–829, 2019

    work page 2019

  11. [11]

    J. Fox, J. Pach, and A. Suk. Bounded VC-dimension implie s the Schur-Erd˝ os conjecture.Com- binatorica, 41(6):803–813, 2021. 24

    work page 2021

  12. [12]

    J. Fox, J. Pach, and A. Suk. Sunflowers in set systems of bo unded dimension. Combinatorica, 43(1):187–202, 2023

    work page 2023

  13. [13]

    Frankl and J

    P. Frankl and J. Pach. On disjointly representable sets . Combinatorica, 4(1):39–45, 1984

    work page 1984

  14. [14]

    F¨ uredi and J

    Z. F¨ uredi and J. R. Griggs. Families of finite sets with m inimum shadows. Combinatorica, 6(4):355–363, 1986

    work page 1986

  15. [15]

    G. Ge, Z. Xu, C. H. Yip, S. Zhang, and X. Zhao. The Frankl-P ach upper bound is not tight for any uniformity. arXiv preprint, arXiv: 2412.11901, 2024

    work page internal anchor Pith review arXiv 2024

  16. [16]

    Gruslys, S

    V. Gruslys, S. Letzter, and N. Morrison. Hypergraph Lag rangians I: The Frankl-F¨ uredi conjec- ture is false. Adv. Math., 365:107063, 30, 2020

    work page 2020

  17. [17]

    A. J. W. Hilton and E. C. Milner. Some intersection theor ems for systems of finite sets. Quart. J. Math. Oxford Ser. (2) , 18:369–384, 1967

    work page 1967

  18. [18]

    G. Katona. A theorem of finite sets. In Theory of Graphs (Proc. Colloq., Tihany, 1966) , pages 187–207. Academic Press, New York-London, 1968

    work page 1966

  19. [19]

    Keller and N

    N. Keller and N. Lifshitz. The junta method for hypergra phs and the Erd˝ os-Chv´ atal simplex conjecture. Adv. Math. , 392:Paper No. 107991, 95, 2021

    work page 2021

  20. [20]

    J. B. Kruskal. The number of simplices in a complex. In Mathematical optimization techniques , pages 251–278. Univ. California Press, Berkeley-Los Angel es, Calif., 1963

    work page 1963

  21. [21]

    Lov´ asz

    L. Lov´ asz. Combinatorial problems and exercises . North-Holland Publishing Co., Amsterdam- New York, 1979

    work page 1979

  22. [22]

    Mubayi and Y

    D. Mubayi and Y. Zhao. On the VC-dimension of uniform hyp ergraphs. J. Algebraic Combin. , 25(1):101–110, 2007

    work page 2007

  23. [23]

    Nguyen, A

    T. Nguyen, A. Scott, and P. Seymour. Induced subgraph de nsity. VI. Bounded VC-dimension. arXiv preprint, arXiv: 2312.15572, 2023

    work page arXiv 2023

  24. [24]

    N. Sauer. On the density of families of sets. J. Comb. Theory, Ser. A , 13:145–147, 1972

    work page 1972

  25. [25]

    S. Shelah. A combinatorial problem; stability and orde r for models and theories in infinitary languages. Pac. J. Math. , 41:247–261, 1972

    work page 1972

  26. [26]

    V. N. Vapnik and A. Y. Chervonenkis. On the uniform conve rgence of relative frequencies of events to their probabilities. In Measures of complexity , pages 11–30. Springer, Cham, 2015. Reprint of Theor. Probability Appl. 16 (1971), 264–280. 25

    work page 2015