Note on bipartite graph tilings Jan Hladký ∗ Mathias Schacht † January 11, 2010 Abstract Let s < t be two fixed positive integers. We study sufficient minimum degree conditions for a 0 1 bipartite graph G, with both color classes of size n = k(s+t), which ensure that G has a Ks,t- factor. Ourresult extends the work of Zhao, who determined the minimum degree threshold which 0 2 guarantees that a bipartite graph has a Ks,s-factor. n a 1 Introduction J 1 For two (finite, loopless, simple) graphs H and G, we say that G contains an H-factor if there exist 1 v(G)/v(H) vertex-disjoint copies of H in G. As a synonym, we say that there exists an H-tiling of G. ] Obviously, if G contains an H-factor, then v(G) is a multiple of v(H). For a fixed graph H, necessary O and sufficient conditions on the minimum-degree of G which guarantee that G contains an H-factor C were studied extensively. Results in this spirit include the Tutte 1-factor Theorem (see [7]), the Hajnal- . Szemerédi Theorem [4], and series of improving results by Alon and Yuster [1, 2], Komlós [5], Zhao and h t Shokoufandeh [8], and by Kühn and Osthus [6]. In [6] the answer to the problem is settled (up to a a constant) for any H. It was shown that the relevant parameters are the chromatic number and the m critical chromatic number of H. [ The additionalinformationthat G is r-partite mighthelp to decreasethe minimum-degreethreshold 2 for G containing an H-factor. The conjectured r-partite version of the Hajnal-Szemerédi Theorem [3] v is such an example. (Recently a proof of the approximate version of the r-partite Hajnal-Szemerédi 2 Theorem was announced by Csaba.) In this paper we determine the threshold for the minimum-degree 9 of a balanced bipartite graph G which guarantees that G contains a K -factor, for arbitrary integers 1 s,t s<t. IfthecardinalitiesofbothcolorclassesofGaren,anecessaryconditionforGhavingaK -factor 1 s,t . is that n is a multiple of s+t. The sufficient minimum-degree condition is given in Theorem 2, and a 6 matching lower bound is provided in Theorem 3. Our work can be seen as an extension of the work of 0 8 Zhao [9], who investigated the case s=t. 0 : Theorem 1 (Zhao,[9]). Foreachs≥2thereexistsanumberk0 suchthat ifG=(A,B;E)is abipartite v graph, |A|=|B|=n=ks, where k >k0, and i X n +s−1 if k is even, r δ(G)≥ 2 a n n+3s −2 if k is odd, 2 then G has a K -factor. s,s Moreover, Zhao showed that the bounds in Theorem 1 are tight. We extend those results to K - s,t factors with s<t. ∗Department ofAppliedMathematics, Facultyof Mathematics andPhysics,Charles University,Malostranskénáměstí 25, 118 00, Prague, Czech Republic and Zentrum Mathematik, Technische Universität München, Boltzmannstraße 3, D- 85747 Garching bei München, Germany. E-mail: [email protected]. Research was supported by the Grant Agency of Charles University, and by the DFG Research Training Group 1408 “Methods for Discrete Structures” via its 2007predoccourse“Integer PointsinPolyhedra”. †Institut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, D-10099 Berlin, Germany. E-mail: [email protected] 1 Theorem 2. Let 1≤ s < t be fixed integers. There exists a number k0 ∈N such that if G= (A,B;E) is a bipartite graph, |A|=|B|=n=k(s+t), with k>k0, and n +s−1 if k is even, δ(G)≥ 2 n n+t+s −1 if k is odd, 2 then G has a K -factor. s,t On the other hand, we show that these bounds are best possible. Theorem 3. Let 1≤ s < t be fixed integers. There exists a number k0 ∈N such that for every k > k0 there exists a bipartite graph G=(A,B;E), |A|=|B|=k(s+t)=n, such that n +s−2 if k is even, δ(G)= 2 n n+t+s −2 if k is odd and t≤2s+1, 2 and G does not have a K -factor. s,t The bounds in Theorem 2 and 3 exhibit a somewhat surprising phenomenon: for the case when k is eventhe bound is independent of the valuet, while for the case k is odd, the minimum-degree condition depends on t. Moreover, we note that our results are not tight for the case t > 2s+1 and k odd. We are very grateful to Andrzej Czygrinow and Louis DeBiasio for drawing our attention to an oversightin Theorem 3 in an earlier version of this note. 2 Lower bound In this section we prove Theorem 3. We treat three cases (based on the parity of k and on the relation between s and t) separately. The proof of Theorem 3 is constructive, i.e., we will construct a graph G with the demanded minimum-degree and then argue that G does not contain a K -factor. s,t ThebuildingblocksofourconstructionsarethegraphsP(m,p),wherem,p∈N. ThegraphsP(m,p) were introduced in [9]. We just state their properties, which will be used throughout this section. Lemma 4. For any p ∈ N there exists a number m0 such that for any m ∈ N,m > m0 there exists a bipartite graph P(m,p)=(P1,P2;EP) satisfying • |P1|=|P2|=m, • P(m,p) is p-regular, and • P(m,p) does not contain a copy of K2,2. In all constructions we assume that n is large enough. 2.1 Case k is even For two integers m and q we write Q(m,q) to denote (any of possibly many) bipartite graph Q(m,q)= (Q1,Q2;EQ) with the following properties: • |Q1|=m,|Q2|=m−2, • Q(m,q) does not contain any K2,2, • deg(x)∈{q−1,q} for any vertex x∈Q1, and • deg(y)=q for any vertex y ∈Q2. SuchgraphsQ(m,q)do existforfixed q andlargem. One wayto constructthem is by takingthe graph P(m,q) = (P1,P2;EP) from Lemma 4, selecting two vertices w1,w2 ∈ P2 such that they do not share a common neighbor in P1, and then take Q(m,q) to be the subgraph of P(m,q) induced by the vertex sets P1, P2\{w1,w2}. In particular, the graph Q(m,0) is the empty graph. Now we describe the construction of the graph G. Partition A = A1 +A2, B = B1 +B2, |A1| = |B1|= n2 +1, |A2|=|B2|= n2 −1. The graph G is described by 2 • G[A ,B ] is a complete bipartite graph for i=1,2, and i i • G[A1,B2]∼=G[B1,A2]∼=Q(n/2+1,s−1). We have δ(G) = n +s−2. The fact that there exists no K -factor is implied immediately by the 2 s,t fact that there is no subgraph isomorphic to Ks,t whose vertices would touch both A1 and B2, or A2 and B1. 2.2 Case k is odd, 2s+1 ≥ t > s+1 Let k = 2l+1, n = k(s+t). Note that n−t+2s+2 is an integer. Partition A = A1 +A2 +A∗, B = B1+B2+B∗, |A1|=|A2|=|B1|=|B2|= n−t+2s+2, |A∗|=|B∗|=t−s−2. The graph G is described by • G[A ,B ] is a complete bipartite graph for i=1,2, i i • G[A∗,Bi] and G[B∗,Ai] are complete bipartite graphs for i=1,2, • G[A1,B2]∼=G[A2,B1]∼=P(n−t+2s+2,s−1), • the graph G[A∗,B∗] is empty. We have δ(G) = n+t+s −2. To see that G does not have a K -factor, we argue as follows. Suppose 2 s,t for contradiction that G has a K -factor. Fix a K -factor of G. First, observe that there cannot be a s,t s,t copyisomorphictoKs,t intersectingbothA1∪B1 andA2∪B2. Letr1 andr2 be thenumberofcopiesof Ks,t in the tiling whose color class of size t touches A1 and B1, respectively. Let Ac and Bc be vertices covered by these r1+r2 copies. It holds A1 ⊂Ac ⊂A1∪A∗ and B1 ⊂Bc ⊂B1∪B∗. (1) If r1 6=r2 then ||Ac|−|Bc||≥t−s, which contradicts (1). Thus, r1 =r2. We conclude that l(s+t)+s+1 l(s+t)+t−1 ≤r1 ≤ , s+t s+t a contradiction to the integrality of r1. 2.3 Case k is odd, t = s+1 By R(m,q) we denote (any ofpossibly many)bipartite graphR(m,q)=(R1,R2;ER) with the following properties: • |R1|=m,|R2|=m−1, • R(m,q) does not contain any K2,2, • for any vertex x in R1, it holds deg(x)∈{q−1,q}, and • for any vertex y in R2, it holds deg(y)=q. For fixedq and largem the existence ofsucha graphR(m,q)follows by a constructionanalogousto the construction of the graph Q(m,q). Let k = 2l+1. Partition A = A1 +A2, B = B1 +B2, |A1| = |B1| = l(s+t)+s, |A2| = |B2| = l(s+t)+s+1. The graph G is described by • G[A ,B ] is a complete bipartite graph for i=1,2, i i • G[B2,A1]∼=G[A2,B1]∼=R((n+1)/2,s−1). One immediately sees that δ(G)= n+t+s −2 and no K -tiling of G exists. 2 s,t 3 3 Upper bound We prove Theorem2 in this section. The proof of Theorem2 utilizes the previous work of Zhao [9]. We will need the following lemma, which allows us to find many vertex disjoint copies of certain stars. For h∈N, an h-star is a graph K1,h, its center is the unique vertex in the part of size one. Moreover, for a graph G and two disjoint sets A,B ⊂V(G) we define δ(A,B)=min{deg(v,B) : v ∈A}, ∆(A,B)=max{deg(v,B) : v ∈A} and e(A,B) d(A,B)= . |A||B| Lemma 5 (Zhao, [9]). Let 1≤h≤δ ≤M and 0<c<1/(6h+7). Suppose that H =(U1,U2;EH) is a bipartite graph such that ||Ui|−M|≤cM for i=1,2. If δ =δ(U1,U2)≤cM and ∆=∆(V2,V1)≤cM, thenwecanfindafamilyofvertex-disjointh-stars,2(δ−h+1)ofwhichhavecentersinU1 and2(δ−h+1) of which have centers in U2. As in [9] we distinguish between an extremal and a non-extremal case. If we find a Ks+t,s+t-factor in G we are done, as each copy of Ks+t,s+t can be split into two copies of Ks,t and hence we have a K -factor. Thus the theorem stated next is just a corollary of [9, Theorem 4.1]. s,t Theorem 6 (Zhao, [9]). For every α > 0 and positive integers s < t, there exist β > 0 and a positive integer k0 such that the following holds for all n = k(s + t) with k > k0. Given a bipartite graph G = (A,B;E) with |A| = |B| = n, if δ(G) > (1 −β)n, then either G contains a K -factor, or there 2 s,t exist A1 ⊂A, B1 ⊂B such that |A1|=|B1|=⌊n/2⌋, d(A1,B1)<α. Therefore, we reduce the problem to the extremal case. Let α= α(t) > 0 be small. As in the proof of Theorem 11 in [9], define A′1=nx∈A:deg(x,B1)<α13 n2o, B1′=nx∈B :deg(x,A1)<α13 n2o, A′2=nx∈A:deg(x,B1)>(1−α13)n2o, B2′=nx∈B :deg(x,A1)>(1−α31)n2o, ′ ′ ′ ′ A0=A−A1−A2, B0=B−B1−B2, ′ ′ ′ ′ G1=G[A1,B1], G2=G[A2,B2]. Similarly as in the proof of Theorem 11 in [9], we assume that removing any edge from G would violate ′ ′ 1 theminimum-degreeconditionandthenchangeAi andBi alittlesothat∆(G1),∆(G2)<α9n. Vertices in A0∪B0 are called special. 3.1 k is even To exhibit the existence of a tiling in this case, it is sufficient to translate carefully the proof of Case I of Theorem 11 from [9]. We give a sketch of the proof below and refer the reader to the corresponding places in [9] for more details. ′ ′ ′ ′ Set V = (A ,B ,A ,B ). First assume, that no member of V contains more than n/2 vertices. We 1 1 2 2 add vertices from A0 and B0 into sets of V in such a way, that every set has size exactly n/2. Then, we may apply arguments used in [9], based on Hall’s Marriage Theorem, to find a Ks+t,s+t tiling. Next, assume that there is only one set in V which has more than n/2 elements. Without loss of ′ ′ ′ ′ generality, assume that it is A , i.e., |A | = c > n/2. Lemma 5 applied to the graph G[A ,B ] yields 2 2 2 2 ′ ′ the existence of c−n/2 disjoint s-stars with centers in A . We move the centers of the stars into A 2 1 ′ ′ and extend each of the stars into a copy of K (each of these copies lies entirely in A ∪B , with s,t 1 2 ′ ′ ′ the color class of size s being contained in B2). We distribute vertices of B0 into B1 and B2 so, that ′ ′ |B | = |B | = n/2. Then, it is easy to finish the entire tiling. This is done in three steps. In the 1 2 first step, we find in an arbitrary manner c−n/2 copies of K (disjoint with the previous ones) in s,t ′ ′ ′ G[A ,B ] placed in such a way, that the color-class of size s lies in A . This step ensures us, that the 1 2 1 cardinalities of untiled (i.e., those vertices which are not covered by the partial K -factor) vertices in s,t ′ ′ the both color-classes of G[A ,B ] are equal and divisible by s+t. In the second step, all yet untiled 1 2 4 ′ ′ vertices of G[A ,B ] which were originally special vertices are tiled. In the third step, the tiling is in an 1 2 ′ ′ analogous manner defined for G[A ,B ]. 2 1 ′ ′ Now, assume that two diagonal sets of V, say A and B have sizes more than n/2. Then we apply 2 1 ′ ′ ′ ′ separately Lemma 5 to G[A ,B ] and G[A ,B ] to obtain families S and S of disjoint s-stars with 2 2 1 1 A B ′ ′ ′ ′ centers in A and B , such that |A |−|S | = |B |−|S | = n/2. We move the centers of the stars to 2 1 2 A 1 B ′ ′ A and B and proceed as in the previous case. 1 2 The remaining case is when two non-diagonal sets from V have size more than n/2. Assume these ′ ′ ′ ′ are A and B . We apply Lemma 5 to the graph G[A ,B ] to obtain families S ,S of disjoint s-stars 2 1 2 2 A B ′ ′ ′ ′ with centers in A and B , such that |A |−|S | = |B |−|S | = n/2. We proceed as in the previous 2 2 2 A 2 B cases. 3.2 k is odd Let k =2l+1. We say that a set of special vertices (A0 and/or B0) is small if its size is less than t−s. Otherwise, it is called big. We distinguish four cases. ′ ′ • Both A0 and B0 are small. Then there exist i,j ∈{1,2},such that |Ai|,|Bj|≥l(s+t)+s+1. If i=j,thenweapply Lemma5tothe graphG andfindfamiliesS , S ofpairwisedisjoints-stars i A B ′ ′ ′ ′ with centers in A and B respectively, so that |A |−|S | = |B |−|S | = l(s+t)+s. Move the i i i A i B ′ ′ ′ ′ centers of the stars in A and B . After the changes we shall tile two graphs: G[A ,B ] and 3−i 3−i 1 2 ′ ′ G[A ,B ]. Note, that both those graphs are not balanced. The tiling procedure is analogous to 2 1 the previous cases (when k is even); the only difference is that one copy of K has to be found in s,t the graphs first to make each of them balanced. ′ ′ If i 6= j, we can assume that |A |,|B | ≤ l(s+t)+s. Since if this does not hold, then we could j i change one index and continue as in the case when i=j. We will show that one can add vertices ′ ′ ′ ′ to A and to B so that |A | = l(s+t)+s and |B | = l(s+t)+t. Then, the existence of the j i j i tilingwillfollowbystandardarguments. We applyLemma 5tothe graphG to obtainafamily of j ′ ′ ′ |B |−(l(s+t)+s) vertex disjoint s-stars with centers in B and end-vertices in A . If we moved j j j ′ ′ all the centers to Bi and all the vertices of B0, the cardinality of Bi would be ′ ′ |Bi|+(|Bj|−(l(s+t)+s))+|B0|=l(s+t)+t. ′ ′ The same applies for A . Therefore, by removing some of the vertices, we may attain |A | = j j ′ l(s+t)+s and |B |=l(s+t)+t. Then, the existence of a tiling follows. i ′ ′ • A0 is small and B0 is big. ThenatleastoneBi (sayB2)hasatmostl(s+t)+svertices. Lemma5 ′ ′ asserts that we can find a family S of disjoint s-stars with centers in B and end-vertices in A , B 1 1 ′ suchthat |B1|−|SB|≤l(s+t)+s. This implies, that we can find vertices(in B0 or centers ofthe ′ ′ stars of S ) which can be moved to B so that |B |=l(s+t)+t. B 2 2 ′ ′ AsA0 issmall,oneofA1 andA2 musthaveatleastl(s+t)+s+1vertices. Thetilingcanbefound ′ ′ by standard arguments if we achieve to have |A | = l(s+t)+s. If |A | > l(s+t)+s, Lemma 5 1 1 ′ ′ yields existence of a family S of disjoint s-stars with centers in A and end-vertices in B such A 1 1 ′ ′ ′ that|A |−|S |=l(s+t)+s. MovingthecenterstoA ,weachieve|A |=l(s+t)+s. Assumethat 1 A 2 1 ′ ′ ′ |A1|≤l(s+t)+s. ThesizeofA2 isk(s+t)−|A1|−|A0|>l(s+t)+s. Lemma5yieldsexistenceof ′ ′ afamilySA ofdisjoints-starsinG2 centeredinA2 withthepropertythat|A1|+|SA|=l(s+t)+s. ′ ′ Moving the centers to A yields demanded A =l(s+t)+s. 1 1 • A0 is big and B0 is small. The analysis of this case is analogous to the previous one. ′ • Both A0 and B0 are big. We shall show in the next paragraph, that we can achieve A1 to be of size l(s+t)+s and of size l(s+t)+t. An analogous procedure can be used to show the same ′ property for the set B . Then, the existence of the tiling follows immediately; one prescribes the 1 ′ ′ cardinalities of A and B to be equal to the same number l(s+t)+s. 1 1 ′ ′ If |Ai ∪A0| < l(s+t)+t for some i ∈ {1,2}, then we have |A3−i| > l(s+t)+s. Appealing to ′ ′ Lemma 5 we can remove centers of s-stars from A in such a way that |A | = l(s+t)+s. 3−i 3−i 5 ′ ′ Also, by moving t−s vertices from the big set A0 to A3−i arrive at |A3−i| = l(s+t)+t. Then, the partial K -tiling can be extended to a K -factor. s,t s,t ′ ′ Finally,if both|A |≤l(s+t)+s and|A |≤l(s+t)+s then weredistribute some vertices(again, 1 2 ′ appealing to Lemma 5, and using the set A0) to arrive at the situation when |A1| = l(s+t)+s, ′ |A |=l(s+t)+t. Then the tiling can be extended as before. 2 Acknowledgement We thank a careful referee for suggesting several improvements in the presentation. References [1] N. Alon and R. Yuster. Almost H-factors in dense graphs. Graphs Combin., 8(2):95–102,1992. [2] N. Alon and R. Yuster. H-factors in dense graphs. J. Combin. Theory Ser. B, 66(2):269–282,1996. [3] E. Fischer. Variants of the Hajnal-Szemerédi theorem. J. Graph Theory, 31(4):275–282,1999. [4] A. Hajnal and E. Szemerédi. Proof of a conjecture of P. Erdo˝s. In Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), pages 601–623. North-Holland, Amsterdam, 1970. [5] J. Komlós. Tiling Turán theorems. Combinatorica, 20(2):203–218,2000. [6] D. Kühnand D. Osthus. The minimum degree thresholdforperfect graphpackings. Combinatorica, 29(1):65–107,2009. [7] L.LovászandM.D. Plummer. Matching theory, volume 121ofNorth-Holland Mathematics Studies. North-Holland Publishing Co., Amsterdam, 1986. Annals of Discrete Mathematics, 29. [8] A.ShokoufandehandY.Zhao.ProofofatilingconjectureofKomlós.RandomStructuresAlgorithms, 23(2):180–205,2003. [9] Y. Zhao. Bipartite graph tiling. SIAM J. Discrete Math., 23(2):888–900,2009. 6