Pré-visualização50 páginas

ensuresM 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) \u20200 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 j¡1 i ): unless Y j¡1 i 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 > (3) (d¡ \u2020)¢\u2018¡¢\u2020\u2018 > (d¡ \u20200)¢\u2018¡¢\u20200\u2018 > (1) \u20200\u2018 > s whenever j < i, so in particular jY ji j > \u20200\u2018 > \u2020\u2018 and jY j¡1j j ¡¢\u2020\u2018 > s. \u2044 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. On