Graph Theory
322 pág.

Graph Theory

DisciplinaTeoria dos Grafos342 materiais1.556 seguidores
Pré-visualização50 páginas
that any n > M is large enough to satisfy (5).
We flnally have to show that every graph G = (V;E) of order at
least m has an \u2020-regular partition fV0; V1; : : : ; Vk g with m 6 k 6M . So
let G be given, and let n := jGj. If n 6 M , we partition G into k := nn
singletons, choosing V0 := ; and jV1j = : : : = jVkj = 1. This partition of
G is clearly \u2020-regular. Suppose now that n > M . Let C0 µ V be minimal
such that k divides jV rC0j, and let fC1; : : : ; Ck g be any partition of
V rC0 into sets of equal size. Then jC0j < k, and hence jC0j 6 \u2020n by (5).
Starting with fC0; C1; : : : ; Ck g we apply Lemma 7.2.4 again and again,
until the partition of G obtained is \u2020-regular; this will happen after at
most s iterations, since by (5) the size of the exceptional set in the
partitions stays below \u2020n, so the lemma could indeed be reapplied up to
the theoretical maximum of s times. \u2044
7.3 Applying the regularity lemma
The purpose of this section is to illustrate how the regularity lemma
is typically applied in the context of (dense) extremal graph theory.
Suppose we are trying to prove that a certain edge density of a graph G
su\u2013ces to force the occurrence of some given subgraph H, and that we
have an \u2020-regular partition of G. The edges inside almost all the pairs
(Vi; Vj) of partition sets are distributed uniformly, although their density
may depend on the pair. But sinceG has many edges, this density cannot
be zero for all the pairs: some sizeable proportion of the pairs will have
positive density. Now if G is large, then so are the pairs: recall that
the number of partition sets is bounded, and they have equal size. But
any large enough bipartite graph with equal partition sets, flxed positive
edge density (however small!) and a uniform distribution of edges will
contain any given bipartite subgraph5|this will be made precise below.
Thus if enough pairs in our partition of G have positive density that H
can be written as the union of bipartite graphs each arising in one of
those pairs, we may hope that H µ G as desired.
These ideas will be formalized by Lemma 7.3.2 below. We shall then
use this and the regularity lemma to prove the Erd}os-Stone theorem
from Section 7.1; another application will be given later, in the proof of
Theorem 9.2.2.
Before we state Lemma 7.3.2, let us note a simple consequence of
the \u2020-regularity of a pair (A;B): for any subset Y µ B that is not too
5 Readers already acquainted with random graphs may flnd it instructive to com-
pare this statement with Proposition 11.3.1.
7.3 Applying the regularity lemma 161
small, most vertices of A have about the expected number of neighbours
in Y :
Lemma 7.3.1. Let (A;B) be an \u2020-regular pair, of density d say, and let
Y µ B have size jY j > \u2020 jBj. Then all but at most \u2020 jAj of the vertices
in A have (each) at least (d¡ \u2020)jY j neighbours in Y .
Proof . Let X µ A be the set of vertices with fewer than (d ¡ \u2020)jY j
neighbours in Y . Then kX;Y k < jXj(d¡ \u2020)jY j, so
d(X;Y ) =
kX;Y k
jXj jY j < d¡ \u2020 = d(A;B)¡ \u2020 :
Since (A;B) is \u2020-regular, this implies that jXj < \u2020 jAj. \u2044
Let G be a graph with an \u2020-regular partition fV0; V1; : : : ; Vk g, with
exceptional set V0 and jV1j = : : : = jVkj =: \u2018. Given d 2 (0; 1 ], let R be R
the graph with vertices V1; : : : ; Vk in which two vertices are adjacent if
and only if they form an \u2020-regular pair in G of density > d. We shall call
R a regularity graph of G with parameters \u2020, \u2018 and d. Given s 2 N, let regularitygraph
us now replace every vertex Vi of R by a set V si of s vertices, and every V si
edge by a complete bipartite graph between the corresponding s-sets.
The resulting graph will be denoted by Rs. (For R = Kr, for example, Rs
we have Rs = Krs .)
The following lemma says that subgraphs of Rs can also be found
in G, provided that \u2020 is small enough and the Vi are large enough. In
fact, the values of \u2020 and \u2018 required depend only on (d and) the maximum
degree of the subgraph:
Lemma 7.3.2. For all d 2 (0; 1 ] and ¢ > 1 there exists an \u20200 > 0 with [ 9.2.2 ]
the following property: if G is any graph, H is a graph with ¢(H) 6 ¢,
s 2 N, and R is any regularity graph of G with parameters \u2020 6 \u20200,
\u2018 > s=\u20200 and d, then
H µ Rs ) H µ G :
Proof . Given d and ¢, choose \u20200 < d small enough that d;¢
¢ + 1
(d¡ \u20200)¢ \u20200 6 1 ; (1)
such a choice is possible, since (¢ + 1)\u2020=(d¡ \u2020)¢! 0 as \u2020! 0. Now let G;H;R;Rs
G, H, s and R be given as stated. Let fV0; V1; : : : ; Vk g be the \u2020-regular Vi
partition of G that gave rise to R; thus, \u2020 6 \u20200, V (R) = fV1; : : : ; Vk g \u2020; k; \u2018
and jV1j = : : : = jVkj = \u2018. Let us assume that H is actually a subgraph
162 7. Substructures in Dense Graphs
of Rs (not just isomorphic to one), with vertices u1; : : : ; uh say. Eachui; h
vertex ui lies in one of the s-sets V sj of Rs; this deflnes a map ¾: i 7! j.¾
Our aim is to deflne an embedding ui 7! vi 2 V¾(i) of H in G; thus,vi
v1; : : : ; vh will be distinct, and vivj will be an edge of G whenever uiuj
is an edge of H.
Our plan is to choose the vertices v1; : : : ; vh inductively. Throughout
the induction, we shall have a \u2018target set\u2019 Yi µ V¾(i) assigned to each i;
this contains the vertices that are still candidates for the choice of vi.
Initially, Yi is the entire set V¾(i). As the embedding proceeds, Yi will
get smaller and smaller (until it collapses to f vi g when vi is chosen):
whenever we choose a vertex vj with j < i and ujui 2 E(H), we delete
all those vertices from Yi that are not adjacent to vj . The set Yi thus
evolves as
V¾(i) = Y 0i ¶ : : : ¶ Y ii = f vi g ;
where Y ji denotes the version of Yi current after the deflnition of vj (and
any corresponding deletion of vertices from Y j¡1i ).
In order to make this approach work, we have to ensure that the
target sets Yi do not get too small. When we come to embed a vertex uj ,
we consider all the indices i > j with ujui 2 E(H); there are at most ¢
such i. For each of these i, we wish to select vj so that
Y ji = N(vj)\Y j¡1i (2)
is large, i.e. not much smaller than Y j¡1i . Now this can be done by
Lemma 7.3.1 (with A = V¾(j), B = V¾(i) and Y = Y
i ): unless Y
is tiny (of size less than \u2020\u2018), all but at most \u2020\u2018 choices of vj will be such
that (2) implies
jY ji j > (d¡ \u2020)jY j¡1i j : (3)
Doing this simultaneously for all of the at most ¢ values of i considered,
we flnd that all but at most ¢\u2020\u2018 choices of vj from V¾(j), and in particular
from Y j¡1j µ V¾(j), satisfy (3) for all i.
It remains to show that the sets Y considered for Lemma 7.3.1 above
are indeed never tiny, and that jY j¡1j j¡¢\u2020\u2018 > s to ensure that a suitable
choice for vj exists: since ¾(j0) = ¾(j) for at most s¡ 1 of the vertices
uj0 with j0 < j, a choice between s suitable candidates for vj will su\u2013ce
to keep vj distinct from v1; : : : ; vj¡1. But all this follows from our choice
of \u20200. Indeed, the initial target sets Y 0i have size \u2018, and each Yi has
vertices deleted from it only when some vj with j < i and ujui 2 E(H)
is deflned, which happens at most ¢ times. Thus,
jY ji j ¡¢\u2020\u2018 >
(d¡ \u2020)¢\u2018¡¢\u2020\u2018 > (d¡ \u20200)¢\u2018¡¢\u20200\u2018 >
\u20200\u2018 > s
whenever j < i, so in particular jY ji j > \u20200\u2018 > \u2020\u2018 and jY j¡1j j ¡¢\u2020\u2018 > s.
7.3 Applying the regularity lemma 163
We are now ready to prove the Erd}os-Stone theorem.
Proof of Theorem 7.1.2. Let r > 2 and s > 1 be given as in the (7.1.1)(7.1.4)
statement of the theorem. For s = 1 the assertion follows from Tur¶an\u2019s
theorem, so we assume that s > 2. Let ° > 0 be given; this ° will play r; s°
the role of the \u2020 of the theorem. Let G be a graph with jGj =: n and
kGk > tr¡1(n) + °n2: kGk
(Thus, ° < 1.) We want to show that Krs µ G if n is large enough.
Our plan is to use the regularity lemma to show that G has a regu-
larity graph R dense enough to contain a Kr by Tur¶an\u2019s theorem. Then
Rs contains a Krs , so we may hope to use Lemma 7.3.2 to deduce that
Krs µ G.