6
P
Bonferroni-Galambos Inequalities
for Partition Lattices
Klaus Dohmen and Peter Tittmann
Department of Mathematics
Mittweida University of Applied Sciences
09648 Mittweida, Germany
e-mail: dohmen@htwm.de, peter@htwm.de
Submitted: Jul 16, 2004; Accepted: Nov 18, 2004; Published: Nov 30, 2004
Mathematics Subject Classication: 05A18, 05A20, 05C65, 60C05, 60E15
Abstract
In this paper, we establish a new analogue of the classical Bonferroni inequali-
P
jj−1ties and their improvements by Galambos for sums of type (−1) (jj−
2 (U)
1)!f()whereU is a nite set, P(U) is the partition lattice of U and f : P(U)! R
is some suitable non-negative function. Applications of this new analogue are given
to counting connected k-uniform hypergraphs, network reliability, and cumulants.
1 Introduction
The classical Bonferroni inequalities of probability theory state that for any probability
space (Ω;E;P) and any nite family of events fE g E,
u u2U
! !
\ X \
r r jIj(−1) P E (−1) (−1) P E (r=0; 1; 2;:::): (1)
u i
IU
u2U i2I
jIj r
Thus, for even r the sum on the right-hand side of (1) provides an upper bound on the
T
probability P E that none of the events E , u 2 U, happen, while for odd r it
u u
u2U
provides a lower bound on this probability. Note that for r j Uj the preceding inequality
becomes an identity, which is known as the inclusion-exclusion principle. This principle
and its associated truncation inequalities (1) have many applications in statistics and
reliability theory (see [7] for a detailed survey and [4] for some recent developments).
Galambos [6] sharpened the classical Bonferroni bounds by including additional terms
based on the (r + 1)-subsets of U in case that U =;:
! ! !
\ X \ X \
r+1
r r jIj(−1) P E (−1) (−1) P E − P E :
u i i
jUj
IU IU
u2U i2I i2I
jIj r jIj=r+1
the electronic journal of combinatorics 11 (2004), #R85 1
P
P
P
P
P
P
P
Evidently, the preceding inequality can equivalently be stated in the form
X X X
r+1
r jIj r jIj(−1) (−1) f(I) (−1) (−1) f(I) − f(I)(2)
jUj
IU IU
IU
jIj r jIj=r+1
T
where f(I)=P E for any I U. Recently, in [5], this latter inequality has been
i
i2I
Ugeneralized to a broader class of functions f :2 ! R.
In this paper, we establish an analogue of (2) for non-negative real-valued functions
f de ned on the partition lattice P(U) of some nite set U and thus obtain approximate
estimations for M¨obius inversions on the lattice of partitions of a set. The need for such
es has been pointed out by Gian-Carlo Rota in his famous Fubini Lectures [8,
Problem 11].
2 Main result
Let U be a nite set. A partition of U is a set of pairwise disjoint non-empty subsets of
U whose union is U.WeuseP(U) to denote the set of partitions of U. The elements of a
partition are called blocks. The number of blocks in a partition is denoted by jj.The
set of partitions P(U) is given the structure of a lattice by imposing if and only if
is a re nement of , which means that each block of is a subset of a block of .
+ +By R we denote the set of non-negative reals, and by Z the set of non-negative
n+integers. For n; k 2 Z we use to denote the number of k-block partitions of an n-set,
k
the so-called Stirling number of the second kind.
+Theorem 2.1 Let U be a non-empty nite set, and let f;g : P(U) ! R such that
P
+
f()= g() for any 2 P(U). Then, for any r2 Z ,
X
r jj−1(−1) (−1) (jj−1)!f()
2 (U)
X X
r!
r jj−1
(−1) (−1) (jj−1)!f()+ f()
jUj
2 (U) 2 (U)
r+1
jj r jj=r+1
or equivalently, by means of Mobius¨ inversion,
X X
r!
r r jj−1^(−1) g(1) (−1) (−1) (jj−1)!f()+ f()
jUj
2 (U) 2 (U)
r+1
jj r jj=r+1
^where 1 denotes the largest element fUg of P(U).
Proof. It su ces to prove that
X X
r!
r jj−1(−1) (−1) (jj−1)!f() f() : (3)
jUj
2 (U) 2 (U)
r+1
jj>r jj=r+1
the electronic journal of combinatorics 11 (2004), #R85 2P
P
P
P
P
P
P
P
P
Let S denote the left-hand side of (3). We obtain
X X
r jj−1
S =(−1) (−1) (jj−1)! g()
2 (U)
jj>r
X X
r jj−1=(−1) g() (−1) (jj−1)!
2 (U)
jj>r
jj
X X
jj
r k−1=(−1) g() (−1) (k− 1)!: (4)
k
2 (U) k=r+1
It is well-known that (see e.g., [10])
n n− 1 n− 1
= + k (n; k =1; 2; 3;:::):
k k− 1 k
Thus, for the inner sum in (4) we obtain
jj jj
X X
jj−1 jj−1
k−1 k−1(−1) (k− 1)! + (−1) k!
k− 1 k
k=r+1 k=r+1
jj−1 jj−1
X X
jj−1 jj−1
k k= (−1) k! − (−1) k! :
k k
k=r k=r+1
jj−1
rAfter cancelling out, we are left with (−1) r!. Thus, we nd that
r
X X
jj−1 jj−1
r r
S =(−1) g() (−1) r!= g() r! :
r r
2 (U) 2 (U)
Therefore, for any ! 2 P(U),
X X
jj−1 j!j−1 j!j−1
S g() r! g() r!=f(!) r! :
r r r
2 (U) 2 (U)
! !
By choosing ! uniformly at random among all (r + 1)-block partitions of U and taking
theexpectationweobtain
X X
r!
S E(f(!))r!= Prob[! = ]f()r!= f() ;
jUj
2 (U) 2 (U)
r+1
jj=r+1 jj=r+1
which nally proves (3). Thus, the proof of the theorem is complete.
The following weaker bounds obtained from Theorem 2.1 may be considered as a
partition lattice analogue of the classical Bonferroni inequalities.
the electronic journal of combinatorics 11 (2004), #R85 3P
P
P
P
P
P
Corollary 2.2 Under the requirements of Theorem 2.1,
X X
r jj−1 r jj−1(−1) (−1) (jj−1)!f() (−1) (−1) (jj−1)!f()
2 (U)
2 (U)
jj r
respectively,
X
r r jj−1^(−1) g(1) (−1) (−1) (jj−1)!f() :
2 (U)
jj r
3 Connected k-uniform hypergraphs
It is well-known (cf. [1, 10]) that for any n; k 2 N the number c of connected k-uniform
n;k
hypergraphs on vertex-set f1;:::;ng is given by the formula
X Y
jXj
jj−1 ( )
k
c = (−1) (jj−1)! 2 ;
n;k
X2
2 (V)
which can equivalently be stated as
jj
X Y
n jj 1
i
jj−1 ( )
k
c = (−1) 2 ;
n;k
() jj
‘n i=1
where ‘ n means that is a number partition of n,thatis,=( ;:::; ) for some1 m
m2 N such that + + = n,and()isann-tuple whose i-th component counts1 m
the number of occurrences of i in for i=1;:::;n.Weusejj to denote the number of
parts in (that is, the length of when considered as a tuple), and for any m; i2 N and
iany m-tuple j =(j ;:::;j ) of non-negative integers we use to denote the multinomial1 m
j
coe cient
i i!
= :
j ;:::;j j ! j !1 m 1 m
From Theorem 2.1 we now deduce the following bounds on c , some of which are listed
n;k
in Table 1.
+Theorem 3.1 For any n; k2 N and r2 Z ,
X Y X Y
jXj r! jXj
r r jj−1 ( ) ( )
k k
(−1) c (−1) (−1) (jj−1)! 2 + 2 ;
n;k
n
r+1
2 (V) 2 (V)
X2 X2
jj r jj=r+1
or equivalently, in terms of number partitions,
jj
X Y
n jj 1
i
r r jj−1 ( )
k(−1) c (−1) (−1) 2
n;k
() jj
‘n
i=1
jj r
r+1
X Y
1 n r+1
i( )
k
+ 2 :
n
()(r+1)
‘n
r+1
i=1
jj=r+1
the electronic journal of combinatorics 11 (2004), #R85 4
P
P
P
n; k bounds on c for r=1;:::;n− 1 (last bound in each line gives the exact value)
n;k
5,2 992, 555, 812, 728
5,3 1017, 927, 988, 958
5,4 31, 14, 56, 26
6,2 32487, 24109, 28113, 26152, 26704
6,3 1048369, 1042160, 1042894, 1042416, 1042632
6,4 32761, 32538, 32740, 32380, 32596
7,2 2092544, 1807132, 1892306, 1853896, 1870336, 1866256
7,3 34359621500, 34352375869, 34352423041, 34352416580, 34352420630, 34352418950
7,4 34359734715, 34359508257, 34359510357, 34359508078, 34359511294, 34359509614
7,5 2097144, 2096629, 2097265, 2095195, 2098411, 2096731
Table 1: Bounds on c for di erent values of n; k and r.
n;k
Proof. Every hypergraph H on vertex-set V =f1;:::;ng induces a partition of V,where
each block in the partition corresponds to a connected component of H. For any partition
2 P(V)letg()resp.f()bethenumberofk-uniform hypergraphs on V whose induced
P
partition is resp. a re nement of . Then, f()= g() for any 2 P(V ), and
^ ^
g(1) = c where 1=fVg denotes the largest element of P(V ). By Theorem 2.1,
n;k
X X
r!
r r jj−1
(−1) c (−1) (−1) (jj−1)!f()+ f(): (5)
n;k
n
2 (V) r+1 2 (V)
jj r jj=r+1
jXj( )
kSince for any partition 2 P(V)andanyblockX 2 there are exactly 2 k-uniform
Q jXj( )
khypergraphs having vertex-set X, we nd that f()= 2 , which in combination
X2
with (5) proves the rst inequality of this theorem. Since for any number partition
n jj
=( ;:::; )ofn there are exactly =jj! di erent set partitions in P(V )1 m
()
whose block sizes agree with ;:::; , we can re-write the right-hand side of the rst1 m
inequality as a sum over integer partitions. Thus, the second inequality is proved.
4 Network reliability
Let G =( V;E) be a nite undirected graph having vertex-set V and edge-set E.We
assume that the edges of G are subject to random and independent failures, while the
nodes are perfectly reliable. The failure probabilities of the edges are assumed to be
known and denoted by q for each edge e 2 E. Under this random graph model, the
e
all-terminal reliability R(G) is the probability that each pair of vertices of G is joined by
a path of operating (that is, non-failing) edges. This reliability measure has been studied
extensively, see e.g., Colbourn [3] for a survey. A well-known result due to Buzacott and
Chang [2], which is often referred to as the node partition formula, states that
X Y
jj−1
R(G)= (−1) (jj−1)! q (6)
e
2 (V) e2E(G;)
where E(G; ) denotes the set of edges of G whose endpoints belong to di erent blocks
of (see also [11]). The following theorem states that by restricting the sum in (6) to
the electronic journal of combinatorics 11 (2004), #R85 5
P
P
P
partitions having at most r blocks lower bounds and upper bounds to R(G) are obtained
depending on whether r is even or odd. As in Theorem 2.1 an additional term is included
in these bounds which sharpens the estimates and which can be omitted if convenient.
Theorem 4.1 Let G =( V;E) be a nite undirected graph whose nodes are perfectly
reliable and whose edges fail randomly and independently with probability q for each edge
e
+
e2 E. Then, for any r2 Z ,
X Y X Y
r!
r r jj−1(−1) R(G) (−1) (−1) (jj−1)! q + q :
e e
jVj
2 (V) 2 (V)
r+1
e2E(G;) e2E(G;)
jj r jj=r+1
Proof. The state of the network induces a partition 2 P(V ), where two nodes are in
thesameblockof if and only if they are joined by a path of operating edges in G.Let
g() denote the probability that is the partition induced by the state of the network
and f() denote the probability that the induced partition is a re nement of . Then,
P
^ ^
f()= g() for any 2 P(V ), and g(1) = R(G)where1=fVg denotes the largest
Q
element of P(V ). It is easily seen that, on the other hand, f()= q for any
e
e2E(G;)
2 P(V ). Thus, the result follows by applying Theorem 2.1.
Example 4.2 For G = K (the complete graph on n nodes), r =2andq = q for each
n e
edge e2 E the inequality in Theorem 4.1 specializes to
n−1 n−1
X X1 n n− 1
k(n−k) k(n−k)
R(K ) 1− q =1− q
n
2 k k− 1
k=1 k=1
where the last term in the estimate of Theorem 4.1 has been omitted. Thus, for n =
3;:::;6 the following lower bounds on R(K ) are obtained:
n
2 4 6
R(K ) 1− 3q;R (K ) 1− 5q − 10q ;3 5
3 4 5 8 9
R(K ) 1− 4q − 3q (K ) 1− 6q − 15q − 10q :4 6
Figure 1 compares the bound for R(K ) with the exact reliability given by6
5 8 9 11 12 13 14 15
R(K )=1− 6q − 15q +20q + 120q − 90q − 270q + 360q − 120q :6
It turns out that the bound for R(K ) is close to the exact reliability if the common edge6
failure probability q is small. Fortunately, this is the typical case in real-world computer
and communications networks.
5 Cumulants
Let X ;:::;X be random variables. Due to Speed [9] (see also Rota [8]) the multilinear1 n
cumulant of these random variables can be expressed as
!
X Y Y
jj−1
(X ;:::;X)= (−1) (jj−1)! E X (7)1 n b
B2 b2B
2 (f1;:::;ng)
the electronic journal of combinatorics 11 (2004), #R85 6P
P
P
1 exact reliability
lower bound
0.8
0.6
0.4
0.2
0
0 0.2 0.4 0.6 0.8 1
edge failure probability
Figure 1: Exact and approximate reliability of K .6
which, for simplicity, is considered here as a de nition. We now generalize the notion
of a multilinear cumulant to what we call a partition cumulant: For any partition 2
P(f1;:::;ng) we de ne
!
X Y Y
()= ( ; ) E X (8)
b
2 (f1;:::;ng)
B2 b2B
^where denotes the M¨ obius function of P(f1;:::;ng) (see [10] for details). Since ( ; 1) =
jj−1 ^(−1) (jj−1)!, where 1 denotes the largest element of P(f1;:::;ng), we nd that
^
(1) = (X ;:::;X ), so (8) generalizes (7).1 n
Theorem 5.1 Let X ;:::;X be random variables such that all partition cumulants of1 n
+
X ;:::;X are non-negative. Then, for any r2 Z ,1 n
!
X Y Y
r r jj−1(−1) (X ;:::;X ) (−1) (−1) (jj−1)! E X1 n b
2 (f1;:::;ng)
B2 b2B
jj r
!
X Y Y
r!
+ E X :
b
n
r+1
2 (f1;:::;ng)
B2 b2B
jj=r+1
the electronic journal of combinatorics 11 (2004), #R85 7
all-terminal reliability