Zeros of Reliability Polynomials and f-vectors of Matroids
From MaRDI portal
Publication:4496439
Combinatorial aspects of matroids and geometric lattices (05B35) Connectivity (05C40) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Reliability, availability, maintenance, inspection in operations research (90B25)
Abstract: 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.
Recommendations
Cited in
(34)- Zero-free regions for multivariate tutte polynomials (alias Potts-model partition functions) of graphs and matroids
- The closure of the set of roots of strongly connected reliability polynomials is the entire complex plane
- On the log concavity of reliability and matroidal sequences
- Reliability polynomials and their asymptotic limits for families of graphs
- Homogeneous multivariate polynomials with the half-plane property
- On the stability of independence polynomials
- Polynomials with the half-plane property and the support theorems
- The k-fractal of a simplicial complex
- Non-Stanley bounds for network reliability
- Hurwitz matrices of doubly infinite series
- On the roots of domination polynomials
- Descent generating polynomials and the Hermite-Biehler theorem
- On the reliability roots of simplicial complexes and matroids
- On the roots of all-terminal reliability polynomials
- A note on the real part of complex chromatic roots
- Spanning forests and the \(q\)-state Potts model in the limit \(q \to 0\)
- On conjectures by Csordas, Charalambides and Waleffe
- Elements of Pólya-Schur theory in the finite difference setting
- On the roots of strongly connected reliability polynomials
- The distribution of zeros of a class of Jacobi polynomials
- Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs
- Graphs with a minimal number of convex sets
- Unimodality of independence polynomials of rooted products of graphs
- Broken circuit complexes of series-parallel networks
- Recurrences for Eulerian polynomials of type B and type D
- Acyclic polynomials of graphs
- A new property of a class of Koornwinder Laguerre polynomials
- Brenti's open problem on the real-rootedness of q-Eulerian polynomials of type D
- The s-Eulerian polynomials have only real roots
- The Brown-Colbourn conjecture on zeros of reliability polynomials is false
- Network reliability: Heading out on the highway
- Roots of two‐terminal reliability polynomials
- Rational roots of all‐terminal reliability
- The blowup-polynomial of a metric space: connections to stable polynomials, graphs and their distance spectra
This page was built for publication: Zeros of Reliability Polynomials and f-vectors of Matroids
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4496439)
