Bounds for Optimal Coverings

Carlos Gustavo T. de A. Moreira^{a} and Yoshiharu Kohayakawa^{b}

aIMPA – Estrada Dona Castorina 110, 22460–320 Rio de Janeiro, RJ, Brazil –

e-mail: gugu@impa.br

bInstituto de Matemática e Estatística, USP – Rua do Matão 1010, 05508–090 São Paulo, SP, Brazil – e-mail: yoshi@ime.usp.br

Abstract

We give bounds for optimal coverings of finite sets by elements of regular families of subsets, and show that both upper and lower bounds are asymptotically sharp for some families of examples.

Key words: Coverings, set systems, hypergraphs, the probabilistic method

1 Introduction

We study coverings of finite sets by subsets belonging to a regular family. By an (a, b)-regular family of subsets of a finite set F, or an (a, b)-regular hypergraph on F, we mean a family C for which there are integers a and b such that for each C ∈ C we have |C| = a, and, for each x ∈ F, we have deg(x) = b, where as usual deg(x) = |{C ∈ C | x ∈ C}|. Thus (a, b)-regular families are what are sometimes called a-uniform, b-regular hypergraphs. The problem of constructing small covers for such hypergraphs and of estimating the minimum possible size for such covers are common, and appear in many contexts, as in the study of covering codes (see [3]), in particular, in football pool problems (see [6]), in the study of vertex covers of graphs, and others. Somewhat surprisingly, some sharp results are known for problems of this kind, see, e.g., [1], [4, Theorem 8.11], [5], and [9]. In this paper, we prove another result that

⋆ Partially supported by MCT/FINEP/CNPq (ProNEx Projects 416/96 and 107/97), FAPESP (Proc. 96/04505–2), CNPq (Proc. 300647/95–6, 300334/93–1, and 468516/2000–0), and by FAPERJ. ⋆⋆The authors gratefully acknowledge the careful work of the referees.

Preprint submitted to Elsevier Preprint 9 July 2003

shows that one may require strong regularity conditions and still obtain hypergraphs that behave asymptotically ‘badly’ with respect to the size of covers that they admit.

Let us now introduce the extremal parameter that we are interested in. If C is a hypergraph on F, we let α(F, C) be the minimal integer r for which there exist C_{1}, …, C_{r} ∈ C such that ⋃_{1≤j≤r} C_{j} = F. We are concerned with estimating the extremal values of α(F, C).

This paper is organized as follows. In Sections 2 and 3, we prove our upper and lower bounds for α(F, C). Our proof for the existence of systems C with large covering number α(F, C) is probabilistic; in Section 3.2, we briefly discuss a construction of Alon [1] based on finite fields and character sums. In Section 4 we mention the dual problem of estimating the packing number of hypergraphs. We conclude with some remarks and an open problem.

2 Upper bounds

Our first result is a slight improvement of classical results by Johnson, Stein, and Lovász (see [7], [8], and [10]). Let us say that a family C of subsets of a set F is (a, b)-semiregular if |C| ≤ a for all C ∈ C and deg(x) ≥ b for all x ∈ F.

Proposition 1 Let a and b be positive integers and suppose C is an (a, b)- semiregular family on an n-element set F. Let m = |C|. Then, for any positive integer ℓ′,

\frac{n}{a} ≤ α(F, C) ≤ \frac{ln(mℓ′/bn)}{ln(1 − b/m)} + \frac{m}{b} ∑_{1≤j≤ℓ′} \frac{1}{j}.  (1)

In particular, we have α(F, C) ≤ f(a, b, m, n), where we let ℓ = ⌈bn/m⌉ and

f(a, b, m, n) = \begin{cases}\frac{n}{ℓ} + \frac{m}{b} ∑_{j=2}^{ℓ} \frac{1}{j} & if b ≤ m/\sqrt{n} \\ \frac{m}{b} (ln (\frac{bn}{m}) + γ) − \frac{1}{2} ln (\frac{b^{2}n}{m^{2}}) + \frac{1}{2} & if b > m/\sqrt{n}. \end{cases} (2)

Moreover, if b ≤ m/\sqrt{n}, we have

f(a, b, m, n) ≤ \frac{n}{a} + \frac{m}{b} ∑_{2≤j≤a} \frac{1}{j} < \frac{m}{b}(ln(a + 1) + γ),  (3)

where γ = 0.5772156649 … is Euler’s constant.

We prove Proposition 1 in Section 2.1 below.

Corollary 2 Let F be an n-element set and C an (a, b)-regular hypergraph on F. Let also ℓ = min{a, ⌈n/a⌉}. Then

⌈\frac{n}{a}⌉ ≤ α(F, C) ≤ \frac{ln(a/ℓ)}{ln \frac{1}{1 − a/n}} + \frac{n}{a} ∑_{j=1}^{ℓ} \frac{1}{j}

< \frac{n}{a}( ln(a + 1) + γ) − \frac{1}{2} ln \frac{a}{ℓ} + \frac{1}{2}. (4)

Our main result, given in Section 3 (see Proposition 6), shows that the estimates for α(F, C) above are asymptotically sharp for certain regular families of subsets of finite sets.

2.1 Proof of Proposition 1

We state and prove two auxiliary lemmas first. For the remainder of this section, we fix an (a, b)-semiregular family C on a set F, where a and b are positive integers. We also let n = |F | and m = |C|. Our first lemma follows from a well known double counting argument.

Lemma 3 We have am ≥ bn. Moreover, given any A ⊂ F, there is C ∈ C such that |C ∩ A| ≥ (b/m)|A|.

PROOF. Indeed, for any B ⊂ F, we have

ma ≥ ∑_{C∈C} |C ∩ B| = ∑_{C∈C} ∑_{x∈B} χ_{C}(x) = ∑_{x∈B} ∑_{C∈C} χ_{C}(x) = ∑_{x∈B} deg(x) ≥ b|B|,

where, as usual, χ_{C} is the characteristic function for the set C, that is, χ_{C}(x) = 1 if x ∈ C and χ_{C}(x) = 0 otherwise. Taking B = F, we obtain am ≥ nb, which proves the first inequality in our lemma. Taking B = A, we deduce that ∑_{C∈C} |C ∩ A| ≥ b|A|, which implies that there is a set C ∈ C for which |C ∩ A| ≥ (b/|C|)|A|, as required. □

An immediate corollary to Lemma 3 is the following.

Corollary 4 For each positive integer k, there are C_{1}, …, C_{k} ∈ C such that

|F \ ⋃_{1≤i≤k} C_{i}| ≤ n (1 − \frac{b}{m})^{k} .  (5)

A finer corollary to Lemma 3 is as follows.

Corollary 5 It is possible to cover any A ⊂ F with at most

\frac{r}{ℓ} + \frac{m}{b} ∑_{2≤j≤ℓ} \frac{1}{j} ≤ \frac{m}{b} ∑_{1≤j≤ℓ} \frac{1}{j}  (6)

members of C, where ℓ = ⌈br/m⌉ and r = |A|.

PROOF. We can cover A by C_{1}, C_{2}, … ∈ C so that, for each i, the cardinality of C_{i}∩(A\⋃_{1≤j<i} C_{j}) is as large as possible, given C_{1}, …, C_{i−1}. For 1 ≤ s ≤ a, let k_{s} be the number of sets C_{i} in this covering such that |C_{i}∩(A\⋃_{1≤j<i} C_{j})| = s. A little thought shows that Lemma 3 implies that

k_{1} ≤ \frac{m}{b}, k_{1} + 2k_{2} ≤ \frac{2m}{b}, …, k_{1} + 2k_{2} + ⋯ + sk_{s} ≤ \frac{ms}{b}  (7)

for all s. Moreover, clearly,

k_{1} + 2k_{2} + ⋯ + sk_{s} ≤ r  (8)

for all s as well. Of course

k_{1} + 2k_{2} + ⋯ + ak_{a} = r.  (9)

Note also that a ≥ ℓ. From (7)–(9) it thus follows that

k_{1} + ⋯ + k_{a}

= \frac{1}{a}(k_{1} + 2k_{2} + ⋯ + ak_{a}) + ∑_{1≤j<a} \frac{1}{j(j + 1)}(k_{1} + 2k_{2} + ⋯ + jk_{j})

≤ \frac{r}{a} + \frac{m}{b} ∑_{1≤j<ℓ} \frac{1}{j + 1} + r ∑_{ℓ≤j<a} \frac{1}{j(j + 1)}

= \frac{r}{ℓ} + \frac{m}{b} ∑_{1≤j<ℓ} \frac{1}{j + 1} ≤ \frac{m}{b} ∑_{1≤j≤ℓ} \frac{1}{j},

as required. □

We may finally prove Proposition 1.

PROOF. (Proof of Proposition 1) In the case b ≤ m/\sqrt{n}, the result in (2) follows from Corollary 5 by taking r = n. The first inequality in (3) follows from

\frac{n}{ℓ} = \frac{n}{a} + ∑_{ℓ≤j<a} \frac{n}{j(j + 1)} ≤ \frac{n}{a} + \frac{m}{b} ∑_{ℓ≤j<a} \frac{ℓ}{j(j + 1)} ≤ \frac{n}{a} + \frac{m}{b} ∑_{ℓ≤j<a} \frac{1}{j + 1},

and hence

\frac{n}{ℓ} + \frac{m}{b} ∑_{2≤j≤ℓ} \frac{1}{j} ≤ \frac{n}{a} + \frac{m}{b} ∑_{2≤j≤a} \frac{1}{j}.

The second inequality in (3) is clear.

In general, given a positive integer ℓ′, we claim that the upper bound in (1) holds. To prove this claim, take r′ = mℓ′/b, and let

\frac{ln(mℓ′/bn)}{ln(1 − b/m)} = p + c,  (10)

where p is an integer and 0 ≤ c < 1. Let k = p + 1, and set

r = ⌊n (1 − \frac{b}{m})^{k}⌋ ≤ r′.  (11)

We now apply Corollary 4 with the above value of k; this leaves us with an uncovered set A of cardinality at most r. We then apply Corollary 5 with ℓ = ⌈br/m⌉ ≤ ⌈br′/m⌉ = ℓ′ to cover A. Using (10), (11), and the fact that the left-hand side of (6) is increasing in ℓ for ℓ ≥ br/m, we deduce that this application of Corollary 5 uses at most

\frac{r}{ℓ} + \frac{m}{b} ∑_{2≤j≤ℓ} \frac{1}{j} ≤ \frac{r}{ℓ′} + \frac{m}{b} ∑_{2≤j≤ℓ′} \frac{1}{j} ≤ \frac{1}{ℓ′} n (1 − \frac{b}{m})^{p+c+1−c} + \frac{m}{b} ∑_{2≤j≤ℓ′} \frac{1}{j}

≤ \frac{n}{ℓ′} (\frac{mℓ′}{bn} ) (1 − \frac{b}{m})^{1−c} + \frac{m}{b} ∑_{2≤j≤ℓ′} \frac{1}{j}

= \frac{m}{b} (1 − \frac{b}{m})^{1−c} + \frac{m}{b} ∑_{2≤j≤ℓ′} \frac{1}{j} (12)

members of C. Therefore, in this covering we have used in total at most

(p + 1) + \frac{m}{b} (1 − \frac{b}{m})^{1−c} + \frac{m}{b} ∑_{2≤j≤ℓ′} \frac{1}{j}

= \frac{ln(mℓ′/bn)}{ln(1 − b/m)} + (1 − c) + \frac{m}{b} (1 − \frac{b}{m})^{1−c} + \frac{m}{b} ∑_{2≤j≤ℓ′} \frac{1}{j} (13)

members of C. The function ϕ(c) = 1 − c + (m/b)(1 − b/m)^{1−c} is convex, as may be seen by computing its second derivative, and hence its maximum is ϕ(0) = ϕ(1) = m/b. Therefore (13) is bounded by

\frac{ln(mℓ′/bn)}{ln (1 − b/m)} + \frac{m}{b} ∑_{1≤j≤ℓ′} \frac{1}{j},

as required.

In order to prove the inequality α(F, C) ≤ f(a, b, m, n) in the case b > m/\sqrt{n}, we just take ℓ′ = ⌊m/b⌋ and apply the above inequality.

Some calculations complete the proof. The two main ingredients in these calculations are the inequalities

∑_{1≤r≤k} \frac{1}{r} − ln k − γ < \frac{1}{2k} − \frac{1}{12k(k + 1)},

which is valid for every positive integer k, and

−\frac{1}{ln(1 − x)} < \frac{1}{x} − \frac{1}{2},

valid for all 0 < x < 1. □

2.2 Proof of Corollary 2

Since C is an (a, b)-regular family, we have ma = nb. We take ℓ′ = ℓ in Proposition 1. Note that, then, the right-hand side of (1) becomes

\frac{ln(a/ℓ)}{ln \frac{1}{1 − a/n}} + \frac{n}{a} ∑_{1≤j≤ℓ} \frac{1}{j}.  (14)

Therefore, we shall be done if we prove the last inequality in (4). Consider first the case in which b > m/\sqrt{n}. Note that, then, we have ℓ = min\{a, ⌈n/a⌉\} = ⌈n/a⌉, and hence ℓ ≥ n/a. This implies that ln b^{2}n/m^{2} = ln a^{2}/n ≥ ln a/ℓ, and hence, by the second bound in (2), we have that (14) is at most

\frac{n}{a}(ln a + γ) − \frac{1}{2} ln \frac{a}{ℓ} + \frac{1}{2}.

Let us now consider the case in which b ≤ m/\sqrt{n}. Then ℓ = a. Notice that, moreover, ⌈bn/m⌉ = bn/m = a. Therefore the first bound in (2) becomes

\frac{n}{a} + \frac{n}{a} ∑_{2≤j≤a} \frac{1}{j} = \frac{n}{a} ∑_{1≤j≤a} \frac{1}{j} < \frac{n}{a}(ln(a + 1) + γ).

This completes the proof of the second inequality in (4), and Corollary 2 follows.

3 Lower bounds

We work with families of translations of a-element subsets of ℤ/nℤ.

If A = \{¯0, ¯1, …, \overline{a − 1}\} ⊂ ℤ/nℤ and C = \{A + t | t ∈ ℤ/nℤ\}, where A + t = {x + t | x ∈ A}, then α(ℤ/nℤ, C) = ⌈n/a⌉.

In the other direction, we have the following proposition.

Proposition 6 There is a_{0} ∈ ℕ such that if n > a ≥ a_{0} then, for some A ⊂ F := ℤ/nℤ with |A| = a, the family C = {A + t | t ∈ ℤ/nℤ} is such that

α(F, C) > k_{0} = (1 − \frac{12 ln ln a}{ln a}) \frac{ln a}{ln \frac{1}{1 − a/n}}

> (1 − \frac{12 ln ln a}{ln a}) (\frac{n}{a} − 1) ln a. (15)

An interesting feature of Proposition 6 is that it claims the existence of uniform, regular hypergraphs with large α. More importantly, the parameters n > a are free and (15) gives good estimates regardless of the relation between them. The reader is invited to compare the bounds in (4) and (15) for the cases in which (i) a ∼ ln n, (ii) a ∼ n/ ln n, and (iii) a ∼ n/2. In the course of answering a question of Tuza, Alon [1] obtained sharp bounds for case (ii), although, strictly speaking, the hypergraphs in [1] are not precisely a-uniform (the hyperedges have average cardinality a). We also observe that, in Proposition 6 above, for simplicity, we restrict ourselves to (a, b)-regular hypergraphs with a = b.

3.1 Proof of the lower bound

We now prove Proposition 6. The proof is split into two cases, according to the size of a. We deal with the case in which a is large first; the other case will require an additional idea.

3.1.1 Large a

Here, we suppose that a ≥ n/(ln n)^{3}. We consider all the a-element subsets of ℤ/nℤ, taken with equal probability. Let us estimate the probability that such a set A has k translations that cover F, where k is a given positive integer, i.e., let us estimate the probability p(n, a, k) that there should exist t_{1}, …, t_{k} ∈ ℤ/nℤ such that (A + t_{1}) ∪ ⋯ ∪ (A + t_{k}) = ℤ/nℤ. Note that 1 − p(n, a, k) is the probability that (A + t_{1}) ∪ ⋯ ∪ (A + t_{k}) ≠ ℤ/nℤ for any t_{1}, …, t_{k} ∈ ℤ/nℤ, i.e., (A^{c} + t_{1}) ∩ ⋯ ∩ (A^{c} + t_{k}) ≠ ∅ for any t_{1}, …, t_{k} ∈ ℤ/nℤ. Observe that, given t_{1}, …, t_{k} ∈ ℤ/nℤ, we have (A^{c} + t_{1}) ∩ ⋯ ∩ (A^{c} + t_{k}) ≠ ∅ if and only if there is x ∈ ℤ/nℤ such that {x − t_{1}, …, x − t_{k}} ⊂ A^{c}.

Fix T = {t_{1}, …, t_{k}} ⊂ ℤ/nℤ.

Claim 7 Set r = ⌈n/k^{2}⌉. There exist x_{1}, …, x_{r} ∈ ℤ/nℤ such that the sets B_{i} = x_{i} − T = {x_{i} − t_{1}, …, x_{i} − t_{k}} (1 ≤ i ≤ r) are pairwise disjoint.

PROOF. To prove our claim, take x_{1} = 0, and suppose that we have chosen x_{1}, …, x_{s}, with s < n/k^{2}, such that B_{1}, …, B_{s} are pairwise disjoint. Since s < n/k^{2}, clearly U = ⋃_{1≤i≤s}(x_{i} − T) has fewer than n/k elements. Thus the average cardinality of the intersection of U with x − T, for x ∈ ℤ/nℤ, is strictly smaller than one, whence there is x_{s+1} ∈ ℤ/nℤ such that x_{s+1} − T is disjoint from U. Our claim thus follows by induction. (See also Section 4.) □

Let us now proceed with the proof of our proposition. For any fixed set T = {t_{1}, …, t_{k}}, the probability that x − T ⊂ A^{c} for some x ∈ ℤ/nℤ is at least the probability that x_{j} − T ⊂ A^{c} for some j ∈ [r] := {1, …, r}, where the x_{j} (1 ≤ j ≤ r) are fixed and are as given by our claim. This latter probability is 1 − p̃(n, a, k, r), where p̃(n, a, k, r) is the probability that x_{j} − T ⊄ A^{c} for each j ∈ [r]. To estimate p̃(n, a, k, r), we consider random subsets Ã ⊂ ℤ/nℤ constructed as follows: let y ∈ Ã with probability a/n, independently for all y ∈ ℤ/nℤ. The probability that Ã has m elements is \binom{n}{m}(a/n)^{m}(1 − a/n)^{n−m}, which is maximal for m = a, so the probability that |Ã| = a is at least 1/(n+1). With this probability distribution, the events B_{j} = x_{j} −T ⊄ Ã^{c} (j ∈ [r]) are independent (because the sets B_{j} are pairwise disjoint), and the probability of each of these events is 1 − (1 − a/n)^{k}. Hence the probability that B_{j} ⊄ Ã^{c} for all j ∈ [r] is (1 − (1 − a/n)^{k})^{r}. So we have

p̃(n, a, k, r) = ℙ (∀j ∈ [r] we have x_{j} − T ⊄ Ã^{c} | |Ã| = a)

≤ (n + 1) ℙ(∀j ∈ [r] we have x_{j} − T ⊄ Ã^{c}) = (n + 1) (1 − (1 − \frac{a}{n})^{k})^{r} ,

and hence p(n, a, k) is at most

\binom{n}{k}p̃(n, a, k, r) ≤ \binom{n}{k}(n + 1) (1 − (1 − \frac{a}{n})^{k})^{r} ≤ n^{k+1} (1 − (1 − \frac{a}{n})^{k})^{r} .

(16)

Let k = −β ln a/ ln(1 − a/n) ≤ β(n/a) ln n, where β ≤ 1. We have that the right-hand side of (16) is n^{k+1} (1 − a^{−β})^{r}, which is less than

n^{1+β ln^{4} n} exp (−\frac{a^{−β}n}{k^{2}}) < exp (−\frac{a^{2−β}}{β^{2}n ln^{2} n} + ln n (1 + ln^{4} n)) .

One may check that if β ≤ (1 − 12(ln ln a)/ ln a), then a^{2−β}/β^{2}n ln^{2} n ≥ ln^{6} n for large n.

Since ln^{6} n ≫ ln n(1 + ln^{4} n), we have p(n, a, k) ≪ 1. Therefore there is A ⊂ ℤ/nℤ with |A| = a such that (A + t_{1}) ∪ ⋯ ∪ (A + t_{k}) ≠ ℤ/nℤ for any t_{1}, …, t_{k} ∈ ℤ/nℤ. This implies that, for some A ⊂ ℤ/nℤ with |A| = a, we have α(F, C) > k_{0}, where k_{0} is as in (15). This completes the proof of Proposition 6 in the case in which a ≥ n/(ln n)^{3}.

3.1.2 Small a

We now deal with the case in which a is ‘small’, that is, a < n/(ln n)^{3}. Let

b = ⌈a(ln a + 1)⌉, r = ⌈ln a⌉, ε = \frac{1}{r}, δ = \frac{10 ln ln a}{ln a},  (17)

and

k = ⌈\frac{1 − δ}{1 + ε}r(ln a)^{2}⌉ .  (18)

We shall make use of the following claim, to be proved later (see §3.1.2.1).

Claim 8 There exist 0 ≤ y_{i} < b (1 ≤ i ≤ a) so that if we let A_{0} = \{\overline{y}_{1}, …, \overline{y}_{a}\} ⊂ \{\overline{0}, \overline{1}, …, \overline{b − 1}\} ⊂ ℤ/rbℤ, then

(A_{0} + t_{1}) ∪ ⋯ ∪ (A_{0} + t_{k}) ≠ ℤ/rbℤ

for all t_{1}, …, t_{k} ∈ ℤ/rbℤ.

We now prove Proposition 6 for a < n/(ln n)^{3} assuming Claim 8. Let ℓ = ⌊n/(r + 1)b⌋, and let y_{i} (1 ≤ i ≤ a) be as in Claim 8 above. Put A_{0} = \{\overline{y}_{1}, …, \overline{y}_{a}\} ⊂ ℤ/rbℤ, and let A = \{y_{1} mod n, …, y_{a} mod n\} ⊂ ℤ/nℤ. We claim that

(A + s_{1}) ∪ ⋯ ∪ (A + s_{m}) = ℤ/nℤ  (19)

implies that m > ℓ(k + 1). To prove this claim, suppose (19) holds for some s_{1}, …, s_{m} ∈ ℤ/nℤ. For 0 ≤ j < ℓ, let

B_{j} = {jb(r + 1) + q | 0 ≤ q < rb} and I_{j} = {i ≤ m | (A + s_{i}) ∩ B_{j} ≠ ∅}.

The sets I_{j} are pairwise disjoint, since the diameter of A + s_{i} is at most b, and the distance between B_{j} and B_{j+1} is b + 1. Moreover, each I_{j} must have at least k + 1 elements, since

⋃_{i∈I_{j}}(A + s_{i}) ⊃ B_{j}

implies that

⋃_{i∈I_{j}}(A_{0} + \overline{s}_{i}) = ℤ/rbℤ,

which, by the choice of A_{0} = \{\overline{y}_{1}, …, \overline{y}_{a}\}, implies that |I_{j}| > k.

To finish the proof we just notice that

ℓ(k + 1) = ⌊\frac{n}{(r + 1)b}⌋ (⌈\frac{1 − δ}{1 + ε}r(ln a)^{2}⌉ + 1)

> (\frac{n}{(r + 1)b} − 1) \frac{1 − δ}{1 + ε}(ln a)^{3} > \frac{n}{b(r + 1)}(ln a)^{3} (1 − \frac{11 ln ln a}{ln a})

> \frac{n}{a}(ln a) (1 − \frac{12 ln ln a}{ln a}) ≥ (1 − \frac{12 ln ln a}{ln a}) \frac{ln a}{ln \frac{1}{1 − a/n}} ,

for large enough a. □

3.1.2.1 Proof of Claim 8. In order to prove Claim 8, we consider a random subset A_{0} of \{\overline{0}, \overline{1}, …, \overline{b − 1}\}, with each element present in A_{0} independently with probability a/b. The probability that A_{0} has m elements is \binom{b}{m}(a/b)^{m}(1 − a/b)^{b−m}, which is maximal for m = a. Therefore, the probability that such a set A_{0} has a elements is at least 1/(b + 1). As before, we shall condition on the event |A_{0}| = a later in the proof.

Let us fix t_{1}, …, t_{k} and let us estimate from above the probability that

(A_{0} + t_{1}) ∪ ⋯ ∪ (A_{0} + t_{k}) = ℤ/rbℤ.  (20)

Put T = {t_{1}, …, t_{k}}, and observe that (20) occurs if and only if for all x ∈ ℤ/rbℤ, the set x − T = {x − t_{1}, …, x − t_{k}} meets A_{0}. Let

s = ⌈\frac{ε}{1 + ε}rb⌉ and s_{0} = ⌈\frac{s}{k^{2}} ⌉ .  (21)

We now prove the following two facts (cf. Claim 7):

(*) There are x_{1}, …, x_{s} such that, for each i, we have

|(x_{i} − T) ∩ \{\overline{0}, \overline{1}, …, \overline{b − 1}\}| ≤ (1 + ε)\frac{k}{r} .

. (**) There are x̃_{1}, …, x̃_{s_{0}} ∈ {x_{1}, …, x_{s}} such that the sets x̃_{j} −T (1 ≤ j ≤ s_{0})

are pairwise disjoint.

To prove (*), it suffices to observe that the average number of elements in (x − T) ∩ \{\overline{0}, \overline{1}, …, \overline{b − 1}\} (x ∈ ℤ/rbℤ) is k/r. The proof of (**) is similar to the proof of Claim 7: suppose we have x̃_{1}, …, x̃_{s_{1}} ∈ {x_{1}, …, x_{s}} such that the sets x̃_{j} − T (1 ≤ j ≤ s_{1}) are pairwise disjoint, but s_{1} < s/k^{2}. Then

| ⋃_{1≤j≤s_{1}}(x̃_{j} − T)| = s_{1}k < \frac{s}{k} .  (22)

If we select x_{i} ∈ {x_{1}, …, x_{s}} uniformly at random, then the probability that a fixed element z in ℤ/rbℤ belongs to x_{i} − T is at most k/s, because k = |T | translates of T contain z. Because of (22), the expected cardinality of

(x_{i} − T) ∩ ⋃_{1≤j≤s_{1}}(x̃_{j} − T)

is strictly smaller than 1. Therefore the sequence x̃_{1}, …, x̃_{s_{1}} may be extended with a new element x_{i} ∈ {x_{1}, …, x_{s}}. This completes the proof of (**).

For the remainder of the proof, we concentrate our attention on the x̃_{j} in (**). One may easily check that the probability that (x̃_{j} − T) ∩ A_{0} ≠ ∅ occurs for all 1 ≤ j ≤ s_{0} is at most

(1 − (1 − \frac{a}{b})^{(1+ε)k/r})^{s_{0}} .

Therefore the probability that, for some T = {t_{1}, …, t_{k}} ⊂ ℤ/rbℤ, we have (x̃_{j} − T) ∩ A_{0} ≠ ∅ for all 1 ≤ j ≤ s_{0}, conditioned on the event |A_{0}| = a, is at most

(b + 1)(rb)^{k} (1 − (1 − \frac{a}{b})^{(1+ε)k/r})^{s_{0}} .  (23)

We now estimate (23) in parts. In the calculations below, we tacitly assume that a is larger than a suitable constant. Since 1 − a/b ≥ 1 − 1/(ln a + 1), we have

(1 − \frac{a}{b})^{(1+ε)k/r} ≥ exp (−(1 + ε)\frac{k}{r(ln a)}) .  (24)

We have

(1 + ε)\frac{k}{r(ln a)} ≥ (1 − δ) ln a.  (25)

Putting together (24) and (25), we have

(1 − (1 − \frac{a}{b})^{(1+ε)k/r})^{s_{0}} ≤ (1 − a^{−1+δ})^{s_{0}} ≤ exp (−a^{−1+δ} \frac{εrb}{(1 + ε)k^{2}} ) . (26)

Very generously, we have rb/k^{2} ≥ a/3(ln a)^{4}. Therefore, again generously, we have

a^{−1+δ} \frac{εrb}{(1 + ε)k^{2}} ≥ \frac{a^{δ}}{7(ln a)^{5}} .  (27)

On the other hand, a crude estimate gives

(b + 1)(rb)^{k} ≤ exp (4(ln a)^{4}) .  (28)

Putting together (26), (27), and (28), we see that the quantity in (23) is bounded from above by

exp (−\frac{a^{δ}}{7(ln a)^{5}} + 4(ln a)^{4}) .  (29)

Because of our choice of δ (see (17)), we have that a^{δ} = (ln a)^{10} ≫ (ln a)^{9} as a → ∞, and hence the quantity in (29) is < 1 for any large enough a. We conclude that the probability that A_{0} will do in Claim 8 is positive, and hence the claim is proved. □

3.2 Constructive lower bounds

Recall that we prove the existence of systems C with large α(F, C) by taking F = ℤ/nℤ and considering translates A + t (t ∈ ℤ/nℤ) for suitable random sets A ⊂ ℤ. As already observed by Alon [1], if we take n to be a prime power q and let A ⊂ F = GF(q) be the set of squares in GF(q), then

C = {A + t | t ∈ GF(q)}

is an (a, a)-regular system for a = (q − 1)/2 and

α(F, C) ≥ (\frac{1}{2} − o(1)) lg q,  (30)

where we write lg for the logarithm to the base 2. The bound in (30) follows from the following result, which we quote from [2] (see Lemma 9, Chapter 13) without proof. Let χ be the quadratic character on GF(q), so that χ(x) = x^{(q−1)/2} (x ∈ GF(q)). We have χ(x) ∈ {±1, 0}, with χ(x) = 0 if x = 0 and χ(x) = 1 if and only if x is a square in GF(q) \ {0}.

Lemma 9 If T ⊂ GF(q) and k = |T |, then

|q − ∑_{x∉T} ∏_{t∈T} (1 − χ(x − t)) | ≤ ((k − 2)2^{k−1} + 1) q^{1/2} + k2^{k−1}. (31)

Lemma 9 is in fact a consequence of a well known estimate of Weil for character sums (see [2]). To deduce (30) from Lemma 9, let T ⊂ GF(q) be an arbitrary set with k = |T | = ⌊(1/2) lg q − lg lg q⌋. The element x ∈ GF(q) will not be covered by the translates A + t (t ∈ T) if and only if x − T fails to meet A, that is, x − t is not a square for any t ∈ T. Now, the number of such x is

2^{−k} ∑_{x∉T} ∏_{t∈T} (1 − χ(x − t)) .

Since by the choice of k we have

2^{−k}q > \frac{1}{2}(k − 2)q^{1/2} + 2^{−k}q^{1/2} + \frac{k}{2},

the existence of such an x follows from (31).

Finally, let us observe that our lower bound k_{0} in Proposition 6 for the case in which a = n/2 (suppose n even for simplicity) is

k_{0} = (1 − \frac{12 ln ln n}{ln n}) lg n.

Furthermore, the upper bound for α(F, C) in Corollary 2 for this case is lg n+1. Therefore Alon’s construction is off only by a factor of 2.

4 Packings

We briefly consider the problem of finding large packings in regular families. Suppose C is a family of subsets of a set F. Let β(F, C) be the maximal integer r for which there exist pairwise disjoint sets C_{1}, …, C_{r} ∈ C.

We prove the following proposition.

Proposition 10 Suppose C is an (a, b)-regular family on an n-element set F. Then

\frac{n}{a^{2}} ≤ β(F, C) ≤ \frac{n}{a}.  (32)

Proposition 10 follows from the following lemma.

Lemma 11 Let C be an (a, b)-regular family of sets on a set F. Given a subset C̃ ⊂ C with r elements, it is possible to find a subset B ⊂ C̃ of disjoint sets with at least r/ab elements.

To prove Proposition 10, observe that if C is as in the statement of that result, then we may take C̃ = C. Note that then r = |C̃| = |C| = bn/a, and hence r/ab = n/a^{2}, and the lower bound in (32) follows. The upper bound in (32) is obvious.

We now prove Lemma 11.

PROOF. (Proof of Lemma 11) Let s be the maximal number of pairwise disjoint members in C̃. Suppose for a contradiction that s < r/ab, and let C_{1}, …, C_{s} ∈ C̃ be such a maximal collection. Let A = ⋃_{1≤j≤s} C_{j}. We have |A| = as, so the number of members of C̃ that intersect A is at most abs < r = |C̃|. Therefore there is C_{s+1} ∈ C̃ that is disjoint from all the C_{j} (1 ≤ j ≤ s), which contradicts the maximality of C_{1}, …, C_{s}. □

4.1 An example

We now observe that the bounds in Proposition 10 cannot be substantially improved without further hypotheses. Indeed, given a prime power q we may take F to be the projective plane over the finite field GF(q), and C to be the collection of lines of F. Then |F | = q^{2} + q + 1, the system C is (q + 1, q + 1)- regular, and β(F, C) = 1. Notice that the lower bound in (32) tells us that β(F, C) ≥ (q^{2} + q + 1)/(q + 1)^{2} → 1 as q → ∞.

More generally, given a positive integer r we may take F_{r} = F × {1, 2, …, r} and C_{r} = {L × {j} | L ∈ C, 1 ≤ j ≤ r} (i.e., F_{r} is the union of r disjoint copies of the projective plane over GF(q) and C_{r} is the collection of lines in these copies). We have |F_{r}| = r(q^{2}+q+1), the system C_{r} is (q+1, q+1)-regular, and β(F, C) = r, which is close to the lower bound r(q^{2} + q + 1)/(q + 1)^{2} given by (32) provided q is large. We can use these examples in order to show that, given sequences of integers (a_{k}) and (n_{k}), with a_{k} → ∞ and n_{k}/a_{k}^{2} → ∞ as k → ∞, there exist sequences (ã_{k}) and (ñ_{k}) such that ã_{k}/a_{k} and ñ_{k}/n_{k} tend to 1 as k → ∞ and for which there exist F^{(k)} and C^{(k)} such that C^{(k)} is an (ã_{k}, ã_{k})-regular family of sets on F^{(k)}, where |F^{(k)}| = ñ_{k}, and

lim_{k→∞} β(F^{(k)}, C^{(k)}) (\frac{ñ_{k}}{ã_{k}^{2}} )^{−1} = 1

(here we use the fact that there is always a prime between x and (1 + o(1))x, which follows from the prime number theorem).

5 Concluding remarks

If a is a positive integer, let

α(a, n) = max α(F, C),

where the maximum is taken over all (a, b)-regular families of sets C on an n-element set F, and b ≥ 1 is arbitrary. Put

f(a) = lim sup_{n→∞} \frac{a}{n}α(a, n).

Our results imply that, for any large enough fixed a, we have

ln a − 12 ln ln a ≤ f(a) ≤ ∑_{1≤k≤a} \frac{1}{k} = ln a + γ + O (\frac{1}{a}) .  (33)

Notice that the upper bound for f(a) in (33) above holds for every a, by Corollary 2.

Consider the case in which a = 2, that is, the case of regular graphs. It is not difficult to show that (2/n)α(2, n) = 4/3+o(1) as n → ∞, so that f(2) = 4/3. Indeed, for the lower bound, just take for C a collection of, say, k vertex disjoint triangles on an 3k-element set F. Then α(F, C) = 2k and we conclude that f(2) ≥ 4/3.

To prove the upper bound, we show that any b-regular graph G (b > 0) must contain a matching that covers at least 2/3 of its vertices. Let M be a maximum matching in G, and suppose U is the set of vertices that are covered by M. Suppose for a contradiction that |U| < (2/3)n, where n = |V (G)|. Let W = U^{c} = V (G) \ U. Let the number of neighbours in W of a vertex u in U be the W -degree d_{W} (u) of u. The average W -degree of a vertex in U is |W |b/|U|. Thus there is an edge e ∈ M whose endpoints x and y are such that

d_{W} (x) + d_{W} (y) ≥ 2|W |b/|U| > b.  (34)

Note that d_{W} (x), d_{W} (y) < b (because of the edge e = {x, y} ⊂ U). Therefore (34) implies that d_{W} (x), d_{W} (y) ≥ 2. But then there exist distinct vertices x′, y′ ∈ W, with x′ adjacent to x and y′ adjacent to y′. Now observe that M \ {e} ∪ {xx′, yy′} is a larger matching than M, which contradicts the maximality of |M|. This contradiction shows that M does indeed cover (2/3)n vertices of G, and hence α(F, C) ≤ 2n/3. This implies f(2) ≤ 4/3.

Problem 12 Determine f(a) for all a ≥ 3.

Finally, we believe that it would be very interesting to improve on the constructive lower bounds (see Section 3.2).

References

[1] N. Alon: Transversal numbers of uniform hypergraphs, Graphs Combin. 6 (1990), 1–4.

[2] B. Bollobás: Random Graphs, Academic Press, London, 1985.

[3] G. Cohen, I. Honkala, S. Litsyn and A. Lobstein: Covering Codes, North-Holland, Amsterdam, 1997.

[4] Z. Füredi: Matchings and covers in hypergraphs, Graphs Combin. 4 (1988), 115–206.

[5] Z. Füredi, G.J. Székely and Z. Zubor: On the lottery problem, J. Combin. Des. 4 (1996), 5–10.

[6] H. Hämäläinen, I. Honkala, S. Litsyn and P. Östergård: Football pools — a game for mathematicians, Amer. Math. Monthly 102 (1995), 579–588.

[7] D.S. Johnson: Approximation algorithms for combinatorial problems, J. Comput. System Sciences 9 (1974), 256–298.

[8] L. Lovász: On the ratio of optimal integral and fractional covers, Discrete Math. 13 (1975), 383–390.

[9] V. Rödl: On a packing and covering problem, Europ. J. Combin. 6 (1985), 69–78.

[10] S.K. Stein: Two combinatorial covering problems, J. Comb. Th., Ser. A 16 (1974), 391–397.