Pith. sign in

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

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
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.

fields

math.CO 1

years

2026 1

verdicts

UNVERDICTED 1

representative citing papers

A disproof of the uniform witness conjecture

math.CO · 2026-06-23 · 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.

citing papers explorer

Showing 1 of 1 citing paper.

  • A disproof of the uniform witness conjecture math.CO · 2026-06-23 · unverdicted · none · ref 21 · internal anchor

    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.