arXiv:2610.00828 · v2

Entrywise Logarithmic Matrix Algebra and Dichotomy of Planar Graph Homomorphisms

首次提交 2026-10-01 07:38

版本更新 2026-10-27 10:07

雷达观测 2026-10-29 00:35

摘要

We prove a complexity classification of counting planar graph homomorphisms with non-negative weights. For a real symmetric matrix $M$ with nonnegative entries, the problem $\GH(M)$ is either (1) P-time computable over all graphs, or (2) \#P-hard in general but P-time computable over planar graphs, or (3) \#P-hard over planar graphs. Furthermore, $\GH(M)$ in (2) consists of precisely those that involve the P-time FKT algorithm to count planar perfect matchings with a holographic transformation. The dichotomy for entrywise positive and full rank matrices lies at the core of the proof. In this setting, the main tool is a matrix algebra ${A}$ (a vector space with bilinear multiplication) formed by taking the real span of (centered) entrywise logarithms of all realizable matrices from $M$ using planar edge gadgets and polynomial interpolation. We then define a multiplicative homomorphism $F(\cdot)$ on the algebra ${A}$, which turns out to be a polynomial map. The exponents of prime factorization of component polynomials of $F$ induce graph distances for distance-regular graphs. These graphs are either the Hamming graphs or Doob graphs using a classification result for distance-regular graphs (if $\PlGH(M)$ is not \#P-hard), after obtaining their intersection numbers. The dichotomy is proved in either case. We then extend the complexity classification to all nonnegative matrices.

作者备注：93 pages, 6 figures