Improved inclusion-exclusion identities and inequalities based on a particular class of abstract tubes. (English) Zbl 0920.05008

Recently, D. Q. Naiman and H. P. Wynn [Ann. Stat. 25, No. 5, 1954-1983 (1997; Zbl 0902.60017)] introduced the concept of an abstract tube in order to obtain improved inclusion-exclusion identities and inequalities that involve much fewer terms than their classical counterparts. Roughly speaking, an abstract tube is a collection of sets together with an appropriate abstract simplicial complex. In this paper a particular class of abstract tubes which plays an important role with respect to chromatic polynomials and network reliability is introduced and it is shown that under some restrictive assumptions, a polynomial time inclusion-exclusion algorithm can be devised, which generalizes an important result of Provan and Ball on network reliability.
The inclusion-exclusion identities and inequalities associated with this class simultaneously generalize several well-known results such as Whitney’s broken circuit theorem, Shier’s expression for the reliability of a network as an alternating sum over chains in a semilattice and Narushima’s inclusion-exclusion identity for posets. In the subsection on chromatic polynomials, a link is established between the theory of abstract tubes and the theory of broken circuit complexes, which was initiated by Wilf. Some numerical values of bounds based on paths and on cutsets in the network reliability problem are reported.


05A19 Combinatorial identities, bijective combinatorics
05A20 Combinatorial inequalities
05C15 Coloring of graphs and hypergraphs
60C05 Combinatorial probability
68M15 Reliability, testing and fault tolerance of networks and computer systems
90B18 Communication networks in operations research
90B25 Reliability, availability, maintenance, inspection in operations research
60E15 Inequalities; stochastic orderings


Zbl 0902.60017