https://doi.org/10.31449/inf.v43i1.2684 Informatica 43 (2019) 23–31 23 On Embedding Degree Sequences Béla Csaba Bolyai Institute, Interdisciplinary Excellence Centre, University of Szeged, Hungary E-mail: csaba@math.u-szeged.hu Bálint Vásárhelyi University of Szeged, Hungary E-mail: mesti@math.u-szeged.hu Keywords: graph theory, degree sequence, embedding Received: October 30, 2018 Assume that we are given two graphic sequences, 1 and 2 . We consider conditions for 1 and 2 which guarantee that there exists a simple graphG 2 realizing 2 such thatG 2 is the subgraph of any simple graph G 1 that realizes 1 . Povzetek: Recimo, da imamo grafni zaporedji 1 in 2 . V prispevku preuˇ cujemo pogoje za zaporedji, ki zagotavljajo, da obstaja preprost graf G 2 , ki je realizacija 2 in je podgraf grafa G 1 , ki je realizacija zaporedja 2 . 1 Introduction All graphs considered in this paper are simple. We use stan- dard graph theory notation, see for example [16]. Let us provide a short list of a few perhaps not so common no- tions, notations. Given a bipartite graphG(A;B) we call it balanced ifjAj =jBj. This notion naturally generalizes forr-partite graphs withr2N;r 2. IfS V for some graphG = (V;E) then the subgraph spanned byS is denoted byG[S]. Moreover, letQ V so thatS\Q =;; thenG[S;Q] denotes the bipartite sub- graph ofG on vertex classesS andQ; having every edge ofG that connects a vertex ofS with a vertex ofQ. The number of vertices in G is denoted by v(G); the number of its edges is denoted by e(G). The degree of a vertex x2 V (G) is denoted by deg G (x); or if G is clear from the context, bydeg(x). The number of neighbors ofx in a subsetS V (G) is denoted bydeg G (x;S); and (G) and ( G) denote the minimum and maximum degree ofG; re- spectively. The complete graph onn vertices is denoted by K n ; the complete bipartite graph with vertex class sizesn andm is denoted byK n;m . A finite sequence of natural numbers = (d 1 ;:::;d n ) is a graphic sequence or degree sequence if there exists a graph G such that is the (not necessarily) monotone degree se- quence ofG. Such a graphG realizes . For example, the degree sequence = (2; 2;:::; 2) can be realized only by vertex-disjoint union of cycles. The largest value of is denoted by ( ). Often the po- sitions of will be identified with the elements of a vertex setV . In this case, we write (v) (v2 V ) for the corre- sponding component of . The degree sequence = (a 1 ;:::;a k ;b 1 ;:::;b l ) is a bi- graphic sequence if there exists a simple bipartite graph G =G(A;B) withjAj =k,jBj =l realizing such that the degrees of vertices inA area 1 ;:::;a k ; and the degrees of the vertices ofB areb 1 ;:::;b l . LetG andH be two graphs onn vertices. We say thatH is a subgraph ofG; if we can delete edges fromG so that we obtain an isomorphic copy ofH. We denote this relation byH G. In the literature the equivalent complementary formulation can be found as well: we say that H and G pack if there exist edge-disjoint copies ofH andG inK n . HereG denotes the complement ofG. It is an old an well-understood problem in graph theory to tell whether a given sequence of natural numbers is a de- gree sequence or not. We consider a generalization of it, which is remotely related to the so-called discrete tomog- raphy 1 (or degree sequence packing) problem (see e.g. [5]) as well. The question whether a sequence of n numbers is a degree sequence can also be formulated as follows: DoesK n have a subgraphH such that the degree sequence of H is ? The question becomes more general if K n is replaced by some (simple) graph G on n vertices. If the answer is yes, we say that can be embedded intoG; or equivalently, packs withG. Let us mention two classical results in extremal graph the- ory. Theorem 1 (Dirac, [6]). Every graphG withn 3 ver- tices and minimum degree (G) n 2 has a Hamilton cycle. 1 In the discrete tomography problem we are given two degree se- quences of lengthn, 1 and 2 ; and the questions is whether there exists a graphG onn vertices with a red-blue edge coloration so that the fol- lowing holds: for every vertexv the red degree ofv is 1 (v) and the blue degree ofv is 2 (v). 24 Informatica 43 (2019) 23–31 B. Csaba et al. Theorem 2 (Corrádi-Hajnal, [3]). Let k 1, n 3k, and letH be ann-vertex graph with (H) 2k. ThenH containsk vertex-disjoint cycles. Observe, that Dirac’s theorem implies that given a constant 2 degree sequence of length n and any graph G on n vertices having minimum degree (G) n=2; can be embedded into G: One can interprete the Corrádi-Hajnal theorem similarly, but here one may require more on the structure of the graph that realizes and in exchange a larger minimum degree ofG is needed. One of our main results is the following. Theorem 3. For every > 0 andD2 N there exists an n 0 =n 0 (;D ) such that for alln>n 0 ifG is a graph onn vertices with (G) 1 2 + n and is a degree sequence of lengthn with ( ) D, then is embeddable intoG. It is easy to see that Theorem 3 is sharp up to then ad- ditive term. For that let n be an even number, and sup- pose that every element of is 1. Then the only graph that realizes is the union of n=2 vertex disjoint edges. Let G = K n=2 1;n=2+1 be the complete bipartite graph with vertex class sizesn=2 1 andn=2 + 1. ClearlyG does not haven=2 vertex disjoint edges. In order to state the other main result of the paper we intro- duce a new notion. Definition 4. Letq 1 be an integer. A bipartite graphH with vertex classesS andT isq-unbalanced, ifqjSjj Tj. The degree sequence isq-unbalanced, if it can be realized by aq-unbalanced bipartite graph. Theorem 5. Let q 1 be an integer. For every > 0 and D 2 N there exist an n 0 = n 0 (;q ) and an M = M(;D;q ) such that ifn n 0 ; is aq-unbalanced degree sequence of lengthn M with ( ) D;G is a graph on n vertices with (G) ( 1 q+1 + )n, then can be embedded intoG. Hence, if is unbalanced, the minimum degree require- ment of Theorem 3 can be substantially decreased, what we pay for this is that the length of has to be slightly smaller than the number of vertices in the host graph. 2 Proof of Theorem 3 Proof. First, we find a suitable realization H of ; our H will consists of components of bounded size. Second, we embedH intoG using a theorem by Chvátal and Sze- merédi and a result on embedding so called well-separable graphs. The details are as follows. We construct H in several steps. At the beginning, let H be the empty graph and let all degrees in be active. While we can find 2i active degrees of with valuei (for some 1 i ( )) we realize them with a K i;i (that is, we add this complete bipartite graph to H, and the 2i degrees are “inactivated”). When we stop we have at most P ( ) i=1 (2i 1) active degrees. This way we obtain sev- eral components, each being a balanced complete bipar- tite graph. These are the type 1 gadgets. Observe that if a vertexv belongs to some type 1 gadget, then its degree is exactly (v): Observe further that if there are no active degrees in at this point then the graph H we have just found is a realization of: Assume that there are active degrees left in : Let R = R odd [R even be the vertex set that is identified with the active vertices (v2R odd if and only if the assigned active degree is odd). Since P v2R d(v) must be an even number we have thatjR odd j is even. Add a perfect matching onR odd toH. With this we achieved that every vertex ofR misses an even number of edges. Next we construct the type 2 gadgets using the following al- gorithm. In the beginning every type 1 gadget is unmarked. Suppose thatv2R is an active vertex. Take a type 1 gad- get K; mark it, and let M K denote an arbitrarily chosen perfect matching in K (M K exists since K is a balanced complete bipartite graph). Let xy be an arbitrary edge in M K . Delete thexy edge and add the new edgesvx andvy. Whilev is missing edges repeat the above procedure with edges ofM K ; untilM K becomes empty. IfM K becomes empty, take a new unmarked type 1 gadget L; and repeat the method withL. It is easy to see that in (v)=2 stepsv reaches its desired degree and gets inactivated. Clearly, the degrees of vertices in the marked type 1 gadgets have not changed. 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 1 1 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 2 2 2 2 2 3 3 3 3 3 Figure 1: Type 2 gadgets ofH with a 3-coloring Figure 1 shows examples of type 2 gadgets. In the upper one two vertices ofR odd were first connected by an edge and then two type 1 gadgets were used so that they could reach their desired degree, while in the lower one we used three type 1 gadgets for a vertex ofR: The numbers at the On Embedding Degree Sequences Informatica 43 (2019) 23–31 25 vertices indicate the colors in the 3-coloring ofH: Let A V (H) denote the set of vertices containing the union of all type 2 gadgets. Observe that type 2 gadgets are 3-colorable and all have less than 5 2 ( ) vertices. Let us summarize our knowledge aboutH for later reference. Claim 6. (1) jAj 5 3 ( ); (2) the components of H[V A] are balanced complete bipartite graphs, each having size at most 2( ); (3) (H[A]) 3; and (4) e(H[A;V A]) = 0. We are going to show thatH G. For that we first em- bed the possibly 3-chromatic partH[A] using the follow- ing strengthening of the Erd˝ os–Stone theorem proved by Chvátal and Szemerédi [2]. Theorem 7. Let’> 0 and assume thatG is a graph onn vertices wheren is sufficiently large. Letr2N;r 2. If e(G) r 2 2(r 1) +’ n 2 ; then G contains a K r (t), i.e. a complete r-partite graph witht vertices in each class, such that t> logn 500 log 1 ’ : (1) Since (G) (1=2+ )n; the conditions of Theorem 7 are satisfied withr = 3 and’ == 2; hence,G contains a bal- anced complete tripartite subgraphT on (log n) vertices. Using Claim 6 and the 3-colorability ofH[A] this implies thatH[A] T . Observe that after embedding H[A] into G every uncov- ered vertex ofG still has at least (G) v(F ) > (1=2 + = 2)n uncovered neighbors. Denoting the subgraph of the uncovered vertices of G by G 0 we obtain that (G 0 ) > (1=2 += 2)n: In order to prove that H[V A] G 0 we first need a definition. Definition 8. A graphF onn vertices is well-separable if it has a subsetS V (F ) of sizeo(n) such that all compo- nents ofF S are of sizeo(n). We need the following theorem. Theorem 9 ([4]). For every > 0 and positive integer D there exists an n 0 such that for all n > n 0 if F is a bipartite well-separable graph onn vertices, ( F ) D and (G) 1 2 + n for a graph G of order n, then F G. SinceH[V A] has bounded size components by Claim 6, we can apply Theorem 9 forH[V A] andG 0 ; with pa- rameter = = 2. With this we finished proving what was desired. 3 Further tools for Theorem 5 When proving Theorem 3, we used the Regularity Lemma of Szemerédi, but implicitly, via the result on embedding well-separable graphs. When proving Theorem 5 we will apply this very powerful result explicitly, hence, below we give a very brief introduction to the area. The inter- ested reader may consult with the original paper by Sze- merédi [15] or e.g. with the survey paper [10]. 3.1 Regularity lemma The density between disjoint setsX andY is defined as: d(X;Y ) = e(X;Y ) jXjjYj : We will need the following definition to state the Regularity Lemma. Definition 10 (Regularity condition). Let " > 0. A pair (A;B) of disjoint vertex-sets inG is"-regular if for every X A andY B, satisfying jXj>"jAj;jYj>"jBj we have jd(X;Y ) d(A;B)j<": This definition implies that regular pairs are highly uni- form bipartite graphs; namely, the density of any reason- ably large subgraph is almost the same as the density of the regular pair. We will use the following form of the Regularity Lemma: Lemma 11 (Degree Form). For every " > 0 there is an M = M(") such that if G = (W;E) is any graph and d2 [0; 1] is any real number, then there is a partition of the vertex setV into‘ + 1 clustersW 0 ;W 1 ;:::;W ‘ , and there is a subgraphG 0 ofG with the following properties: – ‘ M, – jW 0 j "jWj, – all clusters W i , i 1, are of the same size m j jWj ‘ k <"jWj , – deg G 0(v)>deg G (v) (d +")jWj for allv2W , – G 0 j Wi =; (W i is an independent set in G 0 ) for all i 1, – all pairs (W i ;W j ), 1 i < j ‘, are "-regular, each with density either 0 or greater thand inG 0 . 26 Informatica 43 (2019) 23–31 B. Csaba et al. We call W 0 the exceptional cluster, W 1 ;:::;W ‘ are the non-exceptional clusters. In the rest of the paper we will assume that 0<" d 1. Herea b means thata is sufficiently smaller thanb. Definition 12 (Reduced graph). Apply Lemma 11 to the graphG = (W;E) with parameters" andd, and denote the clusters of the resulting partition by W 0 ;W 1 ;:::;W ‘ (W 0 being the exceptional cluster). We construct a new graphG r , the reduced graph of G 0 in the following way: The non-exceptional clusters of G 0 are the vertices of the reduced graph G r (hence v(G r ) = ‘). We connect two vertices ofG r by an edge if the corresponding two clusters form an"-regular pair with density at leastd. The following corollary is immediate: Corollary 13. Apply Lemma 11 with parameters" andd to the graphG = (W;E) satisfying (G) n (v(G) =n) for some > 0. DenoteG r the reduced graph ofG 0 . Then (G r ) ( )‘, where = 2" +d. The (fairly easy) proof of the lemma below can be found in [10]. Lemma 14. Let (A;B) be an"-regular–pair with density d for some> 0. Letc> 0 be a constant such that" c. We arbitrarily divideA andB into two parts, obtaining the non-empty subsets A 0 ;A 00 and B 0 ;B 00 , respectively. As- sume thatjA 0 j;jA 00 j cjAj andjB 0 j;jB 00 j cjBj. Then the pairs (A 0 ;B 0 ); (A 0 ;B 00 ); (A 00 ;B 0 ) and (A 00 ;B 00 ) are all"=c–regular pairs with density at leastd "=c. 3.2 Blow-up lemma LetH andG be two graphs onn vertices. Assume that we want to find an isomorphic copy of H in G. In order to achieve this one can apply a very powerful tool, the Blow- up Lemma of Komlós, Sárközy and Szemerédi [8, 9]. For stating it we need a new notion, a stronger one-sided prop- erty of regular pairs. Definition 15 (Super-Regularity condition). Given a graph G and two disjoint subsets of its verticesA andB, the pair (A;B) is ("; )-super-regular, if it is"-regular and further- more, deg(a)>jBj; for alla2A; and deg(b)>jAj; for allb2B: Theorem 16 (Blow-up Lemma). Given a graph R of order r and positive integers ; ; there exists a posi- tive " = "(; ;r) such that the following holds: Let n 1 ;n 2 ;:::;n r be arbitrary positive parameters and let us replace the verticesv 1 ;v 2 ;:::;v r ofR with pairwise dis- joint sets W 1 ;W 2 ;:::;W r of sizes n 1 ;n 2 ;:::;n r (blow- ing up R). We construct two graphs on the same vertex set V =[ i W i . The first graph F is obtained by replac- ing each edge v i v j 2 E(R) with the complete bipartite graph between W i and W j . A sparser graph G is con- structed by replacing each edge v i v j arbitrarily with an ("; )-super-regular pair betweenW i andW j . If a graph H with ( H) is embeddable intoF then it is already embeddable intoG. 4 Proof of Theorem 5 Let us give a brief sketch first. Recall, that is a q- unbalanced and bounded degree sequence with ( ) D. In the proof we first show that there exists aq-unbalanced bipartite graph H that realizes such that H is the ver- tex disjoint union of the graphs H 1 ;:::;H k ; where each H i graph is a bipartiteq-unbalanced graph having bounded size. We will apply the Regularity lemma to G; and find a special substructure (a decomposition into vertex-disjoint stars) in the reduced graph ofG. This substructure can then be used to embed the union of theH i graphs, for the ma- jority of them we use the Blow-up lemma. 4.1 FindingH The goal of this subsection is to prove the lemma below. Lemma 17. Let be aq-unbalanced degree sequence of positive integers with ( ) D. Then can be real- ized by a q-unbalanced bipartite graph H which is the vertex disjoint union of the graphsH 1 ;:::;H k ; such that for every i we have that H i is q-unbalanced, moreover, v(H i ) 4D 2 . Before starting the proof of Lemma 17, we list a few nec- essary notions and results. We call a finite sequence of integers a zero-sum sequence if the sum of its elements is zero. The following result of Sahs, Sissokho and Torf plays an important role in the proof of Lemma 17. Proposition 18. [14] Assume that K is a positive inte- ger. Then any zero-sum sequence onf K;:::;Kg having length at least 2K contains a proper nonempty zero-sum subsequence. The following result, formulated by Gale [7] and Ryser [13], will also be useful. We present it in the form as dis- cussed in Lovász [11]. Lemma 19. [11] Let G = (A;B;E(G)) be a bipar- tite graph and f be a nonnegative integer function on A[B withf(A) = f(B). ThenG has a subgraphF = (A;B;E(F )) such thatd F (x) = f(x) for allx2 A[B if and only if f(X) e(X;Y ) +f(Y ) (2) for anyX A andY B, whereY =B Y . We remark that such a subgraphF is also called anf-factor ofG. On Embedding Degree Sequences Informatica 43 (2019) 23–31 27 Lemma 20. Iff = (a 1 ;:::;a s ;b 1 ;:::;b t ) is a sequence of positive integers withs;t 2 2 , where is the maxi- mum off, andf(A) = f(B) withA =fa 1 ;:::;a s g and B =fb 1 ;:::;b t g thenf is bigraphic. Proof. All we have to check is whether the conditions of Lemma 19 are met ifG =K s;t . Suppose indirectly that there is an (X;Y ) pair for which (2) does not hold. Choose such a pair with minimaljXj +jYj. Then X =; or Y =; are impossible, as in those cases (2) trivially holds. Hence,jXj;jYj 1. Assuming that (2) does not hold, we have that f(X) e(X;Y ) +f(Y ) + 1; (3) which is equivalent to f(X)j XjjYj +f(Y ) + 1; (4) asG is a complete bipartite graph. Furthermore, using the minimality ofjXj +jYj, we know that f(X a)j X ajjYj +f(Y ) (5) for anya2X. (5) is equivalent to f(X) f(a)j XjjYjj Yj +f(Y ): (6) From (4) and (6) we have f(a) 1j Yj (7) for anya2X, which implies >jYj: (8) The same reasoning also implies that >jXj whenever (X;Y ) is a counterexample. Therefore we only have to verify that (2) holds in casejXj< andjYj< . Recall that f(B) t, as all elements of f are positive. Hence, f(X) jXj 2 , andf(Y ) =f(B) f(Y ) t 2 ; and we get that f(X) 2 t 2 f(Y ) f(Y ) +e G (X;Y ) (9) holds, sincet 2 2 . Proof. (Lemma 17) Assume thatJ = S;T ;E(J) is aq- unbalanced bipartite graph realizing . Hence,qjSjj Tj. Moreover,jTj DjSj; since ( ) D. We form vertex disjoint tuples of the form (s;t 1 ;:::;t h ); such thats2S; t i 2 T; q h D; and the collection of these tuples contains every vertex ofS[T exactly once. We define the bias of the tuple as = (t 1 ) + + (t h ) (s): Obviously, D D 2 . The conditions of Proposi- tion 18 are clearly met withK =D 2 . Hence, we can form groups of size at most 2D 2 in which the sums of biases are zero. This way we obtain a partition of (S;T ) intoq- unbalanced set pairs which have zero bias. While these sets may be small, we can combine them so that each combined set is of size at least 2D 2 and has zero bias. By Lemma 20 these are bigraphic sequences. The realizations of these small sequences give the graphsH 1 ;:::;H k . It is easy to see thatv(H i ) 4D 2 for every 1 i k. Finally, we let H =[ i H i . 4.2 DecomposingG r Let us apply the Regularity lemma with parameters 0 < " d . By Corollary 13 we have that (G r ) ‘=(q + 1) +‘= 2. Leth 1 be an integer. Anh-star is aK 1;h . The center of anh-star is the vertex of degreeh; the other vertices are the leaves. In caseh = 1 we pick one of the vertices of the 1-star arbitrarily to be the center. Lemma 21. The reduced graphG r has a decompositionS into vertex disjoint stars such that each star has at mostq leaves. Proof. Take a partial star-decomposition of G r that is as large as possible. Assume that there are uncovered vertices inG r . LetU denote those vertices that are covered (so we assume thatU has maximal cardinality), and letv be an un- covered vertex. Observe thatv has neighbours only inU; otherwise, ifuv2 E(G r ) withu = 2 U, then we can sim- ply adduv to the star-decomposition, contradicting to the maximality ofU. See Figure 2 for the possible neighbors ofv. a) Ifv is connected to a 1-star, then we can replace it with a 2-star. b) If v is connected to the center u of an h-star, where h < q, then we can replace this star with anh + 1-star by adding the edgeuv to theh-star. c) If v is connected to a leaf u of an h-star, where 2 h q, then replace the star with the edge uv and an (h 1)-star (i.e., deleteu from it). We have not yet considered one more case: whenv is con- nected to the center of aq-star. However, simple calcula- tion shows that for every vertexv at least one of the above three cases must hold, using the minimum degree condi- tion ofG r . Hence we can increase the number of covered vertices. We arrived at a contradiction,G r has the desired star-decomposition. 4.3 PreparingG for the embedding Consider the q-star-decomposition S of G R as in Lemma 21. Let ‘ i denote the number of (i 1)-stars in 28 Informatica 43 (2019) 23–31 B. Csaba et al. v a) b) c) d) Figure 2: An illustration for Lemma 21 the decomposition for every 2 i q +1. It is easy to see that q+1 X i=2 i‘ i =‘: First we will make every"-regular pair inS super-regular by discarding a few vertices from the non-exceptional clus- ters. Let for exampleC be a star in the decomposition of G r with center cluster A and leaves B 1 ;:::;B k ; where 1 k q. Recall that the (A;B i ) pairs has density at leastd. We repeat the following for every 1 i k : if v2A such thatv has at most 2dm=3 neighbors inB i then discardv fromA; put it intoW 0 . Similarly, ifw2B i has at most 2dm=3 neighbors in A; then discard w from B i ; put it intoW 0 . Repeat this process for every star inS. We have the following: Claim 22. We do not discard more thanq"m vertices from any non-exceptional cluster. Proof. Given a starC in the decompositionS assume that its center cluster isA and letB be one of its leaves. Since the pair (A;B) is"-regular with density at leastd; neither A; norB can have more than"m vertices that have at most 2dm=3 neighbors in the opposite cluster. Hence, during the above process we may discard up toq"m vertices fromA. Next, we may discard vertices from the leaves, but since no leafB had more than"m vertices with less than (d ")m neighbors inA; even after discarding at mostq"m vertices ofA; there can be at most"m vertices inB that have less than (d (q + 1)")m neighbors inA. Using that" d; we have that (d (q + 1)") > 2d=3. We obtained what was desired. By the above claim we can make every "-regular pair in S a (2"; 2d=3)-super-regular pair so that we discard only relatively few vertices. Notice that we only have an upper bound for the number of discarded vertices, there can be clusters from which we have not put any points into W 0 . We repeat the following for every non-exceptional cluster: ifs vertices were discarded from it withs deg(w;A)=3 for every w2B – deg(w;B 0 );deg(w;B 00 ) > deg(w;B)=3 for every w2A – the densityd(A 0 ;B 0 ) d=2 It is easy to see that Lemma 29 implies that (A 0 ;B 0 ) is a (5";d=6)-super-regular pair having density at least d=2 with high probability. Assume thatv was an element ofW 0 before we assigned it to the cluster A; and assume further that deg(v;B) m= 4. Since (A;B) is an edge of the star-decomposition, eitherA orB must be the center ofC. LetH i be one of theq-unbalanced bipartite subgraphs ofH that has not been embedded yet. We will useH i to cover v. DenoteS i andT i the vertex classes ofH i ; wherejS i j qjT i j. LetS i =fx 1 ;:::;x s g andT i =fy 1 ;:::;y t g. If A is the center ofC then the vertices of T i will cover vertices ofA 0 ; and the vertices ofS i will cover vertices of B 0 . If B is the center, S i and T i will switch roles. The embedding ofH i is essentially identical in both cases, so we will only discuss the case whenA is the center. 2 In order to cover v we will essentially use a well-known method called Key lemma in [10]. We will heavily use the fact that 0<" d : The details are as follows. We construct an edge-preserving injective mapping’ : S i [T i ! A 0 [B 0 . In particular, we will have’(S i ) B 0 and’(T i ) v A 0 . First we let’(y 1 ) =v. SetN 1 =N(v)\B 0 . Using Lemma 29 we have thatjN 1 j m= 12 "m. Next we find ’(y 2 ). SincejN 1 j "m; by 5"-regularity the majority of the vacant vertices ofA 0 will have at least djN 1 j=3 neighbors inN 1 . Pick any of these, denote it by v 2 and let’(y 2 ) =v 2 . Also, setN 2 =N 1 \N(v 2 ). In general, assume that we have already found the vertices v 2 ;v 3 ;:::;v i ; their common neighborhood inB 0 isN i ; and jN i j d i 1 3 i 2 36 m "m: By 5"-regularity, this implies that the majority of the vacant vertices ofA 0 has large degree intoN i ; at leastdjN i j=3; and this, as above, can be used to findv i+1 . Then we set ’(y i+1 ) = v i+1 . Since and d is large compared to "; even into the last setN t 1 many vacant vertices will have large degrees. 2 Recall that ifh < q then we may assignedv to a leaf, so in such a caseB could be the center. 30 Informatica 43 (2019) 23–31 B. Csaba et al. As soon as we have’(y 1 );:::;’(y t ); it is easy to find the images for x 1 ;:::;x t . SincejN t j "m s =jS i j; we can arbitrarily chooses vacant points fromN t for the ’(x j ) images. Note that we use less than v(H i ) 4D 2 vertices from A 0 andB 0 during this process. We can repeat it for every vertex that were assigned toA; and still at most p d2D 2 m vertices will be covered fromA 0 and fromB 0 . Another observation is that everyh-star in the decomposi- tion before this embedding phase wash-unbalanced, now, since we were careful, these have becomeh 0 -balanced with h 0 h. Of course, the above method will be repeated for every (A;B) edge of the decomposition for which we have as- signed vertices ofW 0 . 4.4.2 The second phase In the second phase we first unite all the randomly parti- tioned clusters. For example, assume that after covering the vertices that were coming from W 0 the set of vacant ver- tices ofA 0 is denoted byA 0 v . Then we letA v =A 0 v [A 00 ; and using analogous notation, letB v =B 0 v [B 00 . Claim 30. All the (A v ;B v ) pairs are (3";d=6)-super- regular with density at leastd=2. Proof. The 3"-regularity of these pairs is easy to see, like the lower bound for the density, since we have only covered relatively few vertices of the clusters. For the large mini- mum degrees note that by Lemma 29 every vertex ofA had at leastdm=6 neighbors inB 00 ; hence, inB v as well, and analogous bound holds for vertices ofB. At this point we want to apply the Blow-up lemma for every star ofS individually. For that we first have to assign those subgraphs ofH to stars that were not embedded yet. We need a lemma. Lemma 31. LetK a;b be a complete bipartite graph with vertex classesA andB; wherejAj = a andjBj = b. As- sume thata b = ha; where 1 h q. LetH 0 be the vertex disjoint union ofq-unbalanced bipartite graphs: H 0 = t [ j=1 H j ; such thatv(H j ) 2D 2 for everyj. Ifv(H 0 ) a +b 4(2q + 1)D 2 ; thenH 0 K a;b . Observe that if we have Lemma 31, we can distribute the H i subgraphs among the stars ofS; and then apply the Blow-up lemma. Hence, we are done with proving The- orem 5 if we prove Lemma 31 above. Proof. The proof is an assigning algorithm and its analysis. We assign the vertex classes of theH j subgraphs toA and B; one-by-one. Before assigning thejth subgraphH j the number of vacant vertices of A is denoted by a j and the number of vacant vertices ofB is denoted byb j . Assume that we want to assignH k . Ifha k b k > 0; then the larger vertex class ofH k is assigned toA; the smaller is assigned to B. Otherwise, if ha k b k 0; then we assign the larger vertex class to B and the smaller one to A. Then we update the number of vacant vertices ofA and B. Observe that using this assigning method we always havea k b k . The question is whether we have enough room forH k . If ha 4hD 2 ; then we must have enough room, sinceb k a k and everyH j has at most 2D 2 vertices. Hence, if the algorithm stops, we must have a k < 4D 2 . Since b k ha k 2D 2 must hold, we have b k < (2h + 1)2D 2 < (2q + 1)2D 2 . From this the lemma follows. 5 Remarks One can prove a very similar result to Theorem 5, in fact the result below follows easily from it. For stating it we need the notion of graph edit distance which is detailed e.g. in [12]: the edit distance between two graphs on the same labeled vertex set is defined to be the size of the sym- metric difference of the edge sets Theorem 32. Let q 1 be an integer. For every > 0 and D 2 N there exists an n 0 = n 0 (;q ) and a K = K(;D;q ) such that ifn n 0 , is aq-unbalanced degree sequence of lengthn with ( ) D,G is a graph onn vertices with (G) ( 1 q+1 + )n, then there exists a graph G 0 onn vertices such that the edit distance ofG andG 0 is at mostK, and can be embedded intoG 0 . Here is an example showing that Theorem 5 and 32 are essentially best possible. Example 33. Assume that has only odd numbers andG has at least one odd sized component. Then the embedding is impossible. Indeed, any realization of has only even sized components, hence,G cannot contain it as a spanning subgraph. Note that this example does not work in case G is con- nected. In Theorem 3 the minimum degree (G) (1=2 + )n; hence,G is connected, and in this case we can embed intoG. Acknowledgement Partially supported by Ministry of Human Capacities, Hun- gary, grant 20391-3/2018/FEKUSTRAT, by ERC-AdG. 321400 and by the National Research, Development and Innovation Office - NKFIH Fund No. SNN-117879 and KH 129597. Supported by TÁMOP-4.2.2.B-15/1/KONV-2015-0006. On Embedding Degree Sequences Informatica 43 (2019) 23–31 31 References [1] N. Alon, J. Spencer. The probabilistic method. Third edition, John Wiley & Sons, Inc., 2008. https: //doi.org/10.1002/9780470277331 [2] V . Chvátal and E. Szemerédi. On the Erd˝ os–Stone Theorem. Journal of the London Mathematical So- ciety, s2-23 (2):207–214, 1981. [3] K. Corrádi and A. Hajnal. On the maximal num- ber of independent circuits in a graph. Acta Mathematica Academiae Scientiarum Hungari- cae, 14:423–439, 1963. https://doi.org/ 10.1007/BF01895727 [4] B. Csaba. On embedding well-separable graphs. Discrete Mathematics, 308(19):4322–4331, 2008. https://doi.org/10.1016/j.disc. 2007.08.015 [5] J. Diemunsch, M. Ferrara, S. Jahanbekam, and J. Shook. Extremal theorems for degree se- quence packing and the 2-color discrete tomog- raphy problem. SIAM Journal of Discrete Mathe- matics, 29(4):2088–2099, 2015. https://doi. org/10.1137/140987912 [6] G. Dirac. Some theorems on abstract graphs. Pro- ceedings of the London Mathematical Society, s3-2(1):69–81, 1952. https://doi.org/10. 1112/plms/s3-2.1.69 [7] D. Gale. A theorem on flows in networks. Pacific Journal of Mathematics, 7(2):1073–1082, 1957. https://doi.org/10.2140/pjm.1957. 7.1073 [8] J. Komlós, G. Sárközy, and E. Szemerédi. Blow- up lemma. Combinatorica, 17:109–123, 1997. https://doi.org/10.1007/BF01196135 [9] J. Komlós, G. Sárközy, and E. Szemerédi. An algorithmic version of the blow-up lemma. Random Structures and Algorithms, 12:297– 312, 1998. https://doi.org/10.1002/ (SICI)1098-2418(199805)12:3<297:: AID-RSA5>3.0.CO;2-Q [10] J. Komlós and M. Simonovits. Szemerédi’s regular- ity lemma and its applications in graph theory. Com- binatorics: Paul Erd˝ os is eighty, 2:295–352, 1993. [11] L. Lovász. Combinatorial problems and exercises. Corrected reprint of the 1993 second edition, AMS Chelsea Publishing, Providence, RI, 2007. [12] R. Martin. The edit distance in graphs: Meth- ods, results, and generalizations. In A. Beveridge, J. Griggs, L. Hogben, G. Musiker, and P. Tetali, edi- tors, Recent Trends in Combinatorics, pages 31–62. Springer International Publishing, Cham, 2016. [13] H. Ryser. Combinatorial properties of matrices of zeros and ones. Canadian Journal of Mathemat- ics, 9:371–377, 1957. https://doi.org/10. 4153/CJM-1957-044-3 [14] M. Sahs, P. Sissokho, and J. Torf. A zero-sum theo- rem overZ. Integers, 13:#A70, 2013. [15] E. Szemerédi. Regular partitions of graphs. Collo- ques Internationaux C.N.R.S 260 - Problèmes Com- binatoires et Théorie des Graphes, pages 399–401, 1976. [16] D. West. Introduction to graph theory. Prentice Hall, Second edition, 2001. 32 Informatica 43 (2019) 23–31 B. Csaba et al.