pith. sign in

arxiv: 2605.21961 · v3 · pith:2AYW2ULLnew · submitted 2026-05-21 · 🧮 math.CO

Excess Obstructions and Star-Isolated Certificates for the Hypergraph Nash--Williams--Tutte Conjecture

Yutong Zhang , Yaoran Yang This is my paper

Pith reviewed 2026-05-22 05:00 UTC · model grok-4.3

classification 🧮 math.CO
keywords hypergraph Nash-Williams-Tutte conjecturetree assignmentweakly partition connectedexcesscounterexamplestar realizationintersection matrix
0
0 comments X

The pith

The published hypergraph Nash-Williams-Tutte conjecture is false because some k-weakly-partition-connected hypergraphs have excess strictly larger than k(t-1).

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

The paper shows that the conjecture claiming every k-weakly-partition-connected hypergraph on t vertices admits a k-distinguishable tree assignment is false in its literal form. The counterexample is the hypergraph made from k+q identical copies of the complete hyperedge on all t vertices, for any q at least 1. This object meets the connectivity hypothesis yet its total excess exceeds the exact edge count k(t-1) required by any tree assignment. The authors isolate the corrected equality form of the conjecture, verify that it matches the necessary row-rank condition on the intersection matrix, and construct an infinite family of positive instances via layer-contained star realizations.

Core claim

A k-weakly-partition-connected hypergraph need not admit a k-distinguishable tree assignment, since weak partition connectivity guarantees only that the excess ρ(H) is at least k(t-1) while any k-distinguishable tree assignment requires exactly k(t-1) edges; the hypergraph consisting of k+q copies of the full hyperedge V therefore supplies an obstruction for every t≥2, k≥1, q≥1.

What carries the argument

Excess ρ(H), the sum over all hyperedges e of (|e|−1), which equals the total number of edges produced when each hyperedge is replaced by a spanning tree on its vertices.

If this is right

  • The equality ρ(H)=k(t-1) is necessary for any k-distinguishable tree assignment to exist.
  • The corrected conjecture therefore adds the equality condition on excess to the original connectivity hypothesis.
  • A large class of hypergraphs satisfying the corrected conjecture is given by layer-contained star realizations with extremal signature weights.

Where Pith is reading between the lines

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

  • The quotient-rank argument used to establish weak partition connectivity may apply to other hypergraph connectivity parameters.
  • The obstruction construction suggests that similar excess mismatches could appear in related decomposition conjectures for hypergraphs.
  • One-vertex sums and two-sided star blocks might serve as building blocks for further certificates in matroid or graph packing problems.

Load-bearing premise

A k-distinguishable tree assignment is produced by replacing each hyperedge with a tree on its vertex set, thereby contributing exactly |e|−1 edges to the overall count.

What would settle it

For the concrete values t=3, k=2, q=1, form the hypergraph consisting of three copies of the single 3-uniform hyperedge on three vertices and determine whether it possesses a 2-distinguishable tree assignment.

Figures

Figures reproduced from arXiv: 2605.21961 by Yaoran Yang, Yutong Zhang.

Figure 1
Figure 1. Figure 1 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 5
Figure 5. Figure 5 [PITH_FULL_IMAGE:figures/full_fig_p012_5.png] view at source ↗
read the original abstract

Guo, Li, Shangguan, Tamo, and Wootters formulated in SIAM Journal on Computing a hypergraph Nash--Williams--Tutte conjecture: every $k$-weakly-partition-connected hypergraph on $t$ vertices should admit a $k$-distinguishable tree assignment. We show that the conjecture, in its literal published form, is false for a sharp and structural reason. A tree assignment replaces every hyperedge $e$ by a tree with $|e|-1$ labelled edges, so its edge number is the excess $\rho(H)=\sum_e(|e|-1)$. A $k$-tree decomposition, however, has exactly $k(t-1)$ edges. Thus $\rho(H)=k(t-1)$ is a necessary condition, whereas weak partition connectivity only implies $\rho(H)\ge k(t-1)$. Consequently, for every $t\ge2$, $k\ge1$, and $q\ge1$, the hypergraph consisting of $k+q$ copies of the full hyperedge $V$ is $k$-weakly-partition-connected but has no $k$-distinguishable tree assignment. We then isolate the critical corrected form, prove that its equality is exactly the equality required for the full intersection-matrix row set, and give a large non-graphic class of critical positive instances. The positive construction uses layer-contained star realizations and extremal signature weights, producing weak partition connectivity by a quotient-rank argument and unique signatures under one-vertex sums and explicit two-sided star blocks.

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 paper disproves the literal form of the hypergraph Nash--Williams--Tutte conjecture of Guo-Li-Shangguan-Tamo-Wootters: every k-weakly-partition-connected hypergraph on t vertices need not admit a k-distinguishable tree assignment. The obstruction is that a tree assignment (replacing each hyperedge e by a tree on its vertices) produces exactly ρ(H) = ∑(|e|−1) edges, while a k-tree decomposition requires precisely k(t−1) edges; weak partition connectivity supplies only the inequality ρ(H) ≥ k(t−1). The authors exhibit the family consisting of k+q identical copies of the complete hyperedge V (t≥2, k≥1, q≥1) as counterexamples, verify the connectivity condition via the cut contribution of a full hyperedge, and then isolate the corrected equality ρ(H)=k(t−1), prove it coincides with the row-rank condition on the intersection matrix, and construct a large class of positive instances via layer-contained star realizations, extremal signature weights, and quotient-rank arguments.

Significance. The excess-counting disproof is direct from the definitions and supplies a sharp, parameter-free obstruction that separates connectivity from the numerical requirement. The equivalence to the matrix-rank condition and the explicit positive constructions (layer-contained stars with unique signatures under one-vertex sums) give concrete support for the corrected statement and identify a non-graphic family of critical instances. These elements together refine the conjecture and provide falsifiable certificates.

major comments (2)
  1. [definitions and excess] § on definitions and excess: the necessity claim that every k-distinguishable tree assignment yields exactly ρ(H) edges rests on the replacement of each hyperedge e by a spanning tree contributing |e|−1 edges; this step is load-bearing for the entire obstruction argument and should be stated as a numbered lemma with the precise edge-count equality.
  2. [counterexample family] Counterexample family (abstract and § on counterexamples): the assertion that k+q copies of the full hyperedge V is k-weakly-partition-connected for every t,k,q relies on the claim that a single full hyperedge contributes its full span (r−1) to any r-part partition; an explicit verification of this cut condition for the multi-hyperedge case would confirm the connectivity hypothesis is not merely asserted.
minor comments (2)
  1. The positive constructions using layer-contained stars and signature uniqueness are only sketched in the abstract; a self-contained subsection spelling out the quotient-rank argument and the two-sided star blocks would make the certificates fully checkable.
  2. Notation for the intersection matrix and its row set should be introduced with a displayed definition before the equivalence proof is invoked.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the constructive suggestions that strengthen the clarity of the obstruction argument and the counterexample verification. We address each major comment below.

read point-by-point responses

  1. Referee: [definitions and excess] § on definitions and excess: the necessity claim that every k-distinguishable tree assignment yields exactly ρ(H) edges rests on the replacement of each hyperedge e by a spanning tree contributing |e|−1 edges; this step is load-bearing for the entire obstruction argument and should be stated as a numbered lemma with the precise edge-count equality.

    Authors: We agree that this foundational counting step benefits from explicit formalization. In the revised version we will insert a new numbered lemma (placed immediately after the definitions of tree assignment and ρ(H)) that states: every k-distinguishable tree assignment on H produces precisely ρ(H) edges. The short proof will record that each hyperedge e is replaced by a tree on its vertex set, which contributes exactly |e|−1 edges, and sum over all hyperedges. This makes the subsequent excess-obstruction argument self-contained. revision: yes

  2. Referee: [counterexample family] Counterexample family (abstract and § on counterexamples): the assertion that k+q copies of the full hyperedge V is k-weakly-partition-connected for every t,k,q relies on the claim that a single full hyperedge contributes its full span (r−1) to any r-part partition; an explicit verification of this cut condition for the multi-hyperedge case would confirm the connectivity hypothesis is not merely asserted.

    Authors: We accept the suggestion. Although the multi-copy case follows immediately from monotonicity of the cut function (adding identical full hyperedges cannot decrease connectivity), we will add a short explicit paragraph in the counterexample section. For an arbitrary r-partition of V we compute the total cut contribution of the k+q identical copies of the complete hyperedge and verify that it is at least k(r−1), thereby confirming k-weak partition connectivity directly from the definition. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation follows directly from definitions

full rationale

The paper derives its counterexample family from the explicit definitions of excess ρ(H) = ∑(|e|−1) and the requirement that a k-distinguishable tree assignment contributes exactly k(t−1) edges. Weak partition connectivity supplies only the inequality ρ(H) ≥ k(t−1), so any hypergraph with ρ(H) > k(t−1) (such as k+q copies of the complete hyperedge) is a counterexample by direct comparison. No parameters are fitted, no self-citation chain is load-bearing for the necessity argument, and the corrected equality condition is shown to match an independent matrix-rank characterization. The positive constructions rely on quotient-rank and star-block arguments that are independent of the disproof. The derivation is therefore self-contained against the paper's own stated definitions and external matrix conditions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The argument rests on the standard definition of k-weakly-partition-connected hypergraphs and the replacement rule that turns each hyperedge into a tree; no free parameters or invented entities are introduced.

axioms (2)
  • domain assumption A k-distinguishable tree assignment is formed by replacing every hyperedge e with a tree on its vertices, contributing exactly |e|-1 edges.
    Invoked in the paragraph explaining why ρ(H) must equal k(t-1).
  • domain assumption Weak partition connectivity implies only ρ(H) ≥ k(t-1).
    Standard property of the connectivity notion used throughout.

pith-pipeline@v0.9.0 · 5810 in / 1384 out tokens · 45246 ms · 2026-05-22T05:00:51.024873+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.