@article{EJP42,
author = {Klaus Dohmen},
title = {Improved Inclusion-Exclusion Identities and Inequalities Based on a Particular Class of Abstract Tubes},
journal = {Electron. J. Probab.},
fjournal = {Electronic Journal of Probability},
volume = {4},
year = {1999},
keywords = {Inclusion-exclusion, Bonferroni inequalities, sieve formula, abstract tube, abstract simplicial complex, partial order, chain, dynamic programming, graph coloring, chromatic polynomial, broken circuit complex, network reliability.},
abstract = {Recently, Naiman and Wynn 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. In this paper, we introduce a particular class of abstract tubes which plays an important role with respect to chromatic polynomials and 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. Moreover, we show 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.},
pages = {no. 5, 1-12},
issn = {1083-6489},
doi = {10.1214/EJP.v4-42},
url = {http://ejp.ejpecp.org/article/view/42}}