Efficient covering designs of the complete graph

Yair Caro ^{∗} and Raphael Yuster ^{†} Department of Mathematics University of Haifa-ORANIM, Tivon 36006, Israel. AMS Subject Classification: 05B05,05B40 (primary), 05B30,51E05,94C30,62K05,62K10 (secondary).

Submitted: November 1, 1996; Accepted: February 3, 1997

Abstract Let H be a graph. We show that there exists n_{0} = n_{0}(H) such that for every n ≥ n_{0}, there is a covering of the edges of K_{n} with copies of H where every edge is covered at most twice and any two copies intersect in at most one edge. Furthermore, the covering we obtain is asymptotically optimal.

1 Introduction

All graphs considered here are finite, undirected and simple, unless otherwise noted. For the standard graph-theoretic notations the reader is referred to [5]. Let H = (V_{H}, E_{H}) be a graph. An H-covering design of a graph G = (V_{G}, E_{G}) is a set L = {G_{1}, … G_{s}} of subgraphs of G such that each G_{i} is isomorphic to H and every edge e ∈ E_{G} appears in at least one member of L. The H-covering number of G, denoted by cov(G, H), is the minimum number of members in an H-covering design of G. (If there is an edge of G which cannot be covered by a copy of H, we put cov(G, H) = ∞). Clearly, cov(G, H) ≥ |E_{G}|/|E_{H}|. In case equality holds, the H-covering design is called an H-decomposition (or H-design) of G. Two trivial necessary conditions for a decomposition are that |E_{H}| divides |E_{G}| and that gcd(H) divides gcd(G) where the gcd of a graph the electronic journal of combinatorics 4 (1997), #R10 2 is the greatest common divisor of the degrees of all the vertices. In case G = K_{n}, it was shown by Wilson in [17] that the two necessary conditions are also sufficient, provided n ≥ n_{0}(H), where n_{0}(H) is a sufficiently large constant. If, however, the necessary conditions do not hold, the best one could hope for is an H-covering design of K_{n} where the following three properties hold:

∗e-mail: zeac603@uvm.haifa.ac.il

†e-mail: raphy@math.tau.ac.il

1. 2-overlap: Every edge is covered at most twice.

2. 1-intersection: Any two copies of H intersect in at most one edge.

3. Efficiency: s|E_{H}| < \binom{n}{2} + c(H) · n, where s is the number of members in the covering, and c(H) is some constant depending only on H.

The papers of Mills and Mullin [12] and of Brouwer [4], provide an excellent survey of covering designs. Covering designs with the 2-overlap property were first introduced in statistical designs by [10] and are also mentioned in [2], [6] and [11]. Covering designs with the 1-intersection property (also called super-simple designs) are mentioned by Adams et. al. in [1], Teirlinck [15, 16], Fort and Hedlund [8], Brouwer [3] and Schreiber [14]. The existence of efficient Covering designs of complete hypergraphs was first proved by Rödl in [13].

Our main result is that H-covering designs of K_{n}, having these three properties, exist for every fixed graph H, and for all n ≥ n_{0}(H):

Theorem 1.1 Let H be a fixed graph. There exists n_{0} = n_{0}(H) such that if n ≥ n_{0}, K_{n} has an H-covering design with the 2-overlap, 1-intersection, and efficiency properties.

2 Proof of the main result

We shall prove Theorem 1.1 whenever H = K_{h} is a complete graph. This suffices, since if H is not a complete graph, it is known by Wilson’s theorem [17] that there exists an h_{0} = h_{0}(H) such that K_{h_{0}} has an H-decomposition. By applying Theorem 1.1 to K_{h_{0}}, we shall obtain an n_{0} = n_{0}(h_{0}) = n_{0}(H), such that if n ≥ n_{0}, K_{n} has a K_{h_{0}}-covering design with the 2-overlap and 1-intersection properties and such that \binom{h_{0}}{2}s < \binom{n}{2} + h_{0}^{3} · n, where s is the number of members in the covering. Thus, there is an H-covering design of K_{n} with the 2-overlap and 1-intersection properties, and with s\frac{\binom{h_{0}}{2}}{|E_{H}|} elements, such that s\frac{\binom{h_{0}}{2}}{|E_{H}|}|E_{H}| < \binom{n}{2} + h_{0}^{3} · n = \binom{n}{2} + c(H) · n.

Fix K_{h}, where h ≥ 3 (for h = 2 the result is trivial), and let h_{1} be the minimum positive integer such that whenever n ≥ h_{1} and \binom{h}{2} divides \binom{n}{2}, and h − 1 divides n − 1, K_{n} has a K_{h}- decomposition. As mentioned before, the existence of h_{1} is guaranteed by Wilson’s Theorem [17]. Now let n ≥ max{h^{8}, h_{1} +h(h−1)}. We will show that K_{n} has a K_{h}-covering design, as required in the electronic journal of combinatorics 4 (1997), #R10 3 Theorem 1.1. Let k be the minimum positive integer such that \binom{h}{2} divides \binom{n−k}{2} and h − 1 divides n − k − 1. It is easy to see that 0 ≤ k < h(h − 1). If k = 0 we are done, since in this case n satisfies the conditions in Wilson’s Theorem, and there is a K_{h}-decomposition of K_{n}. Assume, therefore, that 1 ≤ k < h(h − 1), and put r = n − k. Note that r > h_{1}. Partition the vertices of K_{n} into two subsets. The big subset has r vertices, namely B = {a_{1}, …, a_{r}}. The small subset has k vertices, namely S = {b_{1}, …, b_{k}}. We create the members of our efficient covering design in three stages. Stage 1: Let B_{0} be the subgraph induced by the vertices {a_{1}, …, a_{r−1}}. Note that B_{0} is a complete graph on r − 1 vertices, and since h − 1 divides r − 1, there exists a K_{h−1}-factor in B_{0}. (Recall that an X-factor of a graph is a set of vertex-disjoint copies of X which cover all the vertices of the graph). Let F_{1} be such a factor. We repeat the following process for i = 2, …, k. Let B_{i−1} be the graph obtained from B_{i−2} after the edges of the members of F_{i−1} have been removed. Let F_{i} be a K_{h−1}-factor in B_{i−1}. In order to show that our process works, we need to show that a K_{h−1}-factor exists in B_{i−1}. We prove this by induction on i. For i = 1, this is simply the factor F_{1} defined above. Assume the claim holds for all j < i. This implies that B_{i−1} is regular of degree (r − 2) − (i − 1)(h − 2). According to the theorem of Hajnal and Szemerédi [9] if (r − 2) − (i − 1)(h − 2) ≥ \frac{h−2}{h−1}(r − 1) then B_{i−1} has a K_{h−1}-factor. Indeed,

(r − 2) − (i − 1)(h − 2) ≥ (r − 2) − (k − 1)(h − 2) > (r − 2) − h(h − 1)(h − 2) > r − h^{3}.

Since r− \frac{r−1}{h−1} > \frac{h−2}{h−1}(r−1) it suffices to show that r−h^{3} ≥ r− \frac{r−1}{h−1} and this holds since r = n−k > h^{4}. Having defined the K_{h−1}-factors F_{1}, …, F_{k}, we now define a set L_{1} of edge-disjoint copies of K_{h} in our K_{n}, which cover all the edges between S and {a_{1}, …, a_{r−1}}. This is done by joining the vertex b_{i} to every member of F_{i}, for i = 1, …, k. Note that whenever we join b_{i} to a member of F_{i} we obtain a copy of K_{h}. Note also that L_{1} has exactly k(r − 1)/(h − 1) members. Stage 2: Since r ≥ h_{1}, and since h − 1 divides r − 1 and \binom{h}{2} divides \binom{r}{2}, we have by Wilson’s Theorem that the subgraph induced by B (which is a K_{r}), has a K_{h}-decomposition. Fix a labeled K_{h}-decomposition D of this K_{r}. That is, D is a set of \binom{r}{2}/\binom{h}{2} h-subsets of \{a_{1}, …, a_{r}\}, where for each 1 ≤ i < j ≤ r, the pair (a_{i}, a_{j}) appears in exactly one member of D. If π is any permutation of {1, …, r} then let D_{π} be the labeled K_{h}-decomposition obtained from D by replacing each appearance of a_{i} in any member of D with π(a_{i}), for i = 1, …, r. Our aim is to show that there exists a permutation π, and a set L^{∗} of less than h^{5} members of L_{1} (recall that L_{1} is constructed in stage 1), such that every member of D_{π} intersects every member of L_{1} \ L^{∗} in at most one edge. In order to achieve this goal, we pick π randomly, where each of the r! permutations is equally likely. Consider two distinct edges (a_{i}, a_{j}) and (a_{k}, a_{l}) which both appear in the same member of L_{1} (note that when h = 3, there is no such pair, since every member of L_{1} contains only two vertices of B). We call such a pair of edges D_{π}-bad if they both appear in the same member of D_{π}. We shall the electronic journal of combinatorics 4 (1997), #R10 4 compute the probability that two fixed edges (a_{i}, a_{j}) and (a_{k}, a_{l}) are D_{π}-bad. Consider first the case where (a_{i}, a_{j}) and (a_{k}, a_{l}) share an endpoint, say a_{k} = a_{i}. Since π is random, the probability that (a_{i}, a_{j}) and (a_{i}, a_{l}) appear in the same member of D_{π} is exactly \frac{h−2}{r−2}. To see this, fix π(a_{i}) and π(a_{j}), and let Q denote the unique member of D which contains both π(a_{i}) and π(a_{j}). There are r − 2 possible choices for π(a_{l}), where h − 2 of them result in a member of Q. Thus, D_{π} is bad with probability \frac{h−2}{r−2}, given that π(a_{i}) and π(a_{j}) are known. Note, however, that the expression \frac{h−2}{r−2} does not depend on the specific choices for π(a_{i}) and π(a_{j}). Now consider the case where (a_{i}, a_{j}) and (a_{k}, a_{l}) are two independent edges (this is possible only if h − 1 ≥ 4, since every member of L_{1} contains only h − 1 vertices from B). By a similar reasoning to the above, the probability that both these edges appear in the same member of D_{π} is exactly \frac{h−2}{r−2} \frac{h−3}{r−3}. There are (h − 1)(h − 2)(h − 3)/2 pairs of adjacent edges of the form (a_{i}, a_{j}), (a_{i}, a_{l}) in every member of L_{1}. Thus, there are k \frac{r−1}{h−1}(h − 1)(h − 2)(h − 3)/2 such pairs in all the members of L_{1}. There are 3\binom{h−1}{4} pairs of two independent edges of the form (a_{i}, a_{j}), (a_{k}, a_{l}) in every member of L_{1}. Thus there are 3k \frac{r−1}{h−1} \binom{h−1}{4} such pairs in all the members of L_{1}. Therefore, if μ is the expected number of D_{π}-bad pairs, then

μ = k \frac{r − 1}{h − 1} \frac{(h − 1)(h − 2)(h − 3)}{2} \frac{h − 2}{r − 2} + k \frac{r − 1}{h − 1}3\binom{h − 1}{4}\frac{h − 2}{r − 2} \frac{h − 3}{r − 3} <

\frac{h^{5}}{2} + \frac{3}{24}h^{7} \frac{r − 1}{(r − 2)(r − 3)} < h^{5}.

Thus, there exists a permutation π such that the number of D_{π}-bad pairs is less than h^{5}. Fix such a permutation, and let L_{2} = D_{π}. Let L^{∗} be the set of all members of L_{1} which contain a D_{π}-bad pair. Clearly, |L^{∗}| < h^{5}. Thus, every member of L_{2} intersects every member of L_{1} \ L^{∗} in at most one edge. Put L_{3} = L_{2} ∪ (L_{1} \ L^{∗}). Stage 3: Every edge of K_{n} appears in at most two members of L_{3} and any two members of L_{3} intersect in at most one edge. However, there may still be uncovered edges. In fact, all the \binom{k}{2} edges connecting two members of S are not covered, and all the k edges of the form (b_{i}, a_{r}), for i = 1, …, k, are not covered. Furthermore, each member of L^{∗} covers h − 1 edges connecting some b_{i} ∈ S to a subset of h − 1 vertices of {a_{1}, …, a_{r−1}}, and these edges are uncovered in L_{3}. Thus there are |L^{∗}|(h − 1) uncovered edges of this form. Hence, if M denotes the set of uncovered edges, we have that

|M| = \binom{k}{2} + k + |L^{∗}|(h − 1) < h^{6}.

The crucial point is that the number of uncovered edges is bounded by a constant depending only on h. We shall show how to sequentially create a set L_{4} of copies of K_{h}, beginning with L_{4} = ∅, the electronic journal of combinatorics 4 (1997), #R10 5 where at each stage, a new copy of K_{h} containing at least one non-covered edge by members of L_{3} ∪L_{4}, is added to L_{4} (thus |L_{4}| < h^{6}) and such that the following three invariants are maintained:

1. Every edge is covered at most twice by members of L_{3} ∪ L_{4}.

2. Any two members of L_{3} ∪ L_{4} intersect in at most one edge.

3. If L_{4} already contains j members, then any vertex of B ∪ S is adjacent to at most jh + h^{3}

edges which are covered twice by members of L_{3} ∪ L_{4}. Note that at the beginning of the process, when L_{4} = ∅, the first two invariants hold, since they hold for L_{3}. We must show that the third invariant holds initially, when j = 0. Indeed, in L_{3}, all the edges adjacent to a vertex of S are either non-covered, or covered once in L_{1}. Now consider a vertex a_{i} ∈ B. If i < r, a_{i} is adjacent to exactly (h−2)k edges which are covered twice by members of L_{1} ∪ L_{2} (recall that a_{r} is not adjacent to any edge which is covered in L_{1}). Since L_{3} ⊂ L_{1} ∪ L_{2}, we have that any vertex in B ∪ S is adjacent to at most (h − 2)k < h^{3} edges which are covered twice by members of L_{3}. Suppose L_{4} already contains j members, and there still exists an uncovered edge e = (q_{1}, q_{2}) in M. We shall find a set Q = {q_{3}, …, q_{h}} of h − 2 vertices in B ∪ S, and add the complete graph K_{h} induced by {q_{1}, q_{2}, …, q_{h}} to L_{4}, while maintaining our three invariants. We select the elements of Q sequentially. The first element, q_{3}, needs to have the property that (q_{1}, q_{3}) is not covered twice, and (q_{2}, q_{3}) is not covered twice. Indeed there are at most 2(jh + h^{3}) vertices of (B ∪ S) \ {q_{1}, q_{2}} which are ruled out as candidates for q_{3}. Since

2(jh + h^{3}) < 2(h^{7} + h^{3}) ≤ h^{8} − 2 ≤ n − 2

we can find the desired q_{3}. It is important to note that there does not exist any member of L_{3} ∪ L_{4} which contains both (q_{1}, q_{3}) and (q_{2}, q_{3}), since this would require it to contain (q_{1}, q_{2}) which we assume to be uncovered. Therefore, invariants 1 and 2 still hold. Suppose we have already found appropriate vertices q_{3}, …, q_{i}, where i < h, and we wish to find q_{i+1}. Our requirements of q_{i+1} are as follows: All the edges (q_{t}, q_{i+1}) for t = 1, …, i should each be covered at most once, and for each once-covered edge (q_{t}, q_{p}) where 1 ≤ t < p ≤ i, q_{i+1} does not appear in the unique copy of L_{3} ∪ L_{4} containing (q_{t}, q_{p}). These requirements rule out at most

i · (jh + h^{3}) + \binom{i}{2}(h − 2)

possible candidates for q_{i+1} from (B ∪ S) \ {q_{1}, …, q_{i}}. In order to show that q_{i+1} can be selected we need to show that

n − i > i(jh + h^{3}) + \binom{i}{2}(h − 2).

Indeed,

i(jh + h^{3}) + \binom{i}{2}(h − 2) ≤ (h − 1)(h^{7} + h^{3}) + \binom{h − 1}{2}(h − 2) < h^{8} − (h − 1) ≤ n − i.

Our construction of Q shows that after adding the K_{h} subgraph induced by {q_{1}, …, q_{h}} as the j + 1’th element to L_{4}, invariants 1 and 2 still hold. Note also that invariant 3 holds as any vertex may only have at most h − 1 edges which are now covered twice, and which were not covered twice prior to this stage. (The only vertices for which this may happen are q_{1}, …, q_{h}). In order to complete our proof we only need to show that if L = L_{3} ∪ L_{4} contains s elements then s\binom{h}{2} < \binom{n}{2} + h^{3}n. Clearly, it suffices to show that

sh(h − 1) < n(n − 1) + h^{3}(n − 1).  (1)

L_{4} contains less than h^{6} members. L_{1} contains exactly k(r − 1)/(h − 1) members, and L_{2} contains exactly \binom{r}{2}/\binom{h}{2} members. Thus,

s < h^{6} + k \frac{r − 1}{h − 1} + \begin{matrix}( & {r \atop 2} & ) \\ ( & {h \atop 2} & ) \end{matrix}.  (2)

We shall prove (1) using (2) and using the facts that k < h(h − 1), r = n − k and n ≥ h^{8}. Indeed

sh(h − 1) < h^{7}(h − 1) + hk(r − 1) + r(r − 1) = h^{8} − h^{7} + hkn − hk^{2} − hk + n^{2} − 2kn + k^{2} − n + k <

h^{8} − h^{3} + hkn + n^{2} − 2kn − n < n(n − 1) + h^{3}(n − 1).

□

3 Concluding remarks and an open problem

When H = K_{h}, the constant n_{0}(H) in Theorem 1.1 is shown in the proof to be no larger than max{h^{8}, h_{1} + h(h − 1)}, where h_{1} = h_{1}(h) is the corresponding constant in Wilson’s Theorem. However, the best known bound for h_{1} (and, consequently, for n_{0}(H)), is rather large, and highly exponential in h [7]. It is plausible, however, that the statement of Theorem 1.1 is still valid for n_{0}(H) which is much smaller. In fact, we conjecture the following:

Conjecture 3.1 There exists a positive constant C such that for all h ≥ 2, if n ≥ Ch^{2} then K_{n} has a K_{h} covering design where each edge is covered at most twice and any two copies intersect in at most one edge. the electronic journal of combinatorics 4 (1997), #R10 7 Note that a positive answer to Conjecture 3.1 requires a proof which does not use Wilson’s Theorem, as improving Wilson’s constant to O(h^{2}) is unlikely. The h^{2} factor in Conjecture 3.1 cannot be reduced since we have the following simple 0.25h^{2} lower bound: Assume that h ≥ 10. If n = ⌊0.25h^{2}⌋ then any K_{h}-covering of K_{n} contains \binom{n}{2}/\binom{h}{2} > h/2 members. However, the union of t K_{h}-subgraphs with the 1-intersection property contains at least h + (h − 2) + … + (h − 2t + 2) vertices. For t = ⌈h/2⌉ this sum is greater than 0.25h^{2} ≥ n. Thus, any K_{h}-covering of K_{n} does not have the 1-intersection property.

4 Acknowledgment

The authors wish to thank T. Etzion and A. Rosa for useful discussions.

References

[1] P. Adams, E. Bryant and A. Khodkar, On the existence of super-simple designs with block-size 4, Aequationes Mathematicae 51 (1996), 230-246.

[2] N. Alon, Y. Caro and R. Yuster, Covering the edges of a graph by a prescribed tree with minimum overlap, submitted.

[3] A. E. Brouwer, On the packing of quadruples without common triples, Ars Combinatoria 5 (1978), 3-6.

[4] A. E. Brouwer, Block Designs, in: Chapter 14 in ”Handbook of Combinatorics”, R. Graham, M. Grötschel and L. Lovász Eds. Elsevier, 1995.

[5] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, Macmillan Press, London, 1976.

[6] Y. Caro, Y. Roditty and Y. Schonheim, Covering the edges of the complete graph with minimum overlap, Manuscript.

[7] Y. Chang, A bound for Wilson’s Theorem - III, J. Combinatorial Designs 4 (1996), 83-93.

[8] M. K. Fort and G. A. Hedlund, Minimal covering of pairs by triples, Pacific J. Math. 8 (1958), 709-719. the electronic journal of combinatorics 4 (1997), #R10 8 [9] A. Hajnal and E. Szemerédi, Proof of a conjecture of Erdös, in: Combinatorial Theory and its

Applications, Vol. II (P. Erdös, A. Renyi and V. T. Sós eds.), Colloq. Math. Soc. J. Bolyai 4, North Holland, Amsterdam 1970, 601-623.

[10] J. A. John and T. J. Mitchell, Optimal incomplete block designs J. Roy. Statist. Soc. 39B (1977) 39-43.

[11] D. L. Kreher, G. F. Royle and W. D. Wallis, A family of resolvable regular graph designs, Discrete Math. 156 (1996), 269-275.

[12] W. H. Mills and R. C. Mullin, Coverings and packings, in: Contemporary Design Theory: A collection of Surveys, 371-399, edited by J. H. Dinitz and D. R. Stinson. Wiley, 1992.

[13] V. Rödl, On a packing and covering problem, Europ. J. of Combin. 6 (1985), 69-78.

[14] S. Schreiber, Covering all triples on n marks by disjoint Steiner systems, J. Combin. Theory, Ser. A 15 (1973), 347-350.

[15] L. Teirlinck, On making two Steiner triple systems disjoint, J. Combin. Theory, Ser. A 23 (1977), 349-350.

[16] L. Teirlinck, On large sets of disjoint quadruple systems, Ars Combinatoria 17 (1984), 173-176.

[17] R. M. Wilson, Decomposition of complete graphs into subgraphs isomorphic to a given graph, Congressus Numerantium XV (1975), 647-659.