CS Paper Radar

Binary Belief Propagation Fixed Points: Finiteness, Rigidity, and Topological Complexity

Yusuke Watanabe

cs.IT math.AGmath.CO ·submitted 2026-11-09 00:18 UTC · v1
theorycode/data

Abstract

A fixed finite binary Ising model has only finitely many admissible complex belief propagation fixed points, even at degenerate parameter values. Families of positive fixed points obtained by varying external fields can nevertheless have nontrivial topology. We study this distinction through the external-field projection. For a fixed field, we prove finiteness by bounding the pole orders of the magnetizations on a hypothetical complex solution curve. The generic degree on the support graph then bounds the total local multiplicity. A graph has a single smooth real line as its full positive response for every choice of positive couplings, base field, and strictly positive sweep direction exactly when it contains no two vertex-disjoint connected subgraphs of cycle rank at least two. Two such subgraphs suffice to create a circular component. For a plane obtained by varying two vertex fields, connected simple bipartite cubic graphs with one uniform coupling and a universal bound on the fixed fields realize every genus. The minimum number of vertices grows logarithmically in the genus, by a matching algebraic upper bound on Betti numbers. Finally, we certify the complete field discriminant of an eighteen-vertex product model and recover its torus component's genus from the counts of distinct roots on all field cells. The three main theorems, including the logarithmic size bounds, are formally verified in Lean 4 with Mathlib.

Comment
37 pages, 3 figures. Lean 4 formalization and interval certificates at https://github.com/ywatanabex/bp-response-geometry-lean

Closest papers

Nearest neighbours by meaning across the whole index.

Counting the Fixed Points of Binary Belief Propagation: Generic Degree, Syzygies, and Real Solutions

cs.IT math.ACmath.AGmath.CO ·2026-10-27 ·Yusuke Watanabe
theorycode/data similarity 0.71
Abstract · 33 pages (main text and supplementary material SM1-SM6 in one PDF), 1 figure. Lean 4 formalization of the main results: https://github.com/y…

How many fixed points does belief propagation have on a binary pairwise model? Over complex parameters, the admissible equations of a finite loopless multigraph form an algebraic family whose generic degree we determine: it is a graph state sum over edge sets without vertices of degree one, each vertex of positive degree contributing one less than its degree. We give two geometric realizations of this state sum. The first is the total Betti number of a universal edge-incidence ring constructed without parameters. Its full graded Betti table is the state sum, its Tor algebra is natural for noncontracting graph maps, the alternating numerator recovers the graph polynomial of Watanabe and Fukumizu, and an Artin reduction by a regular sequence realizes the one-variable specialization, corrected for tree components. The second lies in the actual family: at the strong-field boundary each state factor is a ramification index, and at sufficiently strong field the state charts exhaust the admissible complex fiber. For fixed nonzero real couplings, every Eulerian message-sign sector contains a real fixed point at every external field, and strong fields attain this lower bound: one admissible real fixed point per element of the binary cycle space and one positive fixed point. For graphs of maximum degree at most three, this minimum equals the number of minimal module generators of the edge-incidence ring. One state decomposition connects the complex degree, graded syzygies, and an attained minimum real count. The degree, selected ring and resolution statements, and the real counts are formalized in Lean 4.

0.65

A Dichotomy for Planar Graph Homomorphisms with Nonnegative Weights

cs.CC ·2026-10-04 ·Chenghua Liu, Boning Meng
theorycode/data similarity 0.57
Abstract · 29 pages. Lean 4 formalization: https://github.com/liuchliuch/planar-homomorphisms-lean

We prove a complete complexity dichotomy for planar graph homomorphism counting with any fixed symmetric nonnegative matrix of arbitrary finite order, giving an explicit criterion for tractability. We also characterize exactly which fixed positive vertex weights preserve tractability, with both classifications extending from algebraic weights to fixed real weights in a prescribed exact representation. Our proof hinges on an entropy-based continuation argument: maximal logarithmic support identifies distance kernels as maximum-entropy completions, extending their positive definiteness throughout the parameter interval. This enables distance geometry to recover hidden product coordinates even when planar gadgets cannot distinguish colors; counting-hardness arguments then force the factors to be zero-field Boolean Ising interactions. The classification also yields complete tractability criteria for clock models, coupled Ising systems, and planar contractions of stoquastic imaginary-time kernels. All results have been formally verified in Lean 4.

0.39

Critical and near-critical influence bounds for ferromagnetic Ising models

cs.DS math-phmath.PR ·2026-09-15 ·Yan Ru Pei
theory similarity 0.53
Abstract · 6 pages

For a ferromagnetic Ising model on a graph of maximum degree $Δ\ge3$, we prove a bound of order $\sqrt n$ on every row of the influence matrix at the tree uniqueness threshold. The estimate is uniform in the degree, the external fields, and all pinnings. More generally, if the couplings are bounded by $β$ and $\varepsilon=((Δ-1)\tanhβ-1)_+$, the bound is $C(\sqrt n+n\varepsilon)$. The proof combines a pointwise cavity bound with a positive-series magnetization tilt and the field comparison theorem of Ding, Song and Sun. The critical estimate removes the logarithm in recent general graphical bounds for the ferromagnetic case. As a consequence, zero-field single-site Glauber dynamics mixes in polynomial time throughout the supercritical window $\varepsilon=O(\sqrt{\log n/n})$, with the polynomial degree depending on the window size.

0.18

Smallest Cubic Non-1-Planar Graphs

cs.CG math.COcs.DM ·2026-09-23 ·Sergey Pupyrev
similarity 0.53
Abstract

A graph is 1-planar if it has a drawing in which every edge is crossed at most once. We show that the smallest cubic non-1-planar graphs have $30$ vertices. Two such graphs are the Tutte-Coxeter graph of girth eight and a graph of girth seven that we call the Byte graph. Every subcubic graph with fewer than $30$ vertices is 1-planar. Our proof is computer-assisted, but directly testing all relevant graphs is impractical. To establish non-1-planarity of the two graphs, we extend a SAT-based solver with a custom clause propagator based on separating cycles and a case split based on graph automorphisms, allowing independent cases to be solved in parallel. To show that all smaller subcubic graphs are 1-planar, we introduce the concept of $k$-flexibility: every set of at most $k$ prescribed edges can remain uncrossed in some 1-planar drawing. We use this property to reconstruct 1-planar drawings of larger graphs from drawings of smaller $k$-flexible graphs. This replaces exhaustive testing of more than forty billion cubic graphs with computations on far fewer graphs of smaller order.

0.28

A Dichotomy for Cubic Bipartite Holant Problems with Complex Algebraic Weights

cs.CC ·2026-09-27 ·Yin Liu
similarity 0.52
Abstract · 87 pages. Supplementary polynomial certificates and verification code included. Corrected author metadata; manuscript unchanged

We classify the exact evaluation of $\operatorname{Holant}(f\mid=_3)$ for every fixed complex algebraic symmetric Boolean ternary signature $f$. An input is a cubic bipartite multigraph: every vertex on one side carries $f$, every vertex on the other side carries ternary equality, and no auxiliary signatures are freely available. The tractable signatures are precisely rank-one tensors, generalized equalities, and equality-preserving cube-root diagonal transformations of six affine signatures, together with nonzero scalings and reversal. Every other signature gives a $\#\mathrm{P}$-hard problem under polynomial-time Turing reductions. We also identify the exact real intersection: it consists of the same tractable families as in the rational classification, with real algebraic parameters. The proof preserves degree exactly three on both sides of every oracle instance. A rank-one matrix extracted by interpolation supplies one unary signature only after its unused factor has been absorbed in triples. Over the complex numbers this absorption has three exceptional projective directions. We combine this constraint with projective matrix-group orbits, explicit ternary replacements, and an exhaustive treatment of finite projective orders. The cases of orders three and five include exact polynomial certificates; the certificate identities and a rational-arithmetic verifier are supplied as supplementary material.

0.13

Coupling Independence Implies Zero-Freeness

cs.DS math-phmath.PR ·2026-10-08 ·Shuai Shao, Ke Shi
theory similarity 0.52
Abstract · 40 pages, 2 figures

For $Δ\ge2$ and $q\ge11Δ/6$, we prove that the antiferromagnetic $q$-state Potts partition function on finite simple graphs of maximum degree at most $Δ$ has no Fisher zeros in a graph-uniform complex neighbourhood of $[0,1]$. For $q>11Δ/6$, the proof establishes coupling independence throughout $[0,1]$ using a soft version of Vigoda's flip dynamics. Our main tool is a separator-shell transfer theorem for the Potts model on induced-subgraph closed classes of graphs of maximum degree at most $Δ$, with $q\geΔ+1$. It yields a graph-uniform zero-free neighbourhood of $[0,1]$ from Hamming coupling independence at $0$ and a uniform coupling-independence bound on each interval $[δ,1]$, $δ\in(0,1]$. We also obtain zero-free Lee-Yang polydiscs around the uniform field for vertex- and edge-colour fields. For Boolean Holant problems on bounded-degree graphs whose signatures come from a fixed finite family of log-concave symmetric signatures $f$ with $f(0)>0$, such as $b$-matchings, we obtain graph-uniform zero-free polytubes around every bounded box of nonnegative activities; their union is an open zero-free neighbourhood of the nonnegative orthant. An appendix summarizes further coupling-independence inputs and the zero-free regions they yield.

0.23

Kronecker Products, Polarity Quotients and Large Graph Constructions

cs.DM math.CO ·2026-08-27 ·Kelly Isham, Kartik Lakhotia, Laura Monroe, Fabrizio Petrini
theory similarity 0.52
Abstract · 24 pages, 4 figures, 3 tables Changes in v.2: Added an analysis of bipartite compatibility graphs. Complete documentation of the (19,3) and …

In this paper, we establish a structural compatibility between the Kronecker product of bipartite graphs that admit polarity and their polarity quotients, and provide a sharp upper bound on the diameter of these graphs. We use these properties to construct new families of graphs, all of which have orders that asymptotically approach the Moore bound. We show that the bipartite compatibility graphs have a natural polarity, and that the corresponding polarity quotients comprise a new family of graphs of any even diameter $2k$ with degree $(q+1)^k$ for any prime power $q$, much smaller than those of other known families of that diameter and field order $q$. These families generalize the Erdős-Rényi-Brown polarity graphs. Kronecker products of these polarity quotients give another new family of graphs of any even diameter for every pair of prime powers $q,r$. Certain generalized polygons are known to admit polarity with polarity quotients approaching the Moore bound asymptotically. Kronecker products of these polarity quotients give another new family of graphs of diameters $2$, $3$ and $5$, including a diameter-$3$ degree-$18$ graph of order larger than any previously known for that degree and diameter.

0.22

Riesz Energy Subset Selection in the Euclidean Plane is NP-Hard: A Reduction from the Ising Model on Planar Cubic Graphs

cs.CG cs.CCphysics.comp-ph ·2026-08-24 ·Michael Emmerich
theory similarity 0.52
Abstract · Keywords: Riesz energy, subset selection, NP-completeness, geometric optimization, planar cubic graphs, independent set, Ising model, comput…

We prove that minimum Riesz $s$-energy subset selection in the Euclidean plane is NP-complete already for the fixed exponent $s=2$. To our knowledge, this is the first Euclidean hardness result for exact Riesz-energy subset selection in which both the ambient dimension and the exponent are fixed. The reduction uses Barahona's planar cubic Ising model with uniform field. A spin is encoded by one diagonal of a four-point square. Axis-aligned selector chains implement ferromagnetic consistency, while a $45^\circ$ terminal geometry yields an antiferromagnetic source interaction. Rational diagonal perturbations realize the magnetic field, and all remaining interactions are dominated by polynomial separation. Because $s=2$ and all coordinates are rational, every constructed energy and the decision threshold are rational exactly.

0.44