Hypergraph Nash–Williams–Tutte conjecture in literal form
Hypergraph Nash–Williams–Tutte conjecture in literal form
A tree assignment of a hypergraph chooses, for each hyperedge occurrence , a tree on vertex set , with every edge of that tree labelled by . A -tree decomposition of the resulting labelled graph is an ordered partition of its edges into spanning trees. Such a graph is -distinguishable if it has a -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 -weakly-partition-connected when it satisfies the corresponding weak partition-connectivity condition, and write for its number of vertices.
Hypergraph Nash–Williams–Tutte conjecture. For positive integers and , every -weakly-partition-connected hypergraph on vertices has a -distinguishable tree assignment.
The paper states that this literal formulation is false: an excess obstruction shows that any -distinguishable tree assignment would require the equality , while weak partition connectivity permits hypergraphs with . 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
Sign in to submit a solution.
No solutions have been posted yet.