×

The Brown-Colbourn conjecture on zeros of reliability polynomials is false. (English) Zbl 1052.05038

In 1992, 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, 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.

MSC:

05C40 Connectivity
05C99 Graph theory
68M10 Network design and communication in computer systems
68M15 Reliability, testing and fault tolerance of networks and computer systems
68R10 Graph theory (including graph drawing) in computer science
82B20 Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics
90B15 Stochastic network models in operations research
90B18 Communication networks in operations research
90B25 Reliability, availability, maintenance, inspection in operations research
94C15 Applications of graph theory to circuits and networks

Software:

MPSolve; na20
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahlfors, L. V., Complex Analysis (1966), McGraw-Hill: McGraw-Hill New York · Zbl 0154.31904
[2] D.A. Bini, G. Fiorentino, Numerical computation of polynomial roots using MPSolve version 2.2 (January 2000), Software package and documentation available for download at; D.A. Bini, G. Fiorentino, Numerical computation of polynomial roots using MPSolve version 2.2 (January 2000), Software package and documentation available for download at
[3] Bini, D. A.; Fiorentino, G., Design, analysis and implementation of a multiprecision polynomial rootfinder, Numer. Algorithms, 23, 127-173 (2000) · Zbl 1018.65061
[4] A. Brandstädt, Le Van Bang, J.P. Spinrad, Graph Classes: A Survey, SIAM, Philadelphia, 1999.; A. Brandstädt, Le Van Bang, J.P. Spinrad, Graph Classes: A Survey, SIAM, Philadelphia, 1999. · Zbl 0919.05001
[5] Brown, J. I.; Colbourn, C. J., Roots of the reliability polynomial, SIAM J. Discrete Math., 5, 571-585 (1992) · Zbl 0774.05046
[6] Chang, S.-C; Shrock, R., Reliability polynomials and their asymptotic limits for families of graphs, J. Statist. Phys., 112, 1019-1077 (2003), cond-mat/0208538 at xxx.lanl.gov · Zbl 1118.82301
[7] Colbourn, C. J., The Combinatorics of Network Reliability (1987), Oxford University Press: Oxford University Press New York, Oxford
[8] Diestel, R., Graph Theory (1997), Springer: Springer New York
[9] Duffin, R. J., Topology of series-parallel graphs, J. Math. Anal. Appl., 10, 303-318 (1965) · Zbl 0128.37002
[10] Kirchhoff, G., Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme gefürht wird, Ann. Phys. Chem., 72, 497-508 (1847)
[11] Krantz, S. G., Function Theory of Several Complex Variables (1992), Wadsworth & Brooks/Cole: Wadsworth & Brooks/Cole Pacific Grove, California · Zbl 0776.32001
[12] Nerode, A.; Shank, H., An algebraic proof of Kirchhoff’s network theorem, Amer. Math. Monthly, 68, 244-247 (1961) · Zbl 0102.33902
[13] Oxley, J., Graphs and series-parallel networks, (White, N., Theory of Matroids (1986), Cambridge University Press: Cambridge University Press Cambridge), 97-126, (Chapter 6)
[14] Oxley, J. G., Matroid Theory (1992), Oxford University Press: Oxford University Press New York
[15] Simon, B., The \(P(ϕ)_2\) Euclidean (Quantum) Field Theory (1993), Princeton University Press: Princeton University Press Princeton
[16] Sokal, A. D., Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions, Combin. Probab. Comput., 10, 41-77 (2001), cond-mat/9904146 at xxx.lanl.gov. · Zbl 0999.82022
[17] Sokal, A. D., Chromatic roots are dense in the whole complex plane, Combin. Probab. Comput., 13, 221-261 (2004), cond-mat/0012369 at xxx.lanl.gov · Zbl 1100.05040
[18] Wagner, D. G., Zeros of reliability polynomials and \(f\)-vectors of matroids, Combin. Probab. Comput., 9, 167-190 (2000) · Zbl 0994.05085
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.