Non-Stanley bounds for network reliability (Q1906250): Difference between revisions

Let \(G\) be a connected graph with \(n\) vertices and \(m\) edges. If each edge is independently operational with probability \(p\) then the reliability of \(G\) is the probability that the operational edges form a spanning connected subgraph. This amount can be written as \[ p^{n- 1} \sum^{m- n+ 1}_{i= 0} H_i(1- p)^i \] and the (nonnegative integer) coefficients \(H_i\) form the \(H\)-vector. The authors prove new bounds for \(H\)-vectors and the results ``shed light on the problem of characterizing the \(H\)-vectors of matroids''.