Non-Stanley Bounds for Network Reliability
Jason I. Brown1
and Charles J. Colbourn2
1Dalhousie University Department of Mathematics, Statistics and Computing Science Halifax Canada
2University of Waterloo Department of Combinatorics and Optimization Waterloo Canada
2University of Waterloo Department of Combinatorics and Optimization Waterloo Canada
DOI: 10.1023/A:1022484229443
Abstract
Suppose that each edge of a connected graph G of order n is independently operational with probability p; the reliability of G is the probability that the operational edges form a spanning connected subgraph. A useful expansion of the reliability is as p n - 1 å i = 0 d H i ( 1 - p ) i p^{n - 1} \sum\nolimits_{i = 0}^d {H_i \left( {1 - p} \right)^i } , and the Ball-Provan method for bounding reliability relies on Stanley's combinatorial bounds for the H-vectors of shellable complexes. We prove some new bounds here for the H-vectors arising from graphs, and the results here shed light on the problem of characterizing the H-vectors of matroids.
Pages: 13–36
Keywords: network reliability; H-vector; shellable complex; matroid; graph polynomial
Full Text: PDF
References
1. M.O. Ball and J.S. Provan, "Bounds on the reliability polynomial for shellable independence systems," SIAM J. Alg. Disc. Meth. 3 (1982), 166-181.
2. L.J. Billera and C.W. Lee, "A proof of the sufficiency of McMullen's conditions for f-vectors of simplicial convex polytopes," J. Comb. Th. A 31 (1981), 237-255.
3. A. Bjorner, "Homology and Shellability," in Matroid Applications, N. White (Ed.), Cambridge University Press, Cambridge, 1992.
4. FT. Boesch, A. Satyanarayana, and C.L. Suffel, "Least reliable networks and the reliability domination," IEEE Trans. Comm. 38 (1990), 2004-2009.
5. J.I. Brown and C.J. Colbourn, "A set system polynomial with colouring and reliability applications," SIAM J. Disc. Math. 1 (1988), 151-157.
6. J.I. Brown and C.J. Colbourn, "On the log concavity of reliability and matroidal sequences," Adv. Appl. Math. 15(1994),114-127.
7. J.I. Brown and C.J. Colbourn, "Roots of the reliability polynomial," SIAM J. Disc. Math. 5 (1992), 571-585.
8. J.I. Brown, C.J. Colbourn, and J.S. Devitt, "Network transformations and bounding network reliability," Networks 23 (1993), 1-17.
9. C.J. Colbourn, The Combinatorics of Network Reliability, Oxford Univ. Press, New York, 1987.
10. C.J. Colbourn and W.R. Pulleyblank, "Matroid Steiner Problems, the Tutte polynomial and network reliability," J. Comb. Th. B 47 (1989), 20-31.
11. T. Hibi, "Face number inequalities for matroid complexes and Cohen-Macaulay types of Stanley-Reisner rings of distributive lattices," Pacific J. Math. 154 (1992), 253-264.
12. F.S. Macaulay, "Some properties of enumeration in the theory of modular systems," J. Land. Math. Soc. 26 (1927), 531-555.
13. R.P. Stanley, "Cohen-Macaulay complexes," in Higher Combinatorics, M. Aigner (Ed.), Reidel, 51-64,1977.
14. R.P. Stanley, Combinatorics and Commutative Algebra, Birkhauser, Boston, 1983.
15. W.T. Tutte, "A ring in graph theory," Proc. Cambridge Phil. Soc. 43 (1947), 26-40.
16. D.J.A. Welsh, Matroid Theory, Academic Press, London, 1976.
2. L.J. Billera and C.W. Lee, "A proof of the sufficiency of McMullen's conditions for f-vectors of simplicial convex polytopes," J. Comb. Th. A 31 (1981), 237-255.
3. A. Bjorner, "Homology and Shellability," in Matroid Applications, N. White (Ed.), Cambridge University Press, Cambridge, 1992.
4. FT. Boesch, A. Satyanarayana, and C.L. Suffel, "Least reliable networks and the reliability domination," IEEE Trans. Comm. 38 (1990), 2004-2009.
5. J.I. Brown and C.J. Colbourn, "A set system polynomial with colouring and reliability applications," SIAM J. Disc. Math. 1 (1988), 151-157.
6. J.I. Brown and C.J. Colbourn, "On the log concavity of reliability and matroidal sequences," Adv. Appl. Math. 15(1994),114-127.
7. J.I. Brown and C.J. Colbourn, "Roots of the reliability polynomial," SIAM J. Disc. Math. 5 (1992), 571-585.
8. J.I. Brown, C.J. Colbourn, and J.S. Devitt, "Network transformations and bounding network reliability," Networks 23 (1993), 1-17.
9. C.J. Colbourn, The Combinatorics of Network Reliability, Oxford Univ. Press, New York, 1987.
10. C.J. Colbourn and W.R. Pulleyblank, "Matroid Steiner Problems, the Tutte polynomial and network reliability," J. Comb. Th. B 47 (1989), 20-31.
11. T. Hibi, "Face number inequalities for matroid complexes and Cohen-Macaulay types of Stanley-Reisner rings of distributive lattices," Pacific J. Math. 154 (1992), 253-264.
12. F.S. Macaulay, "Some properties of enumeration in the theory of modular systems," J. Land. Math. Soc. 26 (1927), 531-555.
13. R.P. Stanley, "Cohen-Macaulay complexes," in Higher Combinatorics, M. Aigner (Ed.), Reidel, 51-64,1977.
14. R.P. Stanley, Combinatorics and Commutative Algebra, Birkhauser, Boston, 1983.
15. W.T. Tutte, "A ring in graph theory," Proc. Cambridge Phil. Soc. 43 (1947), 26-40.
16. D.J.A. Welsh, Matroid Theory, Academic Press, London, 1976.