Zeros of reliability polynomials and f-vectors of matroids

Original · EN

For a finite multigraph G, the reliability function of G is the probability RG(q) that if each edge of G is deleted independantly with probability q then the remaining edges of G induce a connected spanning subgraph of G; this is a polynomial function of q. In 1992, Brown and Colbourn conjectured that for any connected multigraph G, if the complex number q is such that RG(q)=0 then |q|<=1. We verify that this conjectured property of RG(q) holds if G is a series-parallel network. The proof is by an application of the Hermite-Biehler Theorem and development of a theory of higher-order interlacing for polynomials with only real nonpositive zeros. We conclude by establishing some new inequalities which are satisfied by the f-vector of any matroid without coloops, and by discussing some stronger inequalities which would follow (in the cographic case) from the Brown-Colbourn Conjecture, and are hence true for cographic matroids of series-parallel networks.