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

Iz MaFiRaWiki

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.

Osebna orodja