An Effective O((log n)/n) Bound for Complete-Graph Reliability Roots Near −1
Vasek Rozhon·Adrian Zámečník
Abstract
Let Rn(q) be the all-terminal reliability polynomial of the complete graph Kn, written in the edge-failure variable. We prove that, for every n ≥ 256 with n ≡ 0, 3 (mod 4), the polynomial Rn has a real zero qn satisfying −1 < qn < −n^(−2/n). Consequently, 0 < qn + 1 < 2 log n/n. More precisely, Rn(−n^(−2/n)) > 1/3 throughout this range and Rn(−n^(−2/n)) → 1. The endpoint sign is supplied by an exact sign theorem, while positivity at the moving point follows from Möbius inversion on the partition lattice and explicit estimates for partitions with and without a block larger than n/2. This gives an effective quantitative refinement of the known accumulation of complete-graph reliability roots at −1.Discussion
Sign in to join the discussion.