pith. sign in

arxiv: 2606.24776 · v1 · pith:HDDYNAJEnew · submitted 2026-06-23 · 🧮 math.CO

A disproof of the uniform witness conjecture

Zixiang Xu This is my paper

Pith reviewed 2026-06-25 22:43 UTC · model grok-4.3

classification 🧮 math.CO
keywords uniform witness conjecturemissing traceVC-dimensionErdős–Ko–Rado theoremextremal set theory(d+1)-uniform familiesdisproof
0
0 comments X

The pith

For d≥4 and ⌈(d+2)/2⌉≤s≤d−1, (d+1)-uniform families with uniform missing traces of size s can exceed size binom(n−1,d).

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

The uniform witness conjecture proposed that (d+1)-uniform families where every set has a missing trace of the same size s must have at most binom(n-1,d) members. The paper constructs explicit counterexamples for d at least 4 and s in the upper half of the range up to d-1. These families achieve a strictly larger size given by binom(n-1,d) plus an additional binomial term, for all n at least 2(d+1). This shows the conjecture does not hold in those cases, even though it was verified for smaller s and for s=d.

Core claim

For d≥4 and ⌈(d+2)/2⌉≤s≤d−1, there exists a family F of (d+1)-subsets of [n] with |F| = binom(n-1,d) + binom(n-2(d+1-s)-2, 2s-d-2) such that every member of F has a missing trace of size exactly s, for every n≥2(d+1). This construction directly disproves the uniform witness conjecture.

What carries the argument

An explicit combinatorial construction of a (d+1)-uniform family on n elements that meets the uniform missing-trace condition of size s while exceeding the conjectured extremal size.

If this is right

  • The uniform witness conjecture is false in the stated parameter range.
  • The extremal size for such families is at least the constructed quantity.
  • Previous proofs of the conjecture for s ≤ d/2 and s=d do not extend to the intermediate s values.
  • The link between Erdős–Ko–Rado and VC-dimension requires a different formulation for uniform missing traces.

Where Pith is reading between the lines

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

  • The true maximum size may involve a different expression that interpolates between the cases.
  • Similar constructions might apply to non-uniform families or other notions of traces.
  • Checking the construction for small values of d like 4 could reveal the smallest counterexample.
  • One could try to find the correct conjectured bound based on this construction.

Load-bearing premise

The explicitly constructed family satisfies the missing-trace condition of size s for every one of its members.

What would settle it

Verification for a specific d=4, s=3, n=10 showing whether all sets in the constructed family have missing traces of size exactly 3, or if the size formula produces a number larger than known bounds.

read the original abstract

The study of $(d+1)$-uniform set systems with VC-dimension at most $d$ links the Erd\H{o}s--Ko--Rado theorem with VC-dimension. But already in 1997, Ahlswede and Khachatrian showed that this is not the right extension of the Erd\H{o}s--Ko--Rado theorem. In 2025, Chao, Xu, Yip and Zhang proposed the uniform witness conjecture as a possible right extension: for $0\le s\le d$, if every set of a $(d+1)$-uniform family has a missing trace of the same fixed size $s$, then the family should have size at most $\binom{n-1}{d}$. They proved the conjecture when $s=d$, and when $s=1$ and $n$ is large. Very recently, Chao, Xu and Zakharov proved the conjecture when $s\le \frac{d}{2}$ and $n$ is large. We fill in the missing half of the picture, although the picture is not the one suggested by the conjecture. More precisely, for $d\ge 4$ and $\left\lceil \frac{d+2}{2}\right\rceil\le s\le d-1$, we construct such a family $\mathcal{F}\subseteq\binom{[n]}{d+1}$ with $|\mathcal{F}|=\binom{n-1}{d}+\binom{n-2(d+1-s)-2}{2s-d-2}$ for every $n\ge2(d+1)$, thereby disproving the uniform witness conjecture.

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

2 major / 2 minor

Summary. The manuscript claims to disprove the uniform witness conjecture by constructing, for d≥4 and ⌈(d+2)/2⌉≤s≤d−1, an explicit (d+1)-uniform family F⊆binom([n],d+1) on [n] with |F|=binom(n−1,d)+binom(n−2(d+1−s)−2,2s−d−2) for all n≥2(d+1), where every member of F has a missing trace of size exactly s.

Significance. If the construction and verification hold, the result is significant: it supplies concrete counterexamples in the parameter range left open by prior partial proofs (s=d; s=1 and large n; s≤d/2 and large n), with an explicit binomial formula that is parameter-free and falsifiable for small d,n. This shows the uniform missing-trace condition does not force the EKR-type bound binom(n−1,d) in general.

major comments (2)
  1. [Construction (presumably the main technical section following the abstract)] The load-bearing step is the claim that the constructed family satisfies the uniform missing-trace condition of size s for every member. The abstract invokes 'such a family' with the stated size but supplies no equations or section references for the construction itself; the manuscript must contain an explicit definition of F together with a proof that, for every A∈F, there exists a trace of size s missing from A (otherwise the disproof collapses even if the cardinality formula is correct).
  2. [Size formula in the abstract and its derivation] The second binomial coefficient binom(n−2(d+1−s)−2,2s−d−2) must be shown to be strictly positive throughout the stated range of d,s,n so that |F|>binom(n−1,d); this positivity is required for the family to be a genuine counterexample rather than a trivial or empty extension.
minor comments (2)
  1. The lower bound ⌈(d+2)/2⌉ on s should be compared explicitly with the already-proved regime s≤d/2 to clarify the gap being filled (e.g., for d=4 the new range begins at s=3 while prior results cover s≤2).
  2. Notation: ensure the binomial coefficients are written consistently (e.g., inom vs. binom) and that the ground set [n] and uniformity d+1 are defined at first use.

Simulated Author's Rebuttal

2 responses · 0 unresolved

Thank you for the detailed report. We appreciate the identification of points that require clarification in the presentation. Below we respond to the major comments. We will revise the manuscript to address these issues.

read point-by-point responses

  1. Referee: [Construction (presumably the main technical section following the abstract)] The load-bearing step is the claim that the constructed family satisfies the uniform missing-trace condition of size s for every member. The abstract invokes 'such a family' with the stated size but supplies no equations or section references for the construction itself; the manuscript must contain an explicit definition of F together with a proof that, for every A∈F, there exists a trace of size s missing from A (otherwise the disproof collapses even if the cardinality formula is correct).

    Authors: The full manuscript contains an explicit definition of F in Section 2 together with a complete proof (Theorem 3.1) that every member has a missing trace of size exactly s. We agree the abstract would be improved by adding a direct reference to these sections. We will revise the abstract to read: 'In Section 2 we construct such a family F ⊆ binom([n],d+1) ... (the uniform missing-trace property is verified in Theorem 3.1).' revision: yes

  2. Referee: [Size formula in the abstract and its derivation] The second binomial coefficient binom(n−2(d+1−s)−2,2s−d−2) must be shown to be strictly positive throughout the stated range of d,s,n so that |F|>binom(n−1,d); this positivity is required for the family to be a genuine counterexample rather than a trivial or empty extension.

    Authors: We will add a short remark immediately after the main theorem stating that the second binomial coefficient is strictly positive for the given range. This follows because s ≥ ⌈(d+2)/2⌉ forces 2s−d−2 ≥ 0, while n ≥ 2(d+1) ensures the upper index is large enough that the binomial coefficient is positive (both indices are non-negative integers and the upper exceeds the lower). revision: yes

Circularity Check

0 steps flagged

No circularity: explicit combinatorial construction

full rationale

The paper's central claim is an explicit construction of a (d+1)-uniform family F whose size exceeds the conjectured bound while satisfying the uniform missing-trace condition of size s. The cardinality is expressed directly via binomial coefficients with no fitted parameters, self-referential definitions, or load-bearing self-citations. Prior results cited in the abstract concern only the conjecture's validity in other regimes and are not invoked to justify the new counterexample family. The derivation therefore reduces to a direct combinatorial argument that stands independently of its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The disproof uses only standard binomial counting and set-system definitions; no free parameters, ad-hoc axioms, or new entities are introduced in the abstract.

axioms (1)
  • standard math Standard definitions and identities of binomial coefficients and uniform hypergraphs
    The size formula is expressed directly in terms of binomial coefficients whose properties are taken from prior mathematics.

pith-pipeline@v0.9.1-grok · 5810 in / 1448 out tokens · 33572 ms · 2026-06-25T22:43:46.338600+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

21 extracted references · 5 canonical work pages · 2 internal anchors

  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, 2025(17):Paper No. rnaf269, 20, 2025

    2025

  3. [3]

    T.-W. Chao, Z. Xu, and D. Zakharov. Uniform set systems with uniform witnesses.arXiv preprint, arXiv: 2602.17459, 2026

    work page arXiv 2026

  4. [4]

    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

  5. [5]

    Erd˝ os, C

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

    1961

  6. [6]

    Frankl and R

    P. Frankl and R. L. Graham. Old and new proofs of the Erd˝ os-Ko-Rado theorem.Sichuan Daxue Xuebao, 26:112–122, 1989

    1989

  7. [7]

    Frankl and J

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

    1984

  8. [8]

    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

  9. [9]

    Han and Y

    J. Han and Y. Kohayakawa. The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton-Milner family.Proc. Amer. Math. Soc., 145(1):73–87, 2017

    2017

  10. [10]

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

    1967

  11. [11]

    Huang and Y

    H. Huang and Y. Zhao. Degree versions of the Erd˝ os-Ko-Rado theorem and Erd˝ os hypergraph matching conjecture.J. Combin. Theory Ser. A, 150:233–247, 2017

    2017

  12. [12]

    Huang and Y

    Y. Huang and Y. Peng. Stability of intersecting families.European J. Combin., 115:Paper No. 103774, 22, 2024

    2024

  13. [13]

    Mubayi and Y

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

    2007

  14. [14]

    L. Pyber. A new generalization of the Erd˝ os-Ko-Rado theorem.J. Combin. Theory Ser. A, 43(1):85–90, 1986

    1986

  15. [15]

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

    1972

  16. [16]

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

    1972

  17. [17]

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

    T. Tran and Z. Xu. Beating the Ahlswede–Khachatrian bound for the Erd˝ os–Frankl–Pach problem.arXiv preprint, arXiv: 2606.23469, 2026

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  18. [18]

    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

  19. [19]

    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

  20. [20]

    Yang and X

    T. Yang and X. Yu. Maximum size of a uniform family with bounded VC-dimension.arXiv preprint, arXiv: 2508.14334, 2025

    work page arXiv 2025

  21. [21]

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

    X. Zhao and G. Ge. Recursive lower bounds for uniform set systems of bounded VC-dimension. arXiv preprint, arXiv: 2606.22064, 2026. 5

    work page internal anchor Pith review Pith/arXiv arXiv 2026