Zeros of reliability polynomials and f-vectors of matroids
| dc.creator | Wagner, David G. | |
| dc.date | 1998-02-09 | |
| dc.date.accessioned | 2026-07-07T05:23:49Z | |
| dc.date.available | 2026-07-07T05:23:49Z | |
| dc.description | For a finite multigraph G, the reliability function of G is the probability R_G(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 R_G(q)=0 then |q|<=1. We verify that this conjectured property of R_G(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. | |
| dc.description | 21 pages | |
| dc.identifier | https://arxiv.org/abs/math/9802047 | |
| dc.identifier | http://arxiv.org/abs/math/9802047 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/76591 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C99 (Primary) 26C10, 95C15, 06A08 (Secondary) | |
| dc.title | Zeros of reliability polynomials and f-vectors of matroids | |
| dc.type | text |