network modelers

Abstract: We study antiferromagnetic spin systems on random regular graphs through the lens of the phase transitions characterized by the complex zeros of the partition function. Our motivating examples include the hardcore model and the antiferromagnetic Potts model (including proper $q$-colorings at $β=0$). For both models on random $d$-regular graphs, we establish, with high probability over the graph, zero-free regions throughout the interior of the replica-symmetric regime. Asymptotically, this regime extends up to tree occupation density $$α< α_{\mathrm{RSB}}(d) = (2\log d - 2\log\log d + 2 - 2\log 2 + o_d(1))/d$$ for the hardcore model and up to degree $$d < d_{\mathrm{RSB}}(q) = (2q-1)\log q - 2\log 2 + o_q(1)$$ for proper $q$-colorings. Leveraging the standard algorithmic implications of zero-freeness, we obtain deterministic polynomial-time algorithms that multiplicatively approximate the corresponding partition functions at fixed rational parameters throughout this regime, with high probability over the graph. Our algorithmic guarantees significantly improve upon prior work and extend beyond the parameter ranges reached by previously known search algorithms. To establish our results, we first develop reinforced small subgraph conditioning, which resolves short-cycle fluctuations in the complex plane by lifting classical small subgraph conditioning on random regular graphs to random holomorphic functions. Second, we overcome the standard second-moment barrier caused by the exponential blowup of the bare second moment inside the replica-symmetric phase, by showing that replica symmetry implies a nonpositive Bethe functional and upgrading planted overlap concentration to an exponentially small bound, which enables a typical-graph truncation that controls complex second moments up to the replica symmetry breaking threshold.

Abstract: A ring Petri net (weighted circuit, cyclic weighted T-system) consists of a single directed circuit with arbitrary positive arc weights. We show that deciding liveness of ring Petri nets is coNP-complete, and that coNP-hardness holds in the strong sense already for token-conserving rings, in which every transition consumes and produces the same number of tokens. The proof is a short reduction from the covering problem for systems of residue classes (the complement of Simultaneous Incongruences). Together with a known reduction to circuits, it follows that liveness of weighted T-systems (weighted marked graphs, synchronous dataflow graphs) is coNP-complete, and coNP-hard in the strong sense. As a further consequence, the halting problem for chip-firing on simple directed graphs is NP-complete, which answers a question of Farrell and Levine. On 7 October 2026, the problem of liveness was posed to the AI model Claude Opus 5.5 (Anthropic), which found the reduction, also suggesting the application to the chip-firing problem, and wrote a first version of this paper; the human authors checked it and, together with the model, revised it iteratively into the present form.

Abstract: We study the computational complexity of graph distortion distances, a family of graph metrics measuring how vertex distances differ between two graphs. Formally, these distances are defined in terms of standard matrix norms on the difference of distance matrices under an optimal vertex alignment. The resulting metrics have natural interpretations, corresponding to three ways of measuring the distortion of shortest-path distances: the maximum distortion among all vertex pairs (entrywise maximum norm), global aggregation (entrywise $p$-norms), and local aggregation (operator $p$-norms) of distortions. For maximum distortion, we show that approximation below a factor of two is NP-hard even for highly restricted trees. Due to the close connection to the Gromov-Hausdorff distance, we obtain a similar hardness result for the latter. In both cases, we show essentially optimal additive inapproximability. On the algorithmic side, we give a subcubic-time algorithm for optimal embeddings of connected graphs into paths, based on a structural decomposition along a diametral path. Additionally, we give a simple approximation algorithm when one input graph has a "relatively path-like" metric structure, i.e. has bounded pathlength. For local and global distortion, we derive various hardness results even for restricted inputs. Making use of a close connection between the global distortion distances and Gromov-Wasserstein distances, we give the first formal proof of NP-hardness of the latter, which has been claimed in the literature many times but has, to the best of our knowledge, never been correctly proven.

Abstract: In this paper, we investigate three fundamental convexity parameters of graphs under cycle convexity, namely the Helly number, Radon number, and rank. We first study the computational complexity of these parameters. For each of these parameters, we consider the associated threshold decision problem of determining whether the parameter of a given graph is at least a prescribed integer. We establish that all three problems are $\NP$-hard and $\W[1]$-hard when parameterized by the threshold. Moreover, we strengthen these results by showing that the $\NP$-hardness persists even when the input is restricted to planar graphs of maximum degree at most $6$. We also focus on the structural properties of connected graphs corresponding to extremal values of these parameters. In particular, we characterize the graph classes for which the three parameters attain the values $n-1$ and $n-2$, where $n$ is the order of $G$.

Abstract: The Pfaffian number of a graph is the minimum number of Pfaffians needed to obtain its perfect-matching polynomial by linear combination. In 2009, Norine conjectured that every Pfaffian number is a power of four. Miranda and Lucchesi disproved this conjecture in 2011 by constructing a graph of Pfaffian number six, and conjectured instead that every nontrivial Pfaffian number is even. We disprove their conjecture by proving that the Pfaffian number of $K_{3,3}\sqcup K_{3,3}$ is 13. We also construct a connected cubic bipartite matching-covered graph with Pfaffian number 13.

Abstract: AD-k stands for Alternating Differences through order k, and it is a property of set functions denoting that the first order difference of the set function is nonnegative (a.k.a. monotnocity), the second order difference is nonpositive (submodularity), and so on with signs alternating through order k. Chen et al. [1] conjectured that in an influence diffusion model called the general threshold model originally defined by Kempe et al. [2], if every local influence function is AD-k, then the global influence spread function is also AD-k, for any (possibly cyclic) directed graph and any k. This paper provides a complete proof showing that the conjecture is true. The proof utilizes Mobius inversion and decision tree partition method and extends the probability distribution of node triggering sets into a generalized algebraic structure allowing negative weights for triggering sets. The extension to negative-weighted triggering sets may be of independent interest.

Abstract: We construct a finite connected simple cubic graph $F$ such that every signing of its edges yields an adjacency matrix with an eigenvalue outside $[-2\sqrt2,2\sqrt2]$. This disproves the Bilu--Linial signing conjecture for general regular graphs. The proof is elementary, using a four-vertex calculation and a scalar recurrence.

Abstract: Network motifs and colored local interaction patterns provide a useful way to describe the structure of complex networks. Motivated by an inverse realization perspective, we study the problem of assigning colors to the vertices of a fixed graph so that its edges realize a prescribed multiset of colored pairwise interactions. This problem is formalized by the Matching-Match Puzzle, introduced by Iburi and Uehara. We investigate how its computational complexity depends on the number of colors and on the structure of the host graph. We first prove that Matching-Match is NP-complete with only two colors, even when no vertex is precolored and the graph has maximum degree three. We then focus on spiders. We show that the problem is W[1]-hard parameterized by the number of colors even on spiders with only the body precolored. In contrast, for spiders whose legs have length at most two, we give a fixed-parameter tractable algorithm parameterized by the number of colors, allowing arbitrary precoloring. Finally, we prove NP-completeness for spiders whose legs all have length exactly three when precoloring is allowed.

Abstract: At a 2021 AIM workshop, Guo conjectured that the positive square energy s+ = E+_2 should inherit the familiar edge-addition monotonicity of the spectral radius, rho(G + uv) >= rho(G). That conjecture was subsequently shown to fail at p = 2. Tang, Liu, and Wang then introduced positive p-energy, proved nonmonotonicity for every 1 <= p < 3, and in version 3 of their preprint (26 March 2025) explicitly conjectured that monotonicity should hold for p >= 3. We disprove this conjectured high-exponent extension completely: for every real p > 2 there are infinitely many connected graphs G and nonedges uv such that E+_p(G + uv) < E+_p(G). Together with the Tang-Liu-Wang counterexamples below 3, this shows that no exponent p >= 1 restores the spectral-radius-style monotonicity: positive p-energy can decrease under the addition of an edge for every real p >= 1. The construction is a chain of clique blocks joined by regular bipartite graphs. An equitable quotient converges to Q = I + cA(P_k). For noninteger p, a binomial-series sign argument for a fractional power of I - cA(P_k) gives the required negative endpoint entry. At integer exponents, choosing c across the first spectral threshold leaves exactly one negative eigenvalue, and path locality forces the positive spectral contribution to have negative sign. We also give a fully rational 38-vertex certificate at p = 4 and determine the complete failure interval of a fixed 17-vertex counterexample at p = 3.