Printer Friendly

On Embedding Degree Sequences.

Assume that we are given two graphic sequences, [[pi].sub.1] and [[pi].sub.2]. We consider conditions for [[pi].sub.1] and [[pi].sub.2] which guarantee that there exists a simple graph [G.sub.2] realizing [[pi].sub.2] such that [G.sub.2] is the subgraph of any simple graph [G.sub.1] that realizes [[pi].sub.1].

Povzetek: Recimo, da imamo grafni zaporedji [[pi].sub.1] in [[pi].sub.2]. V prispevku preucujemo pogoje za zaporedji, ki zagotavljajo, da obstaja preprost graf [G.sub.2], ki je realizacija [[pi].sub.2] in je podgraf grafa [G.sub.1], ki je realizacija zaporedja [[pi].sub.2].

Keywords: graph theory, degree sequence, embedding

1 Introduction

All graphs considered in this paper are simple. We use standard graph theory notation, see for example [16]. Let us provide a short list of a few perhaps not so common notions, notations. Given a bipartite graph G(A, B) we call it balanced if [absolute value of A] = [absolute value of B]. This notion naturally generalizes for r-partite graphs with r [member of] N, r [greater than or equal to] 2.

If S [subset] V for some graph G = (V, E) then the subgraph spanned by S is denoted by G[5]. Moreover, let Q [subset] V so that S [intersection] Q = [empty set], then G[S, Q] denotes the bipartite subgraph of G on vertex classes S and Q, having every edge of G that connects a vertex of S with a vertex of Q. 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 x [member of] V(G) is denoted by [deg.sub.G](x), or if G is clear from the context, by deg(x). The number of neighbors of x in a subset S [subset] V(G) is denoted by [deg.sub.G]{x, S), and [delta](G) and [DELTA](G) denote the minimum and maximum degree of G, respectively. The complete graph on n vertices is denoted by [K.sub.n], the complete bipartite graph with vertex class sizes n and m is denoted by [K.sub.n,m].

A finite sequence of natural numbers [pi] = ([d.sub.1],..., [d.sub.n]) is a graphic sequence or degree sequence if there exists a graph G such that [pi] is the (not necessarily) monotone degree sequence of G. Such a graph G realizes [pi]. For example, the degree sequence [pi] = (2,2,..., 2) can be realized only by vertex-disjoint union of cycles.

The largest value of [pi] is denoted by [DELTA]([pi]). Often the positions of [pi] will be identified with the elements of a vertex set V. In this case, we write [pi](v) (v [member of] V) for the corresponding component of [pi].

The degree sequence [pi] = ([a.sub.1],..., [a.sub.k]; [b.sub.1],..., [b.sub.l]) is a bigraphic sequence if there exists a simple bipartite graph G = G(A, B) with [absolute value of A] = k, [absolute value of B] = l realizing [pi] such that the degrees of vertices in A are [a.sub.1],..., [a.sub.k], and the degrees of the vertices of B are [b.sub.1],..., [b.sub.l].

Let G and H be two graphs on n vertices. We say that H is a subgraph of G, if we can delete edges from G so that we obtain an isomorphic copy of H. We denote this relation by H [subset] G. In the literature the equivalent complementary formulation can be found as well: we say that H and [bar.G] pack if there exist edge-disjoint copies of H and [bar.G] in [K.sub.n]. Here [bar.G] denotes the complement of G.

It is an old an well-understood problem in graph theory to tell whether a given sequence of natural numbers is a degree sequence or not. We consider a generalization of it, which is remotely related to the so-called discrete tomography (1) (or degree sequence packing) problem (see e.g. [5]) as well. The question whether a sequence of n numbers [pi] is a degree sequence can also be formulated as follows: Does [K.sub.n] have a subgraph H such that the degree sequence of H is [pi]? The question becomes more general if [K.sub.n] is replaced by some (simple) graph G on n vertices. If the answer is yes, we say that [pi] can be embedded into G, or equivalently, [pi] packs with [babr.G].

Let us mention two classical results in extremal graph theory.

Theorem 1 (Dirac, [6]). Every graph G with n [greater than or equal to] 3 vertices and minimum degree [delta](G) [greater than or equal to] | n/2 has a Hamilton cycle.

Theorem 2 (Corradi-Hajnal, [3]). Let k [greater than or equal to] 1, n [greater than or equal to] 3k, and let H be an n-vertex graph with [delta](H) [greater than or equal to] 2k. Then H contains k vertex-disjoint cycles.

Observe, that Dirac's theorem implies that given a constant 2 degree sequence [pi] of length n and any graph G on n vertices having minimum degree [delta](G) [greater than or equal to] n/2, [pi] can be embedded into G. One can interprete the Corradi-Hajnal theorem similarly, but here one may require more on the structure of the graph that realizes [pi] and in exchange a larger minimum degree of G is needed.

One of our main results is the following.

Theorem 3. For every [eta] > 0 and D [member of] N there exists an [n.sub.0] = [n.sub.0]([eta], D) such that for all n > [n.sub.0] if G is a graph on n vertices with [delta](G) [greater than or equal to] ([1/2] + [eta]) n and [pi] is a degree sequence of length n with [DELTA]([pi]) [less than or equal to] D, then [pi] is embeddable into G.

It is easy to see that Theorem 3 is sharp up to the [eta]n additive term. For that let n be an even number, and suppose that every element of [pi] is 1. Then the only graph that realizes [pi] is the union of n/2 vertex disjoint edges. Let G = [K.sub.n/2-1,n/2+1] be the complete bipartite graph with vertex class sizes n/2 - 1 and n/2 + 1. Clearly G does not have n/2 vertex disjoint edges.

In order to state the other main result of the paper we introduce a new notion.

Definition 4. Let q [greater than or equal to] 1 be an integer. A bipartite graph H with vertex classes S and T is q-unbalanced, if q[absolute value S] [less than or equal to] [absolute value T]. The degree sequence [pi] is q-unbalanced, if it can be realized by a q-unbalanced bipartite graph.

Theorem 5. Let q [greater than or equal to] 1 be an integer. For every [eta] > 0 and D [member of] N there exist an [n.sub.0] = [n.sub.0]([eta], q) and an M = M([eta], D, q) such that if n [greater than or equal to] [n.sub.0], [pi] is a q-unbalanced degree sequence of length n - M with [DELTA]([pi]) [less than or equal to] D, G is a graph on n vertices with [delta](G) [greater than or equal to] (1/q+1 [eta])n, then [pi] can be embedded into G.

Hence, if [pi] is unbalanced, the minimum degree requirement of Theorem 3 can be substantially decreased, what we pay for this is that the length of [pi] 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 [pi], our H will consists of components of bounded size. Second, we embed H into G using a theorem by Chvatal and Szemeredi 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 [pi] be active. While we can find 2i active degrees of [pi] with value i (for some 1 [less than or equal to] i [less than or equal to] [DELTA]([pi])) we realize them with a [K.sub.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 [[SIGMA].sup.[DELTA]([pi]).sub.i=1] (2i - 1) active degrees. This way we obtain several components, each being a balanced complete bipartite graph. These are the type 1 gadgets. Observe that if a vertex v belongs to some type 1 gadget, then its degree is exactly [pi](v). Observe further that if there are no active degrees in [pi] at this point then the graph H we have just found is a realization of [pi].

Assume that there are active degrees left in [pi]. Let R = [R.sub.odd] [union] [R.sub.even] be the vertex set that is identified with the active vertices (v [member of] [R.sub.odd] if and only if the assigned active degree is odd). Since [summation over (v[member of]R)] d(v) must be an even number we have that [absolute value of [R.sub.odd]] is even. Add a perfect matching on [R.sub.odd] to H. With this we achieved that every vertex of R misses an even number of edges.

Next we construct the type 2 gadgets using the following algorithm. In the beginning every type 1 gadget is unmarked. Suppose that v [member of] R is an active vertex. Take a type 1 gadget K, mark it, and let [M.sub.K] denote an arbitrarily chosen perfect matching in K ([M.sub.K] exists since K is a balanced complete bipartite graph). Let xy be an arbitrary edge in [M.sub.K]. Delete the xy edge and add the new edges vx and vy. While v is missing edges repeat the above procedure with edges of [M.sub.K], until [M.sub.K] becomes empty. If [M.sub.k] becomes empty, take a new unmarked type 1 gadget L, and repeat the method with L. It is easy to see that in [pi](v)/2 steps v reaches its desired degree and gets inactivated. Clearly, the degrees of vertices in the marked type 1 gadgets have not changed.

Figure 1 shows examples of type 2 gadgets. In the upper one two vertices of [R.sub.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 of R. The numbers at the vertices indicate the colors in the 3-coloring of H.

Let A [greater than or equal to] 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[[DELTA].sup.2]([pi]) vertices. Let us summarize our knowledge about H for later reference.

Claim 6. (1) [absolute value of A] [less than or equal to] 5[[DELTA].sup.3]([pi]),

(2) the components of H[V - A] are balanced complete bipartite graphs, each having size at most 2[DELTA]([pi]),

(3) [chi](H[A]) [less than or equal to] 3, and

(4) e(H[A,V - A]) = 0.

We are going to show that H [subset] G. For that we first embed the possibly 3-chromatic part H[A] using the following strengthening of the Erdos-Stone theorem proved by Chvatal and Szemeredi [2].

Theorem 7. Let [phi] > 0 and assume that G is a graph on n vertices where n is sufficiently large. Let r [member of] N, r [greater than or equal to] 2. If

e(G) [greater than or equal to] (r - 2)/2(r - 1) + [phi]) [n.sup.2],

then G contains a [K.sub.r](t), i.e. a complete r-partite graph with t vertices in each class, such that

t > log n/500 log 1/[phi]. (1)

Since [delta](G) [greater than or equal to] (1/2 + [eta]])n, the conditions of Theorem 7 are satisfied with r = 3 and [phi] = [eta]/2, hence, G contains a balanced complete tripartite subgraph T on [OMEGA](log n) vertices. Using Claim 6 and the 3-colorability of H[A] this implies that H[A] [subset] T.

Observe that after embedding H[A) into G every uncovered vertex of G still has at least [delta](G) - v(F) > (1/2 + [eta]/2)n uncovered neighbors. Denoting the subgraph of the uncovered vertices of G by G' we obtain that [delta](G') > (1/2 + [eta]/2)n.

In order to prove that H[V - A] [subset] G' we first need a definition.

Definition 8. A graph F on n vertices is well-separable if it has a subset S [subset] V(F) of size o(n) such that all components of F - S are of size o(n).

We need the following theorem.

Theorem 9 ([4]). For every [gamma] > 0 and positive integer D there exists an no such that for all n > [n.sub.0] if F is a bipartite well-separable graph on n vertices, [delta](F) [less than or equal to] D and [delta](G) [greater than or equal to] (1/2 + [gamma]) n for a graph G of order n, then F [subset] G.

Since H[V - A] has bounded size components by Claim 6, we can apply Theorem 9 for H[V - A] and G', with parameter [gamma] = [eta]/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 Szemeredi, 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 interested reader may consult with the original paper by Szemeredi [15] or e.g. with the survey paper [10].

3.1 Regularity lemma

The density between disjoint sets X and Y is defined as:

d(x, y) = e(X, Y)/[absolute value of X][absolute value of Y].

We will need the following definition to state the Regularity Lemma.

Definition 10 (Regularity condition). Let [epsilon] > 0. A pair (A, B) of disjoint vertex-sets in G is [epsilon]-regular if for every X [subset] A and Y [subset] B, satisfying

[absolute value of X] > [epsilon] [absolute value of A], [absolute value of Y] > [epsilon] [absolute value of B]

we have

[absolute value of d(X, Y) - d(A, B)] < [epsilon].

This definition implies that regular pairs are highly uniform bipartite graphs: namely, the density of any reasonably 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 [epsilon] > 0 there is an M = M([epsilon]) such that if G = (W, E) is any graph and d [member of] [0,1] is any real number, then there is a partition of the vertex set V into l + 1 clusters [W.sub.0], [W.sub.1],...,[W.sub.l], and there is a subgraph G' of G with the following properties:

--l [less than or equal to] M,

--[absolute value of [W.sub.0]] [less than or equal to] [epsilon] [absolute value of W],

--all clusters [W.sub.i], i [greater than or equal to] 1, are of the same size m ([less than or equal to] [[absolute value of W]/l] < [epsilon] [absolute value of W]),

--[deg.sub.G]'(v) > [deg.sub.G](v) - (d + [epsilon])[absolute value of W] for all v [member of] W,

--G'|[W.sub.i] = [empty set] ([W.sub.i] is an independent set in G') for all i [greater than or equal to] 1,

--all pairs ([W.sub.i], [W.sub.j]), 1 [less than or equal to] i < j [less than or equal to] l, are [epsilon]-regular, each with density either 0 or greater than d in G'.

We call [W.sub.0] the exceptional cluster, [W.sub.1],..., [W.sub.l] are the non-exceptional clusters. In the rest of the paper we will assume that 0 < [epsilon] [much less than] d [much less than] 1. Here a [much less than] b means that a is sufficiently smaller than b.

Definition 12 (Reduced graph). Apply Lemma 11 to the graph G = (W, E) with parameters [epsilon] and d, and denote the clusters of the resulting partition by [W.sub.0], [W.sub.1],..., [W.sub.l] ([W.sub.0] being the exceptional cluster). We construct a new graph [G.sub.r], the reduced graph of G' in the following way: The non-exceptional clusters of G' are the vertices of the reduced graph [G.sub.r] (hence v([G.sub.r]) = l). We connect two vertices of [G.sub.r] by an edge if the corresponding two clusters form an [epsilon]-regular pair with density at least d.

The following corollary is immediate:

Corollary 13. Apply Lemma 11 with parameters e and d to the graph G = (W, E) satisfying [delta](G) [greater than or equal to] [gamma]n (v(G) = n) for some [gamma] > 0. Denote [G.sub.r] the reduced graph of G'. Then [delta]([G.sub.r]) [greater than or equal to] ([gamma] - [theta])l, where [theta] = 2[epsilon] + d.

The (fairly easy) proof of the lemma below can be found in [10].

Lemma 14. Let (A, B) be an e-regular-pair with density d for some [epsilon] > 0. Let c > 0 be a constant such that [epsilon] [much less than] c. We arbitrarily divide A and B into two parts, obtaining the non-empty subsets A', A" and B', B", respectively. Assume that [absolute value A'], [absolute value of A"] [greater than or equal to] c[absolute value of A] and [absolute value of A], [absolute value of B"] [greater than or equal to] c[absolute value of B]. Then the pairs (A',B'), (A',B"), (A",B') and (A",B") are all [epsilon]/c-regular pairs with density at least d - [epsilon]/c.

3.2 Blow-up lemma

Let H and G be two graphs on n 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 Blowup Lemma of Komlos, Sarkozy and Szemeredi [8, 9]. For stating it we need a new notion, a stronger one-sided property of regular pairs.

Definition 15 (Super-Regularity condition). Given a graph G and two disjoint subsets of its vertices A and B, the pair (A, B) is ([epsilon], [delta])-super-regular, if it is [epsilon]-regular and furthermore,

deg(a) > [delta][absolute value of B], for all a [member of] A,

and

deg(b) > [delta][absolute value of B], for all b [member of] B,

Theorem 16 (Blow-up Lemma). Given a graph R of order r and positive integers [delta], [DELTA], there exists a positive [epsilon] = [epsilon]([delta], [DELTA], r) such that the following holds: Let [n.sub.1], [n.sub.2],..., [n.sub.r] be arbitrary positive parameters and let us replace the vertices [v.sub.1], [v.sub.2],..., [v.sub.r] of R with pairwise disjoint sets [W.sub.1], [W.sub.2],..., [W.sub.r] of sizes [n.sub.1], [n.sub.2],..., [n.sub.r] (blowing up R). We construct two graphs on the same vertex set V = [[union].sub.i][W.sub.i]. The first graph F is obtained by replacing each edge [v.sub.i][v.sub.j] [member of] E(R) with the complete bipartite graph between [W.sub.i] and [W.sub.j]. A sparser graph G is constructed by replacing each edge [v.sub.i][v.sub.j] arbitrarily with an ([epsilon], [delta])-super-regular pair between [W.sub.i] and [W.sub.j]. If a graph H with [DELTA](H) [less than or equal to] [DELTA] is embeddable into F then it is already embeddable into G.

4 Proof of Theorem 5

Let us give a brief sketch first. Recall, that [pi] is a q-unbalanced and bounded degree sequence with [DELTA]([pi]) [less than or equal to] D. In the proof we first show that there exists a q-unbalanced bipartite graph H that realizes [pi] such that H is the vertex disjoint union of the graphs [H.sub.1],..., [H.sub.k], where each [H.sub.i] graph is a bipartite q-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 of G. This substructure can then be used to embed the union of the [H.sub.i] graphs, for the majority of them we use the Blow-up lemma.

4.1 Finding H

The goal of this subsection is to prove the lemma below.

Lemma 17. Let [pi] be a q-unbalanced degree sequence of positive integers with [DELTA]([pi]) [less than or equal to] D. Then [pi] can be realized by a q-unbalanced bipartite graph H which is the vertex disjoint union of the graphs [H.sub.1],..., [H.sub.k], such that for every i we have that [H.sub.i] is q-unbalanced, moreover, v([H.sub.i]) [less than or equal to] 4[D.sup.2].

Before starting the proof of Lemma 17, we list a few necessary 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 integer. Then any zero-sum sequence on {-K,..., K} 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 discussed in Lovasz [11].

Lemma 19. [11] Let G = (A, B; E(G)) be a bipartite graph and f be a nonnegative integer function on A [union] B with f(A) = f(B). Then G has a subgraph F = (A, B; E(F)) such that [d.sub.F](x) = f(x) for all x [member of] A [union] B if and only if

f(X) [less than or equal to] e(X, Y) + f([bar.Y]) (2)

for any X [subset or equal to] A and Y [subset or equal to] B, where [bar.Y] = B - Y.

We remark that such a subgraph F is also called an f-factor of G.

Lemma 20. If f = ([a.sub.1],..., [a.sub.s]; [b.sub.1],..., [b.sub.t]) is a sequence of positive integers with s, t [greater than or equal to] 2[[DELTA].sup.2], where [DELTA] is the maximum of f, and f(A) = f{B) with A = {[a.sub.1],..., [a.sub.s]} and B = {[b.sub.1],..., [b.sub.t]} then f is bigraphic.

Proof All we have to check is whether the conditions of Lemma 19 are met if G = [K.sub.s,t].

Suppose indirectly that there is an (X, Y) pair for which (2) does not hold. Choose such a pair with minimal [absolute value of X] + [absolute value of Y]. Then X = [empty set] or Y = [empty set] are impossible, as in those cases (2) trivially holds. Hence, [absolute value of X], [absolute value of Y] [greater than or equal to] 1. Assuming that (2) does not hold, we have that

f(X) [greater than or equal to] e(X, Y) + f([bar.Y]) + 1, (3)

which is equivalent to

f(X) [greater than or equal to] [absolute value of X] [absolute value of Y] + f([bar.Y]) + 1, (4)

as G is a complete bipartite graph. Furthermore, using the minimality of [absolute value of X] + [absolute value of Y], we know that

f(X - a) [less than or equal to] [absolute value of X - a] [absolute value of Y] + f([bar.Y]) (5)

for any a [member of] X. (5) is equivalent to

f(X) - f(a) [less than or equal to] [absolute value of X] [absolute value of Y] - [absolute value of Y] + f([bar.Y]). (6)

From (4) and (6) we have

f(a) - 1 [greater than or equal to] [absolute value of Y] (7)

for any a [member of] X, which implies

[DELTA] > [absolute value of Y]. (8)

The same reasoning also implies that [DELTA] > [absolute value of X] whenever (X, Y) is a counterexample. Therefore we only have to verify that (2) holds in case [absolute value of X] < [DELTA] and [absolute value of Y] < [DELTA]. Recall that f(B) [greater than or equal to] t, as all elements of f are positive. Hence, f(X) [less than or equal to] [DELTA] [absolute value of X] [less than or equal to] [[DELTA].sup.2], and f([bar.Y]) = f(B) - f(Y) [greater than or equal to] t - [[DELTA].sup.2], and we get that

f(X) [less than or equal to] [[DELTA].sup.2] [less than or equal to] t - [[DELTA].sup.2] [less than or equal to] f([bar.Y]) [less than or equal to] f([bar.Y]) + [e.sub.G](X, Y) (9)

holds, since t [greater than or equal to] 2[[DELTA].sup.2].

Proof (Lemma 17) Assume that J = (S, T; E(J)) is a q-unbalanced bipartite graph realizing [pi]. Hence, q [absolute value of S] [less than or equal to] [absolute value of T]. Moreover, [absolute value of T] [less than or equal to] D[absolute value of S], since [DELTA]([pi]) [less than or equal to] D. We form vertex disjoint tuples of the form (s; [t.sub.1],..., [t.sub.h]), such that s [member of] S, [t.sub.i] [member of] T, q [less than or equal to] h [less than or equal to] D, and the collection of these tuples contains every vertex of S [union] T exactly once. We define the bias of the tuple as

[zeta] = [pi] ([t.sub.1]) + *** + [pi]([t.sub.h]) - [pi](s).

Obviously, -D [less than or equal to] [zeta] [less than or equal to] [D.sup.2]. The conditions of Proposition 18 are clearly met with K = [D.sup.2]. Hence, we can form groups of size at most 2[D.sup.2] in which the sums of biases are zero. This way we obtain a partition of (S, T) into q-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 2[D.sup.2] and has zero bias. By Lemma 20 these are bigraphic sequences. The realizations of these small sequences give the graphs [H.sub.1],..., [H.sub.k]. It is easy to see that v([H.sub.i]) [less than or equal to] 4[D.sup.2] for every 1 [less than or equal to] i [less than or equal to] k. Finally, we let H = [[union].sub.i][H.sub.i].

4.2 Decomposing [G.sub.r]

Let us apply the Regularity lemma with parameters 0 < [epsilon] [much less than] d [much less than] [eta]. By Corollary 13 we have that [delta]([G.sub.r]) [greater than or equal to] l/(q + 1) + [eta]l/2.

Let h [greater than or equal to] 1 be an integer. An h-star is a [K.sub.1,h] The center of an h-star is the vertex of degree h, the other vertices are the leaves. In case h = 1 we pick one of the vertices of the 1 -star arbitrarily to be the center.

Lemma 21. The reduced graph [G.sub.r] has a decomposition S into vertex disjoint stars such that each star has at most q leaves.

Proof. Take a partial star-decomposition of [G.sub.r] that is as large as possible. Assume that there are uncovered vertices in [G.sub.r]. Let U denote those vertices that are covered (so we assume that U has maximal cardinality), and let v be an uncovered vertex. Observe that v has neighbours only in U, otherwise, if uv [member of] E([G.sub.r]) with u [not member of] U, then we can simply add uv to the star-decomposition, contradicting to the maximality of U. See Figure 2 for the possible neighbors of v.

a) If v 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 an h + 1-star by adding the edge uv to the h-star.

c) If v is connected to a leaf u of an h-star, where 2 [less than or equal to] h [less than or equal to] q, then replace the star with the edge uv and an (h - 1)-star (i.e., delete u from it).

We have not yet considered one more case: when v is connected to the center of a g-star. However, simple calculation shows that for every vertex v at least one of the above three cases must hold, using the minimum degree condition of [G.sub.r]. Hence we can increase the number of covered vertices. We arrived at a contradiction, [G.sub.r] has the desired star-decomposition.

4.3 Preparing G for the embedding

Consider the g-star-decomposition S of [G.sub.R] as in Lemma 21. Let [l.sub.i] denote the number of (i - l)-stars in the decomposition for every 2 [less than or equal to] i [less than or equal to] g + 1. It is easy to see that

[q+1.summation over (i=2)] i[l.sub.i] = l.

First we will make every [epsilon]-regular pair in S super-regular by discarding a few vertices from the non-exceptional clusters. Let for example [subset] be a star in the decomposition of [G.sub.r] with center cluster A and leaves [B.sub.1],..., [B.sub.k] where 1 [less than or equal to] k [less than or equal to] q. Recall that the (A, [B.sub.i]) pairs has density at least d. We repeat the following for every 1 [less than or equal to] i [less than or equal to] k : if v [member of] A such that v has at most 2dm/3 neighbors in [B.sub.i] then discard v from A, put it into [W.sub.0]. Similarly, if w [member of] [B.sub.i] has at most 2dm/3 neighbors in A, then discard w from [B.sub.i], put it into [W.sub.0]. Repeat this process for every star in S. We have the following:

Claim 22. We do not discard more than q[epsilon]m vertices from any non-exceptional cluster.

Proof. Given a star C in the decomposition S assume that its center cluster is A and let B be one of its leaves. Since the pair (A, B) is [epsilon]-regular with density at least d, neither A, nor B can have more than [epsilon]m vertices that have at most 2dm/3 neighbors in the opposite cluster. Hence, during the above process we may discard up to q[epsilon]m vertices from A. Next, we may discard vertices from the leaves, but since no leaf B had more than [epsilon]m vertices with less than (d - [epsilon])m neighbors in A, even after discarding at most q[epsilon]m vertices of A, there can be at most [epsilon]m vertices in B that have less than (d - (q + 1)[epsilon])m neighbors in A. Using that [epsilon] [much less than] d, we have that (d - (q + 1)[epsilon]) > 2d/3. We obtained what was desired.

By the above claim we can make every [epsilon]-regular pair in S a (2[epsilon], 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.sub.0]. We repeat the following for every non-exceptional cluster: if s vertices were discarded from it with s < q[epsilon]m then we take q[epsilon]m - s arbitrary vertices of it, and place them into [W.sub.0]. This way every non-exceptional cluster will have the same number of points, precisely m - q[epsilon]m. For simpler notation, we will use the letter m for this new cluster size. Observe that [W.sub.0] has increased by q[epsilon]ml vertices, but we still have [absolute value of [W.sub.0]] [less than or equal to] 3dn since [epsilon] [much less than] d and lm [less than or equal to] n. Since q[epsilon]m [much less than] d, in the resulting pairs the minimum degree will be at least dm/2.

Summarizing, we obtained the following:

Lemma 23. By discarding a total of at most q[epsilon]n vertices from the non-exceptional clusters we get that every edge in S represents a (2[epsilon], d/2)-super-regular pair, and all non-exceptional clusters have the same cardinality, which is denoted by m. Moreover, [absolute value of [W.sub.0]] [less than or equal to] 3dn.

Since v(G) - v(H) is bounded above by a constant, when embedding H we need almost every vertex of G, in particular those in the exceptional cluster [W.sub.0]. For this reason we will assign the vertices of [W.sub.0] to the stars in S. This is not done in an arbitrary way.

Definition 24. Let v [member of] [W.sub.0] be a vertex and (Q, T) be an [epsilon]-regular pair. We say that v [member of] T has large degree to Q if v has at least [eta][absolute value of Q]/4 neighbors in Q. Let S = (A, [B.sub.1],...., [B.sub.k]) be a star in S where A is the center of S and [B.sub.1],..., [B.sub.k] are the leaves, here 1 [less than or equal to] k [less than or equal to] q. If v has large degree to any of [B.sub.1],..., [B.sub.k], then v can be assigned to A. If k < q and v has large degree to A, then v can be assigned to any of the [B.sub.i] leaves.

Observation 25. If we assign new vertices to a q-star, then we necessarily assign them to the center. Since before assigning, the number of vertices in the leaf-clusters is exactly q times the number of vertices in the center cluster, after assigning new vertices to the star, q times the cardinality of the center will be larger than the total number of vertices in the leaf-clusters. If S [member of] S is a k-star with 1 [greater than or equal to] k < q, and we assign up to cm vertices to any of its clusters, where 0 < c [much less than] 1, then even after assigning new vertices we will have that q times the cardinality of the center is larger than the total number of vertices in the leaf-clusters.

The following lemma plays a crucial role in the embedding algorithm.

Lemma 26. Every vertex of [W.sub.0] can be assigned to at least [eta]l/4 non-exceptional clusters.

Proof. Suppose that there exists a vertex w [member of] [W.sub.0] that can be assigned to less than [eta]l/4 clusters. If w cannot be assigned to any cluster of some k-star [S.sub.k] with k < q, then the total degree of w into the clusters of [S.sub.k] is at most k[eta]m/4. If w cannot be assigned to any cluster of some q-star [S.sub.q], then the total degree of w into the clusters of [S.sub.q] is at most m + q[eta]m/4, since every vertex of the center cluster could be adjacent to w. Considering that w can be assigned to at most [eta]l/4 - 1 clusters and that d(w, W - [W.sub.0]) [greater than or equal to] n/(q + 1) + [eta]n/2, we obtain the following inequality:

n/q + 1 + [eta]n/2 [less than or equal to] d(v, W - [W.sub.0]) [less than or equal to] [eta] lm/4 + [q-1.summation over (k=1)] (k + 1)[eta] [l.sub.k+1]m/4 + q[eta] [l.sub.q+1]m/4 + [l.sub.q+1]m.

Using ml [less than or equal to] n and [[SIGMA].sup.q.sub.k=1] (k + 1)[l.sub.k+1] = l, we get

ml/q + 1 + [eta]ml/2 [less than or equal to] [eta] lm/4 + (l - [l.sub.q+1]) [eta]m/4 + q[eta] [l.sub.q+1]m/4 + [l.sub.q+1]m.

Dividing both sides by m and cancellations give

l/q + 1 [less than or equal to] q [eta][l.sub.q+1]/4 + (1 - [eta]/4) [l.sub.q+1].

Noting that (q + 1)[l.sub.q+1] [less than or equal to] l, one can easily see that we arrived at a contradiction. Hence every vertex of [W.sub.0] can be assigned to several non-exceptional clusters.

Lemma 26 implies the following:

Lemma 27. One can assign the vertices of [W.sub.0] so that at most [square root of d]m vertices are assigned to non-exceptional clusters.

Proof. Since we have at least [eta]l/4 choices for every vertex, the bound follows from the inequality 4[absolute value of [W.sub.0]]/[eta]l [less than or equal to] [square root of d]m, where we used d[much less than] [eta] and [absolute value of [W.sub.0]] [less than or equal to] 3dn.

Observation 28. A key fact is that the number of newly assigned vertices to a cluster is much smaller than their degree into the opposite cluster of the regular pair since [square root of d]m [much less than] [eta]m/4.

4.4 The embedding algorithm

The embedding is done in two phases. In the first phase we cover every vertex that belonged to [W.sub.0], together with some other vertices of the non-exceptional clusters. In the second phase we are left with super-regular pairs into which we embed what is left from H using the Blow-up lemma.

4.4.1 The first phase

Let (A, B) be an [epsilon]-regular cluster-edge in the h-star C [member of] S. We begin with partitioning A and B randomly, obtaining A = A' [union] A" and B = B' [union] B" with A' [intersection] A" = B' [intersection] B" = [empty set]. For every w [member of] A (except those that came from [W.sub.0]) flip a coin. If it is heads, we put w into A', otherwise we put it into A". Similarly, we flip a coin for every w [member of] B (except those that came from [W.sub.0]) and depending on the outcome, we either put the vertex into B' or into B". The proof of the following lemma is standard, uses Chernoff's bound (see in [1]), we omit it.

Lemma 29. With high probability, that is, with probability at least 1 - 1/n, we have the following:

--[absolute value of [absolute value of A'] - [absolute value of A"]] = o(n) and [absolute value of [absolute value of B'] - [absolute value of B"]] = o{n)

--deg(w, A'),deg(w, A") > deg(w, A)/3 for every w [member of] B

--deg(w, B'),deg(w, B") > deg(w, B)/3 for every w [member of] A

--the density d{A', B') [greater than or equal to] d/2

It is easy to see that Lemma 29 implies that (A', B') is a (5[epsilon], d/6)-super-regular pair having density at least d/2 with high probability.

Assume that v was an element of [W.sub.0] before we assigned it to the cluster A, and assume further that deg(v, B) [greater than or equal to] [eta]m/4. Since (A. B) is an edge of the star-decomposition, either A or B must be the center of C.

Let [H.sub.i] be one of the q-unbalanced bipartite subgraphs of H that has not been embedded yet. We will use [H.sub.i] to cover v. Denote [S.sub.i] and [T.sub.i] the vertex classes of [H.sub.i], where [absolute value of [S.sub.i]] [greater than or equal to] q[absolute value of [T.sub.i]]. Let [S.sub.i] = {[x.sub.1],..., [x.sub.s]} and [T.sub.i] = {[y.sub.1],..., [y.sub.t]}.

If A is the center of [subset] then the vertices of [T.sub.i] will cover vertices of A', and the vertices of [S.sub.i] will cover vertices of B'. If B is the center, [S.sub.i], and [T.sub.i] will switch roles. The embedding of [H.sub.i] is essentially identical in both cases, so we will only discuss the case when A 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 < [epsilon] [much less than] d [much less than] [eta].

The details are as follows. We construct an edge-preserving injective mapping [phi] : [S.sub.i] [union] [T.sub.i] [right arrow] A' [union] B'. In particular, we will have [phi]([S.sub.i]) [subset] B' and [phi]([T.sub.i]) - v [subset] A'. First we let [phi]([y.sub.1]) = v. Set [N.sub.1] = N(v) [intersection] B'. Using Lemma 29 we have that [absolute value of [N.sub.1]] [greater than or equal to] [eta]m/12 [much greater than] [epsilon]m.

Next we find [phi]([y.sub.2]). Since [absolute value of [N.sub.1]] [much greater than] [epsilon]m, by 5[epsilon]-regularity the majority of the vacant vertices of A' will have at least d[absolute value of [N.sub.1]]/3 neighbors in [N.sub.1]. Pick any of these, denote it by [v.sub.2] and let [phi]([y.sub.2]) = [v.sub.2]. Also, set [N.sub.2] = [N.sub.1] [intersection] N([v.sub.2])

In general, assume that we have already found the vertices [v.sub.2], [v.sub.3],..., [v.sub.i], their common neighborhood in B' is [N.sub.i], and

[absolute value of [N.sub.i]] [greater than or equal to] [eta][d.sup.i-1]/[3.sup.i-2] x 36 m [much greater than] [epsilon]m.

By 5[epsilon]-regularity, this implies that the majority of the vacant vertices of A' has large degree into [N.sub.i], at least d x [absolute value of [N.sub.i]]/3, and this, as above, can be used to find [v.sub.i+1]. Then we set [phi]([y.sub.i+1]) = [v.sub.i+1]. Since [eta] and d is large compared to [epsilon], even into the last set [N.sub.t-1] many vacant vertices will have large degrees.

As soon as we have [phi][(y.sub.1]),..., [epsilon]([y.sub.t]), it is easy to find the images for [x.sub.1],..., [x.sub.t]. Since [absolute value of [N.sub.t]] [much greater than] [epsilon]m [much greater than] s = [absolute value of [S.sub.i]], we can arbitrarily choose s vacant points from [N.sub.t] for the [phi]([x.sub.j]) images.

Note that we use less than v([H.sub.i]) [less than or equal to] 4[D.sup.2] vertices from A' and B' during this process. We can repeat it for every vertex that were assigned to A, and still at most [square root of d]2[D.sup.2]m vertices will be covered from A' and from B'.

Another observation is that every h-star in the decomposition before this embedding phase was h-unbalanced, now, since we were careful, these have become h'-balanced with h' [less than or equal to] h.

Of course, the above method will be repeated for every (A, B) edge of the decomposition for which we have assigned vertices of [W.sub.0].

4.4.2 The second phase

In the second phase we first unite all the randomly partitioned clusters. For example, assume that after covering the vertices that were coming from [W.sub.0] the set of vacant vertices of A' is denoted by [A'.sub.v]. Then we let [A.sub.v] = [A'.sub.v] [union] A", and using analogous notation, let [B.sub.v] = [B'.sub.v] [union] B".

Claim 30. All the ([A.sub.v], [B.sub.v]) pairs are (3[epsilon], d/6-super-regular with density at least d/2.

Proof. The 3[epsilon]-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 minimum degrees note that by Lemma 29 every vertex of A had at least dm/6 neighbors in B", hence, in [B.sub.v] as well, and analogous bound holds for vertices of B.

At this point we want to apply the Blow-up lemma for every star of S individually. For that we first have to assign those subgraphs of H to stars that were not embedded yet. We need a lemma.

Lemma 31. Let [K.sub.a,b] be a complete bipartite graph with vertex classes A and B, where [absolute value of A] = a and [absolute value of B] = b. Assume that a [less than or equal to] b = ha, where 1 [less than or equal to] h [less than or equal to] q. Let H' be the vertex disjoint union of q-unbalanced bipartite graphs:

[mathematical expression not reproducible]

such that v([H.sub.j]) [less than or equal to] 2[D.sup.2] for every j. If v(H') [less than or equal to] a + b - 4(2q + 1)[D.sup.2], then H' [subset] [K.sub.a,b].

Observe that if we have Lemma 31, we can distribute the [H.sub.i] subgraphs among the stars of S, and then apply the Blow-up lemma. Hence, we are done with proving Theorem 5 if we prove Lemma 31 above.

Proof. The proof is an assigning algorithm and its analysis. We assign the vertex classes of the [H.sub.j] subgraphs to A and B, one-by-one. Before assigning the jth subgraph [H.sub.j] the number of vacant vertices of A is denoted by [a.sub.j] and the number of vacant vertices of B is denoted by [b.sub.j].

Assume that we want to assign [H.sub.k]. If h[a.sub.k] - [b.sub.k] > 0, then the larger vertex class of [H.sub.k] is assigned to A, the smaller is assigned to B. Otherwise, if h[a.sub.k] - [b.sub.k] [less than or equal to] 0, then we assign the larger vertex class to B and the smaller one to A. Then we update the number of vacant vertices of A and B. Observe that using this assigning method we always have [a.sub.k] [less than or equal to] [b.sub.k].

The question is whether we have enough room for [H.sub.k]. If ha [greater than or equal to] 4h[D.sup.2], then we must have enough room, since [b.sub.k] [greater than or equal to] [a.sub.k] and every [H.sub.j] has at most 2[D.sup.2] vertices. Hence, if the algorithm stops, we must have [a.sub.k] < 4[D.sup.2]. Since [b.sub.k] - h[a.sub.k] [less than or equal to] 2[D.sup.2] must hold, we have [b.sub.k] < (2h + 1)2[D.sup.2] < (2q + 1)2[D.sup.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 symmetric difference of the edge sets

Theorem 32. Let q [greater than or equal to] 1 be an integer. For every [eta] > 0 and D [member of] N there exists an [n.sub.0] = [n.sub.0]([eta], q) and a K = K([eta], D, q) such that if n [greater than or equal to] [[eta].sub.0], [pi] is a q-unbalanced degree sequence of length n with [DELTA]([pi]) [less than or equal to] D, G is a graph on n vertices with [delta](G) [greater than or equal to] (1/q+1 + [eta])n, then there exists a graph G' on n vertices such that the edit distance of G and G' is at most K, and [pi] can be embedded into G'.

Here is an example showing that Theorem 5 and 32 are essentially best possible.

Example 33. Assume that [pi] has only odd numbers and G has at least one odd sized component. Then the embedding is impossible. Indeed, any realization of [pi] 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 connected. In Theorem 3 the minimum degree [delta](G) [greater than or equal to] (1/2 + [eta])n, hence, G is connected, and in this case we can embed [pi] into G.

Acknowledgement

Partially supported by Ministry of Human Capacities, Hungary, 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 TAMOP-4.2.2.B-15/1/KONV-2015-0006.

References

[1] N. Alon, J. Spencer. The probabilistic method. Third edition, John Wiley & Sons, Inc., 2008. https://doi.org/10.1002/9780470277331

[2] V. Chvatal and E. Szemeredi. On the Erdos-Stone Theorem. Journal of the London Mathematical Society, s2-23 (2):207-214, 1981.

[3] K. Corradi and A. Hajnal. On the maximal number of independent circuits in a graph. Acta Mathematica Academiae Scientiarum Hungaricae, 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 sequence packing and the 2-color discrete tomography problem. SI AM Journal of Discrete Mathematics, 29(4):2088-2099, 2015. https://doi.org/10.1137/140987912

[6] G. Dirac. Some theorems on abstract graphs. Proceedings 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. Komlos, G. Sarkozy, and E. Szemeredi. Blowup lemma. Combinatorica, 17:109-123, 1997. https://doi.org/10.1007/BF01196135

[9] J. Komlos, G. Sarkozy, and E. Szemeredi. 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. Komlos and M. Simonovits. Szemeredi's regularity lemma and its applications in graph theory. Combinatorics: Paul Erdos is eighty, 2:295-352. 1993.

[11] L. Lovasz. 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: Methods, results, and generalizations. In A. Beveridge, J. Griggs, L. Hogben, G. Musiker. and P. Tetali, editors, 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 Mathematics, 9:371-377, 1957. https://doi.org/10.4153/CJM-1957-04 4-3

[14] M. Sahs, P. Sissokho, and J. Torf. A zero-sum theorem over Z. Integers, 13:#A70, 2013.

[15] E. Szemeredi. Regular partitions of graphs. Colloques Internationaux C.N.R.S 260 - Problemes Combinatoires et Theorie des Graphes, pages 399-401, 1976.

[16] D. West. Introduction to graph theory. Prentice Hall, Second edition, 2001.

(1) In the discrete tomography problem we are given two degree sequences of length n, [[pi].sub.1] and [[pi].sub.2], and the questions is whether there exists a graph G on n vertices with a red-blue edge coloration so that the following holds: for every vertex v the red degree of v is [[pi].sub.1] (v) and the blue degree of v is [[pi].sub.2](v).

(2) Recall that if h < q then we may assigned d to a leaf, so in such a case B could be the center.

Bela Csaba

Bolyai Institute, Interdisciplinary Excellence Centre, University of Szeged. Hungary

E-mail: csaba@math.u-szeged.hu

Balint Vasarhelyi

University of Szeged, Hungary

E-mail: mesti@math.u-szeged.hu

Received: October 30, 2018

https://doi.org/10.31449/inf.v43i1.2684

Caption: Figure 1: Type 2 gadgets of H with a 3-coloring

Caption: Figure 2: An illustration for Lemma 21
COPYRIGHT 2019 Slovenian Society Informatika
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2019 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Csaba, Bela; Vasarhelyi, Balint
Publication:Informatica
Date:Mar 1, 2019
Words:8926
Previous Article:Construction of Orthogonal CC-sets.
Next Article:A Self-Bounding Branch & Bound Procedure for Truck Routing and Scheduling.

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters