# Graver, Jack E.; matematični kolokvij junij 2005

## You may rely on the reliability polynomial for much more than you might think

Jack E. Graver

Syracuse University, ZDA

23. junij 2005

The reliability polynomial $R_{\mathcal S}(p)$ of a collection $\mathcal S$ of subsets of a finite set X has been extensively studied in the context of network theory. There, X is the edge set of a graph (V,X) and $\mathcal S$ the collection of the edge sets of certain subgraphs. For example, we may take $\mathcal S$ to be the collection of edge sets of spanning trees. In that case, $R_{\mathcal S}(p)$ is the probability that, when each edge is included with the probability p, the resulting subgraph is connected. Milton Sobel defined $R_{\mathcal S}(p)$ in an entirely different way enabling one to glean additional information about the collection $\mathcal S$ from $R_{\mathcal S}(p)$. Illustrating the extended information available in the reliability polynomial is the main focus of this talk while demonstrating the equivalence of these two definitions is the main theoretical result.