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–900 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

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 [2]), in particular, in football pool problems (see [5]), 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], [3, Theorem 8.11], [4], and [8]. In this note, we prove another result that 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.

If C is a hypergraph on F, 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. In this note, we shall be

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

Preprint submitted to Elsevier Preprint 3 January 2001

concerned with estimating α(F, C). Our first result is a slight improvement of classical results by Johnson, Stein, and Lovász (see [6], [7], and [9]).

Proposition 1 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} ∑_{r=1}^{ℓ} \frac{1}{r} < \frac{n}{a}( ln(a + 1) + γ) − \frac{1}{2} ln \frac{a}{ℓ} + \frac{1}{2}, (1)

where γ = 0.5772156649 … is Euler’s constant.

The proof of Proposition 1 is based on the following remark: given a subset A ⊂ F, there is always a set C ∈ C such that |A ∩ C| ≥ (b/|C|)|A| = (a/n)|A|. (This remark follows from an averaging argument.) We omit the details.

Remark 2 If we just suppose that |C| ≤ a for all C ∈ C and deg(x) ≥ b for all x ∈ F, then we can set m = |C| and conclude that n/a ≤ α(F, C) ≤ f(a, b, m, n), where

f(a, b, m, n) = \begin{cases}\frac{n}{a} + \frac{m}{b} ∑_{r=2}^{a} \frac{1}{r} ≤ \frac{m}{b}(ln(a + 1) + γ) & 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}

Our main result, given in the following proposition, shows that the estimates of the previous proposition are asymptotically sharp for certain regular families of subsets of finite sets. 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 3 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.

(2)

An interesting feature of Proposition 3 is that it claims the existence of uniform, regular hypergraphs with large α. More importantly, the parameters n > a are free and (2) gives good estimates regardless of the relation between them. The reader is invited to compare the bounds in (1) and (2) 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 3 above, for simplicity, we restrict ourselves to (a, b)-regular hypergraphs with a = b.

We now prove Proposition 3. Because of space limitations, we consider the case a ≥ n/ ln^{3} n only (the other case requires an additional idea). 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ℤ. We claim that, for r = ⌈n/k^{2}⌉, there are 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. 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 smaller than one, whence there is x_{s+1} ∈ ℤ/nℤ such that x_{s+1} − T is disjoint from U. Our claim follows by induction. 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}(\frac{a}{n})^{m}(1 − \frac{a}{n})^{n−m}, which is maximum for m = a, so the probability that |Ã| = a is at least 1/n. 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 ℙ(∀j ∈ [r] we have x_{j} − T ⊄ Ã^{c}) = n (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 − \frac{a}{n})^{k})^{r} ≤ n^{k+1} (1 − (1 − \frac{a}{n})^{k})^{r} . (3)

Let k = −β ln a/ ln(1 − a/n) ≤ β(n/a) ln n, where β ≤ 1. We have that the right-hand side of (3) 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 (2).

References

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

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

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

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

[5] 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.

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

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

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

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