User Tools

Site Tools


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 RS(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, RS(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 RS(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.

seminars/comb/1999graver.abstractc.txt · Last modified: 2020/01/29 14:03 (external edit)