Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2605.21961 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918527603048448 |
|---|---|
| author | Zhang, Yutong Yang, Yaoran |
| author_facet | Zhang, Yutong Yang, Yaoran |
| contents | 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 $ρ(H)=\sum_e(|e|-1)$. A $k$-tree decomposition, however, has exactly $k(t-1)$ edges. Thus $ρ(H)=k(t-1)$ is a necessary condition, whereas weak partition connectivity only implies $ρ(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_21961 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Excess Obstructions and Star-Isolated Certificates for the Hypergraph Nash--Williams--Tutte Conjecture Zhang, Yutong Yang, Yaoran Combinatorics 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 $ρ(H)=\sum_e(|e|-1)$. A $k$-tree decomposition, however, has exactly $k(t-1)$ edges. Thus $ρ(H)=k(t-1)$ is a necessary condition, whereas weak partition connectivity only implies $ρ(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. |
| title | Excess Obstructions and Star-Isolated Certificates for the Hypergraph Nash--Williams--Tutte Conjecture |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2605.21961 |