pith. sign in

arxiv: 2606.23469 · v1 · pith:QQJ7NS7Anew · submitted 2026-06-22 · 🧮 math.CO

Beating the Ahlswede--Khachatrian bound for the ErdH{o}s--Frankl--Pach problem

Tuan Tran , Zixiang Xu This is my paper

Pith reviewed 2026-06-26 07:49 UTC · model grok-4.3

classification 🧮 math.CO
keywords Erdős-Frankl-Pach problemVC-dimensionuniform familiesAhlswede-Khachatrian boundMubayi-Zhao conjectureextremal set theoryhypergraph Turán problems
3
0 comments X

The pith

The Mubayi-Zhao conjecture is false for every d≥3 because explicit constructions produce (d+1)-uniform families with VC-dimension d larger than the Ahlswede-Khachatrian bound for infinitely many n.

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

This paper shows that the Mubayi-Zhao conjecture, which held that the Ahlswede-Khachatrian bound is optimal for the Erdős-Frankl-Pach problem, does not hold when d is at least 3. The authors establish this by giving constructions of (d+1)-uniform families on an n-element ground set that have VC-dimension exactly d and exceed the size of the Ahlswede-Khachatrian example for infinitely many n. A sympathetic reader would care because the result indicates that the maximum size in this problem is not captured by the previous bound and instead depends on the interplay between n and d. The paper contrasts this with the case d=2, where the conjecture was recently confirmed for n≥7.

Core claim

We show that the Mubayi-Zhao conjecture is false for every d≥3 by constructing families larger than the Ahlswede--Khachatrian bound. Our constructions suggest that the answer to the Erdős--Frankl--Pach problem depends delicately on both n and d.

What carries the argument

Explicit constructions of (d+1)-uniform families with VC-dimension exactly d whose size exceeds binom(n-1,d) + binom(n-4,d-2) for infinitely many n.

If this is right

  • The Ahlswede-Khachatrian bound is not the maximum size for (d+1)-uniform VC-dimension-d families when d≥3.
  • The extremal function in the Erdős-Frankl-Pach problem depends on both n and d rather than being given by a single closed-form expression.
  • Better lower bounds than the star plus the extra term binom(n-4,d-2) are achievable for all d≥3.
  • The case d=2 remains consistent with the bound for n≥7 while higher d require larger constructions.

Where Pith is reading between the lines

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

  • The exact form of the maximum size may require constructions that change with the range of n relative to d.
  • Related questions about the asymptotic growth rate of the extremal function for fixed d could now be revisited with these larger examples in hand.
  • The dependence on both parameters may extend to other problems that combine uniformity with bounded VC-dimension.

Load-bearing premise

The new families are (d+1)-uniform, have VC-dimension exactly d, and their cardinality exceeds the Ahlswede-Khachatrian bound for infinitely many n.

What would settle it

A direct verification for d=3 and a concrete large n that the constructed family either fails to have VC-dimension d or has size no larger than binom(n-1,d) + binom(n-4,d-2).

read the original abstract

In the 1980s, Erd\H{o}s and, independently, Frankl and Pach conjectured that, for sufficiently large $n$, every $(d+1)$-uniform family on $\{1,\ldots,n\}$ with VC-dimension $d$ has size at most $\binom{n-1}{d}$, the size of a star. Ahlswede and Khachatrian disproved this conjecture in 1997 by giving a family of size $\binom{n-1}{d}+\binom{n-4}{d-2}$. This value has since been widely believed to be best possible, and Mubayi and Zhao explicitly conjectured its optimality in 2007. Very recently, Wang, Xu and Zhang proved their conjecture for $d=2$ and $n\ge 7$, providing further support for this belief. Surprisingly, we show that the Mubayi-Zhao conjecture is false for every $d\ge 3$ by constructing families larger than the Ahlswede--Khachatrian bound. Our constructions suggest that the answer to the Erd\H{o}s--Frankl--Pach problem depends delicately on both $n$ and $d$.

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 / 2 minor

Summary. The paper disproves the Mubayi-Zhao conjecture (that the Ahlswede-Khachatrian bound is optimal) for every d ≥ 3 in the Erdős-Frankl-Pach problem. It does so by supplying explicit (d+1)-uniform families on [n] with VC-dimension exactly d whose cardinality strictly exceeds binom(n-1,d) + binom(n-4,d-2) for infinitely many n.

Significance. If the constructions are correct, the result is significant: it shows that the extremal function for VC-dimension-d uniform families is not given by the Ahlswede-Khachatrian example for d ≥ 3, and that the answer depends delicately on both n and d. The explicit, finite case-analysis constructions constitute a direct, falsifiable disproof rather than an asymptotic or probabilistic argument.

minor comments (2)
  1. In the statement of the main theorem, the precise range of n for which the inequality holds should be stated explicitly rather than only 'infinitely many n'.
  2. Notation for the ground set [n] and the family F is introduced inconsistently between the abstract and §2; a single global definition would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive report, accurate summary of the contribution, and recommendation to accept. The referee correctly notes that the result is a direct, falsifiable disproof via explicit constructions.

Circularity Check

0 steps flagged

No significant circularity; result is explicit construction

full rationale

The paper's central claim is a disproof of the Mubayi-Zhao conjecture via explicit (d+1)-uniform families with VC-dimension d that exceed the Ahlswede-Khachatrian size for d≥3 and infinitely many n. The manuscript supplies the families together with finite case analysis verifying both the cardinality lower bound and the VC-dimension upper bound. No load-bearing step reduces a prediction or theorem to a fitted parameter, self-citation chain, or definitional equivalence; the existence statement is directly witnessed by the constructions themselves. Self-citation to prior d=2 work is peripheral and does not support the d≥3 claim.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work is a pure combinatorial construction relying only on the standard definition of uniform hypergraphs and VC-dimension; no free parameters, ad-hoc axioms, or invented entities appear in the abstract.

axioms (1)
  • standard math Standard definition of VC-dimension for set families
    The paper invokes the usual notion that a family has VC-dimension at most d if no d+1 points are shattered.

pith-pipeline@v0.9.1-grok · 5744 in / 1307 out tokens · 33516 ms · 2026-06-26T07:49:06.216610+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

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.

Reference graph

Works this paper leans on

11 extracted references · 2 canonical work pages · cited by 1 Pith paper

  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

    1997

  2. [2]

    T.-W. Chao, Z. Xu, C. H. Yip, and S. Zhang. Uniform set systems with small VC-dimension. Int. Math. Res. Not. IMRN, (17):Paper No. rnaf269, 20, 2025

    2025

  3. [3]

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

    1983

  4. [4]

    Frankl and J

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

    1984

  5. [5]

    G. Ge, Z. Xu, C. H. Yip, S. Zhang, and X. Zhao. The Frankl-Pach upper bound is not tight for any uniformity.J. Combin. Theory Ser. A, 217:Paper No. 106078, 9, 2026

    2026

  6. [6]

    Mubayi and Y

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

    2007

  7. [7]

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

    1972

  8. [8]

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

    1972

  9. [9]

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

    2015

  10. [10]

    J. Wang, Z. Xu, and S. Zhang. Largest 3-uniform set systems with VC-dimension 2.arXiv preprint, arXiv: 2505.07756, 2025

    work page arXiv 2025

  11. [11]

    Yang and X

    T. Yang and X. Yu. Maximum size of a uniform family with bounded VC-dimension.arXiv preprint, arXiv: 2508.14334, 2025. 5 A The4-uniform construction In this appendix, we prove the 4-uniform case of Theorem 1.2. Proof of Theorem 1.2(i). We retain the notation C“ r 6s, U“ rnszC , and B from the proof of Theorem 1.2(ii). DefineF 3 “ ␣ PYA:PPB, AP ` U 4´|P| ˘...

    work page arXiv 2025