Improved inclusion-exclusion identities and inequalities based on a particular class of abstract tubes
type: Item
instance of: scholarly article
title: Improved inclusion-exclusion identities and inequalities based on a particular class of abstract tubes
zbMATH Open document ID: 0920.05008
author: Klaus Dohmen
published in: Electronic Journal of Probability
publication date: 1999-07-08T00:00:00Z
full work available at URL: https://eudml.org/doc/119894
full work available at URL: paper5.abs.html
review text: 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.
reviewed by: Ioan Tomescu
Mathematics Subject Classification ID: 05A19
Mathematics Subject Classification ID: 05A20
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 68M15
Mathematics Subject Classification ID: 90B18
Mathematics Subject Classification ID: 90B25
Mathematics Subject Classification ID: 60E15
zbMATH DE Number: 1309961
zbMATH Keywords: inclusion-exclusion
zbMATH Keywords: Bonferroni inequalities
zbMATH Keywords: sieve formula
zbMATH Keywords: abstract tube
zbMATH Keywords: partial order
zbMATH Keywords: chain
zbMATH Keywords: graph coloring
zbMATH Keywords: chromatic polynomial
zbMATH Keywords: broken circuit complex
zbMATH Keywords: network reliability
MaRDI profile type: Publication
DOI: 10.1214/EJP.V4-42
Recommended article: Improved Bonferroni inequalities via abstract tubes. Inequalities and identities of inclusion-exclusion type
Recommended article: Improved Inclusion-Exclusion Identities and Bonferroni Inequalities with Reliability Applications
Recommended article: Inclusion-exclusion and network reliability
Recommended article: Network reliability
Recommended article: Combinatorial aspects of network reliability
Recommended article: Improved inclusion-exclusion inequalities for simplex and orthant arrangements
Recommended article: A generalized chromatic polynomial, acyclic orientations with prescribed sources and sinks, and network reliability
Recommended article: Q3081634
Recommended article: Q3789615
Recommended article: Generalized activities and \(K\)-terminal reliability. II
description: scientific article; zbMATH DE number 1309961