Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911153097015296 |
|---|---|
| author | Cai, Jin-Yi Young, Ben |
| author_facet | Cai, Jin-Yi Young, Ben |
| contents | Valiant's Holant theorem is a powerful tool for algorithms and reductions for counting problems. It states that if two sets $\mathcal{F}$ and $\mathcal{G}$ of tensors (a.k.a. constraint functions or signatures) are related by a \emph{holographic transformation}, then $\mathcal{F}$ and $\mathcal{G}$ are \emph{Holant-indistinguishable}, i.e., every tensor network using tensors from $\mathcal{F}$, resp. from $\mathcal{G}$, contracts to the same value. Xia (ICALP 2010) conjectured the converse of the Holant theorem, but a counterexample was found based on \emph{vanishing} signatures, those which are Holant-indistinguishable from 0.
We prove two near-converses of the Holant theorem using techniques from invariant theory. (I) Holant-indistinguishable $\mathcal{F}$ and $\mathcal{G}$ always admit two sequences of holographic transformations mapping them arbitrarily close to each other, i.e., their $\text{GL}_q$-orbit closures intersect. (II) We show that vanishing signatures are the only true obstacle to a converse of the Holant theorem. As corollaries of the two theorems we obtain the first characterization of homomorphism-indistinguishability over graphs of bounded degree, a long standing open problem, and show that two graphs with invertible adjacency matrices are isomorphic if and only if they are homomorphism-indistinguishable over graphs with maximum degree at most three. We also show that Holant-indistinguishability is complete for a complexity class \textbf{TOCI} introduced by Lysikov and Walter, and hence hard for graph isomorphism. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_10991 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem Cai, Jin-Yi Young, Ben Discrete Mathematics G.2.1 Valiant's Holant theorem is a powerful tool for algorithms and reductions for counting problems. It states that if two sets $\mathcal{F}$ and $\mathcal{G}$ of tensors (a.k.a. constraint functions or signatures) are related by a \emph{holographic transformation}, then $\mathcal{F}$ and $\mathcal{G}$ are \emph{Holant-indistinguishable}, i.e., every tensor network using tensors from $\mathcal{F}$, resp. from $\mathcal{G}$, contracts to the same value. Xia (ICALP 2010) conjectured the converse of the Holant theorem, but a counterexample was found based on \emph{vanishing} signatures, those which are Holant-indistinguishable from 0. We prove two near-converses of the Holant theorem using techniques from invariant theory. (I) Holant-indistinguishable $\mathcal{F}$ and $\mathcal{G}$ always admit two sequences of holographic transformations mapping them arbitrarily close to each other, i.e., their $\text{GL}_q$-orbit closures intersect. (II) We show that vanishing signatures are the only true obstacle to a converse of the Holant theorem. As corollaries of the two theorems we obtain the first characterization of homomorphism-indistinguishability over graphs of bounded degree, a long standing open problem, and show that two graphs with invertible adjacency matrices are isomorphic if and only if they are homomorphism-indistinguishable over graphs with maximum degree at most three. We also show that Holant-indistinguishability is complete for a complexity class \textbf{TOCI} introduced by Lysikov and Walter, and hence hard for graph isomorphism. |
| title | Vanishing Signatures, Orbit Closure, and the Converse of the Holant Theorem |
| topic | Discrete Mathematics G.2.1 |
| url | https://arxiv.org/abs/2509.10991 |