Hypergraph Nash–Williams–Tutte conjecture in literal form

From papers

A tree assignment of a hypergraph HH chooses, for each hyperedge occurrence ee, a tree on vertex set ee, with every edge of that tree labelled by ee. A kk-tree decomposition of the resulting labelled graph is an ordered partition of its edges into kk spanning trees. Such a graph is kk-distinguishable if it has a kk-tree decomposition uniquely determined by its signature, where the signature records, for each hyperedge occurrence, the weighted number of its assigned tree edges in each part. A hypergraph is kk-weakly-partition-connected when it satisfies the corresponding weak partition-connectivity condition, and write tt for its number of vertices.

Hypergraph Nash–Williams–Tutte conjecture. For positive integers tt and kk, every kk-weakly-partition-connected hypergraph HH on tt vertices has a kk-distinguishable tree assignment.

The paper states that this literal formulation is false: an excess obstruction shows that any kk-distinguishable tree assignment would require the equality ρ(H)=k(t1)\rho(H)=k(t-1), while weak partition connectivity permits hypergraphs with ρ(H)>k(t1)\rho(H)>k(t-1). Thus overfull weakly partition-connected hypergraphs provide counterexamples.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Yutong Zhang and Yaoran Yang, “Excess Obstructions and Star-Isolated Certificates for the Hypergraph Nash–Williams–Tutte Conjecture”, arXiv:2605.21961 (2026).

Additional references

2 papers in this index state this conjecture (2020–2026). The statement above is taken from the most recent of them; the others are arXiv:2011.04453.

Solutions 0

No solutions have been posted yet.