Jack Graver [Department of Mathematics and Statistics, Binghamton University]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.

====== Jack Graver ======

====== You May Rely on the Reliability Polynomial for Much More Than You Might Expect ======

===== Abstract for the Colloquium November 18, 1999 =====

The reliability polynomial R<sub>S</sub>(p) of a collection S of subsets of a finite set X has been extensively studied in the context of network theory. Here X is the edge set of a graph (V,X) and S the collection of the edge sets of certain subgraphs, for example, the spanning trees. In that case, R<sub>S</sub>(p) is the probability that, when each edge is included with the probability p, the resulting subgraph is connected. Demonstrating that the information about a collection S encoded in the coefficients of R<sub>S</sub>(p) may be capitalized upon in a variety of other probability and combinatorial settings is the main purpose of this talk.

To any collection of subsets S, we may associate b(S), the collection of minimal sets which meet each set in S. For the collections of interest to us, this is a duality operator: b(b(S))=S. Of particular interest are the self-blocking collections: b(S)=S . We illustrate the expanded use of the reliability polynomials to study these self-blocking collections.