Bonferroni galambos inequalities for partition lattices

Sujets

• Sciences et techniques

Informations

• Publié par: opakito
• Nombre de lectures: 119
• Langue: English

Extrait

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: [e-mail], [e-mail] 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 2P 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 3P 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 Proo