Pith. sign in

REVIEW 2 minor 2 cited by

A recursive construction gives a larger lower bound and disproves the Mubayi-Zhao conjecture on the size of uniform families with VC-dimension at most d for all d at least 3.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

A two-cover lifting construction yields the recursive lower bound M_d(n) >= binom(n-1,d) + binom(n-4,d-2) + M_{d-3}(n-5) for d>=3, disproving the Mubayi-Zhao conjecture on the exact value of M_d(n).

T0 review reviewed 2026-06-26 challenge →

load-bearing objection The paper gives a recursive lower bound via two-cover lifting that adds a positive term and disproves the Mubayi-Zhao conjecture for d >= 3.

arxiv 2606.22064 v1 pith:O3JNPD65 submitted 2026-06-20 math.CO math.STstat.TH

Recursive lower bounds for uniform set systems of bounded VC-dimension

Xiaochen Zhao , Gennian Ge This is my paper
classification math.CO math.STstat.TH
keywords uniform familiesVC-dimensionrecursive lower boundsMubayi-Zhao conjectureextremal set theorylifting constructiontraces
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The reading

M_d(n) measures the largest number of (d+1)-subsets of an n-set whose trace on any d+1 points misses at least one pattern. Earlier work supplied the lower bound binom(n-1,d) plus binom(n-4,d-2). The paper adds a new recursive term M_{d-3}(n-5) obtained by lifting a smaller family. This produces a strictly stronger explicit lower bound and shows the conjecture claiming the earlier expression is already optimal must be false. A reader cares because the maximum size of these restricted families is now known to be larger than previously believed.

Core claim

The authors prove that M_d(n) >= binom(n-1,d) + binom(n-4,d-2) + M_{d-3}(n-5) for d >= 3 and n >= d+3 via an explicit two-cover lifting construction. Applying the inequality once more yields the concrete improvement M_d(n) >= binom(n-1,d) + binom(n-4,d-2) + binom(n-6,d-3). This exceeds the value conjectured to be exact for n >= 2(d+2) and thereby falsifies the Mubayi-Zhao conjecture for every d >= 3.

What carries the argument

The two-cover lifting construction that takes a maximum (d-2)-uniform family of VC-dimension at most d-3 on n-5 points and produces a (d+1)-uniform family of VC-dimension at most d on n points.

Load-bearing premise

The two-cover lifting construction applied to a maximum (d-2)-uniform family of VC-dimension at most d-3 on n-5 points produces a valid (d+1)-uniform family of VC-dimension at most d.

What would settle it

An explicit (d+1)-uniform family on n points with VC-dimension at most d whose size exceeds binom(n-1,d) + binom(n-4,d-2) + binom(n-6,d-3) for some d >= 3 and n >= 2(d+2), or a direct verification that the lifting step fails to preserve the VC-dimension bound.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • The Mubayi-Zhao conjecture is false for every d >= 3.
  • M_d(n) is at least as large as the previous conjectured value plus binom(n-6,d-3).
  • The exact value of M_d(n) remains undetermined but exceeds the earlier expression.
  • Repeated application of the recursion produces still larger lower bounds.

Where Pith is reading between the lines

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

  • The same lifting idea may extend to other pairs of uniformity and dimension.
  • The correct asymptotic growth rate of M_d(n) is now known to be strictly larger than the conjectured one.
  • Small-case computation for d=3 and moderate n could test whether the new bound is tight.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 2 minor

Summary. The manuscript defines M_d(n) as the largest possible size of a (d+1)-uniform family on an n-element ground set with VC-dimension at most d. It introduces an explicit two-cover lifting construction and proves the recursive lower bound M_d(n) ≥ binom(n-1,d) + binom(n-4,d-2) + M_{d-3}(n-5) for d ≥ 3 and n ≥ d+3 by partitioning the ground set and analyzing traces on five distinguished points. This immediately yields the improved bound M_d(n) ≥ binom(n-1,d) + binom(n-4,d-2) + binom(n-6,d-3) and shows that the Mubayi-Zhao conjecture (asserting equality with the first two terms for n ≥ 2(d+2)) is false for every d ≥ 3.

Significance. The result supplies an explicit combinatorial construction that falsifies a conjecture in extremal combinatorics on uniform set systems of bounded VC-dimension. The proof is self-contained, relying only on elementary double-counting and trace analysis rather than external theorems, and the recursive form may permit further iterations. These features make the contribution substantive if the central inequality is verified.

minor comments (2)
  1. In the abstract and §1, the range n ≥ 2(d+2) for the Mubayi-Zhao conjecture is stated without an explicit cross-reference to the original source; adding the citation would improve traceability.
  2. The definition of the two-cover lifting construction (presumably in §3) uses five distinguished points; a short diagram or explicit listing of the lifted sets on those points would aid readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript and for recommending acceptance. The report correctly captures the two-cover lifting construction and the resulting disproof of the Mubayi-Zhao conjecture.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation proceeds by an explicit two-cover lifting construction that takes a maximum (d-2)-uniform family of VC-dimension ≤ d-3 on n-5 points and produces a (d+1)-uniform family of VC-dimension ≤ d on n points. The recursive inequality is obtained by partitioning the ground set and analyzing traces on five distinguished points via elementary double-counting; the added term M_{d-3}(n-5) is therefore a genuine combinatorial contribution rather than a definitional or fitted tautology. The improved closed-form lower bound follows by substituting the classical Ahlswede–Khachatrian/Mubayi–Zhao construction into the recursive term. No load-bearing self-citation, self-definitional step, or renaming of a known result occurs; the argument is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The argument rests on standard combinatorial facts about binomial coefficients, set traces, and VC-dimension; no free parameters, ad-hoc axioms, or new entities are introduced.

axioms (1)
  • standard math Binomial coefficient identities and basic properties of uniform set systems hold.
    Used throughout the definition of M_d(n) and the stated bounds.

reviewed 2026-06-26 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Recursive lower bounds for uniform set systems of bounded VC-dimension." pith.science (2026). https://pith.science/paper/O3JNPD65

@misc{pith2026260622064,
  author       = {Pith},
  title        = {Pith review of: Recursive lower bounds for uniform set systems of bounded VC-dimension},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/O3JNPD65}},
  note         = {Machine review of arXiv:2606.22064}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

For integers $n\ge d+1$, let $\mathsf{M}_d(n)$ denote the maximum size of a $(d+1)$-uniform family on an $n$-element ground set with VC-dimension at most $d$. For $n\ge2d+2$, the classical construction of Ahlswede and Khachatrian, later generalized by Mubayi and Zhao, gives \[ \mathsf{M}_d(n)\ge \binom{n-1}{d}+\binom{n-4}{d-2}. \] We introduce a two-cover lifting construction and prove the recursive lower bound \[ \mathsf{M}_d(n)\ge \binom{n-1}{d}+\binom{n-4}{d-2}+\mathsf{M}_{d-3}(n-5) \] for every $d\ge 3$ and $n\ge d+3$. Consequently, \[ \mathsf{M}_d(n)\ge \binom{n-1}{d}+\binom{n-4}{d-2}+\binom{n-6}{d-3}. \] Thus the Mubayi--Zhao conjecture on the exact value of $\mathsf{M}_d(n)$ for $n\ge2(d+2)$ is false for any $d\ge 3$. The proof is elementary and proceeds entirely through an explicit analysis of traces.

discussion (0)

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

Forward citations

Cited by 2 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. 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.

Reference graph

Works this paper leans on

9 extracted references · cited by 2 Pith papers

  1. [1]

    and Khachatrian, L

    Ahlswede, R. and Khachatrian, L. H. , title =. Combinatorica , volume =. 1997 , pages =

    1997

  2. [2]

    and Xu, Z

    Chao, T.-W. and Xu, Z. and Yip, C. H. and Zhang, S. , title =. Int. Math. Res. Not. IMRN , volume =. 2025 , number =

    2025

  3. [3]

    and Pach, J

    Frankl, P. and Pach, J. , title =. Combinatorica , volume =. 1984 , pages =

    1984

  4. [4]

    and Xu, Z

    Ge, G. and Xu, Z. and Yip, C. H. and Zhang, S. and Zhao, X. , title =. J. Combin. Theory Ser. A , volume =. 2026 , pages =

    2026

  5. [5]

    and Zhao, Y

    Mubayi, D. and Zhao, Y. , title =. J. Algebraic Combin. , volume =. 2007 , pages =

    2007

  6. [6]

    , title =

    Sauer, N. , title =. J. Combin. Theory Ser. A , volume =. 1972 , pages =

    1972

  7. [7]

    , title =

    Shelah, S. , title =. Pacific J. Math. , volume =. 1972 , pages =

    1972

  8. [8]

    and Xu, Z

    Wang, J. and Xu, Z. and Zhang, S. , title =. 2025 , eprint =

    2025

  9. [9]

    and Yu, X

    Yang, T. and Yu, X. , title =. 2025 , eprint =

    2025

This paper was first reviewed by grok-4.3 on June 26, 2026.