Problem of the Week
Hilton Memorial Lecture
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.