Variants of the Hajnal–Szemerédi Theorem Eldar Fischer* DEPARTMENT OF MATHEMATICS RAYMOND AND BEVERLY SACKLER FACULTY OF EXACT SCIENCES TEL-AVIV UNIVERSITY TEL-AVIV ISRAEL Received December 30, 1996; revised December 23, 1998 Abstract: The Hajnal–Szemerédi Theorem [Hajnal & Szemerédi, Colloq Math Soc J Bolyai, 1970] states that a graph with hk vertices and minimum degree at least (h − 1)k contains k vertex disjoint copies of Kh . Its proof is not algorithmic. Here, we present an algorithm that, for a fixed h, finds in such a graph k − C(h) vertex disjoint copies of Kh in polynomial time in k, C(h) being a constant depending on h only. The proof suggests a variant of the theorem for h-partite graphs, which is conjectured here and proven in a slightly weaker form in some special c 1999 John Wiley & Sons, Inc. J Graph Theory 31: 275–282, 1999 cases. Keywords: graph embeddings, cliques, incremental approach 1. INTRODUCTION All graphs considered here are finite and without loops or parallel edges. Given a graph G with kh vertices, it is useful to formulate conditions on the minimum *This article forms part of a Ph. D. thesis written by the author under the supervision of Prof. N. Alon. c 1999 John Wiley & Sons, Inc. CCC 0364-9024/99/030275-08 276 JOURNAL OF GRAPH THEORY degree of G that ensure that it contains k vertex disjoint copies of Kh , the complete graph on h vertices. By considering the complete h-partite graph with k−1 vertices in one color class, k + 1 vertices in another, and k vertices in each of the remaining color classes, one sees that a minimum degree of at least (h − 1)k must be required. It is seen from Dirac’s Theorem that this is the exact case for h = 2, and the same for h = 3 was proven by Corrádi and Hajnal [3]. All other cases were resolved by the following classical result of Hajnal and Szemerédi. Theorem 1.1 ([6]). If G is a graph with hk vertices and minimum degree at least (h − 1)k, then G contains k vertex disjoint copies of Kh , the complete graph on h vertices. The proof of this theorem is quite involved, and does not yield an efficient algorithm for finding explicitly the required vertex disjoint Kh copies. We show here, for a graph G that satisfies the condition of Theorem 1.1, an algorithm that finds k − C(h) disjoint Kh copies in O(f (h)k 2 ) time, with C and f dependent only on h. We also state some related conjectures for which we prove some partial results. 2. ALGORITHMIC APPROXIMATION OF THE HAJNAL–SZEMERÉDI THEOREM In this section we prove the following result, yielding the algorithm mentioned in the introduction. Theorem 2.1. There exists an algorithm that runs in time O((h + 5)!k 2 ), such that, given h and a graph G with hk vertices and minimum degree at least (h − 1)k, finds in G at least k − (h − 1)2 vertex disjoint copies of Kh . We need the following simple lemma, whose proof is left to the reader. Lemma 2.1. If a bipartite graph H with color classes A, B, |A| ≤ h, |B| = h, contains at least (l − 1)h + 1 edges, then H contains a matching of size l. Proof of Theorem 2.1. The algorithm keeps at each stage a partition of the vertex set V of G into k sets of size h, V1 , . . . , Vk , together with a vertex maximal complete graph Gi in each Vi . The algorithm begins with an arbitrary partition, where some of the Gi ’s may be single vertices. The algorithm terminates when there are less than h copies of Kj among G1 , . . . , Gk for each 1 ≤ j < h. Otherwise, assume that G1 , . . . , Gh are copies of Kj for some fixed 1 ≤ j < h, and perform the following procedure. / Gl We define a connection to be a pair (v, l), v ∈ V, 1 ≤ l ≤ h, such that v ∈ and all vertices of Gl are neighbors of v . For 1 ≤ i ≤ k , denote by c the number P i of connections (v, l) with v ∈ Vi . Counting arguments show that ki=1 ci ≥ (h − j)hk , since each Kj copy has at least (h − j)k related connections. If there exist i1 = / i2 satisfying 1 ≤ i1 , i2 ≤ h, such that all vertices of Gi1 are neighbors of a vertex in Vi2 , then, by modifying the partition V1 , . . . , Vk in the HAJNAL-SZEMEREDI VARIANTS 277 obvious way, we get G1 , . . . , Gk in which Gi1 is of size j + 1, Gi2 is of size at least j − 1, and all the other sizes remain as before. Otherwise, there exists i > h such that ci > (h − j)h. In that case by Lemma 2.1 there exist v1 , . . . , vh−j+1 ∈ Vi and l1 , . . . , lh−j+1 ∈ {1, . . . , h}, all different, such that all vertices of Gln are neighbors of vn for all 1 ≤ n ≤ h − j + 1. By modifying the partition V1 , . . . , Vk and the graphs G1 , . . . , Gk , we can increase the sizes of Gl1 , . . . , Glh−j+1 by one, decrease the size of Gi by at most h − j + 1, and leave all the other sizes as before. As the search for both cases is done in time O(h3 k), all that remains to be proven is that this process terminates in a number of iterations, which is O((h + 2)!k). To prove this, we assign weights to G1 , . . . , Gk as follows. Denote by w : {0, . . . , h} → R the function defined by w(1) = w(0) = 0, w(j + 1) − w(j) = Pk 1− (h−j+1)! i=1 wi . (h+1)! for 1 ≤ j < h. Define wi = w(|Gi |) for 1 ≤ i ≤ k , and w = It is clear that 0 ≤ w ≤ hk , and we now prove that w increases by a certain amount in each stage of any of the cases described above. In the first case, w gained 1 − (h−j+1)! (h+1)! by the increase in Gi1 , and lost no more (h−j+2)! (h+1)! by the possible (h−j+2)! (h−j+1)! 1 (h+1)! − (h+1)! ≥ (h+1)! . than 1 − decrease in Gi2 . Thus, w is increased by at least In the second case, w gained (h − j + 1)(1 − (h−j+2)!−(h−j+1)! (h+1)! (h−j+1)! (h+1)! ) = h−j +1− by the increase in Gl1 , . . . , Glh−j+1 , and lost no more than w(h) − w(j − 1) ≤ h − j + 1 − (h−j+2)! (h+1)! by the decrease in Gi . Thus, w increased 1 by at least (h−j+1)! (h+1)! ≥ (h+1)! . This bounds the number of iterations by (h + 1)!hk = O((h + 2)!k), completing the proof. 3. COLORED VERSION When G is an h-partite graph with equal color classes, one might want to obtain a partition of G into vertex disjoint Kh copies. This is a generalization of the perfect matching problem in the case of bipartite graphs, solved in full by Hall’s Theorem (see, e.g., [2]). The following conjecture is a variant of the Hajnal–Szemerédi Theorem, with constraints given by the coloring of G. Conjecture 3.1. If G is an h-partite graph with color classes C1 , . . . , Ch of size k, such that each vertex in any class has at least h−1 h k neighbors in each of the other classes, then G contains k vertex disjoint copies of Kh . For h = 2, this conjecture is an easy consequence of Hall’s Theorem. If true, the condition on the number of neighbors of each vertex in each class is tight, since for d < h−1 h k we can define G as the following counter example: Choose a set A that consists of d vertices from each color class, and choose as edges all 278 JOURNAL OF GRAPH THEORY possible edges across color classes that are incident with a vertex from A. Clearly, every possible Kh copy in this G contains at least h − 1 vertices from A. Since |A| = hd < (h − 1)k , there are no k vertex disjoint Kh copies. By using the proof technique of the previous section, we can give the following evidence for the correctness of the conjecture for higher values of h. Proposition 3.1. If, for h = 3 or h = 4, G satisfies the conditions above, then G contains k − C copies of Kh , C being a constant independent of k. These copies can be found in time that is polynomial in k. For proving this, we maintain a partition V1 , . . . , Vk of V , such that |Vi ∩Cj | = 1 for all 1 ≤ i ≤ k, 1 ≤ j ≤ h. We denote by vi,j the single vertex in Vi ∩ Cj . Again, we maintain a list of known complete subgraphs G1 , . . . , Gk in V1 , . . . , Vk , but this time, they are not necessarily vertex maximal. At the beginning, G1 , . . . , Gk are all single vertices. We define each Gi to be colored by the color classes of the vertices it contains. Proposition 3.1 for the case h = 3 follows almost immediately from the following simple lemma, while the case h = 4 needs some extra work. Lemma 3.1. For any partition as above, if Gi is only a single vertex, we can find a new partition in which Gi will be an edge colored with x1 and x2 (1 ≤ x1 < x2 ≤ h of our choice), and all other members of G1 , . . . , Gk will maintain their sizes and colors. Proof. We may assume i = 1 and x1 = 1, x2 = 2. If V1 already contains such an edge, we are done by modifying G1 accordingly. Otherwise, for 1 < j ≤ k we call Vj connected to v1,1 if vj,l for all 1 < l ≤ h are neighbors of v1,1 . A counting argument shows that there is a Vj connected to v1,1 such that vj,1 is also a neighbor of v1,2 . By swapping v1,1 and vj,1 , we arrive at the desired partition of V . Proof of Proposition 3.1 for h = 3. We keep track only of triangles. As long as there are less than k − 2 triangles among G1 , . . . , Gk , we may assume that G1 , G2 , G3 are not triangles. Furthermore, by Lemma 3.1, we may assume that G1 is an edge colored with 2 and 3, G2 an edge colored with 1 and 3, and G3 an edge colored with 1 and 2. If there is a triangle within the vertices of V1 , V2 , V3 , we modify the partition, if necessary, and add it. Otherwise, since for each 1 ≤ j ≤ 3 the graph Gj is connected to at least 13 k of the vertices vi,j , there exists 3 < i ≤ k such that Vi contains two vertices connected to two distinct Gj ’s. By modifying the partition V1 , . . . , Vk , we destroy Gi , which could be a triangle, but obtain two new triangles instead. Remark. In fact, by extending this proof a little we can obtain k triangles minus one edge. This is done by allowing the edges appearing in the proof to be across different Vi ’s in the final stages. Proof of Proposition 3.1 for h = 4. We keep track of triangles and K4 copies. To each triangle we assign a weight of 2, and to each K4 copy a weight of 5. We now describe a procedure that increases the total weight at each stage, and terminates HAJNAL-SZEMEREDI VARIANTS 279 only when G1 , . . . , Gk include less than 9 triangles and less than 4 smaller graphs, and, in particular, all but at most 11 of them are K4 copies. For 1 ≤ j ≤ 4, let tj denote the number of listed triangles that are colored with all colors differing from j . At the beginning of this algorithm these are all 0, and after each stage these numbers will remain between 0 and 3. Moreover, there will be no possibility that at any stage three of them are 3 while the remaining one is 0. At each stage, we execute one of the following procedures, depending on the exact values of t1 , . . . , t4 . • If t1 , . . . , t4 are all positive (but are not greater than 3), assume that Gj for 1 ≤ j ≤ 4 is a triangle colored with all colors differing from j . If one of these triangles is connected to the remaining vertex in its appropriate Vj , say G1 is connected to v1,1 , we complete it to a K4 and strike out from G1 , . . . , Gk also one triangle colored differently from G1 . If one of G1 , . . . , G4 is connected to a vertex in another one of these four triangles, we again complete a K4 and strike out these two differently colored triangles. Otherwise, a counting argument shows the existence of 4 < i ≤ k such that Vi contains vertices connected to two distinct triangles among G1 , . . . , G4 , so we eliminate two triangles, and perhaps one more triangle or K4 copy, to obtain two K4 ’s. It is easily shown that the total weight increases this way, and at least two of t1 , . . . , t4 will be less than 3 (in case one of them becomes 0). • If one of t1 , . . . , t4 is 0 and another one not greater than 1, assume, without loss of generality, that t1 = 0, t2 ≤ 1. Assume further that G1 , . . . , G4 are neither triangles nor K4 copies. By Lemma 3.1, we may assume that G1 and G2 are edges colored with 3 and 4, G3 an edge colored with 2 and 4, and G4 an edge colored with 1 and 3. We want to find a vertex vi,1 connected to G1 , a vertex vi,2 connected to G2 , a vertex vi,3 connected to G3 , and a vertex vi,4 connected to G4 . If any of these is found within the vertices of V1 , . . . , V4 , we complete the stage by modifying the partition (if necessary), and adding the new triangle to G1 , . . . , Gk . The new triangle adds to t1 or t2 , but these remain less than 3 (in case there is still a tj that is 0). Otherwise, a counting argument shows the existence of an 4 < i ≤ k such that Vi contains three of the required vertices. Modifying the partition, we may destroy a K4 or an existing triangle that was Gi , but not a triangle colored with 2, 3, 4 by the assumption t1 = 0. However, we obtain three new triangles. t1 necessarily becomes 1 or 2, t2 may increase by no more than 2, t3 and t4 do not increase. In any case, the total weight increases, and the rules regarding t1 , . . . , t4 in the description of this algorithm are not violated. • If one of t1 , . . . , t4 is 0 and all others are at least 2, then by the description of this algorithm at least one of t1 , . . . , t4 is exactly 2. Assume, without loss of generality, that t1 = 0, t2 = 2. Assume further that G1 , . . . , G4 are neither 280 JOURNAL OF GRAPH THEORY triangles nor K4 copies. By Lemma 3.1, we may assume that G1 and G2 are edges colored with 3 and 4, G3 an edge colored with 2 and 4, and G4 an edge colored with 2 and 3. We want to find a vertex vi,1 connected to G1 , a vertex vi,2 connected to G2 , a vertex vi,3 connected to G3 , and a vertex vi,4 connected to G4 . If any of the last three mentioned vertices is found within V1 , . . . , V4 , we complete the stage by modifying the partition (if necessary), and adding the new triangle to G1 , . . . , Gk , setting t1 = 1. Otherwise, counting arguments show the existence of 4 < i ≤ k and l, which satisfies either l = i or l ≤ 4, such that three of the required four vertices are within vl,1 , vi,2 , vi,3 , and vi,4 . Modifying the partition, we may destroy a K4 or a triangle that was Gi (but not one colored with 2, 3, 4), and we obtain three new triangles. This increases t1 , may increase t2 by at most one, and does not increase t3 or t4 . Since all the ti ’s but t1 were at least 2, none of them becomes 0. In any case here the total weight increases, and t1 , . . . , t4 become positive but do not exceed 3, so the rules regarding them are not violated. All possible cases for the values t1 , . . . , t4 being covered, we note that this procedure is applicable as long as G1 , . . . , Gk contain at least 9 triangles, or at least 4 smaller graphs. Since at each stage the weight increases (by at least 1), and the maximal total weight is 5k , we conclude that the procedure terminates in O(k 2 ) running time. This completes the proof of the proposition for h = 4. The following simple proposition shows that the conclusion of Conjecture 3.1 2h−3 holds, if we replace the function h−1 h k in its assumptions by 2h−2 k . Proposition 3.2. If G is an h-partite graph with color classes C1 , . . . , Ch of size k, such that each vertex in any class has at least 2h−3 2h−2 k neighbors in each of the other classes, then G contains k vertex disjoint copies of Kh . Proof. By induction on h. The case h = 2 is already known. For h > 2, we first apply induction to find k vertex disjoint copies of Kh−1 occupying the first h − 1 color classes. Then we construct a bipartite graph H with color classes A, B as follows: A consists of the Kh−1 copies found earlier, B is the remaining color class of G. u ∈ A is connected to v ∈ B , if all vertices of the Kh−1 copy corresponding to u are neighbors of v in G. A counting argument shows that the known case h = 2 of Conjecture 3.1 applies to H , thus yielding a perfect matching, which corresponds to the required Kh copies in G. 4. CYCLES IN h-PARTITE GRAPHS The proposed conjecture regarding the colored version of the Hajnal–Szemerédi Theorem can be extended to the following problem. Suppose that K is a fixed graph on the vertex set {v1 , . . . , vh }, and G is an h-partite graph with k vertices in each color class. Formulate conditions on the HAJNAL-SZEMEREDI VARIANTS 281 number of neighbors of a vertex from a color class of G in each of the other color classes, such that the existence of k vertex disjoint copies of K in G, each with one vertex from each color class in the manner corresponding to K , is ensured. An instance of the general problem, other than Conjecture 3.1, is the following conjecture. Conjecture 4.1. If G is an h-partite graph with color classes C1 , . . . , Ch of size k, such that for any 1 ≤ i ≤ h each vertex in Ci has at least h+1 2h k neighbors in each of Ci+1 , Ci−1 (the indices are modulo h), then G contains k vertex disjoint cycles, each consisting of one vertex from each class. If true, the condition on the number of neighbors of each vertex in each class is tight, since for d < h+1 2h k we can define as G the following counter example: Choose sets A, B , such that A consists of d vertices from each color class, B consists of max{d, k−d} vertices from each class, and A∩B consists of max{0, 2d−k} < h1 k vertices of each class. Choose as edges all possible edges between Ci , Ci+1 for 1 ≤ i < h, which are incident with two vertices in A or two vertices in B , and all possible edges between C1 , Ch , which are incident with one vertex in A and one vertex in B . It is easily shown that every possible cycle in this G contains at least one vertex from A ∩ B , and since |A ∩ B| < k , there are no k vertex disjoint cycles. If true, Conjecture 4.1 gives strong evidence in favor of El–Zahar’s conjecture ([4], see also [1] and [5]). For h = 3, the conjecture is identical to Conjecture 3.1, and by a simple extension of the proof in the previous section we can arrive at the following. Proposition 4.1. If for a graph G as above each vertex has at least 23 k neighbors in the next class and in the previous one, then G contains k−2 cycles as in Conjecture 4.1, found in polynomial time in k. Sketch of proof. We maintain a partition as in the proof of Proposition 3.1, keeping track of complete cycles only. Suppose that V1 , V2 , V3 do not contain such cycles. By adding edges one by one, using each time the proof method of Lemma 3.1, we may assume that Vi contains a path from vi,i+1 to vi,i−1 in the right color order for each 1 ≤ i ≤ 3. If there is a cycle within V1 , V2 , V3 , we modify the partition, if necessary, and add it to our list. Otherwise, a counting argument shows that by modifying the partition we can complete two of these paths to cycles, with a possibility of destroying one previously found cycle in the process. ACKNOWLEDGMENTS I would like to thank Professor Noga Alon for the helpful discussion and the continuing support. I would also like to thank an anonymous referee for his useful comment. 282 JOURNAL OF GRAPH THEORY References [1] N. Alon and E. Fischer, 2-factors in dense graphs, Discrete Math 152 (1996), 13–23. [2] B. Bollobás, Extremal graph theory, Academic, New York, 1978. [3] K. Corrádi and A. Hajnal, On the maximal number of independent circuits in a graph, Acta Math Acad Sci Hungar 14 (1963), 423–439. [4] M. H. El–Zahar, On circuits in graphs, Discrete Math 50 (1984), 227–230. [5] E. Fischer, Cycle factors in dense graphs, Discrete Math 197/198 (1999), 309–323. [6] A. Hajnal and E. Szemerédi, ‘‘Proof of a conjecture of Erdös,’’ Combinatorial Theory and its Applications, Vol. II, P. Erdös, A. Renyi, and V. T. Sös, (editors) Colloq Math Soc J Bolyai. 4 (1970), 610–623.

1/--страниц