Network Reliability, Simplicial Complexes, and Polynomial Roots

Abstract

Assume that the vertices of a graph G are always operational, but the edges of G fail independently with probability q ∈ [0, 1]. The all-terminal reliability of G is the probability that the resulting subgraph is connected. The all-terminal reliability is a polynomial in q, and it was conjectured that all the roots of (nonzero) reliability polynomials fall inside the closed unit disk centred at 0. It has since been shown that there exist some connected graphs which have their reliability roots outside the closed unit disk, but these examples seem to be few and far between, and the roots are only barely outside the disk. In this dissertation we generalize the notion of reliability to simplicial complexes and matroids and investigate when the roots fall inside the closed unit disk. We then shift our attention to discuss a related problem – among all reliability polynomials of graphs on n vertices, which has a root of smallest modulus (that is, the distance from the root to the origin in the complex plane). We also show a mathematical statement that distinguishes the class of simple graphs from the class of all graphs using all- terminal reliability. Finally, we explore two-terminal reliability — in particular, the similarities and differences between two-terminal reliability polynomials and the all-terminal reliability, with a focus on their roots.