Answers are grounded in this paper and cite their sources.
The reliability polynomial associated with an independence system is g ( p ) = ∑k = 0ⁿ fₖ pᵏ ( 1 - p )n - k, where fₖ is the number of independent sets of cardinality k and n is the cardinality of the ground set. An independence system ( T,Γ ) is shellable if all maximal independent sets have the same cardinality and if there exists an ordered partition of the set of independent sets into intervals \ [ Fᵢ ,Gᵢ ] = 1I (an interval [ F ,G ] = \ F^ :F ⊆ F^ ⊆ G \) where for all n^, n^ I, Gn^, is a maximal independent set and (T, ∪ ᵢ₌₁n^ [ Fᵢ ,Gᵢ ]) is an independence system. For the class of shellable independence systems, tight upper and lower bounds are given on $g ( p )$, when the number of maximal independent sets and the number of minimum cardinality dependent sets are fixed. These results can be applied to obtain bounds on the reachability measure, which is the probability that a stochastic network (directed or undirected) contains a path from a specified node to all other nodes.
No takes yet. Share an insight, caveat, or question.
Ball et al. (1982) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: