DIMACS TR: 93-27

Non-Stanley Bounds for Network Reliability



Authors: Jason I. Brown and Charles J. Colbourn

ABSTRACT

Suppose that each edge of a connected graph $G$ of order $n$ is independently operational with probability $p$; the {\em 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} \sum_{i=0}^{d} H_{i}(1-p)^{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.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-27.ps
DIMACS Home Page