Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 4 (1999) > Paper 5 open journal systems 


Improved Inclusion-Exclusion Identities and Inequalities Based on a Particular Class of Abstract Tubes

Klaus Dohmen, Humboldt-Universitaet zu Berlin


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.


Full text: PDF

Pages: 1-12

Published on: March 26, 1999
Bibliography
  1. G.D. Birkhoff, A determinant formula for the number of ways of coloring a map, Ann. Math. 14 (1912), 42-46.
  2. C.E. Bonferroni, Teoria statistica delle classi e calcolo delle probabilita, Pubblicazioni del R. Istituto Superiore di Scienze Economiche e Commerciali di Firenze 8 (1936), 1-62.
  3. K. Dohmen, Inclusion-exclusion and network reliability, Electron. J. Combin. 5 (1998), paper no. 36. Math. Reviews 99d:60008
  4. K. Dohmen, Improved Bonferroni inequalities for the reliability of a communication network, Preprint, Informatik-Bericht Nr. 114, Humboldt-Universitaet zu Berlin, 1998.
  5. K. Dohmen, Lower bounds and upper bounds for chromatic polynomials, J. Graph Theory 17 (1993), 75-80, Math. Reviews 94e:05103
  6. K. Dohmen, On partial sums of chromatic polynomials, Ars Combin., accepted for publication.
  7. J. Galambos and I. Simonelli, Bonferroni-type Inequalities with Applications, Springer-Verlag, New York, 1996. Math. Reviews 98f:60028
  8. R.M. Karp, Dynamic programming meets the principle of inclusion-exclusion, Oper. Res. Lett. 1 (1982), 49-51. Math. Reviews 83i:90150
  9. T.A. McKee, Graph structure for inclusion-exclusion inequalities, Congr. Numer. 125 (1997), 5-10. Math. Reviews 98i:05005
  10. D.Q. Naiman and H.P. Wynn, Abstract tubes, improved inclusion-exclusion identities and inequalities and importance sampling, Ann. Statist. 25 (1997), 1954-1983. Math. Reviews 1 474 076
  11. H. Narushima, Principle of inclusion-exclusion on partially ordered sets, Discrete Math. 42 (1982), 243-250. Math. Reviews 83k:06004
  12. J.S. Provan and M.O. Ball, Computing network reliability in time polynomial in the number of cuts, Oper. Res. 32 (1984), 516-526. Math. Reviews 85h:90053
  13. D.R. Shier, Network Reliability and Algebraic Structures, Clarendon Press, Oxford, 1991. Math. Reviews 92j:68008
  14. L. Takacs, On the method of inclusion and exclusion, J. Amer. Stat. 62 (1967), 102-113. Math. Reviews 36 #921
  15. I. Tomescu, Hypertrees and Bonferroni inequalities, J. Combinat. Theory Ser. B 41 (1986), 209-217. Math. Reviews 87j:60025
  16. H. Whitney, A logical expansion in mathematics, Bull. Amer. Math. Soc. 38 (1932), 572-579.
  17. H. Wilf, Which polynomials are chromatic? Proc. Colloq. Combinatorial Theory, Rome, 1973. Math. Reviews 56 #11841
















Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489