The Brown-Colbourn conjecture on zeros of reliability polynomials is false (Q598476): Difference between revisions

In 1992, \textit{J. I. Brown} and the reviewer [``Roots of the reliability polynomial'', SIAM J. Discrete Math. 5, No. 4, 571--585 (1992; Zbl 0774.05046)] conjectured that the roots of the all-terminal reliability polynomial \(R(G;p)\) of a multigraph \(G\) all lie in the closed disc \(| p-1| \leq 1\). In 2001, \textit{A. D. Sokal} [``Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions'', Comb. Probab. Comput. 10, No. 1, 41--77 (2001; Zbl 0999.82022)] made the stronger conjecture that when each edge is permitted to have a different operation probability, the same conclusion about the roots holds (the authors call this the multivariate Brown-Colbourn conjecture). This paper first disproves the multivariate conjecture via a small counterexample, the complete graph on four vertices. Using this, the univariate conjecture is then disproved by providing a 4-vertex, 16-edge planar multigraph for which the Brown-Colbourn conjecture fails, and also a 1512-vertex, 3016-edge simple planar counterexample. Indeed the authors prove that the multivariate conjecture holds exactly when the multigraph is series-parallel.