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