HEXAGONbeta

Undecidability of Quiver Mutation Equivalence

A mix of human-written and AI-generated textHuman understanding: some partsmath.CO — Combinatoricscs.CC — Computational Complexity

Contributed by Qiyue Tang ↗

Version 1 / Nov 06, 2026 / CC BY 4.0

Abstract

We prove that quiver mutation equivalence up to relabeling is undecidable even for one fixed source quiver. We also prove strong NP-hardness.

Provenance statement

GPT-6-Pro was used to develop the proofs in a research session lasting approximately 4 hours and 14 minutes. Codex was used to audit the proofs and revise the exposition. A separate Rethlas-OSV review will be added once completed.

References

  1. I. Assem, M. Blais, T. Brüstle, and A. Samson, Mutation classes of skew-symmetric 3×33\times3-matrices , Comm. Algebra 36 (2008), 1209--1220. arXiv:math/0610627 (https://arxiv.org/abs/math/0610627).arXiv
  2. K. T. K. Armstrong-Williams, E. Hirst, B. Jackson, and K.-H. Lee, Mutation-acyclicity in rank four is decidable but not semialgebraic , arXiv:2610.36179v1 (https://arxiv.org/abs/2610.36179v1), 2026.arXiv
  3. S. Fomin, M. Shapiro, and D. Thurston, Cluster algebras and triangulated surfaces. Part I: Cluster complexes , Acta Math. 201 (2008), 83--146. arXiv:math/0608367 (https://arxiv.org/abs/math/0608367).arXiv
  4. A. Felikson, M. Shapiro, and P. Tumarkin, Skew-symmetric cluster algebras of finite mutation type , J. Eur. Math. Soc. 14 (2012), 1135--1180. doi:10.4171/JEMS/329 (https://doi.org/10.4171/JEMS/329).DOI
  5. S. Fomin, Quiver mutations , Open Problems in Algebraic Combinatorics (https://www.samuelfhopkins.com/OPAC/files/slides/fomin.pdf), University of Minnesota, Minneapolis, May 16, 2022.link
  6. S. Fomin, K. Igusa, and K. Lee, Universal quivers , Algebr. Comb. 4 (2021), 683--702. arXiv:2003.01244 (https://arxiv.org/abs/2003.01244).arXiv
  7. S. Fomin and S. Neville, Long mutation cycles , Selecta Math. (N.S.) 31 (2025), article 103. doi:10.1007/s00029-025-01090-1 (https://doi.org/10.1007/s00029-025-01090-1).DOI
  8. S. Fomin, L. Williams, and A. Zelevinsky, Introduction to Cluster Algebras , Chapters 1--3, arXiv:1608.05735v1 (https://arxiv.org/abs/1608.05735v1), 2016.arXiv
  9. S. Fomin, L. Williams, and A. Zelevinsky, Introduction to Cluster Algebras , Chapters 1--3, arXiv:1608.05735v5 (https://arxiv.org/abs/1608.05735v5), 2024.arXiv
  10. S. Fomin and A. Zelevinsky, Cluster algebras I: Foundations , J. Amer. Math. Soc. 15 (2002), 497--529. doi:10.1090/S0894-0347-01-00385-X (https://doi.org/10.1090/S0894-0347-01-00385-X).DOI
Show all 17 referencesShow fewer references
  1. S. Fomin and A. Zelevinsky, Cluster algebras II: Finite type classification , Invent. Math. 154 (2003), 63--121. arXiv:math/0208229 (https://arxiv.org/abs/math/0208229).arXiv
  2. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness , W. H. Freeman, San Francisco, 1979.
  3. G. Higman, Subgroups of finitely presented groups , Proc. Roy. Soc. London Ser. A 262 (1961), 455--475. doi:10.1098/rspa.1961.0132 (https://doi.org/10.1098/rspa.1961.0132).DOI
  4. J.-P. Serre, Trees , translated by J. Stillwell, Springer, Berlin, 1980.
  5. A. Seven, Mutation classes of skew-symmetrizable 3×33\times3 matrices , arXiv:1012.3318v2 (https://arxiv.org/abs/1012.3318v2), 2011.arXiv
  6. D. Soukup, Complexity of ice quiver mutation equivalence , Ann. Comb. 29 (2025), 91--100. doi:10.1007/s00026-023-00668-w (https://doi.org/10.1007/s00026-023-00668-w).DOI
  7. M. Warkentin, Exchange Graphs via Quiver Mutation , Ph.D. thesis, Technische Universität Chemnitz, 2014. Available from the German National Library (https://d-nb.info/1214302807/34).link

Version history

  1. v1 · 15 pagesSubmitted by Qiyue TangInitial depositCurrentNov 06, 2026