arxiv: 2604.07541 · v1 · submitted 2026-04-08 · 🧮 math.CO

Recognition: no theorem link

Density of reliability roots of simple graphs in the unit disk

Pjotr Buys

Authors on Pith no claims yet

Pith reviewed 2026-05-10 17:45 UTC · model grok-4.3

classification 🧮 math.CO

keywords reliability polynomialsimple graphscomplex rootsunit diskdensitycycle substitutioncomplete graphsBrown-McMullin conjecture

0 comments

The pith

The roots of reliability polynomials of connected simple graphs are dense in the unit disk.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves the simple-graph versions of two 1992 results on reliability polynomials: their complex roots are dense in the unit disk, and the closure of their real roots is the set from -1 to 0 together with the point 1. This extends the earlier theorems, which applied only to multigraphs, and thereby confirms a conjecture of Brown and McMullin. The argument constructs a two-parameter family of simple graphs by replacing each edge of a cycle with a complete graph and then uses the limiting behavior of the reliability polynomials of those complete graphs to force the roots to fill the disk.

Core claim

Brown and Colbourn showed that the complex roots of the reliability polynomial of connected multigraphs are dense in the unit disk and that the closure of the real roots is [-1,0] ∪ {1}. The present work establishes the identical statements when the graphs are required to be simple, by analyzing the substituted graphs C_m[K_n] and invoking the known asymptotics of the reliability and split-reliability polynomials of K_n as n grows.

What carries the argument

The family of substituted graphs C_m[K_n] in which every edge of the cycle C_m is replaced by a copy of the complete graph K_n, whose reliability polynomials are controlled by the asymptotic formulas for K_n.

If this is right

The density of complex roots in the unit disk holds for simple graphs.
The closure of the real roots is exactly [-1,0] ∪ {1} for simple graphs.
The conjecture of Brown and McMullin is confirmed.
Multiple edges are not required to produce dense roots inside the unit disk.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same substitution technique may be usable for other graph polynomials whose roots are already known to be dense for multigraphs.
Network reliability calculations can be restricted to simple graphs without losing the density property of the roots.
The result suggests that large cliques embedded in cycles are sufficient to generate arbitrary root locations inside the disk.

Load-bearing premise

The asymptotic behavior of the reliability and split reliability polynomials of the complete graph K_n as n tends to infinity controls the roots of the substituted cycle graphs C_m[K_n].

What would settle it

An open disk of positive radius lying strictly inside the unit disk that contains no roots of the reliability polynomial of any connected simple graph would falsify the density claim.

Figures

Figures reproduced from arXiv: 2604.07541 by Pjotr Buys.

**Figure 1.** Figure 1: Left: an example of the family of graphs𝐶𝑚 [𝐾 ∥𝑛 2 ] used in [BC92] to prove the density of reliability roots for multigraphs. Right: an example of the family 𝐶𝑚 [𝐾𝑛+1] used in this paper to prove the analogous result for simple graphs. 1.3. Formalization. The density of real reliability roots of simple graphs in [−1, 0] (Theorem 1.1, item 2) has been formally verified in the Lean 4 proof assistant. The fo… view at source ↗

**Figure 2.** Figure 2: The zeros of Rel(𝐾25; 𝑞) in the complex plane, together with the unit circle. Note that Lemma 2.1 implies that for any 𝜌 < 1, the closed disk of radius 𝜌 is zero-free for all sufficiently large 𝑛. A positive answer to Question 4.1 would therefore mean that the reliability roots of 𝐾𝑛 approach the unit circle as 𝑛 → ∞. Recall that the zero-counting measure of a polynomial 𝑝 of degree 𝑑 with zeros 𝑧1, . . . … view at source ↗

read the original abstract

Brown and Colbourn (1992) showed that the complex roots of the reliability polynomial of connected multigraphs are dense in the unit disk and that the closure of the real roots is $[-1,0] \cup \{1\}$. We prove the simple graph analogues of both results, confirming a recent conjecture of Brown and McMullin. The proof uses the family of graphs $C_m[K_n]$ obtained by substituting each edge of a cycle $C_m$ with a complete graph $K_n$, and relies on the asymptotic behavior of the reliability and split reliability polynomials of $K_n$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper proves the density of reliability roots for simple graphs in the unit disk via the C_m[K_n] construction, settling the Brown-McMullin conjecture.

read the letter

The main thing here is that the paper proves the roots of the reliability polynomial are dense in the unit disk for simple graphs, and that the closure of the real roots is [-1,0] union {1}. It directly confirms the conjecture of Brown and McMullin that was left open after the multigraph case was settled by Brown and Colbourn in 1992. The argument is built around the explicit family C_m[K_n], where each edge of a cycle is replaced by a complete graph K_n, then taking limits as both m and n grow using the known asymptotics of the reliability and split-reliability polynomials on K_n itself. That construction is the genuinely new piece; it keeps the graphs simple while still letting the roots fill the disk in the limit. The reduction is parameter-free and relies on external asymptotics rather than any fitting or post-hoc adjustment, which keeps the logic straightforward. The paper does a clean job of transferring the density result without adding extra machinery. The only soft spot worth noting is the dependence on the prior asymptotic results for K_n; if those asymptotics turn out to have any restrictions on how the roots approach the boundary for finite n, the density claim would need a bit more justification in the details, but nothing in the outline suggests a gap or circularity. The real-root part follows the same route and looks consistent. This is squarely for people who work on graph polynomials and reliability theory. A reader who already knows the multigraph density result will see exactly how the simple-graph case is handled and why the substitution works. It shows clear, direct engagement with the literature and the conjecture. I would send it to a serious referee because the claim is precise, the method is concrete, and the result closes a stated open question in the area.

Referee Report

0 major / 3 minor

Summary. The paper proves the simple-graph analogues of Brown and Colbourn's 1992 density theorems for reliability roots: the complex roots of reliability polynomials of connected simple graphs are dense in the unit disk, and the closure of the real roots is [-1,0] ∪ {1}. This confirms a conjecture of Brown and McMullin. The argument constructs the family of simple graphs C_m[K_n] (each edge of cycle C_m replaced by K_n) and passes to the limit m,n→∞ using the known asymptotic behavior of the reliability and split-reliability polynomials of K_n.

Significance. The result resolves an open conjecture by transferring the multigraph density statements to simple graphs via an explicit, parameter-free construction that relies only on previously established asymptotics for complete graphs. This strengthens the literature on the location of reliability roots and provides a concrete family of simple graphs whose roots become dense in the stated regions.

minor comments (3)

The notation C_m[K_n] for the edge-substitution construction is introduced in the abstract but should be defined explicitly with a diagram or formal definition in §2 or the introduction to aid readers unfamiliar with graph substitution.
The statement of the main theorem (presumably Theorem 1.1 or similar) should explicitly restate the two parts of the Brown-Colbourn result being extended, for clarity.
Ensure that all citations to the asymptotic results for the reliability polynomial of K_n include precise references to the prior literature establishing those asymptotics.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading and positive report, which accurately summarizes the results and recommends acceptance. We are pleased that the work is viewed as resolving the conjecture via the stated construction.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation constructs the family C_m[K_n] explicitly and passes to the limit using the asymptotic behavior of the reliability and split-reliability polynomials of K_n as n → ∞. This asymptotic is invoked from prior external literature (Brown and Colbourn 1992 and related results on complete graphs), not derived or fitted within the present paper. No equation reduces the target density statement to a self-defined quantity, a fitted parameter renamed as prediction, or a self-citation chain; the limiting argument is parameter-free and transfers the known multigraph density result to simple graphs without internal reduction. The confirmation of the Brown-McMullin conjecture therefore rests on an independent construction rather than circular re-use of the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on the standard definition of the reliability polynomial and on previously published asymptotic results for complete graphs; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (2)

standard math The reliability polynomial is well-defined for connected multigraphs and simple graphs via the standard edge-failure model.
Invoked implicitly when stating the roots of the polynomial.
domain assumption Asymptotic formulas for the reliability and split reliability polynomials of K_n hold as n grows.
Cited as the key tool for controlling roots of the substituted graphs C_m[K_n].

pith-pipeline@v0.9.0 · 5385 in / 1336 out tokens · 51607 ms · 2026-05-10T17:45:00.890775+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

3 extracted references · 3 canonical work pages · 1 internal anchor

[1]

[BPR25] Ferenc Bencs, Chiara Piombi, and Guus Regts

arXiv:2603.09059. [BPR25] Ferenc Bencs, Chiara Piombi, and Guus Regts. On the complex zeros and the computational complexity of approximating the reliability polynomial,

work page arXiv
[2]

[Col87] Charles J Colbourn.The Combinatorics of Network Reliability

arXiv:2512.11504. [Col87] Charles J Colbourn.The Combinatorics of Network Reliability. The International Series of Mono- graphs on Computer Science. Oxford University Press,

work page arXiv
[3]

Real Reliability Roots of Simple Graphs are Dense

arXiv:2604.03530. [RS04] Gordon Royle and Alan D Sokal. The Brown–Colbourn conjecture on zeros of reliability polyno- mials is false.Journal of Combinatorial Theory, Series B, 91(2):345–360,

work page internal anchor Pith review Pith/arXiv arXiv