Pré-visualização50 páginas

number ensure that one of these substructures occurs? Questions of this type are among the most natural ones in graph theory, and there is a host of deep and interesting results. Collectively, these are known as extremal graph theory . Extremal graph problems in this sense fall neatly into two categories, as follows. If we are looking for ways to ensure by global assumptions that a graph G contains some given graph H as a minor (or topological minor), it will su\u2013ce to raise kGk above the value of some linear function of jGj (depending on H), i.e. to make "(G) large enough. The existence of such a function was already established in Theorem 3.6.1. The precise growth rate needed will be investigated in Chapter 8, where we study substructures of such \u2018sparse\u2019 graphs. Since a large enough value of " gives rise to an H minor for any given graph H, its occurrence could be forced alternatively by raising some other global invariants (such as \u2022 or ´) which, in turn, force up the value of ", at least in some subgraph. This, too, will be a topic for Chapter 8. On the other hand, if we ask what global assumptions might imply the existence of some given graph H as a subgraph, it will not help to raise any of the invariants ", \u2022 or ´, let alone any of the other in- variants discussed in Chapter 1. Indeed, as mentioned in Chapter 5.2, 148 7. Substructures in Dense Graphs given any graph H that contains at least one cycle, there are graphs of arbitrarily large chromatic number not containing H as a subgraph (Theorem 11.2.2). By Corollary 5.2.3 and Theorem 1.4.2, such graphs have subgraphs of arbitrarily large average degree and connectivity, so these invariants too can be large without the presence of an H subgraph. Thus, unless H is a forest, the only way to force the presence of an H subgraph in an arbitrary graph G by global assumptions on G is to raise kGk substantially above any value implied by large values of the above invariants. If H is not bipartite, then any function f such that f(n) edges on n vertices force an H subgraph must even grow quadratically with n: since complete bipartite graphs can have 14n 2 edges, f(n) must exceed 14n 2. Graphs with a number of edges roughly1 quadratic in their numberdense of vertices are usually called dense; the number kGk\u2013¡jGj2 ¢|the propor- tion of its potential edges that G actually has|is the edge density of G.edgedensity The question of exactly which edge density is needed to force a given subgraph is the archetypal extremal graph problem in its original (nar- rower) sense; it is the topic of this chapter. Rather than attempting to survey the wide fleld of (dense) extremal graph theory, however, we shall concentrate on its two most important results and portray one powerful general proof technique. The two results are Tur¶an\u2019s classic extremal graph theorem for H = Kr, a result that has served as a model for countless similar theorems for other graphs H, and the fundamental Erd}os-Stone theo- rem, which gives precise asymptotic information for all H at once (Sec- tion 7.1). The proof technique, one of increasing importance in the extremal theory of dense graphs, is the use of the Szemer¶edi regularity lemma. This lemma is presented and proved in Section 7.2. In Sec- tion 7.3, we outline a general method for applying the regularity lemma, and illustrate this in the proof of the Erd}os-Stone theorem postponed from Section 7.1. Another application of the regularity lemma will be given in Chapter 9.2. 7.1 Subgraphs Let H be a graph and n > jHj. How many edges will su\u2013ce to force an H subgraph in any graph on n vertices, no matter how these edges are arranged? Or, to rephrase the problem: which is the greatest possible number of edges that a graph on n vertices can have without containing a copy of H as a subgraph? What will such a graph look like? Will it be unique? 1 Note that, formally, the notions of sparse and dense make sense only for families of graphs whose order tends to inflnity, not for individual graphs. 7.1 Subgraphs 149 A graph G 6¶ H on n vertices with the largest possible number of edges is called extremal for n and H; its number of edges is denoted by extremal ex(n;H). Clearly, any graph G that is extremal for some n and H will ex(n;H) also be edge-maximal with H 6µ G. Conversely, though, edge-maximality does not imply extremality: G may well be edge-maximal with H 6µ G while having fewer than ex(n;H) edges (Fig. 7.1.1). Fig. 7.1.1. Two graphs that are edge-maximal with P 3 6µ G; is the right one extremal? As a case in point, we consider our problem forH = Kr (with r > 1). A moment\u2019s thought suggests some obvious candidates for extremality here: all complete (r¡ 1)-partite graphs are edge-maximal without con- taining Kr. But which among these have the greatest number of edges? Clearly those whose partition sets are as equal as possible, i.e. difier in size by at most 1: if V1; V2 are two partition sets with jV1j¡ jV2j > 2, we may increase the number of edges in our complete (r¡ 1)-partite graph by moving a vertex from V1 across to V2. The unique complete (r ¡ 1)-partite graphs on n > r ¡ 1 vertices whose partition sets difier in size by at most 1 are called Tur¶an graphs; we denote them by T r¡1(n) and their number of edges by tr¡1(n) T r¡1(n) (Fig. 7.1.2). For n < r ¡ 1 we shall formally continue to use these tr¡1(n) deflnitions, with the proviso that|contrary to our usual terminology| the partition sets may now be empty; then, clearly, T r¡1(n) = Kn for all n 6 r¡ 1. Fig. 7.1.2. The Tur¶an graph T 3(8) The following theorem tells us that T r¡1(n) is indeed extremal for n and Kr, and as such unique; in particular, ex(n;Kr) = tr¡1(n). 150 7. Substructures in Dense Graphs Theorem 7.1.1. (Tur¶an 1941) For all integers r; n with r > 1, every graph G 6¶ Kr with n vertices and[ 7.1.2 ][ 9.2.2 ] ex(n;Kr) edges is a T r¡1(n). Proof . We apply induction on n. For n 6 r ¡ 1 we have G = Kn = T r¡1(n) as claimed. For the induction step, let now n > r. Since G is edge-maximal without a Kr subgraph, G has a sub- graph K = Kr¡1. By the induction hypothesis, G ¡K has at mostK tr¡1(n ¡ r + 1) edges, and each vertex of G ¡ K has at most r ¡ 2 neighbours in K. Hence, kGk 6 tr¡1(n¡ r+ 1) + (n¡ r+ 1)(r¡ 2) + µ r¡ 1 2 ¶ = tr¡1(n) ; (1) the equality on the right follows by inspection of the Tur¶an graph T r¡1(n) (Fig. 7.1.3). ¡ r¡1 2 ¢ r¡ 2 tr¡1(n¡ r+1) Fig. 7.1.3. The equation from (1) for r = 5 and n = 14 Since G is extremal for Kr (and T r¡1(n) 6¶ Kr), we have equality in (1). Thus, every vertex of G¡K has exactly r¡2 neighbours in K| just like the vertices x1; : : : ; xr¡1 of K itself. For i = 1; : : : ; r¡ 1 letx1; : : : ; xr¡1 Vi := f v 2 V (G) j vxi =2 E(G) gV1; : : : ; Vr¡1 be the set of all vertices ofG whose r¡2 neighbours inK are precisely the vertices other than xi. Since Kr 6µ G, each of the sets Vi is independent, and they partition V (G). Hence, G is (r¡ 1)-partite. As T r¡1(n) is the unique (r¡1)-partite graph with n vertices and the maximum number of edges, our claim that G = T r¡1(n) follows from the assumed extremality of G. \u2044 The Tur¶an graphs T r¡1(n) are dense: in order of magnitude, they have about n2 edges. More exactly, for every n and r we have tr¡1(n) 6 12n 2 r¡ 2 r¡ 1 ; 7.1 Subgraphs 151 with equality whenever r ¡ 1 divides n (Exercise 8). It is therefore remarkable that just \u2020n2 more edges (for any flxed \u2020 > 0 and n large) give us not only a Kr subgraph (as does Tur¶an\u2019s theorem) but a Krs for any given integer s|a graph itself teeming with Kr subgraphs: Theorem 7.1.2. (Erd}os & Stone 1946) For all integers r > 2 and s > 1, and every \u2020 > 0, there exists an integer n0 such that every graph with n > n0 vertices and at least tr¡1(n) + \u2020n2 edges contains Krs as a subgraph. We shall prove this theorem in