Improved inclusion-exclusion identities and inequalities based on a particular class of abstract tubes (Q1293635)

Recently, \textit{D. Q. Naiman} and \textit{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.