1 Problem, notation, and main results↩︎

The starting point of this note is the following conjecture from the Reed–Solomon list-decoding work of Guo, Li, Shangguan, Tamo, and Wootters [1]. It was introduced as a hypergraph version of the Nash–Williams–Tutte tree-packing theorem [2], [3] and is naturally adjacent to partition-connected hypergraph decomposition [4]; in the Reed–Solomon application it is a possible route to the nonsingularity of intersection matrices. We use the exact terminology needed in Section 6 of [1], but we restate the definitions in a form that keeps the edge-count parameter visible.

Let \(H=(V,E)\) be a finite labelled multihypergraph. Hyperedges are occurrences, not merely subsets; thus two equal subsets of \(V\) may carry two different labels. Throughout the paper every hyperedge occurrence has cardinality at least two. This is the convention under which tree assignments are defined; the support hypergraphs in Section 3 likewise discard supports of size less than two. We write \(t=|V|\) and assume throughout that \(t\ge2\) unless explicitly stated. For a partition \(\mathcal{P}\) of \(V\) and a hyperedge \(e\in E\), put \[\label{eq:pP} p_{\mathcal{P}}(e) \mathrel{:=}\left|\{P\in\mathcal{P}: P\cap e\ne\varnothing\}\right|.\tag{1}\] The weak partition excess of \(H\) across \(\mathcal{P}\) is \[\label{eq:weakcross} w_H(\mathcal{P}) \mathrel{:=}\sum_{e\in E}\bigl(p_{\mathcal{P}}(e)-1\bigr).\tag{2}\] The hypergraph \(H\) is \(k\)-weakly-partition-connected if \[\label{eq:kwpc} w_H(\mathcal{P}) \ge k\bigl(|\mathcal{P}|-1\bigr) \qquad\text{for every partition }\mathcal{P}\text{ of }V.\tag{3}\] For the discrete partition \(\mathcal{P}_0=\{\{v\}:v\in V\}\), the left hand side is the total excess \[\label{eq:rho-def} \rho(H) \mathrel{:=}w_H(\mathcal{P}_0) =\sum_{e\in E}\bigl(|e|-1\bigr).\tag{4}\] Thus every \(k\)-weakly-partition-connected hypergraph satisfies \[\label{eq:wpc-implies-excess} \rho(H)=w_H(\mathcal{P}_0)\ge k(t-1).\tag{5}\] The inequality 5 is the source of the obstruction below: it is a lower bound, while a \(k\)-tree decomposition demands exact equality.

A tree assignment of \(H\) chooses, for each hyperedge occurrence \(e\), a tree \(F_e\) on vertex set \(e\), and labels every edge of \(F_e\) by \(e\). The resulting labelled graph on the ambient vertex set \(V\) is \[\label{eq:tree-assignment} G=\biguplus_{e\in E}F_e, \qquad |E(G)|=\sum_{e\in E}|E(F_e)|=\rho(H).\tag{6}\] A \(k\)-tree decomposition of a labelled graph \(G\) on \(V\) is an ordered partition \[\label{eq:ktree-decomp} E(G)=E(T_0)\,\dot{\cup}\,E(T_1)\,\dot{\cup}\cdots\dot{\cup}\,E(T_{k-1}),\tag{7}\] where each \(T_i\) is a spanning tree of \(V\). Necessarily \[\label{eq:kdecomp-count} |E(G)|=\sum_{i=0}^{k-1}|E(T_i)|=k(t-1).\tag{8}\] If \(G\) is a tree assignment of \(H\) and \(\mathcal{T}=(T_0,\ldots,T_{k-1})\) is a \(k\)-tree decomposition of \(G\), its signature is the vector \[\label{eq:signature} \operatorname{sig}_{\mathcal{T}}(e) \mathrel{:=}\sum_{i=0}^{k-1} i\,\left|E(T_i)\cap E(F_e)\right| \qquad(e\in E).\tag{9}\] The graph \(G\) is \(k\)-distinguishable if it admits a \(k\)-tree decomposition \(\mathcal{T}\) such that every \(k\)-tree decomposition \(\mathcal{T}'\) with \(\operatorname{sig}_{\mathcal{T}'}=\operatorname{sig}_{\mathcal{T}}\) satisfies \(\mathcal{T}'=\mathcal{T}\) as an ordered tuple.

The conjecture is a precise mathematical proposition, not an existentially vague question. The main point of this paper is that Conjecture [conj:literal] is incompatible with the equality forced by 8 . This gives a decisive negative resolution of the literal statement.

The obstruction is sharp: weak partition connectivity always gives \(\rho(H)\ge k(t-1)\) by 5 , so 1 says that the only possible failure of the edge-count test inside the weakly connected class is overfullness.

The natural repair is to add the missing critical-excess equality.

The equality 10 is not an artificial addition. It is the equality appearing in the intersection-matrix conjecture of Shangguan–Tamo [5], and it is exactly what is needed when a full tree assignment is used as the labelled-edge row set of size \(k(t-1)\). Section 3 records this in a form that separates the partition-connectivity calculation from the square-determinant requirement.

We shall call a hypergraph \(H\) on vertex set \(V\) \(k\)-critical if \[\label{eq:k-critical-def} \rho(H)=k(|V|-1).\tag{11}\] This is a purely numerical convention; weak partition connectivity is always stated separately.

Our second contribution is a positive theorem for an explicit infinite non-graphic part of Conjecture [conj:critical]. The theorem is not a proof of the full critical conjecture; rather, it gives an explicitly checkable class where weak partition connectivity follows from a layer-wise quotient-rank argument and uniqueness is forced by an extremal signature mechanism. The class includes full hyperedges of arbitrary rank and is closed under one-vertex sums.

Let \(S_e(c)\) denote the star on a hyperedge \(e\) centered at \(c\in e\): \[\label{eq:star} E(S_e(c))=\bigl\{\{c,u\}:u\in e\setminus\{c\}\bigr\}.\tag{12}\] A tree assignment is star-minimal if every hyperedge of size at least \(3\) is assigned such a star and every hyperedge of size \(2\) is assigned its unique edge.

The next theorem shows that the construction is stable under the main gluing operation for tree packings.

The obstruction, the critical repair, and the positive mechanism fit into the following diagram.

2 The edge-excess obstruction↩︎

This section proves [thm:excess-obstruction,thm:full-edge-counterexamples]. The argument is short, but spelling it out is useful because it identifies the exact point where the literal conjecture and the determinant argument diverge.

3 Critical normalization and the intersection-matrix route↩︎

This section records the exact relation between the missing equality and the Reed–Solomon application through intersection matrices. The equality is not needed merely to derive weak partition connectivity from the weight inequalities; it is needed to make the full tree-assignment row set square and compatible with a \(k\)-tree decomposition on exactly \(k(t-1)\) labelled edges.

Let \(I_1,\ldots,I_t\subseteq[n]\). For \(s\in[n]\) define the support hyperedge \[\label{eq:support-edge} e_s\mathrel{:=}\{j\in[t]:s\in I_j\}.\tag{20}\] The associated labelled multihypergraph has edge-occurrence set \[\label{eq:intersection-H} E_I\mathrel{:=}\{\varepsilon_s=(s,e_s):s\in[n],\;|e_s|\ge2\}, \qquad H(I_1,\ldots,I_t)=([t],E_I).\tag{21}\] We write the occurrence \(\varepsilon_s\) simply as \(e_s\) when no confusion can arise; the label \(s\) is part of the occurrence, so equal supports with different labels are distinct. The standard weight of a subfamily is \[\label{eq:wt-def} \operatorname{wt}(I_J) =\sum_{s=1}^n\max\bigl(0,|e_s\cap J|-1\bigr) =\sum_{j\in J}|I_j|-\left|\bigcup_{j\in J}I_j\right|.\tag{22}\] For \(J=[t]\), 22 gives \[\label{eq:wt-rho} \operatorname{wt}(I_{[t]}) =\sum_{s=1}^n\max(0,|e_s|-1) =\sum_{e\in E(H)}(|e|-1) =\rho(H).\tag{23}\] Thus the equality condition in the intersection-matrix conjecture, \[\label{eq:intersection-critical} \operatorname{wt}(I_{[t]})=k(t-1),\tag{24}\] is exactly the critical equality 10 .

4 Star-realized assignments and partition slack↩︎

We now prove the positive mechanism in 3. A star does not realize the hyperedge cut value for every partition; in general it has extra crossing edges. The point of a two-sided star certificate is different: every hyperedge label is contained in a single tree layer. This layer containment implies weak partition connectivity by a quotient-rank argument, while the extremal layers force signature uniqueness.

For a graph \(G\) on \(V\) and a partition \(\mathcal{P}\) of \(V\), let \[\label{eq:cross-def} \operatorname{cr}_G(\mathcal{P})=|\{xy\in E(G):x\text{ and }y\text{ lie in distinct blocks of }\mathcal{P}\}|.\tag{30}\] If \(F_e\) is a tree on \(e\), then the quotient of \(F_e\) by the blocks met by \(e\) is connected after loops are deleted, and hence \[\label{eq:tree-cross-lower} \operatorname{cr}_{F_e}(\mathcal{P})\ge p_\mathcal{P}(e)-1.\tag{31}\] For arbitrary trees this inequality can be strict. For stars the strictness is completely explicit.

The formula shows that a general proof of the critical conjecture cannot proceed by assigning each hyperedge a fixed star and then replacing every hypergraph cut by the corresponding graph cut. The following definition records the stronger property that such an argument would need.

A single hyperedge of size at least \(3\) cannot be partition-tight for every partition: for any tree on at least three vertices, a bipartition obtained by separating a nonempty proper vertex set whose boundary in the tree has size at least two gives at least two crossing tree edges, while the corresponding hyperedge contribution is only one. The certificates below therefore do not rely on partition-tightness.

The next definition gives a concrete supply of certified non-graphic blocks.

5 One-vertex sums and explicit certified families↩︎

We prove the closure theorem. The operation is standard for tree packings and is particularly clean for ordered decompositions.

Let \(H^{(1)}\) and \(H^{(2)}\) have vertex sets \(V_1,V_2\) with \(V_1\cap V_2=\{r\}\). Their one-vertex sum has vertex set \(V=V_1\cup V_2\) and edge multiset the disjoint union of edge occurrences. If \(t_a=|V_a|\), then \[\label{eq:one-sum-size} |V|=t_1+t_2-1.\tag{46}\]

The closure theorem gives infinite non-graphic examples because a single block may contain hyperedges of arbitrary size in the two extremal layers. Figure 3 illustrates one step of the construction.

6 Signature isolation as a labelled matroid statement↩︎

This section rewrites the uniqueness argument in the language of bases of the graphic matroid. The reformulation is useful because it separates two issues that are conflated in the literal conjecture: existence of a packing and uniqueness of the label signature.

Let \(M(G)\) be the graphic matroid of a graph \(G\) on \(V\). A spanning tree is a basis of \(M(G)\). A \(k\)-tree decomposition is an ordered basis partition \[\label{eq:matroid-basis-partition} E(G)=B_0\dot{\cup}\cdots\dot{\cup} B_{k-1}, \qquad B_i\in\mathcal{B}(M(G)).\tag{49}\] The signature map is the linear projection \[\label{eq:linear-sig} \Phi:\mathbb{Z}^{E(G)}\times\cdots\times\mathbb{Z}^{E(G)}\longrightarrow\mathbb{Z}^{E(H)}, \qquad \Phi(\mathbf{1}_{B_0},\ldots,\mathbf{1}_{B_{k-1}})_e =\sum_{i=0}^{k-1}i\,|B_i\cap E(F_e)|.\tag{50}\] Thus distinguishability asks for a fiber of \(\Phi\) over the set of ordered basis partitions to be a singleton.

For a fixed label \(e\), let \[\label{eq:label-multiplicity} n_e\mathrel{:=}|E(F_e)|=|e|-1, \qquad a_i(e)\mathrel{:=}|B_i\cap E(F_e)|.\tag{51}\] Then every decomposition satisfies \[\label{eq:a-constraints} a_i(e)\in\mathbb{Z}_{\ge0},\qquad \sum_{i=0}^{k-1}a_i(e)=n_e, \qquad \operatorname{sig}(e)=\sum_{i=0}^{k-1}i a_i(e).\tag{52}\] For the extremal layers \(0\) and \(k-1\), the signature determines the whole vector \((a_0(e),\ldots,a_{k-1}(e))\) when the target average is extremal: \[\begin{align} \operatorname{sig}(e)=0 &\Longleftrightarrow (a_0(e),a_1(e),\ldots,a_{k-1}(e))=(n_e,0,\ldots,0),\tag{53}\\ \operatorname{sig}(e)=(k-1)n_e &\Longleftrightarrow (a_0(e),a_1(e),\ldots,a_{k-1}(e))=(0,\ldots,0,n_e). \tag{54} \end{align}\] This is the algebraic core of 3. When \(k=1\) the two displayed extremal conditions coincide and are tautological.

For an interior layer \(c\), the real affine fiber is usually positive-dimensional, and even its integer points need not be unique. The affine fiber is \[\label{eq:interior-fiber} \mathcal{A}_{c,n} =\left\{a\in\mathbb{R}_{\ge0}^k: \sum_i a_i=n, \sum_i i a_i=cn\right\}.\tag{55}\] For \(1\le c\le k-2\) and \(n\ge2\), this polytope contains the nontrivial point \[\label{eq:interior-point} a_c=n-2, \qquad a_{c-1}=a_{c+1}=1, \qquad a_i=0\text{ otherwise},\tag{56}\] so the signature alone cannot force all \(e\)-labelled edges into \(B_c\). This explains why the conjecture is substantially harder than ordinary tree packing: uniqueness is not a matroid-union consequence but a labelled fiber-isolation problem.

7 Critical examples and explicit calculations↩︎

We give three families to clarify the boundary between the negative theorem and the star-isolated positive theorem.

The last example is small but representative: high-rank labels can be made harmless when they sit in an extremal layer and the remaining cut inequalities are supplied by rank-two labels. One-vertex sums of this block yield arbitrarily large examples with high-rank labels.

8 Exact slack calculus and finite verification↩︎

Although the proof of 3 uses quotient rank rather than direct cut counting, it is useful to record the exact slack identity behind any fixed tree assignment and tree decomposition. This identity explains why stars may have extra graph-crossing edges without contradicting weak partition connectivity.

Let \(F=(F_e)_{e\in E(H)}\) be any tree assignment, and put \[\label{eq:global-lambda-def} \Lambda_F(\mathcal{P}) =\sum_{e\in E(H)}\left(\operatorname{cr}_{F_e}(\mathcal{P})-p_\mathcal{P}(e)+1\right)\ge0 .\tag{59}\] If \(G=\biguplus_eF_e\) is decomposed as \(G=T_0\dot{\cup}\cdots\dot{\cup} T_{k-1}\), define the graphical partition surplus \[\label{eq:graphical-surplus-def} B_{\mathcal{T}}(\mathcal{P}) =\sum_{i=0}^{k-1}\operatorname{cr}_{T_i}(\mathcal{P})-k(|\mathcal{P}|-1)\ge0 .\tag{60}\] The nonnegativity in 60 is the ordinary tree crossing inequality applied to each spanning tree \(T_i\).

If the assignment is star-realized with centers \(c(e)\in e\), Lemma 6 turns 59 into a closed expression: \[\label{eq:star-global-lambda} \Lambda_F(\mathcal{P})= \sum_{e\in E(H)}\lambda_{e,c(e)}(\mathcal{P}) =\sum_{e\in E(H)}\sum_{P\in\mathcal{P}\setminus\{P_{c(e)}\}} \max(0,|P\cap e|-1).\tag{64}\] Thus, for a fixed star assignment and fixed decomposition, weak partition connectivity is equivalent to the finite system \[\label{eq:finite-system} \sum_{e\in E(H)}\sum_{P\in\mathcal{P}\setminus\{P_{c(e)}\}} \max(0,|P\cap e|-1) \le \sum_{i=0}^{k-1}\operatorname{cr}_{T_i}(\mathcal{P})-k(|\mathcal{P}|-1) \qquad(\mathcal{P}\in\Pi(V)),\tag{65}\] where \(\Pi(V)\) denotes the set of all set partitions of \(V\). For a two-sided star certificate this system holds automatically by 3; the quotient-rank proof is a shorter certificate of the same inequalities.

The identity also isolates the role of the discrete partition. If \(\mathcal{P}_0=\{\{v\}:v\in V\}\), then every tree edge crosses \(\mathcal{P}_0\), and hence \[\label{eq:discrete-no-slack} \Lambda_F(\mathcal{P}_0)= \sum_e\left(|E(F_e)|-(|e|-1)\right)=0.\tag{66}\] Therefore the discrete partition cannot absorb any overfullness by changing the tree assignment. It only sees \[\label{eq:discrete-gap} w_H(\mathcal{P}_0)-k(|\mathcal{P}_0|-1)=\rho(H)-k(t-1).\tag{67}\] This is the numerical obstruction in 1 in its most rigid form.

The smallest counterexamples are completely classified. This is useful because it shows that the obstruction persists even when no high-rank hyperedge is present.

For arbitrary fixed assignments, the slack identity separates two tasks: \[\label{eq:two-independent-tasks} \boxed{\text{signature isolation}} \qquad\text{and}\qquad \boxed{\Lambda_F(\mathcal{P})\le B_\mathcal{T}(\mathcal{P})\text{ for all }\mathcal{P}}.\tag{74}\] The two-sided certificate class handles them simultaneously: extremal signature weights isolate the labels, and the quotient-rank argument proves the partition inequalities. The literal conjecture fails before either task is relevant, because an overfull assignment has too many labelled graph edges to be a union of exactly \(k\) spanning trees.

9 Consequences for formulations of the conjecture↩︎

The negative theorem suggests three logically distinct statements.

1. Literal full-assignment statement. \[\label{eq:form-A} \begin{align} &k\text{-WPC}(H)\\ &\qquad\Longrightarrow \exists\text{ a }k\text{-distinguishable full tree assignment of }H. \end{align}\tag{75}\] This is false by 2.

2. Critical full-assignment statement. \[\label{eq:form-B} \begin{align} &k\text{-WPC}(H)\text{ and }\rho(H)=k(t-1)\\ &\qquad\Longrightarrow \exists\text{ a }k\text{-distinguishable full tree assignment of }H. \end{align}\tag{76}\] This is Conjecture [conj:critical]. It is not settled here in full generality, but it is the exact form compatible with the intersection-matrix application and with edge counting.

3. Subassignment or row-pruning statement. \[\label{eq:form-C} \begin{align} k\text{-WPC}(H) \Longrightarrow{}& \exists\text{ a tree assignment }G\text{ of }H\\ &\text{and a labelled spanning subgraph }G'\subseteq G \end{align}\tag{77}\] with \(|E(G')|=k(t-1)\) such that \(G'\) has a signature-isolated \(k\)-tree decomposition, where the signature is computed from the label classes inherited by \(G'\). This avoids the overfull obstruction but adds a nontrivial pruning problem. The logarithmic relaxation in [6], [7] can be interpreted in this direction, but it does not imply the exact row-pruning statement.

The implications are \[\label{eq:form-implications} \text{(A)}\Longrightarrow\text{(B)}, \qquad \text{(C)}\Longrightarrow\text{a corrected overfull version},\tag{78}\] while 1 says that (A) is impossible. The formulation of (C) must allow pruning at the level of labelled graph rows or assigned edges, not only at the level of deleting whole hyperedge occurrences. Whole-hyperedge pruning has a separate arithmetic obstruction: for example, on \(V=\{1,2,3,4\}\) with \(k=1\), the two hyperedges \(\{1,2,3\}\) and \(\{1,2,4\}\) form a \(1\)-weakly-partition-connected hypergraph of excess \(4\), but no subhypergraph has excess \(3=k(|V|-1)\). Indeed, for any partition \(\mathcal{P}\) with \(s\) blocks, the two hyperedges cover \(V\) and intersect nontrivially, so their block-incidence counts satisfy \(p_\mathcal{P}(e_1)+p_\mathcal{P}(e_2)\ge s+1\), giving \(w_H(\mathcal{P})\ge s-1\).

From the viewpoint of Reed–Solomon codes, (B) is the appropriate full-assignment conjecture because the labelled-edge row set from a full tree assignment has exactly the required square size precisely when 24 holds.

10 Conclusion↩︎

The literal hypergraph Nash–Williams–Tutte conjecture has a decisive edge-count obstruction. Weak partition connectivity says \[\label{eq:conclusion1} \rho(H)\ge k(t-1),\tag{79}\] whereas a full \(k\)-distinguishable tree assignment requires \[\label{eq:conclusion2} \rho(H)=k(t-1).\tag{80}\] The family \(H_{t,k,q}\) with \(k+q\) copies of the full hyperedge gives counterexamples for every \(t\ge2\), \(k\ge1\), and \(q\ge1\). Thus the original statement must be replaced by either a critical equality hypothesis or by an explicit subassignment/row-pruning conclusion.

The critical form remains the mathematically meaningful version for the Reed–Solomon route through intersection matrices: the equality \(\operatorname{wt}(I_{[t]})=k(t-1)\) is exactly \(\rho(H)=k(t-1)\), and it is precisely the condition under which the full tree-assignment row set has the square size required by the determinant block without row pruning. Within the critical regime, the main structural problem is not merely the existence of spanning-tree packings but the isolation of a label signature. The two-sided star certificates in this paper provide an explicit infinite non-graphic family where weak partition connectivity follows from quotient rank, signature isolation is forced by extremal weights, and the construction remains stable under one-vertex sums.

The next natural target is an exact row-pruning problem: \[\label{eq:pruning-target} \begin{align} &k\text{-WPC}(H),\;\rho(H)>k(t-1)\\ &\qquad\Longrightarrow?\quad \exists\text{ a }k(t-1)\text{-edge labelled subgraph of a tree assignment}\\ &\qquad\text{with isolated signature.} \end{align}\tag{81}\] This pruning statement is independent of signature uniqueness for the critical full-assignment conjecture, and separating the two problems should make future work on the hypergraph Nash–Williams–Tutte program more precise.

Declaration of Generative AI and AI-Assisted Technologies in the Writing Process↩︎

During the preparation of this work, the authors used DeepSeek to build a specialized agent for solving mathematical problems, which was employed to generate an initial proof of the main theorem. After using this tool, the authors reviewed and edited the content as needed and take full responsibility for the content of the published article.

References↩︎