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.
DIMACS Home Page