Pith. sign in

REVIEW 2 major objections 2 minor 21 references

A disproof of the uniform witness conjecture

T0 review · 2 major / 2 minor · reviewed 2026-06-25 · grok-4.3

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

Pith's one-line read 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).

desk verdict Xu gives explicit counterexamples disproving the uniform witness conjecture for ceil((d+2)/2) ≤ s ≤ d-1 when d≥4. read the letter →

arxiv 2606.24776 v1 pith:HDDYNAJE submitted 2026-06-23 math.CO

Zixiang Xu This is my paper · ORCID
classification math.CO
keywords uniformwitnessconjecturemissingtraceVC-dimensionErdős–Ko–Radotheoremextremalsettheory(d+1)-uniformfamiliesdisproof
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

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.

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.

Watch

Extended reading notes

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.

Load-bearing premise

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

Editorial extensions

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.

Reading between the lines

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.
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

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 · score 0.0 of 10

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.

Assumptions & free parameters 0 free parameters · 1 assumptions · 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.

assumptions (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.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A disproof of the uniform witness conjecture." pith.science (2026). https://pith.science/paper/HDDYNAJE

@misc{pith2026260624776,
  author       = {Pith},
  title        = {Pith review of: A disproof of the uniform witness conjecture},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HDDYNAJE}},
  note         = {Machine review of arXiv:2606.24776}
}
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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 5 canonical work pages

  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

Show all 21 references
  1. [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

  2. [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

  3. [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

  4. [12]

    Huang and Y

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

    2024

  5. [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

  6. [14]

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

    1986

  7. [15]

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

    1972

  8. [16]

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

    1972

  9. [17]

    Tran and Z

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

    2026 arXiv

  10. [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

  11. [19]

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

    2025

  12. [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

    2025

  13. [21]

    Zhao and G

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

    2026 arXiv

Pith tools

Reviewed June 25, 2026 · model on record in the stance chip above.