Excess Obstructions and Layer-Contained Certificates for the Hypergraph Nash--Williams--Tutte Conjecture

Abstract

Guo, Li, Shangguan, Tamo, and Wootters proposed a hypergraph analogue of the Nash--Williams--Tutte theorem, asserting that every $k$-weakly-partition-connected hypergraph admits a $k$-distinguishable tree assignment. We identify a sharp edge-count obstruction to the literal statement. A full tree assignment has $\rho (H)={\sum }_{e\in E(H)}(|e|-1)$ labelled graph edges, whereas an ordered decomposition into $k$ spanning trees has exactly $k(t-1)$ edges. Since weak partition connectivity implies only $\rho (H)\ge k(t-1)$, every strict inequality rules out a full decomposition. In particular, for all $t\ge 2$, $k\ge 1$, and $q\ge 1$, the hypergraph consisting of $k+q$ labelled copies of the full hyperedge is $k$-weakly-partition-connected but admits no $k$-distinguishable full tree assignment. We therefore isolate the critical regime $\rho (H)=k(t-1)$ and prove that every tree assignment of a critical $k$-weakly-partition-connected hypergraph admits a full ordered decomposition into $k$ spanning trees. Consequently, the critical conjecture reduces to the existence of some tree assignment having a decomposition whose signature fiber is a singleton. We establish this property for layer-contained certificates, without a star hypothesis or a rank restriction in interior layers. These certificates also imply weak partition connectivity by a quotient-rank argument and are stable under one-vertex sums. Finally, we derive a decomposition-indexed generalized-Laplace expansion for the relevant intersection-matrix minor, together with an exact formula for its collected monomial coefficients; we also give the required row-and-column perfect-shuffle normalization, identify criticality with the square full-assignment row count, and separate the critical conjecture from the additional overfull pruning problem.