You May Rely on the Reliability Polynomial for Much More Than You Might Expect
DATE:
Thursday, October 28, 1999
TIME:
4:30 - 5:30 PM
PLACE:
SW 323
SPEAKER:
Jack Graver, Syracuse University
TITLE:
Abstract
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) (R
subscript S) 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 paper.
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.
R E F R E S H M E N T S
4:00 To 4:25 PM
Kenneth W. Anderson
Memorial Reading Room
