Shuchao Li

Huihui Zhang

Xiaoyan Zhang
email: royxyzhang@gmail.com.

Maximal independent sets in bipartite graphs with at least one cycle

Keywords: Maximal independent set, bipartite graph, cycle

A maximal independent set is an independent set that is not a proper subset of any other independent set. Liu [J.Q. Liu, Maximal independent sets of bipartite graphs, J. Graph Theory, 17 (4) (1993) 495-507] determined the largest number of maximal independent sets among all n-vertex bipartite graphs. The corresponding extremal graphs are forests. It is natural and interesting for us to consider this problem on bipartite graphs with cycles. Let Bn (resp. B ′ n ) be the set of all n-vertex bipartite graphs with at least one cycle for even (resp. odd) n. In this paper, the largest number of maximal independent sets of graphs in Bn (resp. B ′ n ) is considered. Among Bn the disconnected graphs with the first-, second-, . . . , n-2 2 -th largest number of maximal independent sets are characterized, while the connected graphs in Bn having the largest and the second largest number of maximal independent sets are determined. Among B ′ n graphs having the largest number of maximal independent sets are identified.

Introduction

Given a graph G = (V G , E G ), a set I ⊆ V G is independent if there is no edge of G between any two vertices of I. A maximal independent set is an independent set that is not a proper subset of any other independent set. The dual of an independent set is a clique, in the sense that a clique corresponds to an independent set in the complement graph. The set of all maximal independent sets of a graph G is denoted by MI(G) and its cardinality by mi(G).

Around 1960, Erdős and Moser proposed the problem to determine the maximum value of mi(G) when G runs over all n-vertex graphs and to characterize the graphs attaining this maximum, both of which were answered by Moon and Moser [START_REF] Moon | On Cliques in graphs[END_REF]. It is interesting to see that the extremal graphs turn to have most components isomorphic to the complete graph K 3 . On the other hand, the theory on maximal independent set has some applications in other research field. For example, in chemistry, a Clar structure is defined to be a maximal independent set of vertices of the Clar graph of the corresponding benzenoid hydrocarbons [START_REF] El-Basil | Binomial-combinatorial properties of Clar structures[END_REF]. Clar structures recently are used as basis-set to compute resonance energies. The theory of maximal independent set is also applied to the areas of managements and networks. For the compatibility graph G, its vertices denote tasks, and an edge denotes a resource sharing constraint between the two tasks linked by it. A maximal independent set of a compatibility graph represents a maximal set of tasks that can be executed concurrently. Basagni [START_REF] Basagni | A distributed algorithm for finding a maximal weighted independent set in wireless network[END_REF] and Alzoubi et al. [START_REF] Rhodes | CLIP: similarity searching of 3D databases using clique detection[END_REF] pointed out the importance of a maximal independent set in the wireless network. Moscibroda and Watenhofer [START_REF] Moscibroda | Efficient computation of maximal independent sets in unstructured multi-hop radio network[END_REF] obtained the wellknown Maximal Independent Set problem when they modeled the unstructured radio network as a graph.

Along the line on the study of the maximal independent set in mathematical literature, mathematicians focused on determining the largest number of mi(G) in various interesting classes of graphs. Ying et al. [START_REF] Ying | Maximal independent sets in graphs with at most r cycles[END_REF] determined the maximum number of maximal independent sets in graphs of order n with at most r cycles and in connected graphs of order n 3r with at most r cycles. Ortiz [START_REF] Ortiz | Maximal independent sets in caterpillar graphs[END_REF] established a sharp upper bound for the number of maximal independent sets in caterpillar graphs. Arumugam et al. [START_REF] Arumugam | Maximal independent sets in minimum colorings[END_REF] studied the maximal independent set of graphs with minimum coloring. Duffus, Frankl and Rödl [START_REF] Duffus | Maximal independent sets in bipartite graphs obtained from Boolean lattices[END_REF] studied maximal independent sets in graphs obtained from Boolean lattices. Jing and one of the present authors [START_REF] Li | Maximal independent sets in graphs with cyclomatic number at most two[END_REF] studied the maximal independent set of graphs with cyclomatic number at most two. Jin and Li [START_REF] Jin | Graphs with the second largest number of maximal independent sets[END_REF] determined the second largest number of maximal independent sets among all graphs of order n. Hua and Hou [START_REF] Hua | On graphs with the third largest number of maximal independent sets[END_REF] determined the n-vertex graph having the third largest number of maximal independent sets. Jou and Lin [START_REF] Jou | The number of maximal independent sets in graphs[END_REF][START_REF] Jou | Maximal independent sets in graphs with at most one cycle[END_REF] settled the problem for trees and forests. Jin and Yan [START_REF] Jin | Trees with the second and third largest number of maximal independent sets[END_REF] settled the problem for the second and third largest number of maximal independent sets of trees.

This paper is motivated directly from [START_REF] Liu | Maximal independent sets in bipartite graphs[END_REF], in which the author completely characterized the n-vertex bipartite graphs having the largest number of maximal independent sets. The corresponding extremal graphs are forests. Furthermore, for the bipartite graph of order n that contains cycles, the author in [START_REF] Liu | Maximal independent sets in bipartite graphs[END_REF] determined the upper bound on the number of maximal independent sets for odd n. Unfortunately, the graphs which attain this value were not characterized. It is natural and interesting to determine the corresponding extremal graphs, which is settled in this paper. On the other hand, it is necessary and interesting to consider this problem on the n-vertex bipartite graphs with cycles for even n. In this paper, among the set of all disconnected bipartite graphs with even order, the extremal graphs which have the first-, second-, . . . , n-2 2 -th largest number of maximal independent sets are characterized respectively, while among the set of all connected bipartite graphs with even order, the extremal graphs having the largest and the second largest number of maximal independent sets are identified.

Preliminary

Given a simple graph G = (V G , E G ), the cardinality of V G is called the order of G. And Gv denotes the graph obtained from G by deleting vertex v ∈ V G (this notation is naturally extended if more than one vertex is deleted

). For v ∈ V G , let N G (v) (or N (v) for short) denote the set of all the adjacent vertices of v in G and d(v) = |N G (v)|. For convenience, let N G [v] = N G (v)∪{v}.
A leaf of G is a vertex of degree one, while an isolated vertex of G is a vertex of degree zero. For any two graphs G and H, let G⊎H denote the disjoint union of G and H, and for any nonnegative integer t, let tG stand for the disjoint union of t copies of G. For a connected graph H with maximum degree vertex x and a graph

G = G 1 ⊎G 2 ⊎• • •⊎G k with u i being a maximum degree vertex in G i , i = 1, 2, . . . , k. Define the graph H * G to be the graph with vertex set V H * G = V H ∪ V G and edge set E H * G = E H ∪ E G ∪ {xu i : i = 1, 2, . . . , k}.
An odd (resp. even) component is a component of odd (resp. even) order. Throughout the text we denote by P n , C n , K 1,n-1 and K n the path, cycle, star and complete graph on n vertices, respectively. Undefined terminology and notation may be referred to [START_REF] Bondy | Graph Theory with Applications[END_REF].

Throughout this paper, for simplicity, r denotes √ 2. We begin with some useful known results which are needed to prove our main results.

Lemma 1 ([7, 14])

For any vertex v in a graph G, mi(G) mi(G -v) + mi(G -N G [v]). If v is a leaf adjacent to u, then mi(G) = mi(G -N G [v]) + mi(G -N G [u]). Lemma 2 ([14]) If G is the union of two disjoint graphs G 1 and G 2 , then mi(G) = mi(G 1 ) • mi(G 2 ).

Lemma 3 ([13])

If T is a tree with n 1 vertices, then mi(T ) t 1 (n), where

t 1 (n) = r n-2 + 1, if n is even; r n-1 , if n is odd. Furthermore, mi(T ) = t 1 (n) if and only if T ∈ T 1 (n),
where

T 1 (n) = B(2, n-2 2 ) or B(4, n-4 2 ), if n is even; B(1, n-1 2 ), if n is odd,
where B(i, j) is the set of batons, which are the graphs obtained from a basic path P i (i 1) by attaching j 0 paths of length two to the endpoints of P i in any possible ways.

Lemma 4 ([13])

If F is a forest with n 1 vertices, then mi(F ) f 1 (n), where

f 1 (n) = r n , if n is even; r n-1 , if n is odd. Furthermore, mi(F ) = f 1 (n) if and only if F ∈ F 1 (n),
where

F 1 (n) = n 2 K 2 , if n is even; B(1, n-1-2s 2 ) ⊎ sK 2 f or some s with 0 s n-1 2 , if n is odd. Lemma 5 ([14]) If F is a forest with n 4 vertices having F ∈ F 1 (n), then mi(F ) f 2 (n), where f 2 (n) =      3r n-4 , if n 4 is even; 3, if n = 5; 7r n-7 , if n 7 is odd. Furthermore, mi(F ) = f 2 (n) if and only if F ∈ F 2 (n), where
F 2 (n) =      P 4 ⊎ n-4 2 K 2 ,
if n 4 is even;

P 1 * P 4 or, P 1 ⊎ P 4 , if n = 5; P 7 ⊎ n-7 2 K 2 , if n 7 is odd. For n 2, 0 k ⌊ n 2 ⌋, define B n,k = 2P 4 ⊎ n-8 2 K 2 or, T 1 (n -2k) ⊎ kK 2 , if n is even; T 1 (n -2k) ⊎ kK 2 , if n is odd. Then mi(B n,k ) = 2 k • mi(T 1 (n -2k)), or 9r n-8 .

Lemma 6 ([17])

The maximum number of maximal independent sets among all bipartite graphs of order n is 2 ⌊ n 2 ⌋ , and the only bipartite graphs of order n which have this many maximal independent sets are F 1 (n).

Lemma 7 ([17]) If G is an acyclic graph of order n and

G ≇ B n,k , then mi(G) < t 1 (n). Lemma 8 If n 6, then mi(C n ) = mi(C n-2 ) + mi(C n-3 ). Furthermore, one has mi(C n ) < r n-1 , if n 7 is odd; r n-2 , if n 12 is even.
Proof: The first part is due to [START_REF] Jou | Maximal independent sets in graphs with at most one cycle[END_REF]; we show the second part by induction on n. It is routine to check that

mi(C 7 ) = 7 < r 6 , mi(C 9 ) = 12 < r 8 , mi(C 11 ) = 22 < r 10 , mi(C 12 ) = 29 < r 10 , mi(C 13 ) = 39 < r 12 , mi(C 14 ) = 51 < r 12 .
Assume the result holds for n k. Now consider n = k + 1 15. By induction hypothesis, we obtain

mi(C n ) = mi(C n-2 ) + mi(C n-3 ) < r n-2-1 + r n-3-2 = 3r n-5 < r n-1 , if n is odd; r n-2-2 + r n-3-1 = r n-2 , if n is even.
This completes the proof. ✷

Sharp bounds and extremal graphs

Let B n (resp. B ′ n ) be the set of all n-vertex bipartite graphs with at least one cycle for even (resp. odd) n. In this section, among B n the disconnected graphs with the first-, second-, . . . , n-2 2 -th largest number of maximal independent sets are characterized, while the connected graphs in B n having the largest and the second largest number of maximal independent sets are determined; among B ′ n the graphs having the largest number of maximal independent sets are identified.

For even n and 3 Proof: By direct computing, we have

k n 2 , define D n,k = B 2k ⊎ ( n 2 -k)K 2 , where B 2k is depicted in Fig. 1. Then mi(D n,k ) = 2 n 2 -k • mi(B 2k ) = 2 n 2 -k (2 k-1 + 1) r n-2 + r n-6 . Theorem 1 For graphs D n,3 , D n,4 , . . . , D n, n 2 , C 8 ⊎ n-8 2 K 2 , C 10 ⊎ n-10 2 K 2 , (C 8 * K 2 ) ⊎ n-10 2 K 2 , one has mi(D n,3 ) = mi(C 8 ⊎ n -8 2 K 2 ) > mi(D n,4 ) > mi(D n,5 ) = mi(C 10 ⊎ n -10 2 K 2 ) = mi((C 8 * K 2 ) ⊎ n -10 2 K 2 ) > mi(D n,6 ) > mi(D n,7 ) > • • • > mi(D n, n 2 ) = r n-2 + 1. . . . . . . . . .
mi(D n,t ) = 2 n-2t 2 • mi(B 2t ) = 2 n-2 2 + 2 n-2t 2 , t = 3, 4, . . . , n 2 , (1)
mi(C 8 ⊎ n -8 2 K 2 ) = 10 • 2 n-8 2 , (2)
mi(C 10 ⊎ n -10 2 K 2 ) = 17 • 2 n-10 2 , ( 3
) mi((C 8 * K 2 ) ⊎ n -10 2 K 2 ) = 17 • 2 n-10 2 . (4)
By [START_REF] Arumugam | Maximal independent sets in minimum colorings[END_REF], it is easy to see that mi(D n,t ) < mi(D

H 1 (n) H 2 (n) H 0 (8) H 0 (10) H 3 (n) O 1 (n) H 0 (6)
(i) If G ∈ B n \ {D n,3 , D n,4 , . . . , D n, n 2 , C 8 ⊎ n-8 2 K 2 , C 10 ⊎ n-10 2 K 2 , (C 8 * K 2 ) ⊎ n-10 2 K 2 }, then mi(G) r n-2 . ( 5
)
If G is connected, the equality holds in [START_REF] El-Basil | Binomial-combinatorial properties of Clar structures[END_REF] if and only if

G ∼ = H 0 (n), H 1 (n), H 2 (n), or H 3 (n) for n = 6, 8, 10; and G ∼ = H 1 (n), H 2 (n), or H 3 (n) for n 12.
If G is disconnected, the equality holds in [START_REF] El-Basil | Binomial-combinatorial properties of Clar structures[END_REF] if and only if

G ∼ = C 4 ⊎ n-4 2 K 2 , H 0 (6)⊎ n-6 2 K 2 , H 0 (8)⊎ n-8 2 K 2 , H 0 (10) ⊎ n-10 2 K 2 , H 1 (n -2k) ⊎ kK 2 , H 2 (n -2k) ⊎ kK 2 , or H 3 (n -2k) ⊎ kK 2 . (ii) If G ∈ B ′ n , then mi(G) 3r n-5 . ( 6
)
The equality holds in [START_REF] Hua | On graphs with the third largest number of maximal independent sets[END_REF] if and only if

G ∼ = C 6 * K 1 , or O 1 (n) for connected G and G ∼ = O 1 (n - 2k) ⊎ kK 2 , or (C 6 * K 1 ) ⊎ n-7 2 K 2 for disconnected G.
Proof: We put the proofs of (i) and (ii) together as below. Choose

G in B n \ {D n,3 , D n,4 , . . . , D n, n 2 , C 8 ⊎ n-8 2 K 2 , C 10 ⊎ n-10 2 K 2 , (C 8 * K 2 ) ⊎ n-10 2 K 2 } (resp. B ′ n ) such that mi(G)
is as large as possible. We proceed by induction on n.

For 5 n 6, it is straightforward to check that our results hold. Assume that our results hold for n k. Now consider n = k + 1 7.

First we consider that G is disconnected. Denote

G = G o1 ⊎ G o2 ⊎ • • • ⊎ G o l 1 ⊎ G e1 ⊎ G e2 ⊎ • • • ⊎ G e l 2 ,
where G oi is an odd component for 1 i l 1 and G ej is an even component for 1 j l 2 .

Case 1. n is even. In this case, we have that l 1 is also even. If

l 1 2, then mi(G) = l1 i=1 mi(G oi ) • l2 j=1 mi(G ej ) (by Lemma 2) l1 i=1 r |VG o i |-1 • l2 j=1 r |VG e j |
(by Lemma 6)

= r n-l1 r n-2 . (7)
The equality in [START_REF] Hujter | The number of maximal independent sets in triangle-free graphs[END_REF] holds if and only if

G oi ∼ = F 1 (|V Go i |) for 1 i l 1 , G ej ∼ = F 1 (|V Ge j |
) for 1 j l 2 ; while the equality in (8) holds if and only if l 1 = 2, which implies that

G ∼ = F 1 (|V Go 1 |) ⊎ F 1 (|V Go 2 |) ⊎ n-|VG o 1 |-|VG o 2 | 2 K 2 .
Obviously, G does not contain cycles, so mi(G) < r n-2 . Therefore we consider that l 1 = 0, that is to say, each component contained in G is an even component. Without loss of generality, assume that

|V Ge 1 | |V Ge 2 | • • • |V Ge l 2 |. Note that G contains cycles, hence |V Ge 1 | 4. If |V Ge 1 | = 4, then there exists a p ∈ {1, 2, . . . , l 2 } such that |V Ge 1 | = |V Ge 2 | = |V Ge 3 | = • • • = |V Ge p | = 4. As G contains cycles, there is at least one i ∈ {1, 2, . . . , p} such that G ei ∼ = C 4 . We obtain that mi(G) = mi(G ei ) • 1 j =i p mi(G ej ) • l2 k=p+1 mi(G e k )
(by Lemma 2)

2 • 3 p-1 • r n-4p
(by Lemmas 3 and 6) (9)

= r n-2 • ( 3 4 ) p-1 r n-2 . ( 10
)
The equality in (9) holds if and only if

G ei ∼ = C 4 , G ej ∼ = P 4 for 1 j = i p, G -(G e1 ⊎ G e2 ⊎ • • • ⊎ G ep ) ∼ = F 1 (n -4p) = n-4p
2 K 2 ; while the equality in [START_REF] Jou | The number of maximal independent sets in graphs[END_REF] holds if and only if p = 1, which implies that

G ∼ = C 4 ⊎ n-4
2 K 2 , our result holds. If |V Ge 1 | 6, then we consider the following two possible subcases.

• |V Ge 2 | = 2. In this subcase, we have G -G e1 ∼ = n-|VG e 1 | 2 K 2 . Note that G ≇ D n,|VG e 1 |/2 , C 8 ⊎ n-8 2 K 2 , C 10 ⊎ n-10 2 K 2 and (C 8 * K 2 ) ⊎ n-10 2 K 2 , hence G e1 ≇ B |VG e 1 | ,
mi(G) = mi(G e1 ) • mi(G -G e1 ) r |VG e 1 |-2 • r n-|VG e 1 | (11) = r n-2 .
The equality in [START_REF] Jou | Servey on counting maximal independent sets[END_REF] holds if and only if G e1 ∼ = H 0 (6), H 0 (8), H 0 [START_REF] Jou | The number of maximal independent sets in graphs[END_REF], r n-4 + r n-6 + r n-8 + r n-10 < r n-2 .

H 1 (|V Ge 1 |), H 2 (|V Ge 1 |), or H 3 (|V Ge 1 |). Together with G -G e1 ∼ = n-|VG e 1 | 2 K 2 , our result follows immediately. • |V Ge 2 | 4. In this subcase, we have mi(G) = mi(G e1 ) • mi(G e2 ) • l2 j=3 mi(G ej ) (by Lemma 2) (r |VG e 1 |-2 + 1) • (r |VG e 2 |-2 + 1) • r n-|VG e 1 |-|VG
Case 2. n is odd. In this case, l 1 is also odd. If l 1 3, by Lemmas 2 and 6 , we get

mi(G) = l1 i=1 mi(G oi ) • l2 j=1 mi(G ej ) l1 i=1 r |VG o i |-1 • l2 j=1
r |VG e j | = r n-l1 r n-3 < 3r n-5 .

Hence, we consider that l 1 = 1 in what follows.

If G o1 contains cycles, by induction hypothesis and Lemmas 2 and 6 , we obtain that

mi(G) = mi(G o1 ) • mi(G -G o1 ) 3r |VG o 1 |-5 • r n-|VG o 1 | = 3r n-5 ,
the equality holds if and only if

G o1 ∼ = O 1 (|V Go 1 |) or C 6 * K 1 and G -G o1 = n-|VG o 1 | 2 K 2 , which implies that G ∼ = O 1 (|V Go 1 |) ⊎ n-|VG o 1 | 2 K 2 or (C 6 * K 1 ) ⊎ n-7
2 K 2 , the result holds. If G o1 does not contain cycles, then there exists at least one even component G ej containing cycles

with |V Ge j | 4. If |V Ge j | = 4, then G ej ∼ = C 4 . We obtain that mi(G) = mi(G o1 ) • mi(G ej ) • 1 i =j l2 mi(G ei ) (by Lemma 2) r |VG o 1 |-1 • 2 • r n-4-|VG o 1 |
(by Lemmas 3 and 6) < 3r n-5 , the result holds. If |V Ge j | 6, we obtain that

mi(G) = mi(G o1 ) • mi(G ej ) • 1 i =j l2 mi(G ei ) (by Lemma 2) r |VG o 1 |-1 • (r |VG e j |-2 + 1) • r n-|VG o 1 |-|VG e j |
(by Lemmas 3, 6 and Theorem 1)

= r n-3 + r n-|VG e j |-1 r n-3 + r n-7 < 3r n-5 .
The result holds. Now we consider that G is connected. It suffices to consider the following two possible cases.

Case 1. G has a vertex v of degree 4 such that Gv has cycles.

Subcase 1.1. n is even. In this subcase, we have

mi(G) mi(G -v) + mi(G -N G [v])
(by Lemma 1) 3r n-6 + r n-5-1

(by induction hypothesis and Lemma 6) (12) = r n-2 .

The equality in (12) holds if and only if

G -v ∼ = O 1 (k) ⊎ n-k-1 2 K 2 or (C 6 * K 1 ) ⊎ n-8 2 K 2 , G -N G [v] ∼ = F 1 (n -5).
But there is no such bipartite graph since G -N G [v] is obtained from Gv by deleting four independent vertices, hence mi(G) < r n-2 . Subcase 1.2. n is odd.

In this subcase, we first consider that G-v ∼ = D n-1,k . Then by Theorem 1, mi(G-v) r n-3 +r n-7 . If d(v) = 4, then G -N G [v] is either an acyclic bipartite graph which is not isomorphic to B n-5,k or a bipartite graph with cycles which is not isomorphic to D n-5,k . Hence by induction hypothesis or Lemma 7, mi(G -N G [v]) r n-7 , which gives

mi(G) mi(G -v) + mi(G -N G [v])
(by Lemma 1) r n-3 + r n-7 + r n-7

(13) = 3r n-5 .

The equality in (13) holds if and only if

G-v ∼ = C 6 ⊎ n-7 2 K 2 and G-N G [v] ∼ = H 0 (6)⊎ n-11 2 K 2 , H 0 (8)⊎ n-13 2 K 2 , H 0 (10) ⊎ n-15 2 K 2 , H 1 (k) ⊎ n-k-5 2 K 2 , H 2 (k) ⊎ n-k-5 2 K 2 , or H 3 (k) ⊎ n-k-5 2 K 2 . Note that v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v G 1 G 2 G 3 G 4 G 5 G 6 G 7 G 8 G 9 G

Fig. 1 :

 1 Fig. 1: Graph B 2k , where k 3 and t 2.

Fig. 2 : 2

 22 Fig. 2: The extremal graphs

e 2 |

 2 (byLemmas 3,[START_REF] Hua | On graphs with the third largest number of maximal independent sets[END_REF] and Theorem 1)= r n-4 + r n-|VG e 2 |-2 + r n-|VG e 1 |-2 + r n-|VG e 1 |-|VG e 2 |

Fig. 5 :

 5 Fig. 5: Graphs G 1 , G 2 , . . . , G 46 used in Case 2 of Fact 2, in which each number below the graph G i is an upper bound of mi(G i ), i = 1, 2, . . . , 46.

  C 8 , C 10 and C 8 * K 2 . By induction hypothesis and Lemma 2, we have

Acknowledgements

The authors would like to express their sincere gratitude to the referees for a very careful reading of the paper and for all of their insightful comments and valuable suggestions, which led to a number of improvements in this paper. This work was supported by the National Natural Science Foundation of China (Grant No. 11271149) and the Special Fund for Basic Scientific Research of Central Colleges (Grant No. CCNU13F020).

It is easy to see that G -N G [v] contains no cycles, a contradiction. Now we consider that Gv ≇ D n-1,k . In order to use the induction hypothesis, we should show that Gv ≇ C 8 ⊎ n- 9 2 K 2 , C 10 ⊎ n-11 2 K 2 , and

By a similar discussion as above, we may show that Gv ∼ = C 10 ⊎ n-11 2 K 2 , (C 8 * K 2 ) ⊎ n-11 2 K 2 . Therefore, we have

By induction hypothesis, we have mi(Gv) r n-3 . Thus,

(by Lemma 1) r n-3 + r n- 5 (by Lemma 6) (14) = 3r n-5 .

The equality in [START_REF] Jou | Trees with the second largest number of maximal independent sets[END_REF] holds if and only if Gv ∼ = H 0 (6) ⊎ n- 7 2 K 2 , H 0 (8) ⊎ n-9 2 K 2 , H 0 (10)

by deleting four independent vertices which is impossible. Hence mi(G) < 3r n-5 .

Case 2. Every vertex of degree 4 is in all cycles of G.

First we consider

. We distinguish the following two possible subcases to show our results.

By induction hypothesis and Lemma 5 and Theorem 1, we have mi(G 1 ) 3r n-7 and mi(G 2 ) max{3r n-7 , r n-5 +r n-9 } = 3r n-7 . By Lemma 1, we get

the equality holds if and only if

the equality holds if and only if

obtained from G 1 by deleting three independent vertices which is impossible. Subcase 2.2. n is even.

• d(u) = 2. In this subcase, we know that G 1 is a connected graph with cycles. Note that G ≇ C 8 * K 2 , hence G 1 ≇ C 8 . By Theorem 1, we have mi(G 1 ) r n-4 + 1. On the other hand, notice that

, by induction hypothesis or Lemma 7, we have mi(G 2 ) max{r n-4 -1, 3r n-8 } = r n-4 -1. Combining with Lemma 1, we have

the equality holds if and only if G 1 ∼ = B n-2 , C 10 or C 8 * K 2 and mi(G 2 ) = r n-4 -1, but there is no such bipartite graph.

2 K 2 since G have cycles. Thus, by Lemma 5 and Theorem 1, we get mi(G 1 ) r n-4 +r n-8 = 5r n-8 and mi(G 2 ) max{3r n-8 , r n-6 + r n-10 } = 3r n-8 . By Lemma 1, we have

2 K 2 , then for n = 6, we get G 2 = 2K 1 and G ∼ = H 0 (6), the result holds. We assume n 8. Obviously, G 1 ≇ C 8 since G ≇ C 8 * K 2 . By Lemmas 3, 5 and Theorem 1, we have mi(G 1 ) r n-4 + 1, mi(G 2 ) max{3r n-8 , r n-6 + r n-10 } = 3r n-8 . Thus,

(by Lemma 1) r n-4 + 1 + 3r n-8

(15) = 7r n-8 + 1

The equality in [START_REF] Jou | The second largest number of maximal independent sets in connected graphs with at most one cycle[END_REF] holds if and only if

2 K 2 ; while the equality in ( 16) holds if and only if n = 8, i.e., G 1 ∼ = P 4 * K 2 , C 6 or P 6 and G 2 ∼ = P 4 , but there is no such bipartite graph.

By Lemmas 5, 6 and Theorem 1, we get mi(G 1 ) max{3r n-6 , r n-4 + r n-8 } = 3r n-6 and mi(G 2 ) r n-6 . By Lemma 1,

Note that G 2 is obtained from G 1 by deleting three or four independent vertices, hence there is no such bipartite graph of order n. Hence mi(G) < r n-2 . Now we consider δ(G) 2. In this subcase, we used the following two facts (for their proofs one may be referred to the Appendix).

Fact 1 Suppose n 7 is odd and each vertex of degree 4 is in all cycles of G, then mi(G) < 3r n-5 . Fact 2 Suppose n 6 is even and each vertex of degree 4 is in all cycles of G, then mi(G) r n-2 .

The equality holds if and only if

Obviously, in this case, if δ(G) 2, Theorem 2 holds directly from Facts 1 and 2. ✷

Concluding remark

In view of Theorems 1 and 2(i), the disconnected graphs among B n with the first-, second-, . . . , n-2 2 -th largest number of maximal independent sets are characterized, while the connected graphs in B n having the largest and the second largest number of maximal independent sets are determined; whereas in view of Theorem 2(ii), graphs among B ′ n having the largest number of maximal independent sets are identified.

Appendix

In the appendix, we present the proofs for Facts 1 and 2.

Proof of Fact 1:

We first assume that G has a vertex v of degree 3 such that Gv has cycles. Note that G contains no odd cycles and

So we obtain that the graph G is depicted in Fig. 3(a). By Lemma 1, we get mi(G) mi(Gu)

Hence, we have

By induction hypothesis, mi(Gv) r n-3 . In view of Lemmas 1 and 6, we have

The equality in (A.1) holds if and only if

is obtained from Gv by deleting three independent disjoint vertices, but there is no such bipartite graph of order n. Hence mi(G) < 3r n-5 .

•

is either an acyclic graph which is not isomorphic to B n-4,k or a bipartite graph containing cycles. It follows from induction hypothesis or Lemma 7 that mi(G -N G [v]) max{r n-4-1 -1, 3r n-4-5 } = r n-5 -1. Together with Lemma 1, we have

The equality in (A.2) holds if and only if

Note that G is a bipartite graph with δ(G) 2, hence G-v must be the graph as depicted in Fig. 3

Fig. 3: Graphs used in the proof of Fact 1.

Now, we consider the case that each vertex of degree 3 is in all cycles of G. Then G must be a graph with the structures as depicted in Figs. 3(c) or 3(d). Assume that the vertex u is in all cycles of G, then d(u)

3. Note that n is odd and δ(G) 2, hence Gu ≇ B n-1,k and Gu contains no cycles. By Lemma 7, we get mi(Gu) r n-3 . Thus, we have

(by Lemma 1)

The equality in (A.3) holds if and only if mi(G

or T 1 (n -5). Notice that δ(G) 2 and u is in all cycles of G, it is straightforward to check that n ∈ {7, 9, 11} and G -N [u] ≇ T 1 (n -5). So we get that G is a graph of the structure in Fig. 3(d). That is to say, G has exactly two vertices of degree 3, say u and v. It follows that d

Hence, we obtain mi(G) < 3r n-5 . Thus, Fact 1 holds. ✷ Further on we need the following lemma to prove Fact 2.

Lemma A Suppose n 6 is even. If G has a path

Proof: From the assumption it follows that

3r n-3-5 + r n-4-2 + 3r n- 3-5 (by induction hypothesis) (A.4) [START_REF] Jou | The number of maximal independent sets in graphs[END_REF] or the graph depicted in Fig. 4(c). But this implies G -{u 1 , u 2 , u 3 , u 4 , u 5 } has no cycles, a contradiction. If G 1 = G 2 ∼ = O 1 (n -3), we get two such graphs which contain odd cycles, a contradiction. That is to say, the equality in (A.4) does not hold. Hence, mi(G) < r n-2 , as desired. ✷

The equality in (A.4) holds if and only if d(u

Proof of Fact 2:

We say a vertex v is good if

First we consider that G has good vertices by distinguishing the following two possible cases.

Case 1. For all good vertices

For convenience, let

Note that δ(G) 2 and G is bipartite, hence G 1 must be connected and G 1 ∼ = B n-4 . Furthermore, G 1 must be a graph with the structure shown in Fig. 3

Hence, without loss of generality, assume N (w) ∩ N (v) = ∅. Note that d(v) = 3 and δ(G) 2, hence Gw has cycles. Thus, by the assumption that each vertex of degree 4 is in all cycles of G, it follows that 2 d(x)

,k for every good vertex v, G must be the graph shown in Figs. 4(a) or 4(b). For Fig. 4 Case 2. There exists a good vertex

In this case, we are to show that

2 K 2 , then there exist eight such graphs, i.e., G 1 , G 2 , . . . , G 8 ; if G 1 ∼ = C 10 ⊎ n-11 2 K 2 , then there exist thirteen such graphs, i.e., G 9 , G 10 , . . . , G 21

2 K 2 , then there exist twenty-five such graphs, i.e., G 22 , G 23 , . . . , G 46 , where G 1 , G 2 , . . . , G 46 are depicted in Fig. 5. By direct computation, we obtain mi(G) < r n-2 . Hence,

By Lemma 7 (if G 1 is acyclic) or by induction hypothesis (if G 1 contains cycles), we obtain that mi(G 1 ) r n-6 . Thus, we obtain that

(by Lemma 1)

The equality in (A.5) holds if and only if

2 and G contains no odd cycles, Gv contains no K 2 as a component, hence Now we consider that G has no good vertex, that is to say, each vertex of degree 3 must be contained in all cycles of G. This implies that G must be the graph with structures shown in Figs. 3(c) or 3(d). By Lemma 8 and G ≇ C 6 , C 8 and C 10 , we assume that G is not a cycle. If G is a graph of the structure in Fig. 3(c), then G has only one vertex u of degree 3. Since G is a bipartite graph of even order, then d(u) 6 and Gu consists of k 3 disjoint paths of even length, say Pn 1 , Pn 2 , . . . , Pn k (see Fig. and so

r n-4 + r n-8 (by Lemma 6 ) = 5r n-8 < r n-2 .

The result holds.

Suppose G is a graph of the structure in Fig. 3

This gives

Now we consider that all n j 's are even. Let Pn 1 = u 1 u 2 . . . un 1 . By Lemma A, we assume n This completes the proof. ✷


Marcel Wild
email: mwild@sun.ac.za.

Svante Janson
email: svante.janson@math.uu.se

Stephan Wagner
email: swagner@sun.ac.za.

Dirk Laurie

Coupon collecting and transversals of hypergraphs

Keywords:

The classic Coupon-Collector Problem (CCP) is generalized to a setting where coupons can serve more than one purpose. We show how the expected number of coupons that needs to be drawn can be determined by means of enumerating transversals of hypergraphs, where coupons can be drawn either with or without replacement. Only basic probability theory is needed for this purpose. The transversal counting can be done efficiently by a recently introduced algorithm that encodes all possible transversals in an efficient way. Our results are illustrated by applications to, amongst others, chess and roulette.

Introduction

In the popular game of Roulette a small metal bullet is spun and stopped at random on one of the w = 37 numbers 0, 1, 2, . . . , 36. Apart from 0 each one of these numbers has several properties. For example 13 is at the same time odd, black, in the second dozen, the first column; see Figure 1. We will show how to compute the expected time to encounter, in successive draws at random, all these properties: even, odd, red, black, 1-18, 19-36, 1st 12, 2nd 12, 3rd 12, 1st column, 2nd column, 3rd column.

Our general setting is as follows. Let W be a set whose w many elements will be viewed as "coupons". Let G = {G 1 , • • • , G h } be any family of nonempty (not necessarily distinct) subsets. Thus G ⊆ W . By definition G i contains exactly the coupons c of the i-th goal (purpose, property, etc.) Put another way, each fixed coupon c ∈ W is multipurpose in the sense that it can serve many goals according to the sets G i that contain c. If G = W , then every coupon has at least one goal. It is convenient to imagine the w many coupons as being located in an urn.

In a length n trial a set of n coupons is picked at random one by one, and all occuring goals are recorded. For any picked coupon some of its goals may have occured already and are not again taken into account. In a trial with replacement each coupon is put back into the urn after its goals have been ticked off. Thus at each moment every fixed coupon is drawn with probability 1 w . In a trial without replacement no drawn coupons are put back. Then necessarily n ≤ w. Again at each moment every coupon remaining in the urn has the same probability to be drawn (namely 1 r , where r is the number of coupons remaining). A trial is successful if all h goals show up, i.e., if each of the sets G i contains at least one of the coupons that have been drawn. We call a successful trial sharply successful if the h goals are only completed in the last draw.

The Generalized Coupon-Collector Problem (GCCP) is to calculate the expected length ℓ of a sharply successful trial. We shall use the notation ℓ = ℓ r (G) for a GCCP with replacement, and ℓ = ℓ nr (G) for a GCCP without replacement.

Coming back to Roulette, which serves as an example to illustrate our results, the coupons are the numbers 0, 1, . . . , 36, and they constitute the set W . The G i in this example are the sets of all red numbers, all black numbers, all even numbers, etc. As we have seen, all coupons have several properties, except for 0, which has none (so G is a proper subset of W in this case). Using the method of §4 it turns out that the expected length of a sharply successful trial in this GCCP with replacement is 54728027202913 7600186994400 ≈ 7.201.

If after each "drawing" one prevents the spinning wheel from delivering the same number again (so that we have a GCCP without replacement) the corresponding number is obviously smaller; in fact it is 65774035502891 10043104242600 ≈ 6.549.

Notice that we can also model our multipurpose coupons c i ∈ W with different drawing probabilities p i as follows (for simplicity we only focus on drawings with replacement ). If without great loss of generality all p i 's are rational, say p i = m i /(wM ), replace each c i by m i copies c ′ i , c ′′ i , • • • which all have exactly the same goals as c i . Let W ′ be the new wM -element set of coupons and let G ′ match G in the obvious way. Then ℓ nr (G ′ ) is the expected length of a sharply succesful trial with original coupons c i ∈ W if they were subject to the drawing probabilities p i .

There is a simple yet natural situation where the coupons in W already furnish (but do not "have") potentially different drawing probabilities. Namely, suppose that each c ∈ W has exactly one of h goals which we then refer to as its type, and that different coupons can have the same type. Then

G * = {G 1 , • • • , G h } is a partition of W and p i = |G i |/|W |
is the probability for drawing a type i coupon. This matches the "classic" Coupon-Collector Problem (CCP) except that in the latter framework there is no G * but simply an unbounded supply of coupons. Each belongs to exactly one of h types, the i-th type being drawn with probability p i . The expected length ℓ(p 1 , • • • , p h ) of a sharply successful trial is known to be [DB62, p.269]

ℓ(p 1 , . . . , p h ) = 1≤i≤h 1 p i - 1≤i≤j≤h 1 p i + p j + 1≤i<j<k≤h 1 p i + p j + p k -• • • ± 1 p 1 + • • • + p h . (1)
In particular, if

p 1 = p 2 = • • • = p h = 1 h (call this the homogeneous CCP) then (1) can be shown [Fel57, Example IX.3(d)] to simplify to ℓ 1 h , • • • , 1 h = hH(h), (2)
where

H(h) := 1 + 1 2 + • • • + 1
h is the harmonic number. For instance, setting h = 6 in (2) one finds that a die has to be thrown 14.7 times on average until all numbers have shown up. The CCP is very classical and has been studied by many authors from different perspectives, see for example [START_REF] Pólya | Eine Wahrscheinlichkeitsaufgabe in der Kundenwerbung[END_REF][START_REF] Flajolet | Birthday paradox, coupon collectors, caching algorithms and self-organizing search[END_REF][START_REF] Dawkins | Siobhan's problem: the coupon collector revisited[END_REF][START_REF] Pintacuda | Coupons collectors via the martingales[END_REF]. It can also be found in various textbooks, such as those of Feller [START_REF] Feller | An introduction to probability theory and its applications[END_REF] [START_REF] Boneh | The coupon-collector problem revisited-a survey of engineering problems and computational methods[END_REF] provide a survey with a focus on computational methods. Recent extensions can be found in [START_REF] Foata | Les nombres hyperharmoniques et la fratrie du collectionneur de vignettes[END_REF] and [START_REF] Adler | The coupon-collector's problem revisited[END_REF]. As an application, the CCP can be used for testing randomness [Fel57, Footnote 19, p. 59], [START_REF] Knuth | The art of computer programming[END_REF]3.3

.2.E].

Even though our setting is more general than the CCP, whose formula (1) is intimidating enough, the present article does not feature subtle probability arguments, but is rather based on counting transversals of set systems, exploiting an algorithm that has recently been introduced in [START_REF] Wild | Counting or producing all fixed cardinality transversals[END_REF]. The connection to coupon collecting is discussed in §2, and §3 actually deals with counting transversals. Surprisingly perhaps, our approach to the GCCP appeals more to the GCCP without replacement. Only afterwards in §4 we tackle the GCCP with replacement.

A numerical evaluation of our method pitted against the inclusion-exclusion approach (1), as well as further examples, follow in §5 and §6.

The GCCP without replacement

In this and the next section all trials are assumed to be without replacement. Our approach to the GCCP is mathematically straightforward; the main point is that there is an efficient way to realize it algorithmically, as will be explained in the next section.

We shall use the notation [h] := {1, 2, . . . , h} for positive integers h. Recall that G i ⊆ W is the set of coupons of the i-th goal (i ∈ [h]). The hypergraph (= set system) G = {G 1 , . . . , G h } fully determines all aspects of the GCCP. Specifically,

X ⊆ W is a transversal (or hitting set) of G if X ∩ G i = ∅ for all i ∈ [h].
Such a set X of coupons displays each goal at least once, and so each permutation of X corresponds to a successful trial. Conversely, each successful trial uses a set X of coupons that is a transversal of G. Therefore, if

τ k := number of k-element transversals of G
for some fixed k ∈ {0, 1, . . . , w}, then exactly k!τ k trials among the w(w -1) • • • (wk + 1) many length k trials are successful. Now let q k be the probability that a length k trial is successful. In particular q 0 = 0 and q w = 1, and generally

q k = k!τ k w(w -1) • • • (w -k + 1) = τ k w k . (3)
Note that

s k := q k -q k-1 (k ∈ [w]) (4)
is the probability that a length k trial is sharply successful. Therefore ℓ nr (G) can be found by calculating the numbers τ k :

Theorem 1 For drawings without replacement, the expected length of a sharply successful trial is

ℓ nr (G) = w k=1 ks k = w-1 k=0 (1 -q k ) = w - w-1 k=1 q k = w - w-1 k=1 τ k w k
.

(5)

Counting transversals

In this section all trials are still without replacement. In the previous section, we have seen that the GCCP can be reduced to the task of counting transversals, which will be illustrated by means of a simple example now. Consider a set W = {c 1 , . . . , c 8 } of eight coupons, each one of which serves between one and three goals from among G 1 , G 2 , G 3 , G 4 according to Table 1. For instance, the trials c 1 , c 3 , c 5 and c 6 , c 2 , c 8 , c 7 are successful. The first is sharply successful, the second is not. In order to calculate the expected length of a sharply successful trial, we put

G 1 := {G 1 , G 2 , G 3 , G 4 } and aim to count the τ k many k-element transversals of G 1 (k ∈ [8]). c 1 c 2 c 3 c 4 c 5 c 6 c 7 c 8 G 1 X X X G 2 X X X X G 3 X X X X G 4 X X X X X
Tab. 1: Toy problem with 8 coupons and 4 goals

In order to do so we shall encode the transversal hypergraph

Tr (G 1 ) := {X ⊆ W : X is transversal of G 1 }
in a compact way, i.e. not by listing the transversals one by one. This is the main idea behind the transversal e-algorithm that was recently introduced in [START_REF] Wild | Counting or producing all fixed cardinality transversals[END_REF]. We do not repeat the full details of its implementation here, but rather focus on its output only, which is a sequence of {0, 1, 2, e}-valued rows. Note first that each subset X ⊆ W can be encoded as a bitstring of length 8, where each 1 indicates an element of the set. For instance, the set {c 1 , c 3 , c 6 , c 7 } would be encoded as (1, 0, 1, 0, 0, 1, 1, 0). In order to obtain a more compact representation, we introduce additional symbols: 2 is a "don't care" symbol, which indicates that the corresponding entry can be 0 or 1. For example, consider the {0, 1, 2}-valued row (ignore the boldface for the moment)

r := (2, 1, 0, 2, 2, 1, 2, 2).
Each of the 2's stands for a 0 or a 1, so this row r encodes a total of 2 5 = 32 length 8 bitstrings (including, for example, (0, 1, 0, 1, 1, 1, 0, 0) and (1, 1, 0, 0, 1, 1, 0, 1)), or equivalently 32 subsets X ⊆ W . Because {c 2 , c 6 } ⊆ X for each X ∈ r, each X ∈ r is a transversal of G. Similarly, if r ′ := (2, 1, 0, 2, 2, 0, 2, 1), then all 16 members X ∈ r ′ contain c 2 and c 8 and are thus transversals of G. Note that the sets represented by r and r ′ are disjoint: all X ∈ r contain c 6 , while no X ∈ r ′ does. Using r and r ′ is clearly more efficient than listing 32 + 16 = 48 bitstrings individually, but one can compress things even more by introducing another symbol: by definition, a string of symbols ee • • • e (not necessarily on contiguous positions) means that any 0-1-pattern with at least one 1 is allowed. In other words, only 00 • • • 0 is forbidden. Now note that r and r ′ only differ in two positions, indicated by boldface digits. Putting ee in those two positions, we cover both r (all of whose elements contain c 6 and possibly also c 8 ) and r ′ (whose elements do not contain c 6 , but necessarily c 8 ). This gives us r ∪ r ′ = (2, 1, 0, 2, 2, e, 2, e).

(6)

It turns out that the whole transversal hypergraph Tr (G 1 ) can be written as a disjoint union of five such {0, 1, 2, e}-valued rows (Table 2), which are generated by the aforementioned e-algorithm. For instance, r 3 is the row in (6). Note that a row may contain several e-blocks, which are then notationally distinguished (writing e, e ′ or e 1 , e 2 , . . .) as in row r 5 .

It is shown in Theorem 3 of [START_REF] Wild | Counting or producing all fixed cardinality transversals[END_REF] how generally for an h-element hypergraph G ⊆ P([w]) its transversal hypergraph Tr (G) can be represented as a union of R disjoint {0, 1, 2, e}-valued rows in time O(Rh 2 w 2 ). As mentioned earlier, the details of the e-algorithm that performs this task can be found in [START_REF] Wild | Counting or producing all fixed cardinality transversals[END_REF] as well. Let us only emphasize that it does not make use of a merging process as we used to reduce r and r ′ to a single row in (6) (which only served to show that 0, 1, 2, e are more powerful than 0, 1, 2 alone), but rather generates the {0, 1, 2, e}-valued rows from scratch. By the disjointness of rows R is always bounded by N := |Tr (G)|, and in practice often R ≪ N . For instance, in our example R = 5 while N = 120 + 16 + 48 + 6 + 9 = 199 (see Table 2).

Once such a list of rows encoding all possible transversals has been generated, counting them is not difficult any more. Note again that the rows generated by the e-algorithm are mutually disjoint. For the for an arbitrary {0, 1, 2, e}-valued row r of length w, and any k ∈ [w], is only slightly more subtle than getting |r|, and can be done in time O(kw 2 log 2 w) [Wil13, Theorem 1]. One only needs to replace each 0 by a factor 1, each 1 by a factor x, each 2 by a factor 1 + x, and each e-block of length ℓ by (1 + x) ℓ -1 to obtain a polynomial associated with each row whose coefficients are the Card(r, k). For example, row r 1 gives us

pol(r 1 , x) = x(1 + x) 3 ((1 + x) 4 -1) = 4x 2 + 18x 3 + 34x 4 + 35x 5 + 21x 6 + 7x 7 + x 8 .
The full table that we obtain for our toy problem looks as follows: Having the τ k 's we can evaluate the probability q k of having a successful trial of length k by Formula (3). For example, we have q 2 = τ 2 / 8 2 = 7 28 = 1 4 . More generally we obtain the following table: q 1 q 2 q 3 q 4 q 5 q 6 q 7 q 8 0 1 4 37 56 9 10 55 56 1 1 1 Hence (5) gives

ℓ nr (G 1 ) = 8 -q 7 -• • • -q 2 -q 1 = 449 140 ≈ 3.2. ( 8
)
4 The GCCP with replacement

Without further mention all trials in this section are with replacement. Let t ′ n be the number of successful length n trials, i.e. trials where all goals of coupons have occured at some point (so t ′ 0 = 0). Thus

q ′ n := t ′ n w n (n ≥ 0) (9)
is the probability that a length n trial is successful, and

s ′ n := q ′ n -q ′ n-1 (n ≥ 1) (10)
is the probability that a length n trial is sharply successful. The expected length of a sharply successful trial is

ℓ r (G) = ∞ n=1 ns ′ n . ( 11
)
As to calculating the numbers t ′ n , observe that no matter how coupons c i are repeated in a length n trial, the underlying set of (distinct) coupons must be a k-element transversal X of G, for some k ≤ n. For a fixed k-element set of coupons X ⊆ W the number of length n trials with underlying set X equals the number of ways to distribute n distinct balls (corresponding to the positions in the trial) to k distinct buckets (corresponding to the coupons) in such a way that no bucket stays empty. It is well known that this number (the number of surjections from an n-element set to a k-element set) is k!S(n, k), where S(n, k) is the Stirling number of the second kind. Accordingly, recalling that τ k is the number of k-element transversals of G, we deduce that

t ′ n =    1! τ 1 S(n, 1) + 2! τ 2 S(n, 2) + • • • + n! τ n S(n, n), n ≤ w, 1! τ 1 S(n, 1) + 2! τ 2 S(n, 2) + • • • + w! τ w S(n, w), n > w. ( 12
)
Fortunately the infinite sum in (11) can be evaluated as a finite sum. Moreover, one can express it in terms of the probabilities q k that a length k-trial without replacement is successful. Recall from (3) that

τ k = q k w k .
Theorem 2 For drawings with replacement the expected length of a sharply successful trial is

ℓ r (G) = w w-1 k=0 1 -q k w -k = w H(w) - w-1 k=1 q k w -k = wH(w) - w-1 k=1 τ k w-1 k
.

Proof: Drawing with replacement yields an infinite sequence of coupons. If we ignore all repetitions and only keep the new coupons, i.e., the coupons that have not occured earlier in the sequence, we obtain a subsequence of distinct coupons. With probability 1, every coupon occurs eventually, so the subsequence will contain all w coupons, and by symmetry they can come in any order with the same probability 1/w!; hence, the subsequence of new coupons is the same as drawing without replacement.

If we draw with replacement we stop when we first have attained all goals, i.e, when the trial is sharply successful. Since repeated coupons do not help (or hinder), it is clear that we will always stop at a point when we get a new coupon. Moreover, by the argument above, the probability that we stop when we get the k-th new coupon is precisely the probability s k given in (4) that a trial with k drawings without replacement is sharply successful. The positions of the new coupons are, by symmetry, stochastically independent of the sequence of values of the new coupons. Hence, provided that we stop at the k-th new coupon, the expected number of coupons drawn equals the expected number e k of drawings required to get k distinct coupons (ignoring their values), which is known to be

e k = k i=1 w w + 1 -i .
See e.g. [START_REF] Feller | An introduction to probability theory and its applications[END_REF]Example IX.3(d)] for this well-known fact; the standard argument is that when we have got j distinct coupons, the probability that the next coupon is new is (wj)/w, and thus the expected waiting time for the next new coupon is w/(wj). Recalling that q 0 = 0 and q w = 1, we deduce:

ℓ r (G) = w k=1 s k e k = w k=1 (q k -q k-1 ) k i=1 w w + 1 -i = (q 1 -q 0 ) w w + (q 2 -q 1 ) w w + w w -1 + • • • + (q w -q w-1 ) w w + w w -1 + • • • + w 1 = w w (q w -q 0 ) + w w -1 (q w -q 1 ) + • • • + w 2 (q w -q w-2 ) + w 1 (q w -q w-1 ) = wH(w) -w w-1 k=1 q k w -k = w w-1 k=0 1 -q k w -k .
From τ k = q k w k , the rightmost formula in the Theorem follows. ✷

For instance, for our running example Theorem 2 yields ℓ r (G 1 ) = 59 15 ≈ 3.9 as opposed to ℓ nr (G 1 ) ≈ 3.2 from (8). Notice that ℓ r (G) = wH(w) if and only if all q k (k < w) are equal to 0, which is the classical case where each coupon has only one goal (and all these goals are distinct). The other extreme ℓ r (G) = w 1 w = 1 occurs if and only if all q k = 1 (1 ≤ k ≤ w), which means that every coupon fulfils every goal.

Remark 1

The key tool of our proof of Theorem 2 is the fact that q kq k-1 (the probability of a length k trial without replacement being sharply successful) is also the probability that a trial with replacement is sharply successful when the k-th distinct coupon is drawn. This fact can also be used to compute the variance (and in principle also higher moments) of the trial length: to this end, note that the expectation of the square of the number of coupons needed to collect k distinct coupons is (by the same argument as before, decomposing into k independent geometrically distributed random variables)

k i=1 (i -1)w (w + 1 -i) 2 + k i=1 w w + 1 -i 2 .
Now repeating the argument of the proof of Theorem 2 yields the following expression for the variance:

w-1 k=0 (1 -q k ) w(w + k) (w -k) 2 + 2w 2 w -k (H(w) -H(w -k)) -ℓ r (G) 2 .
In our toy example, this yields a variance of 836 225 ≈ 3.7. For drawings without replacement, the situation is much simpler, and the variance is

w-1 k=0 (2k + 1)(1 -q k ) -ℓ nr (G) 2 ,
which equals 18339 19600 ≈ 0.9 in our example. This ends Remark 1. Let us finally consider a related problem: how many goals will be fulfilled once n coupons have been drawn? Referring to Table 1, the probability that goal 1 does not belong to a randomly drawn coupon is a 1 = 5 8 . Similarly define a 2 , a 3 , a 4 , so a i = 1m i /w if goal i is served by m i coupons. Coupled to a random drawing of coupons, set the random variable X i := 1 if goal i comes up, and X i := 0 otherwise. Hence the expected value of X i in a length n trial is E n [X i ] = 1a n i . For drawing without replacement, the corresponding formula is

E n [X i ] = 1 - w-mi n w n = 1 - (w -m i )! (w -n)! (w -n -m i )! w! , interpreted as 1 if m i + n > w.
By linearity of expectation, one calculates that e n = h i=1 E n [X i ] is the expected number of goals gathered in a length n trial. For instance, e 4 ≈ 3.7 for drawing with replacement in our running example.

The nonhomogenous CCP: Pitting the e-algorithm against inclusion-exclusion

In the introduction, we gave the formula

ℓ(p 1 , . . . , p h ) = 1≤i≤h 1 p i - 1≤i≤j≤h 1 p i + p j + 1≤i<j<k≤h 1 p i + p j + p k -• • • ± 1 p 1 + • • • + p h .
for the expected length of a sharply successful trial with h single-purpose coupons whose probabilities are p 1 , p 2 , . . . , p h . Boneh and Hofri [BH97, p. 43] emphasize the computational difficulty to evaluate this formula as h increases, and then go on to use integration for approximation. Recall that for rational p i 's in the (classic) CCP, say One computes the numbers τ k = Card(r, k) (k ∈ [10]) as we have seen in §3 and from them ℓ r (G * ) according to Theorem 2. Table 3 compares the e-algorithm with the inclusion-exclusion approach (1) on instances (p 1 , . . . , p h ) of the particular but natural type

p 1 = 1
p 1 = 1 w , p 2 = 2 w , . . . , p h = h w hence w = 1 + • • • + h = h(h + 1) 2
which is uniquely defined by h (= first column in Table 3). As to inclusion-exclusion, we used a standard Gray-code in order to more economically generate the subsets of [h] one by one from their predecessors, and also used that for common denominator probabilities one can simplify the terms in (1); say

1 p i + p j + p k = 1 i w + j w + k w = w i + j + k .
The value of ℓ r (G * ) is rounded to 6 digits albeit Mathematica, provided with the numbers τ k (k ∈ [w]), delivered the exact value as a fraction of two very large integers. For instance h = 400 gives w = 80200 and 3108 sec of the 96272 sec total time were spent on plugging τ 1 , τ 2 , . . . , τ 80200 into the formula of Theorem 2. As is apparent, inclusion-exclusion (formula (1)) cannot compete. For the particular p i 's considered one can show [DB62, p.269] that ℓ r (G * ) is asymptotically equal to 4π √ 3 -6 h+1 2 as h → ∞. Already for h = 15 the latter gives the tight approximation 150.624 to the true (rounded) value 150.606.

Information spreading and the expected time to dominate a chess board

In many GCCP applications the goals of a coupon c are other coupons, namely those that c wishes to "influence" in some way. More succinctly, we may consider a graph G with vertex set W as a group of people whose friendship relations are reflected by the edges of G. Suppose members c ∈ W are phoned at random from outside W and told a piece of information. If c shares the news with all his friends, what is the expected number ℓ r (G) of phone calls necessary before the whole of W is informed? (The minimum number of phone calls necessary is called the domination number of G.) What is the analogous number ℓ nr (G) when nobody is phoned twice? The method presented in the previous sections can provide answers to these questions.

A nice illustrative example of the graph framework is the problem to determine the expected number ℓ nr (queens) of queens it takes when they are placed on a chessboard at random until the queens dominate the board, i.e., all 64 squares (coupons) are occupied or threatened. If occupied squares can still be drawn (without effect apart from increasing the trial's length), let ℓ r (queens) be the corresponding number. We also define ℓ nr (rooks), ℓ nr (kings), . . . in an analogous fashion. One obtains the following results (rounded to four decimals): If one does not consider a square occupied by a queen as threatened by her (after all, an unthreatened knight can capture her), the numbers ℓ nr (queens) and ℓ r (queens) grow to ℓ * nr (queens)= 12.7094 respectively ℓ * r (queens) = 16.3149. Similar GCCP applications e.g. to trading card games such as Magic: The Gathering, and much more, are conceivable. One may also further want to generalize to problems where a certain number α i of coupons in class G i needs to be collected to fulfil the task. We hope to do so in a future publication.

Fig. 1 :

 1 Fig. 1: Roulette seen as a multi-goal coupon collector's problem.

c

  1 c 2 c 3 c 4 c 5 c 6 c 7 c 8 e ′ |r 5 | = 9 Tab. 2: Tr (G1) as disjoint union of {0, 1, 2, e}-valued rows example in Table 2, we have e.g. r 3 ∩ r 4 = ∅ because each X ∈ r 3 has X ∩ {c 6 , c 8 } = ∅, and each Y ∈ r 4 has Y ∩ {c 6 , c 8 } = ∅. Accordingly, it suffices to count the transversals represented by each row individually. Each 2 contributes a factor 2, and each e-block of length ℓ yields a factor 2 ℓ -1. Thus for example |r 3 | = 2 3 • (2 2 -1) = 48 or |r 5 | = (2 2 -1) • (2 2 -1) = 9. Calculating Card(r, k) := |{X ∈ r : |X| = k}| (7)

  instance, the transversals counted by Card(r 5 , 4) = 4 are {c 1 , c 4 , c 5 , c 7 }, {c 1 , c 4 , c 5 , c 8 }, {c 1 , c 4 , c 7 , c 8 }, and {c 1 , c 5 , c 7 , c 8 }.

ℓ

  nr (queens) = 11.8402 ℓ r (queens) = 15.2945 ℓ nr (rooks) = 15.0045 ℓ r (rooks) = 17.1308 ℓ nr (kings) = 30.4091 ℓ r (kings) = 42.4282

  Because the sets in G * are disjoint, we can do with a single {0, 1, 2, e}-valued row r = (1, e 2 , e 2 , e 3 , e 3 , e 3 , e 4 , e 4 , e 4 , e 4 ). Total time in seconds taken when computing ℓr(G * ) by the e-algorithm (exclusion) and by the inclusionexclusion algorithm.

	h	ℓ r (G * ) exclusion incl-excl.
	10 68.9846		0		0.2
	15 150.606		0		7.7
	27 474.463		0.3		43193
	50 1600.38		4.1		-
	100 6338.75		72		-
	150 14215.1		455		-
	200 25229.5		1829		-
	400 100667		96272		-
	Tab. 3:
		10	, p 2 =	2 10	, p 3 =	3 10	, p 4 =	4 10	,
	our approach uses W = [10] and the partition
	G * = {{1}, {2, 3}, {4, 5, 6}, {7, 8, 9, 10}}.

S. W. was supported financially by the National Research Foundation of South Africa under grant number 70560. 1365-8050