Cliques in Graphs Siu Lun Allan Lo Christ’s College University of Cambridge A thesis submitted for the degree of Doctor of Philosophy 2010 Declaration This dissertation is the result of my own work and includes nothing which is the outcome of work done in collaboration except where specifically indicated in the text. All external results used have been properly attributed. Acknowledgements I would like to say thank you everyone for helping me to survive the past few years. A big thank you to my family for their continuous support, to the lunchtime PhD-gang for reminding me that I am not alone, making sure that I come to the office and eat my lunch, as well as increasing my knowledge of German culture. Also, thanks to the Cambridge University Lion Dance Troupe for keeping me active at many levels, both physically and socially. I would especially thank my supervisor, Prof. Andrew G. Thomason for his invaluable assistance and support throughout my degree. Abstract The main focus of this thesis is to evaluate kr(n, δ), the minimal num- ber of r-cliques in graphs with n vertices and minimum degree δ. A fundamental result in Graph Theory states that a triangle-free graph of order n has at most n2/4 edges. Hence, a triangle-free graph has minimum degree at most n/2, so if k3(n, δ) = 0 then δ ≤ n/2. For n/2 ≤ δ ≤ 4n/5, I have evaluated kr(n, δ) and determined the struc- tures of the extremal graphs. For δ ≥ 4n/5, I give a conjecture on kr(n, δ), as well as the structures of these extremal graphs. Moreover, I have proved various partial results that support this conjecture. Let kregr (n, δ) be the analogous version of kr(n, δ) for regular graphs. Notice that there exist n and δ such that kr(n, δ) = 0 but k reg r (n, δ) > 0. For example, a theorem of Andra´sfai, Erdo˝s and So´s states that any triangle-free graph of order n with minimum degree greater than 2n/5 must be bipartite. Hence k3(n, bn/2c) = 0 but kreg3 (n, bn/2c) > 0 for n odd. I have evaluated the exact value kreg3 (n, δ) for δ between 2n/5 + 12 √ n/5 and n/2 and determined the structure of these ex- tremal graphs. At the end of the thesis, I investigate a question in Ramsey Theory. The Ramsey number Rk(G) of a graph G is the minimum number N , such that any edge colouring of KN with k colours contains a monochromatic copy of G. The constrained Ramsey number f(G, T ) of two graphs G and T is the minimum number N such that any edge colouring of KN with any number of colours contains a monochro- matic copy of G or a rainbow copy of T . It turns out that these two quantities are closely related when T is a matching. Namely, for almost all graphs G, f(G, tK2) = Rt−1(G) for t ≥ 2. iv Contents 1 Introduction 1 1.1 Cliques in graphs - a classical problem . . . . . . . . . . . . . . . 1 1.2 Bounding the minimum degree . . . . . . . . . . . . . . . . . . . . 3 1.3 Constrained Ramsey theory . . . . . . . . . . . . . . . . . . . . . 5 2 Triangles in regular graphs 9 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Structure of the extremal graphs . . . . . . . . . . . . . . . . . . 10 2.3 Sum of squared degrees . . . . . . . . . . . . . . . . . . . . . . . . 11 2.4 Proof of Theorem 2.1.2 . . . . . . . . . . . . . . . . . . . . . . . . 14 2.5 Remark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3 Cliques in graphs 19 3.1 Conjectured extremal graphs and kr(n, δ) . . . . . . . . . . . . . . 19 3.2 Key observation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.3 Proof of Theorem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . 22 4 Degrees of cliques and Kp+2-free graphs 27 4.1 Degree of a clique . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.2 Kp+2-free graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5 Heavy cliques 37 5.1 Basic inequalities for heavy cliques . . . . . . . . . . . . . . . . . 38 5.2 kr(n, δ) for 2n/3 < δ ≤ 3n/4 . . . . . . . . . . . . . . . . . . . . . 41 5.2.1 Strengthening (5.3) . . . . . . . . . . . . . . . . . . . . . . 42 5.2.2 Strengthening (5.4) . . . . . . . . . . . . . . . . . . . . . . 47 5.2.3 Proof of Conjecture 3.1.1 for 1/4 ≤ β < 1/3 . . . . . . . . 47 5.3 Proof of Theorem 5.2.3 . . . . . . . . . . . . . . . . . . . . . . . . 48 6 kr(n, δ) for 3n/4 < δ ≤ 4n/5 59 6.1 kr(n, δ) for 3n/4 < δ ≤ 4n/5 . . . . . . . . . . . . . . . . . . . . . 60 v 6.2 Proof of Lemma 6.1.1 . . . . . . . . . . . . . . . . . . . . . . . . . 63 6.3 Proof of Lemma 6.1.3 . . . . . . . . . . . . . . . . . . . . . . . . . 66 6.4 Proof of Lemma 6.1.2 . . . . . . . . . . . . . . . . . . . . . . . . . 78 7 kr(n, δ) for δ > 4n/5 95 7.1 kr(n, δ) for δ > 4n/5 . . . . . . . . . . . . . . . . . . . . . . . . . 96 7.2 Counting (p+ 1)-cliques . . . . . . . . . . . . . . . . . . . . . . . 104 8 Further directions 111 8.1 Cliques in regular graphs, kregr (n, δ) . . . . . . . . . . . . . . . . . 111 8.2 (n, β) not feasible . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 8.3 Maximum number of cliques . . . . . . . . . . . . . . . . . . . . . 114 8.4 A degree sum condition . . . . . . . . . . . . . . . . . . . . . . . . 115 9 Constrained Ramsey numbers 117 9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 9.2 Rainbow matching f(S, tK2) . . . . . . . . . . . . . . . . . . . . . 120 9.3 Consequences of Theorem 1.3.2 . . . . . . . . . . . . . . . . . . . 124 Bibliography 129 vi Chapter 1 Introduction 1.1 Cliques in graphs - a classical problem Let G be a graph of order n and size e unless stated otherwise. For a given graph H, a graph G is H-free if it does not contain a subgraph isomorphic to H. One of the trademark problems in Extremal Graph Theory is to determine the maximum number of edges in a graph without any triangles. Mantel [34] first proved that a triangle-free graph of order n has at most n2/4 edges. Moreover, he showed that a complete bipartite graph with partition sizes dn/2e and bn/2c is the only triangle-free graph of order n with bn2/4c edges. For a graph H, we denote by ex(n,H) the maximum number of edges in a H-free graph of order n. Thus, using this notation, ex(n,K3) = bn2/4c. The r-partite Tura´n graph of order n, Tr(n), is a complete r-partite graph of order n with vertex classes of sizes either bn/rc or dn/re. Tura´n [45] proved that if G is Kr+1-free, then e(G) ≤ e(Tr) with equality if and only if G = Tr(n). Thus, ex(n,Kr+1) = e(Tr). If we denote by Kr(G) the set of Kr in G and its size kr(G) = |Kr(G)|, then Tura´n’s Theorem states that if kr+1(G) = 0, then e(G) ≤ e(Tr(n)). Given e(G) > e(Tr(n)), we would like to know what values of kr(G) are possible. This naturally leads us to the problem of which values of kr(G) are possible if e(G) > e(Tr(n)), a problem which many people have investigated. Erdo˝s [15] proved that kr(G) is at most ( a r ) + ( b r−1 ) , where a > b ≥ 0 are the unique integers such that e = ( a 2 ) +b. It should be noted that the above statement 1 Chapter 1. Introduction is independent of n. The graph obtained by joining a new vertex to b vertices of a complete graph of order a has precisely ( a 2 ) + b edges and ( a r ) + ( b r−1 ) r-cliques (complete graphs of order r). Now, this problem of bounding kr(G) from above for a given e is in fact a special case of the Kruskal-Katona Theorem [31, 30], which is stated below, taking s = 2 and t = r. Theorem 1.1.1 (Kruskal-Katona Theorem [31, 30]). Let s and t be two positive integers with s < t. Let A be a family of s-sets of size |A| = (ns s ) + ( ns−1 s−1 ) + · · ·+( nj j ) , where ns > ns−1 > · · · > nj ≥ j ≥ 1. Let B be the union of all t-element supersets of the sets in A. Then, |B| ≤ (ns t ) + ( ns−1 t−1 ) + · · ·+ ( nj t−s+j ) . Let fr(n, e) be the minimal kr(G) for graphs G of order n and size e. De- termining fr(n, e) seems to be difficult. First, we give the structure of a family of graphs that are conjectured to achieve fr(n, e). Let p be an integer such that (1 − 1/p)n2/2 < e ≤ (1 − 1/(p + 1))n2/2. Note that a simple calculation shows that e(Tp(n)) ≤ (1 − 1/p)n2/2. We consider a (p + 1)-partite graph with vertex classes V1, . . . , Vp+1 with the following properties. Each vertex class V1, . . . , Vp has size at least |Vp+1|, and |V1| ≥ · · · ≥ |Vp| ≥ |V1|−1. The graph induced by Vi and Vj is a complete bipartite graph with partition Vi and Vj for all 1 ≤ i < j ≤ p+1 unless i = p and j = p+1. The graph induced by Vp and Vp+1 is a bipartite graph with partition Vp and Vp+1 and more than |Vp||Vp+1| − |Vp| edges. Since there is a choice of missing edges between Vp and Vp+1, the above construction defines a family of graphs. Each such graph achieves the conjectured fr(n, e). Note that these graphs are independent of r, so is fr(n, e) (provided that e > e(Tr(n)). Also, the structure of these graphs depends on the edge density e/ ( n 2 ) . Hence, one of the main parameters of fr(n, e) may be assumed to be the edge density e/ ( n 2 ) . Hence, we sometimes say that e is in the interval between c1 and c2, meaning that c1n 2/2 < e ≤ c2n2/2 for 0 ≤ c1 ≤ c2 ≤ 1. Erdo˝s [17] was the first to study f3(n, e) for e ≤ n2/4 + o(1). Lova´sz and Simonovits [33] proceeded to evaluate f3(n, e) for n 2/4 ≤ e ≤ n2/4 + n/2. Bol- loba´s [5] then gave the first concave, actually linear, bound for each interval between 1 − 1/p and 1 − 1/(p + 1) for positive integers p. Moreover, the lower bound is sharp at the boundary points of each interval, i.e. e = (1− 1/p)n2/2 for each integer p ≥ r. Fisher [22] evaluated f3(n, e) asymptotically for the interval 2 1.2 Bounding the minimum degree between 1/2 and 2/3, but it was not until nearly twenty years later that a dra- matic breakthrough of Razborov [40] proved the asymptotic result of f3(n, e) for a general e. The proof of this used the concept of flag algebra developed in [39]. Unfortunately, it seemed difficult to generalise Razborov’s proof even for f4(n, e). Nikiforov [35] later gave a simple and elegant proof of the asymptotic result of both f3(n, e) and f4(n, e) for general e. However, bounds for fr(n, e) when r ≥ 5 have not yet been determined. We recommend Chapter 6 in [6] for a survey of other results related to complete subgraphs. 1.2 Bounding the minimum degree In this thesis, we are interested in a variant of the classical problem described in the last section, where instead of considering the number of edges we consider the minimum degree. In this case, kr(n, δ) is defined to be the minimum value of kr(G) for graphs G of order n with minimum degree δ. In addition, k reg r (n, δ) is defined to be the minimum value of kr(G) for δ-regular graphs G of order n. It can be seen, by Tura´n’s Theorem, that if kr(n, δ) = 0 then δ ≤ (1− 1/r)n. It should be noted that there exist n and δ such that kr(n, δ) = 0, but k reg r (n, δ) > 0. For example, if r = 3, n odd and 2n/5 < δn < 2, then k3(n, δ) = 0 by removing edges from T2(n) until we have minimum degree δ. However, a theorem of Andra´sfai, Erdo˝s and So´s [3] states that every triangle-free graph of order n with minimal degree greater than 2n/5 is bipartite. Since no regular graphs with an odd number of vertices can be bipartite, kreg3 (n, δ) > 0 for n odd and 2n/5 < δ < n/2, whilst k3(n, δ) = 0. In Chapter 2, we determine the exact value of k reg 3 (n, δ) for n odd and δ in the interval between 2n/5 + 12 √ n/5 and n/2. Theorem 1.2.1. For every odd integer n ≥ 107 and even integer δ with 2n/5 + 12 √ n/5 ≤ δ ≤ n/2, kreg3 (n, δ) = δ(3δ − n− 1)/4 holds. In addition, we identify the structure of the extremal graphs for kreg3 (n, δ). The construction given in Chapter 2 implies that kreg3 = O(n 2) for n/3 ≤ δ ≤ n/2. Therefore, the contribution from the parity of n should be o(1) in terms of density of triangles. 3 Chapter 1. Introduction We have also studied k3(n, δ) for δ > n/2. Thus, in Chapter 3, we have given what we conjecture to be the exact structure of extremal graphs for kr(n, δ) subject to certain conditions on n and δ. These extremal graphs for kr(n, δ) share many similarities with the ones for fr(n, e). For example, the extremal graphs are independent of r (provided δ > (1 − 1/r)n). Our main result proves a sharp lower bound on kr(n, δ) for n/2 < δ ≤ 4n/5. Theorem 1.2.2. Let n and δ be integers with n/2 < δ ≤ 4n/5. Let β = 1− δ/n. Then for integers r ≥ 3, kr(n, δ) ≥ gr(β)nr, where the function gr(β) is explicitly defined in Section 3.1. Moreover, for 3 ≤ r ≤ β−1+1 equality holds if and only if (n, β) is feasible, and the extremal graphs are members of G(n, β), where feasible and G(n, β) are also defined in Section 3.1. The proof of the above theorem is spread over Chapters 3 to 6. In Section 3.3, we give an elegant proof for the case n/2 < δ ≤ 2n/3 which then forms the framework for proving Theorem 1.2.2 for 2n/3 ≤ δ ≤ 4n/5. In Chapter 4, we prove that Theorem 1.2.2 is true for Kp+2-free graphs, where p = 3 if 2n/3 < δ ≤ 3n/4, and p = 4 if 3n/4 < δ ≤ 4n/5. In fact, we prove a sharp lower bound on kr(G) for Kp+2-free graphs G of order n and minimum degree δ, where n/2 < δ < n and p = d(1− δ/n)−1e − 1. Theorem 1.2.3. Let n and δ be integers with n/2 < δ < n. Let β = 1− δ/n and p = dβ−1e − 1. Then for integers r ≥ 3, kr(n, δ;Kp+2-free) ≥ gr(β)nr holds, where kr(n, δ;Kp+2-free) is the minimum value of kr(G) for Kp+2-free graphs G of order n with minimum degree δ. Moreover, for 3 ≤ r ≤ p+ 1 equal- ity holds if and only if (n, β) is feasible, and the extremal graphs are members of G(n, β). Various technical difficulties arise when we prove Theorem 1.2.2 for the case 2n/3 < δ ≤ 4n/5 for graphs G containing cliques of sizes p + 2. This is because the existence of (p + 2)-cliques in G introduces error terms into our estimates 4 1.3 Constrained Ramsey theory for kr(G) for 3 ≤ r ≤ p + 1, a situation which we discuss in Section 5.2 when 2n/3 < δ ≤ 3n/4 and G contains a 5-clique. Chapter 5 and Chapter 6 are dedicated respectively to the cases for 2n/3 < δ ≤ 3n/4 and 3n/4 < δ ≤ 4n/5. We study the case δ > 4n/5 in Chapter 7, where we evaluate kr(n, δ) exactly for δ/n ∈ I, where I is a union of infinitely many non-empty intervals between 0 and 1. The following theorem is proved in Section 7.1. Theorem 1.2.4. For positive integers p, there exists 1/(p+ 1) < βp ≤ 1/p such that for all 1/(p+ 1) ≤ β < βp and integers n, δ = (1− β)n and r, kr(n, δ) ≥ gr(β)nr holds. Moreover, for 3 ≤ r ≤ p+ 1 equality holds if and only if (n, β) is feasible, and the extremal graphs are members of G(n, β). 1.3 Constrained Ramsey theory For an edge colouring of a graph G, we say that G is monochromatic if and only if all its edge colours are the same. The Ramsey number R(s, t) is the minimum number N such that for any edge colouring of KN with two colours, say red and blue, there exists a red monochromatic copy of Ks or a blue monochromatic copy ofKt. It is easy to see that R(2, s) = s and R(s, t) = R(t, s). Also, it can be easily shown that R(3, 3) = 6. The existence of R(s, t) was first proved by Ramsey [38] and rediscovered by Erdo˝s and Szekeres [16]. Only a few of the numbers of R(s, t) are known precisely. Erdo˝s and Szekeres [16] showed that R(s, s) ≤ (2s−2 s−1 ) . This bound was later improved by Ro¨dl [24] and Thomason [42]. The best known upper bound was proved by Conlon [12], that is, R(s, s) ≤ s−c log slog log s (2s−2 s−1 ) , whilst the best known lower bound for R(s, s) is of order 2s/2, which is obtained by a simple probabilistic argument. The Ramsey number R(s1, . . . , sk) is defined analogously to be the minimum number N such that for any edge colouring of KN with colours c1, . . . , ck, there exists a monochromatic copy of Ksi of colour ci for some i. If si = s for all i, then we simply write Rk(s). If an edge colouring of KN uses infinitely many colours, then it is possible to avoid monochromatic Ks for s ≥ 3. Nevertheless, there 5 Chapter 1. Introduction exists a well-structured edge coloured complete subgraph in KN . For example, there may exist a complete subgraph that is rainbow (i.e every edge has a distinct colour). If we let the vertices of G be v1, . . . , vn, then a lexicographically coloured (or colexicographically coloured) G is an edge colouring such that the edge vivj has colour ci for i < j (or i > j respectively) with ci distinct. It can be observed that a lexicographically coloured finite graph becomes colexicographically coloured if the ordering on the vertex set is reversed, and vice versa. Erdo˝s and Rado [18] proved that for any edge colouring of KN with any number of colours, there exists a complete subgraph with one of the above colourings. This is known as the Canonical Ramsey Theorem. Theorem 1.3.1 (Canonical Ramsey Theorem [18]). For every positive integer s, there exists an integer N(s) > 0 with the following property. For each integer N ≥ N(s) and every edge colouring of KN , there exists a Ks in KN such that it is either monochromatic, rainbow, lexicographically coloured or colexicographically coloured. The Ramsey number R(G,H) of two graphs, G and H, is the minimum number N such that for any 2-edge colouring of KN with colours red and blue say, there exists a red monochromatic G or a blue monochromatic H. Hence, R(Ks, Kt) = R(s, t). For graphs G1, . . . , Gk, we define R(G1, . . . , Gk) analogously and write Rk(G) if Gi = G for all i. Until now we have considered only monochromatic subgraphs. However, the canonical Ramsey Theorem states that there exists a monochromatic, rainbow, lexicographically coloured or colexicographically coloured subgraph in any edge colouring of KN for N sufficiently large. It should be noted that both lexico- graphical and colexicographical colourings depend on the initial ordering of the vertex set, so they are not preserved under vertex relabelling. Hence, we shall focus our attention on study monochromatic and rainbow subgraphs. The constrained Ramsey number f(S, T ) of two graphs, S and T , is the minimum number N such that for any edge colouring of KN with any num- ber of colours, there exists a monochromatic copy of S or a rainbow copy of T . In the literature, this is sometime called the rainbow Ramsey number or the monochromatic-rainbow Ramsey number. If follows easily from the canonical 6 1.3 Constrained Ramsey theory Ramsey Theorem (see Proposition 9.1.2) that f(S, T ) exists if and only if S is a star of T is acyclic. An obvious lower bound for f(S, T ) is Rt−1(S, T ), where t = e(T ). This is because there exists an edge colouring of KRt−1(S)−1 using t − 1 colours, which does not contain a monochromatic copy of S by the defini- tion of Rt−1(S). Since this edge colouring uses fewer than t colours, there is no rainbow T . Various people have investigated the exact values of f(S, T ). Alon, Jiang, Miller and Pritikin [2] studied the case when S = K1,s. The number f(K1,s, T ) is closely related to an m-good colouring. An m-good colouring is an edge colouring such that any vertex is incident with at most m edges of the same colour. Thus, f(K1,s, T ) is the minimum number N such that any (s − 1)-good colouring of KN contains a rainbow T . On the other hand, f(S,K1,t) coincides with the local (t − 1)-Ramsey number of a graph S. The local (t − 1)-Ramsey number of a graph S, first introduced by Gya´rfa´s, Lehel, Schelp and Tuza [26], is the analogue of the Ramsey number of S restricted to edge colourings such that each vertex is incident with at most t − 1 edges of different colours. Jamison, Jiang and Ling [28] studied f(S, T ) when S and T are both trees. Wagner [46], Loh and Sudakov [32] investigated further the important case when S is a tree and T is a path. In Chapter 9, we study f(S, tK2), where tK2 is a set of vertex disjoint edges of size t. Theorem 1.3.2. Suppose S is a graph of order at least 5 and Rk+1(S) ≥ Rk(S)+3 for all positive integers k. Then, f(S, tK2) = Rt−1(S) for all integers t ≥ 2. We also identify the graphs S that do not satisfy the hypothesis of the theorem above in Proposition 9.3.1. If S has no isolated vertices, then S is bipartite and one of its vertex classes has size at most 3. 7 Chapter 1. Introduction 8 Chapter 2 Triangles in regular graphs with density below a half 2.1 Introduction Mantel [34] proved that a triangle-free graph of order n has at most n2/4 edges. Hence, a triangle-free regular graph of order n has degree δ ≤ n/2. If n is even, it is easy to construct n/2-regular bipartite graphs of order n. Recall that kreg3 (n, δ) is the minimum number of triangles in δ-regular graphs of order n. Therefore, for n even, kreg3 (n, δ) = 0 if and only if δ ≤ n/2. For n odd, we investigate the largest possible δ such that kreg3 (n, δ) = 0. By considering a blow-up of a cycle of length 5, δ can be as large as 2n/5 when n is a multiple of 5. In fact, δ is at most 2n/5 by a theorem of Andra´sfai, Erdo˝s and So´s [3]. We state the special case of their theorem for r = 3 below. Theorem 2.1.1 (Andra´sfai, Erdo˝s and So´s [3]). Any triangle-free graph of or- der n with minimum degree at least 2n/5 must be bipartite. Therefore, if n is odd and kreg3 (n, δ) = 0, then δ ≤ 2n/5. In this chapter, we evaluate kreg3 (n, δ) for n odd and almost all δ between 2n/5 and n/2. Theorem 2.1.2. Let k ≥ 220 and l ≥ 0 be integers with k ≥ 2l + 3√30l + 137. 9 Chapter 2. Triangles in regular graphs Suppose G is a 2k-regular graph with order 4k + 2l + 1. Then, k3(G) ≥ k(k − l − 1) holds. Furthermore equality holds if and only if G ∈ Greg(k, l) (defined in Sec- tion 2.2). By rephrasing the above theorem in terms of n and δ, we prove Theorem 1.2.1. Proof of Theorem 1.2.1. Let n = 4k + 2l + 1 and δ = 2k. Since δ ≥ 2n/5, we have k ≥ 220. Note that l = (n − 2δ − 1)/2 ≤ n/10. By the hypothesis, we have 2k ≥ 2(4k + 2l + 1)/5 + 12√10l/5, that is k ≥ 2l + 6√10l + 1. If l ≥ 212, 6 √ 10l+1 > 3 √ 30l+137. If l ≤ 212, 2l+3√30l+137 < 214 < k. Hence, k and l satisfies the hypothesis of Theorem 2.1.2. Therefore, kreg3 (n, δ) = k(k − l − 1) = δ(3δ − n− 1)/4. In the next section, we define the family G(n, β) of extremal graphs as stated in Theorem 2.1.2. In Section 2.3, we investigate the sum of the squares of the degrees of a graph, which turns out to be an important tool for our proof. Finally, we prove Theorem 2.1.2 in Section 2.4. 2.2 Structure of the extremal graphs First, we look at the case n = 4k+1 and δ = bn/2c = 2k. Our task is to construct a 2k-regular graph of order 4k + 1 by adding a new vertex to a triangle-free 2k- regular graph of order 4k. The only triangle-free 2k-regular graph of order 4k is a complete bipartite graph with vertex classes X and Y with |X| = |Y | = 2k. We remove a matchingM of size k and join all vertices that are incident withM to a new vertex z. Let G be the resulting graph. Figure 2.2 is G for k = 2. Clearly, G is 2k-regular and every triangle contains the vertex z. Hence, k3(G), the number of triangles in G, is k(k−1). This is precisely the bound in Theorem 2.1.2. Next, we extend this construction for δ < n/2 as follows. Let k and l be integers with k > l ≥ 0. Consider a complete bipartite graph K2k+l,2k+l with vertex sets {x1, . . . , x2k+l} and {y1, . . . , y2k+l}. First, we remove an (l+1)-factor from the graph induced by the vertex set {xi, yi : 1 ≤ i ≤ 10 2.3 Sum of squared degrees rz r r r r r r r r x1 x2 x3 x4 y1 y2 y3 y4 ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¢ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡ ´ ´ ´ ´ ´ ´ ´ ´´ A A A A A A A A A A A A A A A A A A @ @ @ @ @ @ @ @ @ @ @ @ Q Q Q Q Q Q Q QQ ¢ ¢ ¢ ´ ´ ´ ´ A A A Q Q Q Q Figure 2.1: G for k = 2 k}, and an l-factor from the graph induced by the vertex set {xi, yi : k < i ≤ 2k+ l}. Join x1, . . . , xk, y1, . . . , yk to a new vertex z. We denote by Greg(k, l) the family of graphs which can be obtained by the above construction. For G ∈ Greg(k, l), G is 2k-regular with 4k + 2l + 1 vertices. Each triangle in G contains the vertex z, so there are k(k− l− 1) triangles in G. Note that Greg(k, l) is family of extremal graphs stated in Theorem 2.1.2. Also, |Greg(k, l)| = 1 for l = 0 or l = k− 1. The case l = 0 corresponds to the case when δ = bn/2c. On the other hand, for l = k − 1, Greg(k, l) is a family of n/3 + o(n)-regular graphs. 2.3 Sum of squared degrees For a general graph H, we write φ(H) for the sum of the squares of the degrees of the vertices of H of order n. Clearly, by the Cauchy-Schwarz inequality, φ(H) is at least 4e(H)2/n. However, for given n and e, determining max{φ(H) : |H| = n and e(H) = e} is non-trivial. Let a and b be the unique non-negative integers such that e = ( a 2 ) + b with 0 ≤ b < a. The quasi-complete graph Cen with e edges of order n is the graph with vertex set v1, . . . , vn and E(C e n) = {vivj : i < j ≤ a} ∪ {va+1vi : i ≤ b}. The quasi-star Sen is the complement graph of Ce′n where e′ = ( n 2 ) − e. Let S(n, e) = φ(Sen) and C(n, e) = φ(Cen). Ahlswede and Katona [1] proved that the maximum of φ(H) over all graphs H with n vertices and e edges is either S(n, e) or C(n, e). This result was rediscovered by Olpp [37]. We paraphrase their theorem below. 11 Chapter 2. Triangles in regular graphs Theorem 2.3.1 (Ahlswede and Katona [1], Olpp [37]). Let H be a graph with n vertices and e edges. Then φ(H) ≤  S(n, e) if 0 ≤ e < (n 2 ) /2− n/2 max{S(n, e), C(n, e)} if (n 2 ) /2− n/2 ≤ e ≤ (n 2 ) /2 + n/2 C(n, e) if ( n 2 ) /2 + n/2 < e ≤ (n 2 ) holds. Moreover, for e < ( n 2 ) /2 − n/2 or e > (n 2 ) /2 + n/2, equality holds if and only if H is Sen or C e n respectively. However, both S(n, e) and C(n, e) are difficult to express in terms of e and n. Clark, Entringer and Sze´kely [10], de Caen [14] and Nikiforov [36] gave simpler but weaker upper bounds on φ(H). Das [13] bounds φ(H) from above with an extra constraint that the degrees of H are bounded. However, for our purpose, we need to determine the exact maximum of φ(H) when the degrees are bounded from above and e is small. Formally speaking, we are going to determine the maximum of φ(H) over all graphs H with e edges and maximal degree ∆(H), where e and ∆(H) are specified in the lemma below. Here, we do not specify n, the number of vertices of H, as it turns out that the maximum value of φ(H) is independent of n. Lemma 2.3.2. Let r be a positive integer greater than 4500, and H be a graph with ∆(H) ≤ r and e(H) = βr for 1 ≤ β < 6/5. Then φ(H) ≤ S(r + 1, βr) = (β2 − 2β + 2)r2 + (5β − 4)r. Furthermore, equality holds if and only if H is Sβrr+1 with isolated vertices. Proof. Suppose H is a graph achieving the maximum value of φ(H), so φ(H) ≥ S(r + 1, βr). First, we would like to determine the number of vertices with maximum degree ∆ in H. Suppose that ∆ ≤ (e(H) + 1)/2. Let W be the set of vertices v ∈ V (H) with d(v) > e(H)/16. Clearly, |W | ≤ 32 and ∑w∈W d(w) ≤ 12 2.3 Sum of squared degrees e(H) + (|W | 2 ) ≤ e(H) + 496 ≤ 10e(H)/9. This means that we have φ(H) = ∑ w∈W d(w)2 + ∑ v/∈W d(v)2 ≤ 1 2 (e(H) + 1) ∑ w∈W d(w) + 1 16 e(H) ∑ v/∈W d(v) = 1 2 (e(H) + 1) ∑ w∈W d(w) + 1 16 e(H)(2e(H)− ∑ w∈W d(w)) ≤ 5 9 e(H)2 + 1 8 e(H)2 = 49 72 e(H)2 < r2, contradicting the maximality of φ(H). Hence, ∆ ≥ e(H)/2 + 1 and there exists a unique vertex u with d(u) = ∆. Next, we would like to identify the isolated vertices of H. Suppose vw is an edge of H with v /∈ N(u) ∪ {u}. If ∆ < r, the graph H ′ = H − vw + uv has φ(H ′)− φ(H) = (d(u) + 1)2 + (d(w)− 1)2 − (d(u)2 + d(w)2) = 2(d(u)− d(w) + 1) > 0. This contradicts the maximality of φ(H), so we may assume ∆ = r. Since d(w) < r, there exists x ∈ N(u)\N(w). If d(v) ≥ d(x), then φ(H − ux+ uv)− φ(H) =2(d(v)− d(x) + 1) > 0. Otherwise, φ(H − vw + xw)− φ(H) =2(d(x)− d(v) + 1) > 0. Hence, d(v) ≥ 1 if and only if v ∈ N(u)∪{u}. This means that the set of isolated vertices of H is precisely the vertex set V (H)\(N(u) ∪ {u}). From now on, we may assume that H contains no isolated vertex. We now claim that ∆ is in fact equal to r. Suppose the contrary. Since ∆ < e(H), there exists an edge lying entirely in the neighbourhood of u. Let 13 Chapter 2. Triangles in regular graphs w1w2 be such an edge with d(w1) + d(w2) minimal. Note that d(w1) + d(w2) ≤ e(H)− (d(u)− 2) + 1 = e(H)−∆+ 3 ≤ ∆+ 1 as ∆ ≥ e(H)/2 + 1. Then the graph H˜ which is obtained by removing the edge w1w2 and joining u to a new vertex w3, has φ(H˜) = φ(H) + 2(∆− dH(w1)− dH(w2) + 2) > φ(H), a contradiction and proves the claim. Hence, V (H) = r+1 and e(H) = βr. This is a special case of Theorem 2.3.1, so φ(H) = S(r + 1, βr). Furthermore, this is achieved if and only if H = Sβrr+1. Clearly the bound on r ≥ 4500 is just an artifact of the proof. This bound could be reduced by a more careful counting argument. In addition, the argument still holds for β ≤ 2 and r sufficiently large. Furthermore, we believe for a graphH with degree at most r ≥ 2 and e ≤ (r 2 ) /2− r/2 edges, the extremal graph which achieves the maximal φ(H), is Ser+1 with isolated vertices. 2.4 Proof of Theorem 2.1.2 Let G be a 2k-regular graph with order 4k + 2l + 1 and k3(G) minimal. By the construction of Greg(k, l), k3(G) ≤ k(k− l−1). Let X and Y be a vertex partition of V (G) with e(X, Y ) maximal. Without loss of generality |X| = 2k + l + p + 1 and |Y | = 2k+l−p for some non-negative integer p. We further define e(X) = βk. Since 2k|X| =∑x∈X d(x) = e(X,Y )+2e(X) ≤ 2k|Y |+2e(X), we have β ≥ 2p+1. For any vertex v, dX(v) denotes the number of neighbours of v in X, i.e. dX(v) = |N(v)∩X|, and dY (v) is defined similarly. By the maximality of e(X,Y ), dX(x) ≤ k for all x ∈ X and dY (y) ≤ k for all y ∈ Y . For an edge v1v2, d(v1v2) denotes the number of common neighbours of v1 and v2. Hence, d(v1v2) is the number of triangles containing the edge v1v2. Similarly, we define dY (v1v2) to be the number of common neighbours of v1 and v2 in Y . For x1x2 ∈ E(X), dY (x1x2) ≥dY (x1) + dY (x2)− |Y | = 2k + p− l − (dX(x1) + dX(x2)). (2.1) 14 2.4 Proof of Theorem 2.1.2 Let t be number of triangles with two vertices inX and one vertex in Y . Summing (2.1) over all edges in X, we get t = ∑ x1x2∈E(X) dY (x1, x2) ≥ ∑ x1x2∈E(X) 2k + p− l − (dX(x1) + dX(x2)) = e(X)(2k + p− l)− φ(G[X]) = βk(2k + p− l)− φ(G[X]). But t ≤ k3(G) ≤ k(k − l − 1) and so k(k − l − 1) ≥ βk(2k + p − l) − φ(G[X]). Since p ≥ 0, this implies k(k − l − 1) ≥ βk(2k − l)− φ(G[X]). (2.2) Moreover since β ≥ 1 and l ≤ k/2 this gives 2φ(G[X]) ≥ (3β − 1)k2. (2.3) In order to apply Lemma 2.3.2 to φ(G[X]), we need to bound β from above. We call the edge e heavy, if e is contained in more than 2(k− l−1)/3 triangles. We write d(e) to denote the number of triangles containing e. Equivalently, an edge e is heavy if and only if d(e) > 2(k − l − 1)/3. Let T be a triangle with edges e1, e2 and e3. For i = 0, 1, 2, 3, let ni denote the number of vertices inG with exactly i neighbours in T . Clearly, ∑ ni = n, ∑ ini = 6k and n2+3n3 = ∑ d(ei) by counting vertices, edges and triangles respectively. Thus, ∑ d(ei) ≥ n2+2n3 ≥∑ ini − ∑ ni = 2k − 2l − 1, so one of e1, e2, e3 is heavy. This means that every triangle contains at least one heavy edge. Hence, G is triangle-free if we remove all the heavy edges. Let h be the number of heavy edges in G. Notice that h ≤ 9k/2, because 2h(k− l− 1)/3 ≤∑ d(e) = 3k3(G) ≤ 3k(k− l− 1). Let W be the set of vertices incident with at least 3 √ 3k/5 heavy edges. Then |W | ≤ 2h/(3√3k/5) ≤√ 15k. Let G′ be the subgraph formed by removing all the heavy edges and the vertex set W . Note that |G′| = n − |W | = 4k + 2l + 1 − |W | and δ(G′) > 2k − |W | − 3√3k/5. We claim that δ(G′) > 2|G′|/5, i.e. 2k − |W | − 3√3k/5 > 2(4k + 2l + 1 − |W |)/5. This is equivalent to 2(k − (2l + 1)) > 3(√15k + |W |). 15 Chapter 2. Triangles in regular graphs Setting |W | = √15k, this is true provided (k − (2l + 1))2 ≥ 135k as k > 2l + 1. Expanding and rearranging the inequality we have k2 − (4l + 137)k + (2l + 1)2 > 0, which is true as k > 2l + 3 √ 30l + 137 > 2l + (3 √ 120l + 2085 + 137)/2 by the hypothesis of the theorem. Thus, the claim holds and so δ(G′) > 2|G′|/5. Moreover, G′ is triangle-free and so is bipartite by Theorem 2.1.1. Now, G′ has at least e(G)− 2k|W | − h ≥ e(G)− 2k √ 15k − 9k/2 ≥ e(G)− 8k √ k edges. Since e(X) + e(Y ) is minimal, it follows that e(X) ≤ 8k√k, in other words β ≤ 8√k. Now let U be the set of vertices x ∈ X with dX(x) ≥ α √ βk, where α ≤√k/β is some number to be decided later. Then, |U | ≤ 2βk/α√βk = 2√βk/α . Also,∑ u∈U dX(u) ≤ e(X) + (|U | 2 ) ≤ (1 + 2/α2)βk . Hence, φ(G[X]) = ∑ u∈U dX(u) 2 + ∑ v∈X\U dX(v) 2 ≤ k ∑ u∈U dX(u) + α √ βk ∑ v∈X\U dX(v) ≤ (1 + 2/α2)βk2 + α(1− 2/α2)(βk)3/2 ≤ (1 + 2/α2)βk2 + α(βk)3/2. The penultimate inequality is true as α < √ k/β. Set α = (16k/β)1/6, so φ(G[X]) ≤ βk2 + 3(β4k5/2)1/3. By (2.3), we know that β − 1− 3(4β4/k)1/3 is negative. Now we claim that β < 6/5. It is enough to show that the above equation is strictly positive when β ∈ [6/5, 8√k]. In fact, we only need to check the cases when β = 6/5 and β = 8 √ k by convexity. If β = 6/5, we are done as k ≥ 220. If β = 8√k, β − 1 − 3(4β4/k)1/3 is an increasing function in k 16 2.5 Remark for k ≥ 220. It is strictly positive when k = 220. Hence, this proves the claim, so β < 6/5. Recall that β ≥ 2p + 1, so we have p = 0. By Lemma 2.3.2, φ(G[X]) ≤ (β2 − 2β + 2)k2 + (5β − 4)k, Notice that βk(2k − l)− φ(G[X]) ≥ βk(2k − l)− ( (β2 − 2β + 2)k2 + (5β − 4)k ) = k(k − l − 1) + (β − 1)(3− β)k2 − (β − 1)(l + 5)k ≥ k(k − l − 1) + (β − 1)(2− β)k2 ≥ k(k − l − 1). Thus equality holds in (2.2). For equality to hold, we need β = 1 , so e(X) = k, and by Lemma 2.3.2 G[X] is a star K1,k. Let z be the centre of K1,k, Xz = X ∩ N(z) and Yz = Y ∩ N(z). By (2.1), each x ∈ Xz has at least k − l − 1 neighbours in Yz. In fact, each has exactly k−l−1 neighbours in Yz as k(k−l−1) = |k3| ≥ ∑ x∈Xz |N(x) ∩ Yz| ≥ |Xz|(k − l − 1) = k(k − l − 1). By regularity of G, |N(x) ∩ Y \Yz| = k + l + 1 = |Y \Yz|. Thus, G[Xz, Y \Yz] is a complete bipartite graph. Similarly, G[Yz, X\Xz] is complete bipartite by considering X ′ = Y ∪ z and Y ′ = X\z. Once again, by the regularity of the graph, G[X\(Xz∪{z}), Y \Yz] is (k − l)-regular. Hence, G is a member of Greg(k, l). Thus completes the proof of Theorem 2.1.2. ¤ 2.5 Remark In summary, the main idea of the proof is to first consider the bipartition of the vertex set into X and Y with e(X,Y ) maximal. Then, we estimate the number of triangles with exactly two vertices inX using a bound on φ(G[X]) (Lemma 2.3.2). Observe that the lower bound on k in the assumption of Theorem 2.1.2 is also an artifact of the proof. This bound on k can be significantly improved if we improve the argument of bounding β from √ k to a constant term. Another way to improve the bound on k would be to prove Lemma 2.3.2 for β ≤ 8√k. We are now interested in kreg3 (n, δ) for n odd and δ ≤ 2n/5. Also, we would like to identify the structures of graphs that achieve kreg3 (n, δ). Clearly, Greg(k, l) 17 Chapter 2. Triangles in regular graphs is a suitable candidate for the extremal graphs for kreg3 (n, δ). Other possible can- didates are graphs that are obtained by modifying triangle-free δ-regular graphs of order n − 1. Hence, we would like to know the structures of the triangle- free regular graphs with degree δ ≤ 2n/5. Fortunately, triangle-free graphs with minimum degree δ have been well studied. We now give a brief overview. A homomorphism f from a graph G to a graph H maps V (G) to V (H) such that f(v)f(u) ∈ E(H) if vu ∈ E(G). We say that G is homomorphic to H, if there exists a homomorphism from G to H. Therefore, with this notation, Theo- rem 2.1.1 states that any triangle-free graph G of order n with minimum degree at least 2n/5 is homomorphic to an edge. Ha¨ggkvist [27] extended this result and showed that if the minimum degree is at least 3n/8, then G is homomorphic to a C5. Jin [29] classified the structures of triangle-free graphs for δ(G) ≥ 10n/29. Later, Chen, Jin and Koh [9], and Brandt [7] identified the structures of graphs which do not contain a Gro¨tzsch graph, or a modified Petersen Graph (with ei- ther an edge deletion or contraction) respectively. It is worth pointing out that such structural results for triangle-free graphs are only valid for δ(G) ≥ n/3. For example, Hajnal (see [19]) used Kneser graphs to show that there exist many triangle-free graphs with minimum degree (1/3 − ²)n and arbitrarily large chro- matic number. Therefore, it is possible to evaluate k3(n, δ) as well as identify the extremal graphs for n/3 ≤ δ ≤ n/2. Also, it might be true that kreg3 (n, δ) = 0 for all n and δ < n/3. From the theorem of Andra´sfai, Erdo˝s and So´s [3], we know that for r ≥ 4, there also exists n and δ < (1−1/(r−1))n such that kregr (n, δ) > 0, but kr(n, δ) = 0. It is easy to see that such n is not divisible by r − 1. The construction of Greg(k, l) can be easily extended for the case (r − 1)|δ and n ≡ 1 (mod r − 1). Moreover, we believe that kregr (n, δ) is of order n r−1. 18 Chapter 3 Cliques in graphs with bounded minimum degree Recall that kr(G) is the number of r-cliques in a graph G. Define kr(n, δ) to be the minimum number of r-cliques in graphs of order n with minimum degree δ. In the next section, we give an explicit construction of a family of graphs G(n, β), which we believe are the extremal graphs for kr(n, (1−β)n). In Section 3.3, we are going to prove that the conjectured value of k3(n, δ) is correct for n/2 < δ ≤ 2n/3. Theorem 3. Let 1/3 ≤ β < 1/2. Suppose G is a graph of order n with minimum degree (1− β)n. Then k3(G) ≥ (1− 2β)βnk2(G) ≥ g3(β)n3. Furthermore, equality holds if and only if (n, β) is feasible and G is a member of G(n, β). The definitions of the term feasible and the family G(n, β) are given in Sec- tion 3.1 below. 3.1 Conjectured extremal graphs and kr(n, δ) Recall that fr(n, e) is the minimum number of r-cliques in graphs of order n and e edges. In Chapter 1, we observed that the structure of the conjectured extremal 19 Chapter 3. Cliques in graphs graphs for fr(n, e) depends on p, where (1− 1/p)n2/2 < e ≤ (1− 1/(p+1))n2/2. We believe that a similar result holds for kr(n, δ) as well. Let δ = (1− β)n with 0 < β ≤ 1 and p = dβ−1e − 1. Hence, β and βn are assumed to be a rational and an integer respectively. Note that p is defined so that by Tura´n’s Theorem kr(n, (1− β)n) > 0 for all n (such that βn is an integer) if and only if r ≤ p+ 1. Since the case β = 1 implies the trivial case δ = 0, we may assume that 0 < β < 1. Furthermore, we consider the cases 1/(p + 1) ≤ β < 1/p separately for positive integers p. Hence, the condition p = 2 is equivalent to 1/3 ≤ β < 1/2, that is, n/2 < δ ≤ 2n/3. Now, we give an upper bound on kr(n, δ) by construction. Let n and (1−β)n be positive integers not both odd with 0 < β < 1. Let p = dβ−1e − 1. Consider a graph G = (V,E) with the following properties. There is a partition of V into V0, V1, . . . , Vp−1 with |V0| = (1− (p− 1)β)n and |Vi| = βn for 1 ≤ i ≤ p− 1. For 0 ≤ i < j ≤ p−1, G[Vi, Vj] is a complete bipartite graph. For 1 ≤ j ≤ p−1, G[Vj] is empty and G[V0] is a (1−pβ)n-regular graph such that the number of triangles in G[V0] is minimal over all (1 − pβ)n-regular graphs of order (1 − (p − 1)β)n. We define G(n, β) to be the family of graphs, which are obtainable by the above construction. Observe that G(n, β) is only defined if n and (1− β)n are not both odd. Thus, whenever we mention G(n, β), we automatically assume that n and (1− β)n are not both odd. We say (n, β) is feasible if G[V0] is triangle-free. Note that G[V0] is regular of degree (1− pβ)n ≤ (1− (p− 1)β)n/2 = |V0|/2. Thus, if |V0| is even, then G[V0] is triangle-free. Therefore, for a given β, there exist infinitely many choices of n such that (n, β) is a feasible pair. If (n, β) is not a feasible pair, then |V0| is odd. Notice that k3(G[V0]) ≤ k3(G′) ≤ n2/16, where G′ ∈ Greg(k, l) (see Section 2.2) |V0| = 4k + 2l + 1 and (1− pβ)n ≤ 2k. Thus, k3(G[V0]) = O(n2). By our construction, it is easy to see that every G ∈ G(n, β) is (1 − β)n- regular. In particular, for positive integers r ≥ 3, the number of r-cliques in G is exactly kr(G) =gr(β)n r + ( p− 1 r − 3 ) (1− pβ)r−3nr−3k3(G[V0]), (3.1) 20 3.1 Conjectured extremal graphs and kr(n, δ) where, gr(β) = ( p− 1 r ) βr + ( p− 1 r − 1 ) (1− (p− 1)β)βr−1 + 1 2 ( p− 1 r − 2 ) (1− pβ)(1− (p− 1)β)βr−2 with ( x y ) defined to be 0 if x < y or y < 0. Since k3(G[V0]) = O(n 2), the term with k3(G[V0]) in (3.1) is of order at most n r−1. Therefore, this term only contributes o(1) in terms of density of r-cliques. In fact, most of the time, we consider the case when (n, β) is feasible, i.e. k3(G[V0]) = 0. In Chapter 8 (Section 8.2), we discuss the case when (n, β) is not feasible including the case when neither n nor (1− β)n is even. If β = 1/(p + 1), then (p + 1)|n and G(n, 1/(p + 1)) = {Tp+1(n)}. Also, kr(Tp+1(n)) = gr(n, 1/(p + 1))n r ≥ kr(n, (1 − 1/(p + 1))n). Bolloba´s [5] proved that if e = (1−1/(p+1))n2/2 and (p+1)|n, then fr(n, e) = kr(Tp+1(n)). Moreover, Tp+1(n) is the only graph of order n with e edges and fr(n, e) r-cliques. Hence, kr(Tp+1(n)) ≥ kr ( n, ( 1− 1 p+ 1 ) n ) ≥ fr ( n, ( 1− 1 p+ 1 ) n2 2 ) = kr(Tp+1(n)), so kr(n, (1−1/(p+1))n) = kr(Tp+1(n)) = gr(n, 1/(p+1))nr. Moreover, G(n, 1/(p+ 1)) is the extremal family. We conjecture that if (n, β) is feasible then G(n, β) is the extremal family for kr(n, (1− β)n). Conjecture 3.1.1. Let 0 < β < 1 and p = dβ−1e − 1. Let n and βn be positive integers. Then kr(n, (1− β)n) ≥ gr(β)nr for positive integers r. Moreover, for 3 ≤ r ≤ p + 1 equality holds if and only if (n, β) is feasible and the extremal graphs are members of G(n, β). By our previous observation, the conjecture is true for the following three cases: p = 1, r > p+1 and β = 1/(p+1). Hence, we consider the situation when 3 ≤ r ≤ p + 1 and β /∈ {0, 1, 1/2, 1/3, . . . }. In Section 3.3, we prove Theorem 3, 21 Chapter 3. Cliques in graphs so Conjecture 3.1.1 is true for p = 2, that is n/2 < δ ≤ 2n/3. Chapters 4-7 are devoted to proving the conjecture for p ≥ 3. 3.2 Key observation We look at the structure of the extremal graphs G(n, β). Recall that G[Vi, Vj] is complete bipartite for i 6= j and G[V0] is (1 − pβ)-regular. Figure 3.2 illusrates the structure of G(n, β) for 1/5 ≤ β < 1/4, that is p = 4. It is natural to see that there are three types of edges e according to the number of vertices of e in V0. However, if we consider d(e) the number of triangles containing e, then there are only two types. To be precise d(e) = { (1− 2β)n if |V (T ) ∩ V0| = 0, 1 and (p− 1)βn if |V (T ) ∩ V0| = 2, (3.2) for e ∈ E(G) and p = dβ−1e − 1. This simple observation plays an important role. 3.3 Proof of Theorem 3 In this section, 1/3 ≤ β < 1/2 and p = 2, so n/2 < δ ≤ 2n/3. Note that the only non-trivial case of kr(n, δ) is when r = 3, that is evaluating the minimum number of triangles. Let G be a graph of order n with n/2 < δ(G) = (1 − β)n ≤ 2n/3. Figure 3.1: a typical member of G(n, β) for p = 4 22 3.3 Proof of Theorem 3 Our aim is to show that k3(G) ≥ (1− 2β)βnk2(G) ≥ g3(β)n3. Since G has at least (1− β)n2/2 edges, the second inequality is true. Recall that for an edge e, d(e) is the number of triangles containing e. We write D(e) = d(e)/n. Clearly, ∑ D(e) = 3k3(G)/n with sum over E(G), where kr(G) is the number of r-cliques in G. In addition, D(e) ≥ 1−2β for each edge e, because each vertex in G misses at most βn vertices. Since β < 1/2, D(e) > 0. Thus, every edge is contained in a triangle. Let T be a triangle in G. Similarly, define d(T ) to be the number of 4-cliques containing T and write D(T ) = d(T )/n. We claim that ∑ e∈E(T ) D(e) ≥ 2− 3β +D(T ). (3.3) Let ni be the number vertices in G with exactly i neighbours in T for i = 0, 1, 2, 3. Clearly, n = n0+n1+n2+n3. By counting the number of edges incident with T , we obtain 3(1− β)n ≤ ∑ v∈V (T ) d(v) = 3n3 + 2n2 + n1 ≤ 2n3 + n2 + n. (3.4) On the other hand, n3 = d(T ) and n2 + 3n3 = ∑ e∈E(G) d(e). Hence, (3.3) holds. Notice that equality holds in (3.3) only if d(v) = (1− β)n for all v ∈ T . Next, by summing (3.3) over all triangles T in G, we obtain n ∑ e∈E(G) D(e)2 = ∑ T ∑ e∈E(T ) D(e) ≥ (2− 3β)k3 + 4k4/n ≥ (2− 3β)k3. (3.5) We would like to bound ∑ D(e)2 above in terms of ∑ D(e), which is equal to 3k3(G)/n. It is well known (or by Proposition 3.3.1 stated below) that ∑ D(e)2 is maximal if D(e) takes only two values. Proposition 3.3.1. Let A be a finite set. Suppose f, g : A → R with f(a) ≤ M 23 Chapter 3. Cliques in graphs and g(a) ≥ m for all a ∈ A. Then∑ a∈A f(a)g(a) ≤ m ∑ a∈A f(a) +M ∑ a∈A g(a)−mM |A|, with equality if and only if for each a ∈ A, f(a) =M or g(a) = m. Proof. Observe that ∑ a∈A(M − f(a))(g(a)−m) ≥ 0. From (3.2), for G ∈ G(n, β) with (n, β) feasible, either D(e) = 1 − 2β or D(e) = β for each edge e. Suppose first that D(e) ≤ β for all edges e. Recall that D(e) ≥ 1 − 2β for all edge e. By Proposition 3.3.1 taking A = E(G), f = g = D, m = 1− 2β and M = β, we have∑ e∈E(G) D(e)2 ≤ (1− β) ∑ e∈E(G) D(e)− (1− 2β)βk2 = 3(1− β)k3/n− (1− 2β)βk2 as k2 = e(G). Substitute the above inequality into (3.5) and rearrange; we get k3(G) ≥ (1− 2β)βk2(G)n ≥ (1− β)(1− 2β)βn3/2 = g3(β)n3 as required. Thus, we may assume that there exists an edge e withD(e) > β. For an edge e, defineD−(e) = min{D(e), β} andD+(e) = D(e)−D−(e). Notice that ∑ D(e)2 =∑ D(e)(D+(e) + D−(e)) = ∑ D(e)D+(e) + ∑ D(e)D−(e). By the definition, D−(e) is at most β. Thus, we can bound ∑ D(e)D−(e) using Proposition 3.3.1 taking A = E(G), f = D−, g = D, m = 1− 2β and M = β. Hence, n ∑ e∈E(G) D(e)D−(e) ≤ (1− 2β)n ∑ e∈E(G) D−(e) + βn ∑ e∈E(G) D(e)− (1− 2β)βnk2 ≤ (1− β)n ∑ e∈E(G) D(e)− (1− 2β)βnk2 (3.6) n ∑ e∈E(G) D(e)D−(e) ≤ 3(1− β)k3 − (1− 2β)βnk2. (3.7) However, there is no non-trivial upper bound on ∑ D(e)D+(e). Fortunately, we 24 3.3 Proof of Theorem 3 can avoid the term ∑ D(e)D+(e) by the following trick. We claim that∑ e∈E(T ) D−(e) ≥ 2− 3β (3.8) for every triangle T . If D(e) = D−(e) for each edge e in T , then (3.8) holds by (3.3). Otherwise, there exists e0 ∈ E(T ) such that D(e0) 6= D−(e0). This means that D−(e0) = β, so ∑ D−(e) ≥ β + 2(1 − 2β) = 2 − 3β. Hence, (3.8) holds for every triangle T . Next, we sum (3.8) over all triangles. We obtain an inequality very similar to (3.5) but with the left hand side equal to n ∑ e∈E(G)D(e)D−(e). After substitution of (3.7) and rearrangement, we have k3(G) ≥ (1− 2β)βk2(G)n ≥ g3(β)n3. Thus, we have proved the inequality in Theorem 3. Now suppose equality holds, i.e. k3 = (1−2β)βk2n. This means that equality holds in (3.6), so (since β < 1/2)D(e) = D−(e) for all e ∈ E(G). Because equality holds in (3.8), ∑ D(e) = 2− 3β. Hence, D(T ) = 0 for every triangle T by (3.3). In particular, by the remark following (3.3), G is (1− β)n-regular, because every vertex lies in a triangle as D(e) > 0 for all edges e. Moreover, G is K4-free as D(T ) = 0 for every triangle T . Since equality holds in Proposition 3.3.1, either D(e) = 1− 2β or D(e) = β for each edge e. Recall that equality holds for (3.3), so every triangle T contains exactly one edge e1 with D(e1) = β and two edges, e2 and e3, with D(e2) = D(e3) = 1 − β. Pick an edge e with D(e) = β and let W be the set of common neighbours of the end vertices of e, so |W | = βn. Clearly W is an independent set, otherwise G contains a K4. For each w ∈ W , d(w) = (1− β)n implies N(w) = V (G)\W . Therefore, G[V (G)\W ] is (1− 2β)n- regular. If there is a triangle T in G[V (G)\W ], then T ∪w forms a K4 for w ∈ W . This contradicts the assumption that G is K4-free, so G[V (G)\W ] is triangle-free. Hence, G is a member of G(n, β) and (n, β) is feasible. Therefore, we have now proved Conjecture 3.1.1 for the case p = 2. 25 Chapter 3. Cliques in graphs 26 Chapter 4 Degrees of cliques and Kp+2-free graphs We define the degree for a general clique in the coming section. Also, we study some of its basic properties. By mimicking the proof of Theorem 3, we show that the conjecture is true for all Kp+2-free graphs in Section 4.2 Theorem 4. Let 0 < β < 1 and p = dβ−1e − 1. Suppose G is a Kp+2-free graph of order n with minimum degree (1− β)n. Then ks(G) gs(β)ns ≥ kt(G) gt(β)nt (4.1) holds for 2 ≤ t < s ≤ p + 1. Moreover, the following three statements are equivalent: (i) Equality holds for some 2 ≤ t < s ≤ p+ 1. (ii) Equality holds for all 2 ≤ t < s ≤ p+ 1. (iii) The pair (n, β) is feasible and G is a member of G(n, β). Notice that the theorem implies Theorem 1.2.3, that is, Conjecture 3.1.1 for Kp+2-free graphs and all β ∈ (0, 1), because k2(G) ≥ (1− β)n2/2 = g2(β). 27 Chapter 4. Degrees of cliques and Kp+2-free graphs 4.1 Degree of a clique Let G ∈ G(n, β) with (n, β) feasible. Let T be a t-clique in G. It is easy to see that there are three types of cliques according to |T ∩V0|. However, if we consider d(T ), the number of (t + 1)-cliques containing T , then there are only two types. To be precise d(T ) = { (1− tβ)n if |V (T ) ∩ V0| = 0, 1 and (p+ 1− t)βn if |V (T ) ∩ V0| = 2, for T ∈ Kt(G), 2 ≤ t ≤ p + 1 and p = dβ−1e − 1. This observation helps us to define the correct notion of degree for a general clique. For a graph G and a vertex set U ⊂ V (G), we write Kt(U) to be the set of t-cliques in G[U ]. Let kt(U) = |Kt(U)|. If U = V (G), we simply write Kt and kt. Define the degree d(T ) of a t-clique T to be the number of (t+1)-cliques containing T . In other words, d(T ) = |{S ∈ Kt+1 : T ⊂ S}|. If t = 1, then d(v) coincides with the ordinary definition of the degree for a vertex v. If t = 2, then d(uv) is the number of common neighours of the end vertices of the edge uv, that is the codegree of u and v. The number d(uv) is known as the book number in the literature. Clearly, n ∑ T∈Kt d(T ) = (t + 1)kt+1 for t ≥ 1. For convenience, we write D(T ) to denote d(T )/n. Next, define the functions D+ and D− as follows. For a graph G with δ(G) = (1− β)n and 1 ≤ t ≤ p+ 1 (where p = dβ−1e − 1), D−(T ) = min{D(T ), (p+ 1− t)β}, and D+(T ) = D(T )−D−(T ) = max{0, D(T )− (p+ 1− t)β} for T ∈ Kt. We say that a clique T is heavy if D+(T ) > 0. Let K+t (U) denote the set of heavy t-cliques in G[U ] and k+t (U) = |K+t (U)|. A graph G is heavy- free if G does not contain any heavy cliques. Note that both D− and D+ are functions depending on β i.e. δ(G). Hence, the notation of a heavy clique is defined only if the base graph is known. Now, we study some basic properties of D(T ) and D−(T ). Lemma 4.1.1. Let 0 < β < 1 and p = dβ−1e − 1. Suppose G is a graph of 28 4.1 Degree of a clique order n with minimum degree (1 − β)n. Suppose S ∈ Ks and T ∈ Kt(S) for 1 ≤ t < s. Then (i) D(S) ≥ 1− sβ, (ii) D(S) ≥ D(T )− (s− t)β, (iii) D+(T ) ≤ D+(S) ≤ D+(T ) + (s− t)β for s ≤ p+ 1, (iv) if D+(S) > 0 and s ≤ p+ 1, then D−(S) = (p− s+ 1)β. Moreover, G is Kp+2-free if and only if G is heavy-free. Proof. For each v ∈ S, there are at most βn vertices not joined to v. Hence, D(S) ≥ 1 − sβ, so (i) is true. Similarly, consider the vertices in S\T , so (ii) is also true. If s ≤ p+ 1 and D+(T ) > 0, then by (ii) we have D+(S) + (p− s+ 1)β ≥D(S) ≥D(T )− (s− t)β =D+(T ) + (p− t+ 1)β − (s− t)β, so the left inequality of (iii) is true. Since D(S) ≤ D(T ), the right inequality of (iii) is also true by the definition of D+(S) and D+(T ). Finally, (iv) is a straightforward consequence of the definition of D+(S). Notice that D(U) = D+(U) for U ∈ Kp+1. Hence, by (iii), G is Kp+2-free if and only if G is heavy- free. Notice that (iii) implies that if a t-subclique T of a clique S is heavy, so is S. However, the converse is false even if all t-subcliques are not heavy. For example, consider an isolated clique of size (p− t + 1)βn + t. Then, D(T ) = (p− t + 1)β for every t-sunclique T . However, for an s-clique S with t < s < p + 1, D(S) = (p− t+ 1)β − (s− t)/n, so S is heavy provided n is not too small. In the next lemma, we prove a generalisation of (3.3). 29 Chapter 4. Degrees of cliques and Kp+2-free graphs Lemma 4.1.2. Let 0 < β < 1. Let s and t be integers with 2 ≤ t < s. Suppose G is a graph of order n with minimum degree (1− β)n. Then ∑ T∈Kt(S) D(T ) ≥ (1− β)s ( s− 2 t− 1 ) − (t− 1) ( s− 1 t ) + ( s− 2 t− 2 ) D(S) for S ∈ Ks. Moreover, if equality holds, then d(v) = (1− β)n for all v ∈ S. Proof. Let ni be the number of vertices with exactly i neighbours in S. The following three equations :∑ i ni = n, (4.2)∑ i ini = ∑ v∈V (S) d(v) ≥ s(1− β)n, (4.3) ∑ i ( i t ) ni = ∑ T∈Kt(S) D(T )n, (4.4) follow from a count of the number of vertices, edges and (t+1)-cliques respectively. Next, by considering (t− 1)(s−1 t ) (4.2)− (s−2 t−1 ) (4.3) + (4.4), we have ∑ T∈Kt(S) D(T )n ≥ ( (1− β)s ( s− 2 t− 1 ) − (t− 1) ( s− 1 t )) n+ ∑ 0≤i≤s xini, where xi = ( i t ) +(t−1)(s−1 t )− i(s−2 t−1 ) . Notice that xi = xi+1+ ( s−2 t−1 )−( i t−1 ) ≥ xi+1 for 0 ≤ i ≤ s− 2. For i = s− 1, we have xs−1 = ( s− 1 t ) + (t− 1) ( s− 1 t ) − (s− 1) ( s− 2 t− 1 ) = t ( s− 1 t ) − (s− 1) ( s− 2 t− 1 ) = 0. 30 4.2 Kp+2-free graphs For i = s, ns = D(S)n and xs = ( s t ) + (t− 1) ( s− 1 t ) − s ( s− 2 t− 1 ) =t ( s− 1 t ) + ( s− 1 t− 1 ) − s ( s− 2 t− 1 ) =(s− t+ 1) ( s− 1 t− 1 ) − s ( s− 2 t− 1 ) =(s− t+ 1) ( s− 2 t− 2 ) − (t− 1) ( s− 2 t− 1 ) = ( s− 2 t− 2 ) . In particular, if equality holds in the lemma, then equality holds in (4.3). This means that d(v) = (1− β)n for all v ∈ S. In fact, most of the time, we are only interested in the case when s = t + 1. Hence, we state the following corollary. Corollary 4.1.3. Let 0 < β < 1. Suppose G is a graph or order n with minimum degree (1− β)n. Then∑ T∈Kt(S) D(T ) ≥ 2− (t+ 1)β + (t− 1)D(S) for S ∈ Kt+1 and integer t ≥ 2. Moreover, if equality holds, then d(v) = (1− β)n for all v ∈ S. ¤ 4.2 Kp+2-free graphs Here, all graphs are assumed to be Kp+2-free. Lemma 4.1.1 implies that these graphs are also heavy-free. This means that D+(T ) = 0 and D(T ) ≤ (p+1− t)β for all T ∈ Kt. We would also like to point out that the family of Kp+2-free graphs is a natural family to study in its own right. Let G be a graph of order n with minimum degree (1 − β)n. Note that G contains a Kp+1 by Tura´n’s theorem, because e(G) = δ(G)n/2 = (1 − β)n2/2 > ex(n,Kp+1) as 1/(p + 1) ≤ β < 31 Chapter 4. Degrees of cliques and Kp+2-free graphs 1/p. Hence, Kp+2-free graphs are those graphs with the minimum possible clique number given δ(G). Following the same approach as in proof of Theorem 3, we are going to first sum Corollary 4.1.3 over S ∈ Kt+1 and then apply Proposition 3.3.1. We obtain the following lemma. Lemma 4.2.1. Let 0 < β < 1 and p = dβ−1e − 1. Suppose G is a Kp+2-free graph of order n with minimum degree (1− β)n. Then kt+1(G) ≥(1− tβ)(p− t+ 1)βnkt(G) + (t− 1)(t+ 2)kt+2(G)/n t− 1 + (p− 2t+ 2)(t+ 1)β for 2 ≤ t ≤ p. Moreover, if equality holds, then G is (1 − β)n-regular and, for each T ∈ Kt, either D(T ) = 1− tβ or D(T ) = (p− t+ 1)β. Proof. Summing Corollary 4.1.3 over S ∈ Kt+1 gives (2− (t+ 1)β)kt+1(G) + (t− 1) ∑ S∈Kt+1 D(S) ≤ ∑ S∈Kt+1 ∑ T∈Kt(S) D(T ) = n ∑ T∈Kt D(T )2. (4.5) Recall that G is heavy-free, so 1 − tβ ≤ D(T ) ≤ (p − t + 1)β, where the lower bound is proved in Lemma 4.1.1 (i). By Proposition 3.3.1 taking A = Kt, f = D, g = D, m = 1− tβ and M = (p− t+ 1)β, the right hand side of (4.5) is at most (1− tβ)n ∑ T∈Kt(S) D(T ) + (p− t+ 1)βn ∑ T∈Kt(S) D(T ) − (1− tβ)(p− t+ 1)βnkt =(1 + (p− 2t+ 1)β)n ∑ T∈Kt(S) D(T )− (1− tβ)(p− t+ 1)βnkt =(1 + (p− 2t+ 1)β)(t+ 1)kt+1 − (1− tβ)(p− t+ 1)βnkt. Note that ∑ D(S) = (t+ 2)kt+2/n. Thus, we prove the inequality in the lemma by rearranging (4.5). Suppose equality holds in the lemma, so that equality holds in Corollary 4.1.3 for every (t+1)-clique S. Since D(T ) ≥ (1− tβ) > 0 for T ∈ Kt and t = 2, . . . , p, 32 4.2 Kp+2-free graphs every vertex v is in a (t+ 1)-clique. Therefore, G is (1− β)n-regular by the case of equality in Corollary 4.1.3. In addition, we have equality in Proposition 3.3.1, so for each T ∈ Kt, either D(T ) = 1− tβ or D(T ) = (p− t+ 1)β. For a fixed β, Lemma 4.2.1 gives a linear relationship between kt, kt+1 and kt+2. Note that kp+2 = 0 and k2 ≥ (1−β)n2/2. By taking t = 2, . . . , p, we obtain p− 1 linear relationships with p − 1 unknowns variables, k3, . . . , kp+1. Therefore, we can solve this set of equations. To keep our calculations simple, we are going to establish a few relationships between gt(β) and gt+1(β) in the next lemma. Lemma 4.2.2. Let 0 < β < 1 and p = dβ−1e − 1. Let t be an integer with 2 ≤ t ≤ p. Then (t+ 1)gt+1(β) =(1− tβ)gt(β) + 1 2 ( p− 1 t− 2 ) ((p+ 1)β − 1)(1− (p− 1)β)(1− pβ)βt−2, (4.6) gt+1(β) = (1− tβ)(p− t+ 1)βgt(β) + (t− 1)(t+ 2)gt+2(β) t− 1 + (t+ 1)(p− 2t+ 2)β . (4.7) Moreover gp(β) gp+1(β) = 1 β ( 1 + βgp−1(β′) (1− β)gp(β′) ) , (4.8) where β′ = β/(1− β). Proof. We fix β (and p) and write gt to denote gt(β). Pick n such that (n, β) is feasible and let G ∈ G(n, β) with partition classes V0, V1, . . . , Vp−1 as described in Section 3.1. For T ∈ Kt, D(T ) = 1 − tβ or D(T ) = (p − t + 1)β. Since D(T ) = (p− t+ 1)β if and only if |V (T ) ∩ V0| = 2, there are exactly 1 2 ( p− 1 t− 2 ) (1− (p− 1)β)(1− pβ)βt−2nt t-cliques T with D(T ) = (p− t+ 1)β. We have (t+ 1)gt+1n t+1 = (t+ 1)kt+1 = n ∑ T∈Kt D(T ). 33 Chapter 4. Degrees of cliques and Kp+2-free graphs Hence, (4.6) is true, by expanding the right hand side of the above equation. For 2 ≤ s < p, let fs and fs+1 be (4.6) with t = s and t = s + 1 respectively. Then (4.7) follows by considering (p− s+ 1)fs − (s− 1)βfs+1. Now let G′ = G\Vp−1. Notice that G′ is (1 − 2β)n-regular with (1 − β)n vertices. We observe that G′ is a member of G(n′, β′), where n′ = (1 − β)n. Observe that dβ′−1e − 1 = p − 1, so 1/p ≤ β′ < 1/(p − 1). Recall that kt(G) = gt(β)n t for all 2 ≤ t ≤ p, so kp+1(G)gp(β) = kp(G)gp+1(β)n. Simi- larly, kp(G ′)gp−1(β′) = kp−1(G′)gp(β′)n. By considering Kp(G) and Kp+1(G), we obtain the following two equations : kp+1(G) = βnkp(G ′), (4.9) kp(G) = βnkp−1(G′) + kp(G′) = βn gp−1(β′)kp(G′) n′gp(β′) + kp(G ′) = ( 1 + βgp−1(β′) (1− β)gp(β′) ) kp(G ′). (4.10) By substituting (4.9) and (4.10) into kp(G)n/kp+1(G) = gp(β)/gp+1(β), we ob- tain (4.8). The proof is complete. We are now ready to prove Theorem 4. Proof of Theorem 4. Fix β and write gt to denote gt(β). First, we are going to prove (4.1). In fact, it is sufficient to prove the case when s = t+ 1. We proceed by induction on t from above. For t = p, Lemma 4.2.1 gives (p− 1− (p− 2)(p+ 1)β)kp+1 ≥ (1− pβ)βnkp. Since gp+2 = 0, (4.7) implies kp+1/gp+1n p+1 ≥ kp/gpnp. Hence, (4.1) is true for t = p. For t < p, Lemma 4.2.1 shows that (t− 1 + (t+ 1)(p− 2t+ 2)β)kt+1 ≥ (1− tβ)(p+ 1− t)βnkt + (t− 1)(t+ 2)kt+2/n 34 4.2 Kp+2-free graphs and by the induction hypothesis, ≥ (1− tβ)(p+ 1− t)βnkt + (t− 1)(t+ 2)gt+2kt+1/gt+1. (4.11) Thus, (4.1) follows from (4.7). It is clear that (iii) implies both (i) and (ii) by the construction of G(n, β) and the feasibility of (n, β). Suppose (i) holds, so equality holds in (4.1) for t = t0 and s = s0 with t0 < s0. We claim that equality must also hold for t = p and s = p+1. Suppose the claim is false and equality holds for t = t0 and s = s0, where s0 is maximal. Since equality holds for t = t0, by (4.1), equality holds for t = t0, . . . , s0− 1 with s = s0. We may assume that t = s0− 1 and s0 6= p+1 and ks0+1/gs0+1n > ks0/gs0 . However, this would imply a strictly inequality in (4.11) contradicting the fact that equality holds for s = s0 and t = s0 − 1. Thus, the proof of the claim is complete, that is, if (i) holds then equality holds in (4.1) for t = p and s = p+ 1. Therefore, in order to prove that (i) implies (iii), it is sufficient to show that if kp+1/gp+1n p+1 = kp/gpn p, then (n, β) is feasible and G is a member of G(n, β). We proceed by induction on p. It is true for p = 2 by Theorem 3, so we may assume p ≥ 3. Since equality holds in (4.1), we have equality in Lemma 4.2.1 and Corollary 4.1.3. Thus, G is (1 − β)n-regular. In addition, for each T ∈ Kp, either D(T ) = 1 − pβ or D(T ) = β. Moreover, Corollary 4.1.3 implies that∑ T∈Kp(S)D(T ) ≥ 2− (p+ 1)β for S ∈ Kp+1. Thus, there exists T ∈ Kp(S) with D(T ) = β. Pick T ∈ Kp with D(T ) = β and let W = ⋂{N(v) : v ∈ V (S)}, so |W | = β. Since G is Kp+2-free, W is a set of independent vertices. For each w ∈W , d(w) = (1−β)n, soN(w) = V (G)\W . Thus, the graphG′ = G[V (G)\W ] is (1− β′)n′-regular, where n′ = (1− β)n, β′n′ = (1− 2β)n and β′ = β/(1− β). Note that dβ′−1e − 1 = p − 1. Since G is Kp+2-free, G′ is Kp+1-free. Also, kp+1(G) = βnkp(G ′) and kp(G) =βnkp−1(G′) + kp(G′) by (4.1) ≤ β gp−1(β ′)kp(G′) gp(β′) + kp(G ′) = ( 1 + β gp−1(β′) (1− β)gp(β′) ) kp(G ′) by (4.8) = gp(β)β gp+1(β) kp(G ′). (4.12) 35 Chapter 4. Degrees of cliques and Kp+2-free graphs Hence, gp(β)βnkp(G ′) = gp(β)kp+1(G) by (4.1) = gp+1(β)nkp(G) by (4.12) ≤ gp(β)βnkp(G′). Therefore, we have kp(G ′)/gp(β′)n′p = kp−1(G′)/gp−1(β′)n′p−1. By the induction hypothesis, G′ ∈ G(n′, β′), which implies G ∈ G(n, β). This completes the proof of the theorem. 36 Chapter 5 Heavy cliques In the previous chapter, we have proved that Conjecture 3.1.1 holds for Kp+2-free graphs. By Lemma 4.1.1, Kp+2-free graphs do not contain any heavy cliques. Hence, in order to prove Conjecture 3.1.1 completely, it remains to tackle heavy cliques. In the proof of Theorem 3, we apply D− and (3.8) to handle heavy cliques. In the following section, we look at the natural generalisation of (3.8). Unfortunately, this natural generalisation is not sufficient to prove the Conjec- ture 3.1.1 even for p = 3. By a detailed analysis of heavy cliques, we prove that Conjecture 3.1.1 is true for p = 3. Theorem 5. Let 1/4 ≤ β < 1/3. Let s and t be integers with 2 ≤ t < s ≤ 4. Suppose G is a graph of order n with minimum degree (1− β)n. Then ks(G) gs(β)ns ≥ kt(G) gt(β)nt . Moreover, the following three statements are equivalent: (i) Equality holds for some 2 ≤ t < s ≤ 4. (ii) Equality holds for all 2 ≤ t < s ≤ 4. (iii) The pair (n, β) is feasible and G is a member of G(n, β). 37 Chapter 5. Heavy cliques 5.1 Basic inequalities for heavy cliques When p = 2 (see Section 3.3), we tackled the heavy cliques by considering (3.8), that is, ∑ e∈E(T )D−(e) ≥ 2 − 3β for T ∈ K3. The contributions of the heavy cliques are completely removed when we sum (3.8) over all triangles T . Therefore, we need to generalise (3.8) for a general clique S and p ≥ 3. Clearly the left hand side of the desired inequality would be ∑ D−(T ) with sum over subcliques T in S. Notice that for p = 2, D− is the zero function on triangles. Hence, (3.8) is equivalent to ∑ D−(e) ≥ 2−3β+D−(T ). Thus, a natural generalisation of (3.8) is to replace the function D with D− in Lemma 4.1.2. Lemma 5.1.1. Let 0 < β < 1 and p = dβ−1e − 1. Let s and t be integers with 2 ≤ t < s ≤ p+1. Suppose G is a graph of order n with minimum degree (1−β)n. Then ∑ T∈Kt(S) D−(T ) ≥ (1− β)s ( s− 2 t− 1 ) − (t− 1) ( s− 1 t ) + ( s− 2 t− 2 ) D−(S). for S ∈ Ks. Proof. Since D+(S) ≥ D+(T ) for every T ∈ Kt(S) by Lemma 4.1.1 (iii), there is nothing to prove by Lemma 4.1.2 if there are at most ( s−2 t−2 ) heavy t-cliques in S. Now suppose there are more than ( s−2 t−2 ) heavy t-cliques in S. In particular, S contains a heavy t-clique, so S is itself heavy with D−(S) = (p + 1 − s)β by Lemma 4.1.1 (iv). Thus, the right hand side of the inequality is ( s t ) (1 − tβ) + ( s−2 t−2 ) ((p + 1)β − 1). By Lemma 4.1.1 (i) we have that D−(T ) ≥ (1 − tβ) for T ∈ Kt(S). Furthermore, by Lemma 4.1.1 (iv) D−(T ) = (p − t + 1)β if T is heavy, so summing D−(T ) over T ∈ Kt(S) gives ∑ T∈Kt(S) D−(T ) ≥ k+t (S)(p− t+ 1)β + (( s t ) − k+t (S) ) (1− tβ) = ( s t ) (1− tβ) + k+t (S)((p+ 1)β − 1). This completes the proof of the lemma. The following notation will help us to keep the calculations simple. For 2 ≤ 38 5.1 Basic inequalities for heavy cliques t ≤ p, we define the function D˜ : Kt+1 → R such that D˜(S) = ∑ T∈Kt(S) D−(T )− ( 2− (t+ 1)β + (t− 1)D−(S) ) for S ∈ Kt+1. Hence, Lemma 5.1.1 has the following corollary for s = t+ 1. Corollary 5.1.2. Let 0 < β < 1 and p = dβ−1e − 1. Let t be integer with 2 ≤ t ≤ p. Suppose G is a graph of order n with minimum degree (1 − β)n. Then D˜(S) ≥ 0 for S ∈ Kt+1. ¤ Next, we sum D˜(S) over S ∈ Kt+1 and bound it from above. The proof is an application of Proposition 3.3.1, which is similar to the proof of Lemma 4.2.1. Lemma 5.1.3. Let 0 < β < 1 and p = dβ−1e − 1. Let t be an integer with 2 ≤ t ≤ p. Suppose G is a graph of order n with minimum degree (1−β)n. Then∑ S∈Kt+1 D˜(S) ≤ (t− 1 + (p− 2t+ 2)(t+ 1)β)kt+1 + (t− 1) ∑ S∈Kt+1 D+(S) −(1− tβ)(p− t+ 1)βnkt − (t− 1)(t+ 2)kt+2 n − (1− tβ)n ∑ T∈Kt D+(T ). Moreover, equality holds if and only if for each T ∈ Kt, either D−(T ) = 1 − tβ or D−(T ) = (p− t+ 1)β. Proof. Notice that the sum D˜(S) over S ∈ Kt+1 is equal to∑ S∈Kt+1 ∑ T∈Kt(S) D−(T )− (2− (t+ 1)β)kt+1 − (t− 1) ∑ S∈Kt+1 D−(S). (5.1) We look at each term separately. Recall that D = D− +D+, so∑ D−(S) = ∑ D(S)− ∑ D+(S) = (t+ 2) kt+2 n − ∑ D+(S). By interchanging the order of summations, ∑∑ D−(T ) = n ∑ D−(T )D(T ) with sum over T ∈ Kt. Hence, by Proposition 3.3.1 taking A = Kt, f = D−, g = D, 39 Chapter 5. Heavy cliques m = 1− tβ and M = (p− t+ 1)β, we obtain n ∑ T∈Kt D−(T )D(T ) ≤(1− tβ)n ∑ T∈Kt D−(T ) + (p− t+ 1)βn ∑ T∈Kt D(T )− (1− tβ)(p− t+ 1)βnkt =(1 + (p− 2t+ 1)β)n ∑ T∈Kt D(T )− (1− tβ)n ∑ T∈Kt D+(T ) − (1− tβ)(p− t+ 1)βnkt =(1 + (p− 2t+ 1)β)(t+ 1)kt+1 − (1− tβ)n ∑ T∈Kt D+(T ) − (1− tβ)(p− t+ 1)βnkt. Hence, substituting these identities back into (5.1), we obtain the desired inequal- ity in the lemma. By Proposition 3.3.1, equality holds if and only if for each T ∈ Kt, either D(T ) = 1− tβ or D−(T ) = (p− t+ 1)β. By Corollary 5.1.2, ∑ S∈Kt+1 D˜(S) ≥ 0. Together with Lemma 5.1.3, we obtain that for 2 ≤ t ≤ p+ 1, ( t− 1 + (p− 2t+ 2)(t+ 1)β)kt+1 + (t− 1) ∑ S∈Kt+1 D+(S) ≥ (1− tβ)(p− t+ 1)βnkt + (t− 1)(t+ 2)kt+2 n + (1− tβ)n ∑ T∈Kt D+(T ). (5.2) In fact, the above inequality implies Lemma 4.2.1 as D+ is the zero function for Kp+2-free graphs. Following the proof of Theorem 4, our next task is to solve for k3, . . . , kp+1. In the next section, we look at the case when p = 3. However, we are going to see that (5.2) is not sufficient to prove Conjecture 3.1.1. 40 5.2 kr(n, δ) for 2n/3 < δ ≤ 3n/4 5.2 kr(n, δ) for 2n/3 < δ ≤ 3n/4 From now on, p is assumed to be 3, so 1/4 ≤ β < 1/3 (that is 2n/3 < δ ≤ 3n/4). Explicitly, (5.2) becomes (1 + 3β)k3 + ∑ T∈K3 D+(T ) ≥ 2(1− 2β)βnk2 + 4k4/n+ (1− 2β)n ∑ e∈K2 D+(e), (5.3) (2− 4β)k4 + 2 ∑ S∈K4 D+(S) ≥ (1− 3β)βnk3 + 10k5/n+ (1− 3β)n ∑ T∈K3 D+(T ), (5.4) for t = 2 and t = 3 respectively. Since D− is a zero function on 4-cliques,∑ S∈K4 D+(S) = ∑ S∈K4 D(S) = ∑ S∈K4 D(S) = 5k5/n. Hence, the terms with k5 and ∑ D+(S) cancel in (5.4). Since (1 − 2β) > 0, we may ignore the term with ∑ D+(e) in (5.3). Substituting (5.4) into (5.3), we get (1 + 3β)k3 + ∑ T∈K3 D+(T ) ≥ 2(1− 2β)βnk2 + 4 (2− 4β)n ( (1− 3β)βnk3 + (1− 3β)n ∑ T∈K3 D+(T ) ) (1− β)k3 ≥ 2(1− 2β)2βnk2 − (4β − 1) ∑ T∈K3 D+(T ). (5.5) Recall that g2(β) = (1−β)/2 and g3(β) = (1− 2β)2β. If (4β− 1) ≥ 0, then (5.5) would imply k3(G) ≥ 2(1− 2β)2βnk2(G)/(1− β) ≥ (1− 2β)2βn3 = g3(β)n3, which prove Conjecture 3.1.1 for 1/4 ≤ β < 1/3 and r = 3. However, (4β−1) ≥ 0 only if β = 1/4. Thus, the natural extension of (3.8) is not sufficient even for the case p = 3. Therefore, we are going to strengthen both (5.3) and (5.4). The methods used to strengthen (5.3) and (5.4) are different. Thus, we will look at them separately. 41 Chapter 5. Heavy cliques 5.2.1 Strengthening (5.3) Recall that (5.3) is a consequence of Corollary 5.1.2 and Lemma 5.1.3 for t = 2. Therefore, a strengthening of Corollary 5.1.2 would lead to a strengthening of (5.3). For t = 2 and p = 3, Corollary 5.1.2 explicitly states that∑ e∈K2(T ) D−(e) ≥2− 3β +D−(T ) (5.6) for T ∈ K3. Even though we already know that the above inequality is not sufficient to prove the Conjecture 3.1.1 for p = 3, they are indeed the best pos- sible by considering G(n, β). Therefore, a strengthening of Corollary 5.1.2 must involve D+. Note that the coefficient of ∑ D+(e) term on the right hand side of (5.3) is (1− 2β) > 0. Next, observe that∑ e∈K2 D+(e)n = ∑ T∈K3 ∑ e∈K2(T ) D+(e)/D(e). Hence, in order to exploit the ∑ D+(e) term, we are going to prove D˜(T ) + (1− 2β) ∑ e∈K2(T ) D+(e)/D(e) ≥ c(4β − 1)D+(T )/(1− 2β), for some constant c > 0. Notice that for a heavy edge e, D(e) = D+(e) + 2β. Thus, D+(e)/D(e) is equivalent to D+(e)/(D+(e) + 2β) for all edges e. Suppose we have proved that the above inequality is true for c = 1. Hence, we obtain a strengthening of (5.3). It turns out that if we substitute this strength- ening of (5.3) into (5.4), we would obtain (5.5) without the ∑ D+(T ) terms on the right hand side. Thus, Conjecture 3.1.1 is true for p = 3 without need- ing to strengthen (5.4). Unfortunately, we are only able to prove it for the case c = 1− 2/(29− 75β) < 1. Lemma 5.2.1. Let 1/4 ≤ β < 1/3. Suppose G is a graph order n with minimum 42 5.2 kr(n, δ) for 2n/3 < δ ≤ 3n/4 degree (1− β)n. Let T ∈ K3. Then D˜(T ) + (1− 2β) ∑ e∈K2(T ) D+(e) D+(e) + β ≥ c(4β − 1)D+(T ) 1− 2β . (5.7) with c = 1 − 2/(29 − 75β). Moreover, equality holds only if T is not heavy and d(v) = (1− β)n for all v ∈ T . Proof. Corollary 5.1.2 gives D˜(T ) ≥ 0, so we may assume that T is heavy. In addition, Corollary 4.1.3 implies that D˜(T ) + ∑ e∈K2(T ) D+(e) ≥ D+(T ). (5.8) Since (4β − 1)/(1− 2β) < 1, we may further assume that T contains at least one heavy edge, or else (5.7) holds as (5.8) becomes D˜(T ) ≥ D+(T ). Let e0 ∈ K2(T ) with D(e0) = max{D(e) : e ∈ K2(T )}. By substituting (5.8) into (5.7), it is sufficient to show that the function f = ( 1− 1− 2β D+(e0) + 2β ) D˜(T )− ( c (4β − 1) 1− 2β − 1− 2β D+(e0) + 2β ) D+(T ) is non-negative. First consider the case when D+(T ) ≤ 1 − 3β. Lemma 4.1.1 (ii) implies D+(e0) ≤ D+(T ) ≤ 1− 3β. Hence, 1− 2β D+(e0) + 2β − c(4β − 1) 1− 2β ≥ 1− 2β 1− β − c (4β − 1) 1− 2β = (1− 3β)(56− 233β + 200β2) (1− β)(1− 2β)(29− 75β) > 0. Also, 1 − 2β ≤ 2β. Therefore, f > 0 by considering the coefficients of D˜(T ) and D(T ). Hence, we may assume D+(T ) > 1 − 3β. Since T is heavy, D−(T ) = β. Therefore, by the definition of D˜, we have D˜(T ) = ∑ D−(e)− 2(1− β). (5.9) 43 Chapter 5. Heavy cliques We split into different cases separately depending on the number of heavy edges in T . Suppose all edges are heavy. Thus, D˜(T ) = 2(4β − 1) by (5.9), because D−(e) = 2β for all edges e in T . Clearly D+(T ) = D(T ) − β ≤ 1 − β. Hence, (5.7) is true as D˜(T ) = 2(4β − 1) ≥ (4β − 1)(1− β)/(1− 2β) ≥ (4β − 1)D+(T )/(1− 2β). Thus, there exists an edge in T that is not heavy. We now show that D+(T ) ≤ β. If not, Lemma 4.1.1 (iii) implies that D+(e) ≥ D+(T ) − β > 0 for all edges e in T , which is a contradiction. Since D+(T ) ≤ β, D(e0) = D−(e0) +D+(e0) ≤ 2β +D+(T ) ≤ 3β. Suppose T contains one or two heavy edges. We are going to show that in both cases D˜(T ) ≥ 2(D+(T )− (1− 3β)). First assume that there is exactly one heavy edge in T . Let e1 and e2 be the two non-heavy edges in T . Note that D−(ei) = D(ei) ≥ D(T ) = D+(T ) + β > 1− 2β for i = 1, 2. Thus, (5.9) and Lemma 4.1.1 imply that D˜(T ) ≥ 2(D+(T )−(1−3β)). Assume that T contains two heavy edges. Let e1 be the non-heavy edge in T . Similarly, we have D−(e1) ≥ D+(T ) + β > 1 − 2β. Recall that D+(T ) ≤ β, so (5.9) and Lemma 4.1.1 imply D˜(T ) ≥(4β +D+(T )− (1− 3β)) =4β − 1 +D+(T )− (1− 3β) ≥ 2(D+(T )− (1− 3β)). Since D˜(T ) ≥ 2(D+(T )− (1− 3β)), in proving (5.7), it is enough to show that D(e0)f ≥2(D+(e0) + 4β − 1)(D+(T )− (1− 3β)) − ( c (4β − 1) 1− 2β (D+(e0) + 2β)− (1− 2β) ) D+(T ) (5.10) is non-negative for 0 < D+(e0) ≤ D+(T ) and 1 − 3β ≤ D+(T ) ≤ β. Notice 44 5.2 kr(n, δ) for 2n/3 < δ ≤ 3n/4 that for a fixed D+(T ) it is enough to check the boundary points of D+(e0). For D+(e0) = 0, we have D(e0)f ≥2(4β − 1)(D+(T )− (1− 3β)) + (1− 3β)(29− 50β − 100β 2) (29− 75β)(1− 2β) D+(T ) = 1500β3 − 1314β2 + 361β − 29 (1− 2β)(29− 75β) D+(T )− 2(4β − 1)(1− 3β) ≥1500β 3 − 1314β2 + 361β − 29 (1− 2β)(29− 75β) (1− 3β)− 2(4β − 1)(1− 3β) = (1− 3β)2(29− 50β − 100β2) (1− 2β)(29− 75β) > 0. For D+(e0) = D+(T ), D(e0)f ≥2(D+(T ) + 4β − 1)(D+(T )− (1− 3β)) − (( 1− 2 29− 75β ) (4β − 1) 1− 2β (2β +D+(T ))− (1− 2β) ) D+(T ). Notice that this is a quadratic function in D+(T ). Moreover, the coefficients of D+(T ) 2 and D+(T ) are (600β 2 − 449β + 85)/(29 − 75β)(1 − 2β) and 3(4β − 1)(200β2 − 151β + 29)/(1 − 2β)(29 − 75β) respectively. More importantly, they are both positive. Thus, it enough to check for D+(T ) = 1− 3β. For D(T )+ = 1− 3β, we have D(e0)f ≥(1− 3β) 2(200β2 − 233β + 56) (29− 75β)(1− 2β) > 0. Hence, we have proved (5.7). It is easy to check that if equality holds in (5.7) then D+(T ) = 0. Thus, for all edges e in T , D+(e) = 0 by Lemma 4.1.1. Furthermore, equality holds in (5.8), so equality holds in Corollary 4.1.3 as D+(T ) = 0 = D+(e). Hence, d(v) = (1− β)n for v ∈ S. This completes the proof of the lemma. Now we sum (5.7) over all T ∈ K3. After rearrangement, we have ∑ T∈K3 D˜(T ) ≥ ( 1− 2 29− 75β ) (4β − 1) 1− 2β ∑ T∈K3 D+(T )− (1− 2β)n ∑ e∈K2 D+(e). 45 Chapter 5. Heavy cliques The left hand side is bounded above by Lemma 5.1.3 with t = 2. Thus, we obtain a strengthening of (5.3). Corollary 5.2.2. Let 1/4 ≤ β < 1/3. Suppose G is a graph of order n with minimum degree (1− β)n. Then (1 + 3β)k3 + 2 1− 2β ( 1− 3β + 4β − 1 29− 75β ) ∑ T∈K3 D+(T ) ≥ 2(1− 2β)βnk2 + 4k4 n holds. Moreover, if equality holds, then G is (1−β)n-regular and for each edge e, either we have D(e) = 1− 2β or D(e) = 2β. ¤ As mentioned before, if Lemma 5.2.1 holds for c = 1, then Conjecture 3.1.1 is true for p = 3 without needing to strengthen (5.4). However, for ² > 0, it is easy to construct graphs which contain a triangle T with D+(T ) = 1 − 3β + ² and edge degrees 1− 2β + ², 1− 2β + ² and 2β + ² respectively. For c = 1, (5.10) becomes D(e0)f ≥− (4β2 + 2β2 − 1)(1− 3β)/(1− 2β) + o(²). Hence, for ² sufficiently small, the right hand is greater than zero only if β ≤ ( √ 5− 1)/4 ≈ 0.309 < 2/3. It can be checked that for 1/4 ≤ β ≤ (√5− 1)/4, the proof of Lemma 5.2.1 also holds with c = 1. Thus, we can prove Theorem 5 for 1/4 < β < ( √ 5− 1)/4. Surprisingly, it is easier to prove Conjecture 3.1.1 for δ = (3/4 − ²)n than for δ = (2/3 + ²)n for small ² > 0. To see this, suppose that we can prove Conjecture 3.1.1 for p = 3 providing for each T ∈ K3, we can approximate∑ e∈K2(T )D−(e) accurately, say within an absolute error. By definition of D−, 1 − 2β ≤ D−(e) ≤ 2β for all edges e. Notice that the interval is of size 4β − 1, which tends to zero as β tends to 1/4. Thus, approximating ∑ e∈K2(T )D−(e) accurately for β = 1/3 − ² is likely to be more difficult than for β = 1/4 + ², where ² > 0 sufficiently small. 46 5.2 kr(n, δ) for 2n/3 < δ ≤ 3n/4 5.2.2 Strengthening (5.4) Next, we are going to strengthen (5.4). Note that by mimicking the proof of Lemma 5.2.1, we could obtain a strengthening of Corollary 5.1.2 for t = 3. It would lead to a strengthening of (5.4). However, it is still not sufficient to prove the Conjecture 3.1.1 when β is close to 1/3. Fortunately, we are able to prove the following strengthening of (5.4). The proof requires a detailed analysis of K5, so it is postponed to Section 5.3. Theorem 5.2.3. Let 1/4 ≤ β < 1/3. Suppose G is a graph of order n with minimum degree (1− β)n. Then (2− 4β)k4 ≥ (1− 3β)βnk3 + ( 1− 3β + 4β − 1 29− 75β ) n ∑ T∈K3 D+(T ). (5.11) Moreover, if equality holds, then (n, β) is feasible and G ∈ G(n, β). 5.2.3 Proof of Conjecture 3.1.1 for 1/4 ≤ β < 1/3 By using the two strengthened versions of (5.3) and (5.4), that is, Corollary 5.2.2 and Theorem 5.2.3, we prove Theorem 5. Proof of Theorem 5. Note that in proving the inequality in Theorem 5, it is suf- ficient to prove the case when s = t + 1. Recall that p = 3 as 1/4 ≤ β < 1/3, so g2(β) = (1− β)/2, g3(β) = (1− 2β)2β and g4 = (1− 2β)(1− 3β)β2/2. Theorem 5.2.3 states that (2− 4β)k4 ≥ (1− 3β)βnk3. This implies k4/g4(β)n4 ≥ k3/g3(β)n 3 by (4.7) with t = 3. Hence, the theorem is true for t = 3. For t = 2, by substituting Corollary 5.2.2 into Theorem 5.2.3, we obtain (1 + 3β)k3 + 2 1− 2β ( 1− 3β + 4β − 1 29− 75β ) ∑ T∈K3 D+(T ) ≥ 2(1− 2β)βnk2 + 4 (2− 4β)n ( (1− 3β)βnk3 + ( 1− 3β + 4β − 1 29− 75β ) n ∑ D+(T ) ) . 47 Chapter 5. Heavy cliques Observe that the ∑ D+(T ) terms on both sides cancel. Hence, after rearrange- ment, we have (1− β)k3 ≥ 2(1− 2β)2βnk2. Thus, k3/g3(β)n4 ≥ k2/g2(β)n3. This is clear that (iii) implies (i) and (ii) by the construction of G(n, β) and the feasibility of (n, β). Suppose (i) holds, so equality holds for t = t0 and s = s0 with t0 < s0. Since equality holds for t0 < s0, equality holds for t = t0, . . . , s0− 1 and s = s0. Hence, we may assume that s = t+1. In both cases, we have equality in Theorem 5.2.3. Hence, (n, β) is feasible and G ∈ G(n, β). 5.3 Proof of Theorem 5.2.3 In this section, T , S and U always denote a 3-clique, 4-clique and 5-clique re- spectively. First, we establish some basic facts almost T , S and U , which we use in the proof. Observe that D−(S) = 0 for S ∈ K4, so D+(S) = D(S). Recall that D˜(S) = ∑ T∈K3(S)D−(T ) − (2 − 4β). Let T1, . . . , T4 be triangles in S with D(Ti) ≤ D(Ti+1) for 1 ≤ i ≤ 3. Since D−(T ) ≤ β, we have D˜(S) =  2(4β − 1) if k+3 (S) = 4, 4β − 1 + (D(T1)− (1− 3β)) if k+3 (S) = 3, D(T1) +D(T2)− 2(1− 3β) if k+3 (S) = 2, (5.12) where k+3 (S) is the number of heavy triangles in S. Also recall that D(T ) ≥ 1−3β by Lemma 4.1.1 (i). We will often make reference to these formulae throughout this section. Our first aim is to prove a result corresponding to Lemma 5.2.1 for the sum of the degrees of triangles in a 4-clique. Define the function η : K4 → R to be η(S) = D˜(S)− 4β − 1 29− 75β ∑ T∈K3(S) D+(T ) D+(T ) + β for S ∈ K4. Recall that for a heavy triangle T , D(T ) = D+(T ) + β. Thus, only heavy 3-cliques in S contribute to ∑ D+(T )/(D+(T )+β). Ideally, we would like η(S) ≥ 0 for all S ∈ K4. This would imply ∑ S∈K4 η(S) ≥ 0. Therefore, we would 48 5.3 Proof of Theorem 5.2.3 have 0 ≤ ∑ S∈K4 η(S) = ∑ S∈K4 D˜(S)− 4β − 1 29− 75βn ∑ T∈K3 D+(T ) ≤(2− 4β)k4 − (1− 3β)βnk3 − ( 1− 3β + 4β − 1 29− 75β ) n ∑ T∈K3 D+(T ) + 2 ∑ S∈K4 D+(S)− 10k5/n, where the last inequality is due to Lemma 5.1.3 with t = 3. Observe that∑ S∈K4 D+(S) = ∑ S∈K4 D(S) = 5k5/n, so the terms with ∑ D+(S) and k5/n cancel. Rearranging the inequality, we obtain the inequality in Theorem 5.2.3. Actually, it is enough to show that ∑ S∈K4 η(S) ≥ 0. Suppose ∑ S∈K4 η(S) < 0. Then, there exists a 4-clique S with η(S) < 0. Such a 4-clique is called bad, otherwise it is called good. The sets of bad and good 4-cliques are denoted by Kbad4 and Kgood4 respectively. In the next claim, we identify the structure of a bad 4-clique. Claim 5.3.1. Suppose S is a bad 4-clique. Let ∆ = (1− 3β)(1 + ²) and ² = (4β − 1)/(150β2 − 137β + 30). Then, the following hold (i) S contains exactly one heavy edge and two heavy triangles, (ii) 0 < D(S) < ∆, (iii) D(T ) +D(T ′) < 2∆, where T and T ′ are the two non-heavy triangles in S. Proof. Let T1, . . . , T4 be triangles in S with D(Ti) ≤ D(Ti+1) for 1 ≤ i ≤ 3. We may assume that D+(T4) > 0, otherwise S is good by Corollary 5.1.2 as η(S) = D˜(S) ≥ 0. Hence, S is also heavy by Lemma 4.1.1. We separate cases by the number of heavy triangles in S. First, suppose all triangles are heavy. Hence, D˜(S) = 2(4β − 1) by (5.12). 49 Chapter 5. Heavy cliques Clearly, D+(Ti) ≤ 1− β for 1 ≤ i ≤ 4, so η(S) ≥2(4β − 1)− 4β − 1 29− 75β ∑ T∈K3(S) D+(T ) D+(T ) + β ≥2(4β − 1) ( 1− 2(1− β) 29− 75β ) = 2(4β − 1)(27− 73β) 29− 75β ≥ 0. This contradicts the assumption that S is bad. Thus, not all triangles in S are heavy. By Lemma 4.1.1 (iii), we see that D+(T ) ≥ D+(S) − β = D(S) − β for T ∈ K3(S), so 0 < D(S) ≤ β or else all T ∈ K3(S) are heavy. Also, D+(T ) ≤ D+(S) = D(S) ≤ β. Suppose all but one triangles are heavy, so D˜(S) ≥ 4β − 1 by (5.12). Hence, η(S) ≥4β − 1− 4β − 1 29− 75β ∑ T∈K3(S) D+(T ) D+(T ) + β ≥ (4β − 1) ( 1− 3 29− 75β D(S) D(S) + β ) ≥(4β − 1) ( 1− 3 2(29− 75β) ) = 5(4β − 1)(11− 30β) 2(29− 75β) ≥ 0. Suppose there is only one heavy triangle, T4, in S. Corollary 4.1.3 implies that D˜(S) +D+(T4) ≥ 2D+(S) = 2D(S). Note that D+(T4) ≤ D+(S) = D(S), so D˜(S) ≥ D(S). Thus, η(S) ≥D(S)− 4β − 1 29− 75β D+(T4) D+(T4) + β ≥ D(S)− 4β − 1 29− 75β D(S) D(S) + β = ( 1− 4β − 1 (29− 75β)(D(S) + β) ) D(S) ≥ ( 1− 4β − 1 (29− 75β)β ) D(S) > 0. Hence, S has exactly two heavy triangles, namely T3 and T4. If D(S) ≥ ∆, then η(S) =D(T1) +D(T2)− 2(1− 3β)− 4β − 1 29− 75β ( D+(T3) D+(T3) + β + D+(T4) D+(T4) + β ) ≥2(D(S)− (1− 3β))− 2(4β − 1) 29− 75β D(S) D(S) + β >2(1− 3β)²− 2(4β − 1) 29− 75β ∆ ∆+ β ≥ 2(1− 3β)²− 2(4β − 1)∆ (29− 75β)(1− 2β) = 0. 50 5.3 Proof of Theorem 5.2.3 Thus, D(S) < ∆. If D(T1) + D(T2) ≥ 2∆, then D˜(S) ≥ 2(∆ − (1 − 3β)) = 2(1− 3β)² by (5.12). Moreover, since D+(Ti) ≤ D(S) < ∆ for i = 3, 4, η(S) >2(1− 3β)²− 2(4β − 1) 29− 75β ∆ ∆+ β ≥ 2(1− 3β)²− 2(4β − 1)∆ (29− 75β)(1− 2β) = 0. Thus, (iii) is true. We have shown that S contains two heavy triangles. Therefore, to prove (i), it is sufficient to prove that S contains exactly one heavy edge. A triangle containing a heavy edge is heavy by Lemma 4.1.1 (iii). Since S contains two heavy triangle, there is at most one heavy edge in S. It is enough to show that if S does not contain any heavy edge and D(S) < ∆, then S is good, which is a contradiction. Assume that S contains no heavy edge. Let ei = Ti ∩ T4 be an edge of T4 for i = 1, 2, 3. We claim that D˜(S) ≥ D+(T4). By Corollary 4.1.3 taking S = T4 and t = 2, we obtain D(e1) +D(e2) +D(e3) ≥2− 3β +D(T4) D(e1) +D(e2) ≥2− 4β +D+(T4). as D(e3) ≤ 2β and D−(T4) = β. By Lemma 4.1.1 (ii), we get D(T1) +D(T2) ≥ D(e1) +D(e2)− 2β ≥ 2(1− 3β) +D+(T4). Hence, D˜(S) ≥ D+(T4) by (5.12). Therefore, η(S) ≥D+(T4)− 4β − 1 29− 75β ∑ T∈K4(S) D+(T ) D+(T ) + β ≥ ( 1− 2(4β − 1) (29− 75β)(D+(T4) + β) ) D+(T4) ≥ ( 1− 2(4β − 1) (29− 75β)β ) D+(T4) > 0 and so S is good, a contradiction. This completes the proof of the claim. Since a bad 4-clique S must be heavy, that is, D(S) > 0, it is contained in some 5-clique. A 5-clique is called bad if it contains at least one bad 4-clique. We 51 Chapter 5. Heavy cliques denote Kbad5 to be the set of bad 5-cliques. Notice that 2 ∑ T∈K3(U) D(T ) = ∑ S∈K4(U) ∑ T∈K3(S) D(T ) (5.13) for a 5-clique U . For a 4-clique S, Corollary 4.1.3 states that∑ T∈K3(S) D(T ) ≥ 2− 4β + 2D(S) ≥ 2− 4β. Therefore, this implies (5.13) is at least 5(2−4β). On the other hand, Lemma 4.1.2 taking s = 5 and t = 3 implies that∑ T∈K3(U) D(T ) ≥ 7− 15β + 3D(U) ≥ 7− 15β. Hence, (5.13) is at least 2(7−15β) > 5(2−4β) as 1/4 ≤ β < 1/3. This observation suggests that summing D(T ) over T ∈ K3(U) would give a better lower bound than summing D(T ) over T ∈ K3(S) followed by summing over S ∈ K4(U). Recall that a 4-clique S lies in D(S)n bad 5-cliques U . We define η˜(S) to be η(S)/D(S) for S ∈ K4 with D(S) > 0. Clearly for a fixed S ∈ K4 with D(S) > 0, summing η˜(S) over U ∈ K5, which contains S, is exactly equal to η(S)n. Thus, n ∑ S∈K4 η(S) = ∑ U∈K5 ∑ S∈K4(U) η˜(S) + n ∑ S∈K4:D(S)=0 η(S). Recall that our aim is to show that ∑ S∈K4 η(S) ≥ 0. Since D(S) = 0 implies that S is good, we have η(S) ≥ 0. Hence, it is enough to show that∑S∈K4(U) η˜(S) ≥ 0 for each bad 5-clique U . Now, we give a lower bound on η˜(S) for bad 4-cliques S. By Claim 5.3.1, η(S) ≥− 4β − 1 29− 75β ∑ T∈K3(S) D+(T ) D+(T ) + β ≥ −2(4β − 1) 29− 75β D(S) D(S) + β . 52 5.3 Proof of Theorem 5.2.3 Hence, η˜(S) ≥ − 2(4β − 1) (29− 75β)(D(S) + β) > − 2(4β − 1) (29− 75β)β . (5.14) Next, we are going to bound D(S) above for S ∈ K4(U)\Kbad4 and U ∈ Kbad5 . Let Sb ∈ Kbad4 (U). Observe that S ∩ Sb is a 3-clique. Then, by Lemma 4.1.1 and Claim 5.3.1, we have D(S) ≤ D(S ∩ Sb) = D+(S ∩ Sb) + β ≤ D(Sb) + β < ∆+ β. (5.15) Recall that a bad 4-clique S contains a heavy edge by Claim 5.3.1 and hence so does a bad 5-clique U . We split Kbad5 into subcases depending on the number of heavy edges in U . The next claim studies the relationship between the number of heavy edges and bad 4-cliques in a bad 5-clique U . Claim 5.3.2. Suppose U ∈ Kbad5 with h ≥ 2 heavy edges and b bad 4-cliques. Then b ≤ 2h/(h − 1) = 2 + 2/(h − 1). Moreover, if there exist two heavy edges sharing a common vertex, b ≤ 3. Proof. DefineH to be the graph induced by the heavy edges in U . Write uS for the vertex in U not in S ∈ K4(U). This defines a bijection between V (U) and K4(U). If S is bad, uS is adjacent to all but one heavy edges by Claim 5.3.1. By summing the degrees of H, 2h = ∑ S∈K4(U) d(uS) ≥ b(h− 1). Thus, b ≤ 2h/(h− 1). If there exist two heavy edges sharing a common vertex inH, then every bad 4- clique must miss one of the vertices of these two heavy edges. Hence, b ≤ 3. Suppose U ∈ Kbad5 has at least two heavy edges, say e and e′. In the following two claims, we study the cases whether e and e′ intersect or not respectively. Claim 5.3.3. Suppose U is a bad 5-clique and there exist two heavy edges e and e′ in U sharing a common vertex. Then ∑ S∈K4(U) η˜(S) > 0. Proof. Suppose U contains b bad 4-cliques. Clearly b ≤ 3 by Claim 5.3.2. Notice that ∑ S∈Kbad4 (U) η˜(S) > −bγ ≥ −3γ by (5.14), where γ = 2(4β − 1)/(29− 75β)β. Observe that there are exactly two heavy 4-cliques containing both e and e′. 53 Chapter 5. Heavy cliques Therefore, it is enough to show that η(S) ≥ 3D(S)γ/2 for each S ∈ K4(U) containing both e and e′. Since S contains two heavy edges, namely e and e′, it contains at least three heavy triangles. Let S ′ be a 4-clique in U distinct to S. Then, for T = S ∩ S ′, D+(T ) ≤ min{D+(S), D+(S ′)} ≤ D+(S ′) = D(S ′) by Lemma 4.1.1 (iii). In particular, if S ′ is bad, then D+(T ) ≤ D(S ′) < ∆ by Claim 5.3.1. Suppose S contains exactly three heavy triangles. Since not all triangles in S are heavy, D+(S) ≤ β by Lemma 4.1.1 (iii). Also, D˜(S) ≥ 4β − 1 by (5.12). Therefore, η(S) is at least 4β − 1− 4β − 1 29− 75β ∑ T∈K3(S) D+(T ) D+(T ) + β ≥ 4β − 1− 4β − 1 29− 75β ∑ S′∈K4(U)\S D(S ′) D(S ′) + β >4β − 1− 4β − 1 29− 75β ( b∆ ∆+ β + 3− b 2 ) ≥ 4β − 1− 4β − 1 29− 75β ( ∆ ∆+ β + 1 ) ≥3βγ/2 ≥ 3D(S)γ/2 as required. Now suppose all triangles in S are heavy. Notice that D(S) < ∆+β by (5.15) and D˜(S) = 2(4β − 1) by (5.12). Hence, η(S) =2(4β − 1)− 4β − 1 29− 75β ∑ T∈K3(S) D+(T ) D+(T ) + β >2(4β − 1) ( 1− 2(∆ + β) (29− 75β)(∆ + 2β) ) >3(∆ + β)γ/2 > 3D(S)γ/2 as required. The proof of the claim is completed. Claim 5.3.4. Suppose U is a bad 5-clique and there exist two vertex disjoint heavy edges e and e′ in U . Then ∑ S∈K4(U) η˜(S) > 0. Proof. By the previous claim, we may assume that U has exactly two heavy edges. Otherwise, there exist two heavy edges sharing a vertex. Hence, U has b ≤ 4 bad 4-cliques by Claim 5.3.2. Clearly, ∑ S∈Kbad4 (U) η˜(S) > −bγ by (5.14), where as before γ = 2(4β − 1)/(29 − 75β)β. Also, there is exactly one heavy 4-clique S 54 5.3 Proof of Theorem 5.2.3 containing both e and e′. Therefore, it is sufficient to prove that η(S) ≥ bD(S)γ. Since S contains two disjoint heavy edges, all triangles in S are heavy by Lemma 4.1.1. Thus, D˜(S) = 2(4β − 1) by (5.12). Observe that T = S ∩ S ′ is a triangle for S ′ ∈ K4(U)\S. Moreover, D+(T ) ≤ min{D+(S), D+(S ′)} ≤ D+(S ′) = D(S ′) by Lemma 4.1.1 (iii). Hence η(S) ≥2(4β − 1)− 4β − 1 29− 75β ∑ S′∈K4(U)\S D(S ′) D(S ′) + β >(4β − 1) ( 2− 1 29− 75β ( b∆ ∆+ β + (4− b)(∆ + β) ∆ + 2β )) . Therefore, η(S)− bD(S)γ is at least (4β − 1) ( 2− 1 29− 75β ( b∆ ∆+ β + (4− b)(∆ + β) ∆ + 2β )) − b(∆ + β)γ ≥(4β − 1) ( 2− 4∆ (29− 75β)(∆ + β) ) − 4(∆ + β)γ > 0. This completes the proof. Recall that a bad 5-clique contains at least one heavy edge. Thus, we are left with the case U ∈ Kbad5 containing exactly one heavy edge. Claim 5.3.5. Suppose U is a bad 5-clique and there is exactly one heavy edge e in U . Then, U contains at most two bad 4-cliques. Moreover, ∑ S∈K4(U) η˜(S) > 0. Proof. Let u1, . . . , u5 be the vertices of U and u4u5 be the heavy edge. Write Si and ηi to be U − ui and η(Si) respectively for 1 ≤ i ≤ 5. Similarly write Ti,j for U−ui−uj for 1 ≤ i < j ≤ 5. Recall that a bad 4-clique contains a heavy edge by Claim 5.3.1. Hence, Si is a bad 4-clique only if i ≤ 3. Without loss of generality, S1, . . . , Sb are the bad 4-cliques in U . Since S3 contains a heavy edge, it contains at least 2 heavy triangles. First suppose that all triangles in S3 are heavy. Thus, S3 is not bad, so b ≤ 2 and it is enough to show that η3 ≥ 2γD(S3), where as before γ = 2(4β − 1)/(29− 75β)β. 55 Chapter 5. Heavy cliques Notice that D(S3) < ∆+ β by (5.15) and D˜(S3) = 2(4β − 1) by (5.12). Hence, η3 =2(4β − 1)− 4β − 1 29− 75β ∑ T∈K3(S3) D+(T ) D+(T ) + β ≥2(4β − 1) ( 1− 2D(S3) (29− 75β)(D(S3) + β) ) >2(4β − 1) ( 1− 2(∆ + β) (29− 75β)(∆ + 2β) ) ≥ 2(∆ + β)γ > 2D(S3)γ. Second, suppose that S3 contains exactly three heavy triangles. Once again, it is enough to show that η3 ≥ 2γD(S3). If D(S3) ≤ 1− 3β, then D˜(S3) ≥ 4β− 1 by (5.12). Hence η3 ≥D˜(S3)− 4β − 1 29− 75β ∑ T∈K3(S3) D+(T ) D+(T ) + β ≥(4β − 1) ( 1− 3D(S3) (29− 75β)(D(S3) + β) ) >(4β − 1) ( 1− 3(1− 3β) (29− 75β)(1− 2β) ) ≥ 2(1− 3β)γ ≥ 2D(S3)γ. So we may assume D(S3) > 1 − 3β. Since not all triangles in S3 are heavy, D(S3) = D+(S3) ≤ β by Lemma 4.1.1 (iii). Also, D˜(S3) ≥ 7β − 2 + D(S3) by (5.12) as D(T ) ≥ D(S3). Therefore, η3 ≥7β − 2 +D(S3)− 3(4β − 1) 29− 75β D(S3) D(S3) + β ≥7β − 2 +D(S3) ( 1− 3(4β − 1) (29− 75β)(1− 2β) ) ≥7β − 2 + (1− 3β) ( 1− 3(4β − 1) (29− 75β)(1− 2β) ) ≥ 2βγ ≥ 2D(S3)γ. Hence, S3 contains exactly two heavy triangles. By a similar argument, we may assume there are exactly two heavy triangles in Si for 1 ≤ i ≤ 3. More- over, D(Si) < β for 1 ≤ i ≤ 3, otherwise all triangles in Si are heavy by 56 5.3 Proof of Theorem 5.2.3 Lemma 4.1.1 (iii). For 1 ≤ i ≤ b, D(Ti,4) +D(Ti,5) < 2∆ = 2(1− 3β)(1 + ²) by Claim 5.3.1 (iii). For b < i ≤ 3, D˜(Si) = D(Ti,4) + D(Ti,5) − 2(1 − 3β) by (5.12). Thus, D(Ti,4) +D(Ti,5) =ηi + 2(1− 3β) + 4β − 1 29− 75β ∑ T∈K3(Si) D+(T ) D+(T ) + β ≤ηi + 2(1− 3β) + 2(4β − 1)D(Si) (29− 75β)(D(Si) + β) ≤ηi + 2(1− 3β) + γβ/2. After applying Corollary 5.1.2 to S4 and S5 taking t = 3, and adding the two inequalities together, we obtain 2(2− 4β) ≤ ∑ 1≤i≤3 (D−(Ti,4) +D−(Ti,5)) + 2D−(T4,5) ≤ ∑ 1≤i≤3 (D−(Ti,4) +D−(Ti,5)) + 2β 2(2− 5β) ≤ ∑ 1≤i≤b (D(Ti,4) +D(Ti,5)) + ∑ b −D(Si)γ > −γ for 1 ≤ i ≤ b. Hence, ∑ S∈Kbad4 (U) η˜(S) > −bγ. Also, recall that D(Si) ≤ β for 1 ≤ i ≤ 3. It is enough to show that ∑ b 0 for a bad 5-clique U . Now, we ready to prove the inequality of Theorem 5.2.3. By the remark at the beginning of the section, it is sufficient to show that ∑ η(S) ≥ 0 with sum over the 4-cliques S. Recall that by Claim 5.3.1 η(S) ≥ 0 for S ∈ K4 with D(S) = 0 and ∑ S∈K4(U) η(S) ≥ 0 if U is not a bad 5-clique. Notice that n ∑ S∈K4 η(S) = ∑ U∈K5 ∑ S∈K4(U) η˜(S) + n ∑ S∈K4:D(S)=0 η(S) ≥ ∑ U∈Kbad5 ∑ S∈K4(U) η˜(S) ≥ 0. Hence, we prove the inequality in Theorem 5.2.3. Now suppose equality holds in Theorem 5.2.3. Claim 5.3.3, Claim 5.3.4 and Claim 5.3.5 imply that no 4-clique is bad. Furthermore, we must have η(S) = 0 for all S ∈ K4. It can be checked that if the definition of a bad 4-clique includes heavy 4-cliques S with η(S) = 0, then all arguments still hold. Thus, we can deduce that G is K5-free. Hence, G is also K5-free. By Theorem 4 taking s = 4 and t = 3, we obtain that (n, β) is feasible and G ∈ G(n, β). 2 58 Chapter 6 kr(n, δ) for 3n/4 < δ ≤ 4n/5 In this chapter, we evaluate kr(n, δ) for 3n/4 < δ ≤ 4n/5, which is implied by the theorem below as k2(G) ≥ (1− β)n2/2 = g2(β)n2. Theorem 6. Let 1/5 ≤ β < 1/4. Let s and t be integers with 2 ≤ t < s ≤ 5. Suppose G is a graph of order n with minimum degree (1− β)n. Then, ks(G) gs(β)ns ≥ kt(G) gt(β)nt . Moreover, the following three statements are equivalent: (i) Equality holds for some 2 ≤ t < s ≤ 5. (ii) Equality holds for all 2 ≤ t < s ≤ 5. (iii) The pair (n, β) is feasible and G is a member of G(n, β). The general approach of the proof is the same as the proof of Theorem 5, so often lemmas and claims are very similar to ones in Chapter 5. However, additional arguments and refinements are needed in various places. We will point out the similarities and differences before giving the proofs. We would also like to make the following remark about proving Conjec- ture 3.1.1 for all p. Our proof of Theorem 5 boils down to proving Corollary 5.2.2 59 Chapter 6. kr(n, δ) for 3n/4 < δ ≤ 4n/5 and Theorem 5.2.3. Each statement is an inequality of the form ct1 ∑ S∈Kt+1 D+(S) + c t 2kt+1(G) ≥ct3kt(G) + ct4kt+2(G) + ct5 ∑ T∈Kt D+(T ), (6.1) for 2 ≤ t ≤ p(= 3), where each cti is a positive coefficient depending only on β, p and t. Note that (5.2) is an inequality of this form. However, by considering Kp+2-free graphs (see Section 4.2 for the case p = 3), it is easy to deduce that the coefficients ct2, c t 3, c t 4 in (5.2) are optimal. Thus, the key to proving Conjec- ture 3.1.1 is obtaining suitable ct1 and c t 5. Since t ranges from 2 to p, for a given p, it seems very likely that one may obtain an ad-hoc proof of Conjecture 3.1.1 for 1/(p + 1) ≤ β < 1/p by mimicking the proof of Corollary 5.2.2 and Theo- rem 5.2.3. However, finding a proof that works for all p looks very hard due to the inequalities involved. 6.1 kr(n, δ) for 3n/4 < δ ≤ 4n/5 for p = 4, (5.2) gives three inequalities, namely for t = 2, 3, 4. All three inequali- ties require strengthening in order to prove Theorem 6. One obvious choice would be to use the method of Section 5.2.1 for t = 2, and of Section 5.2.2 for t = 4. We are now left with a choice when t = 3. It turns out that the method of Section 5.2.1 for t = 3 is not sufficient to prove Theorem 6 when β is close to 1/4. Thus, we adapt the method of Section 5.2.2, namely the proof of Theorem 5.2.3, to strengthen (5.2) for t = 3. We state the three strengthened versions of (5.2) for t = 2, 3, 4 respectively below. Each lemma improves the coefficients of ∑ D+(T ) and ∑ D+(S). These coefficients are not the best possible, but are chosen to be linear in β if possible. Lemma 6.1.1. Let 1/5 ≤ β < 1/4. Suppose G is a graph of order n with minimum degree (1− β)n. Then ( 1 + 6β ) k3(G) + ( 1− 14β − 1 15β ) ∑ S∈K3 D+(S) ≥ 3(1− 2β)βnk2 + 4k4(G) n . Moreover, if equality holds then G is (1−β)n-regular, and for each edge e, either 60 6.1 kr(n, δ) for 3n/4 < δ ≤ 4n/5 we have D(e) = 1− 2β or D(e) = 3β. Lemma 6.1.2. Let 1/5 ≤ β < 1/4. Suppose G is a graph of order n with minimum degree (1− β)n. Then 2k4(G) + ( 2− 64β + 4 35 ) ∑ S∈K4 D+(S) ≥ 2(1− 3β)βnk3(G) + ( 1− 3β − 13− 47β 15 ) n ∑ T∈K3 D+(T ) + 10k5(G) n . Lemma 6.1.3. Let 1/5 ≤ β < 1/4. Suppose G is a graph of order n with minimum degree (1− β)n. Then (3− 10β)k5(G) ≥ (1− 4β)βnk4(G) + ( 1− 4β + 418β − 92 175 ) n ∑ T∈K4 D+(T ). Moreover, if equality holds, then (n, β) is feasible and G ∈ G(n, β). Their proofs are postponed to later sections. Here, we give an outline of each proof. Lemma 6.1.1 is proved in Section 6.2, using virtually the same argument as the one in Section 5.2.1. We then skip Lemma 6.1.2 and prove Lemma 6.1.3 instead in Section 6.3. Lemma 6.1.3 can be seen as the natural generalisation of Theorem 5.2.3. Thus, its proof bears many similarities to the proof of The- orem 5.2.3 (Section 5.3). However, some refinements are needed. Finally, in Section 6.4, we prove Lemma 6.1.2. Roughly speaking, the proof proceeds by applying the proof of Theorem 5.2.3 twice. Assuming these three lemmas, we now prove Theorem 6. Proof of Theorem 6. Recall that g2(β) = (1− β)/2, g3(β) = (20β2 − 15β + 3)β, g4(β) = (1− 3β)(3− 10β)β2/2, and g5(β) = (1− 3β)(1− 4β)β3/2. First, we are going to show that the inequality in Theorem 6 holds. Observe that it is enough to prove the case s = t+ 1. 61 Chapter 6. kr(n, δ) for 3n/4 < δ ≤ 4n/5 By Lemma 6.1.3, we have (3− 10β)k5 ≥(1− 4β)βnk4 + ( 1− 4β + 418β − 92 175 ) n ∑ S∈K4 D+(S) k5 g5(β)n5 ≥ k4 g4(β)n4 + 1− 4β + (418β − 92)/175 (3− 10β)g5(β)n4 ∑ S∈K4 D+(S). (6.2) Thus, the inequality in Theorem 6 holds for t = 4 (and s = 5) as the coefficient of ∑ S∈K4 D+(T ) is non-negative. Next, we substitute (6.2) into Lemma 6.1.2 replacing the k5 term. We obtain 2k4 + ( 2− 64β + 4 35 ) ∑ S∈K4 D+(S) ≥2(1− 3β)βnk3 + ( 1− 3β − 13− 47β 15 ) n ∑ T∈K3 D+(T ) + 10 ( g5(β)k4 g4(β) + 1− 4β + (418β − 92)/175 3− 10β ∑ S∈K4 D+(S) ) A simple calculation shows that the coefficient of ∑ S∈K4 D+(S) on the left hand side is less than the one oo the right, so we can remove the terms involving∑ S∈K4 D+(S). After further rearranging, we obtain k4 g4(β)n4 ≥ k3 g3(β)n3 + (1− 3β − (13− 47β)/15) 2(1− 3β)βg3(β)n3 ∑ T∈K3 D+(T ). (6.3) Therefore, the inequality in Theorem 6 holds for t = 3, because once again the coefficient of ∑ T∈K3 is non-negative. Finally, we substitute (6.3) into Lemma 6.1.1 replacing the k4 term. We obtain ( 1 + 6β ) k3 + ( 1− 14β − 1 15β ) ∑ T∈K3 D+(T ) ≥3(1− 2β)βnk2 + 4g4(β) ( k3 g3(β) + (1− 3β − (13− 47β)/15 2(1− 3β)βg3(β) ∑ T∈K3 D+(T ) ) Again, a simple calculation shows that the coefficient of ∑ T∈K3 D+(T ) on the 62 6.2 Proof of Lemma 6.1.1 right is at least 1−(14β−1)/15β, so we can remove the terms involving∑T∈K3 D+(T ). After rearrangement, we have k3/g3(β)n 3 ≥ k2/g2(β)n2. Therefore we have shown that inequality in Theorem 6 holds. It is clear that (iii) implies (i) and (ii) by the construction of G(n, β) and the feasibility of (n, β). Suppose (i) holds, so equality holds in Theorem 6 for t = t0 and s = s0 with t0 < s0. We claim that equality must also hold for t = 4 and s = 5. Suppose the contrary, so k5(G)/g5(β) = k4(G)/g4(β). By (6.2), ∑ S∈K4 D+(S) > 0. This implies a strict inequality in (6.3). Moreover, this implies that we have strict inequality in Theorem 6 for 2 ≤ t < s ≤ 5, which contradicts (i). Therefore equality holds for t = 4 and s = 5 and so we have that equality holds in Lemma 6.1.3. Hence, (n, β) is feasible, and G ∈ G(n, β). 6.2 Proof of Lemma 6.1.1 The proof follows by mimicking Section 5.2.1. We prove the corresponding version of Lemma 5.2.1 below. First, recall that the definition of D˜(S) and the results in Section 5.1 hold for all p. Lemma 6.2.1. Let 1/5 ≤ β < 1/4. Suppose G is a graph of order n with minimum degree (1− β)n and S ∈ K3(G). Then D˜(S) ≥ 14β − 1 15β D+(S)− (1− 2β) ∑ T∈K2(S) D+(T ) D+(T ) + 3β . (6.4) Moreover, if equality holds, then S is not heavy, and d(v) = (1−β)n for all v ∈ S. Proof. Suppose the lemma is false and let S be such a 3-clique in G. Corol- lary 5.1.2 states that D˜(S) ≥ 0, so S is heavy as (14β − 1)/15β ≥ 0. Also, by Corollary 4.1.3, we have D˜(S) + ∑ T∈K2(S) D+(T ) ≥ D+(S). (6.5) Thus, S contains at least one heavy edge, or else (6.4) holds as (6.5) becomes D˜(S) ≥ D+(S) ≥ (14β−1)D+(S)/15β. Let T0 ∈ K2(S) withD(T0) = max{D(T ) : 63 Chapter 6. kr(n, δ) for 3n/4 < δ ≤ 4n/5 T ∈ K2(S)}. By substituting (6.5) into (6.4), if f = ( 1− 1− 2β D+(T0) + 3β ) D˜(S)− ( 14β − 1 15β − 1− 2β D+(T0) + 3β ) D+(S) (6.6) is non-negative, then S satisfies (6.4), which is a contradiction. Suppose that D+(S) ≤ 1 − 4β. Since T0 is heavy, D(T0) > 3β ≥ 1 − 2β by Lemma 4.1.1 (iv). Lemma 4.1.1 (iii) gives D(T0) ≤ D(S) + β = 3β +D+(S) ≤ 1− β. Notice that 14β − 1 15β − 1− 2β D(T0) ≤14β − 1 15β − 1− 2β 1− β = − (1− 4β)(1 + 4β) 15β(1− β) ≤ 0 Therefore, by considering the coefficients of both D˜(S) and D+(S) in (6.6), f > 0. Hence, D+(S) > 1− 4β. We address different cases separately depending on the number of heavy edges in S. First, suppose all edges are heavy. Then, D˜(S) = 2(5β−1) by Lemma 4.1.1 (iv). Note that 2(5β − 1) ≤ D+(S), otherwise (6.4) holds as D˜(S) = 2(5β − 1) ≥ D+(S) ≥ (14β − 1)D+(S)/15β. Clearly, D(T0) ≤ 1 and D+(S) = D(S) − 2β ≤ 1− 2β. Hence, f =2(5β − 1) ( 1− 1− 2β D(T0) ) − ( 14β − 1 15β − 1− 2β D(T0) ) D+(S) ≥4(5β − 1)β − (1 + 6β)(5β − 1) 15β D+(S) ≥4(5β − 1)β − (1 + 6β)(5β − 1)(1− 2β) 15β = (5β − 1)(72β2 − 4β − 1) 15β ≥ 0 Thus, there is an edge in S that is not heavy. This implies D+(S) ≤ β. If not, Lemma 4.1.1 (iii) implies D+(T ) > 0 for all T ∈ Kt(S), which is a contradiction. Since D+(S) ≤ β, so D+(T ) ≤ β for T ∈ Kt(S). Suppose there are either one or two heavy edges in S. We claim that in both cases D˜(S) ≥ 2(D+(S) − (1 − 4β)). Assume that S contains exactly one heavy edge. Let T1 and T2 be the two non-heavy edges in S. By Lemma 4.1.1 (iii), 64 6.2 Proof of Lemma 6.1.1 D−(Ti) = D(Ti) ≥ D(S) = D+(S)+2β > 0 for i = 1, 2. Thus by Lemma 4.1.1 (iv), D˜(S) = ∑ D−(T )− (2− β) ≥ 2(D+(S)− (1− 4β)). Next, assume that S contains two heavy edges. Let T1 be the non-heavy edge in S. By Lemma 4.1.1 (iii), we have D−(T1) ≥ D+(S)+2β > 1−2β. Recall that D+(S) ≤ β. Therefore, D˜(S) ≥ 5β−1+D+(S)−(1−4β) ≥ 2(D+(S)−(1−4β)). This completes the claim, so D˜(S) ≥ 2(D+(S)− (1− 4β)). Recall that our aim is to show that (6.6) is non-negative. By substituting D˜(S) ≥ 2(D+(S) − (1 − 4β)) into (6.6) and multiplying by D+(T0) + 3β), it is enough to show that D(T0)f ≥2(5β − 1) (D+(T0) + 5β − 1) − ( 14β − 1 15β (D+(T0) + 3β)− (1− 2β) ) D+(S) =2(5β − 1) (D+(T0) + 5β − 1)− ( (14β − 1)D+(T0) 15β − 6(1− 4β) 5 ) D+(S) is non-negative for 0 < D+(T0) ≤ D+(S) and 1 − 4β ≤ D+(S) ≤ β. By con- sidering the Hessian matrix, all stationary points are saddle points. Thus, it enough to check the above inequality on the boundary of D+(T0) and D+(S). In fact, it is sufficient to check it at the extreme values of D+(T0) and D+(S), because if say D−(T0) is fixed, then we take the extremal values of D+(S), and, if D+(T ) = D+(S), then the above inequality is a concave function. If D+(T0) = 0, we have D(T0)f ≥2(5β − 1)2 + 6(1− 4β)D+(S)/5 > 0 If D+(T0) = D+(S) = β, D(T0)f ≥2(5β − 1) (6β − 1)− (86β − 19)β 15 = 814β2 − 311β + 30 15 > 0. 65 Chapter 6. kr(n, δ) for 3n/4 < δ ≤ 4n/5 Finally, if D+(T0) = D+(S) = 1− 4β, we have D(T0)f ≥2(5β − 1)β + (1− 4β)2(1 + 4β)/15β > 0. Hence, (6.4) holds. It is easy to check thatif equality holds in (6.4) thenD+(S) = 0. By Lemma 4.1.1, D+(T ) = 0 for T ∈ K2(S). Furthermore, equality holds in (6.5) implies equality also holds in Corollary 4.1.3 as D+(T ) = 0 = D+(S). Hence, d(v) = (1 − β)n for v ∈ V (S). This completes the proof of the lemma. Proof of Lemma 6.1.1. Lemma 6.2.1 gives a lower bound on D˜(S) for S ∈ K3. Lemma 5.1.3 gives an upper bound on ∑ S∈K3 D˜(S). Together, they prove the lemma. 6.3 Proof of Lemma 6.1.3 As we mentioned earlier, the proof of Lemma 6.1.3 closely follows the proof of Theorem 5.2.3 from Section 5.3. Thus, many claims and statements are similar, but sometimes the proofs require refinements e.g. Claim 6.3.1 and Claim 6.3.6. Here we give an outline of the proof. In this section, T , S and U will always denote a 4-clique, 5-clique and 6-clique respectively. First, we are going to define a function η on 5-cliques such that ∑ S∈K5 η(S) ≥ 0 would imply the inequality in Lemma 6.1.3. Call a 5-clique S bad if η(S) < 0. Claim 6.3.1 identifies the structure of a bad 5-cliques, namely every bad 5-clique is contained in some 6-clique U . Note that ∑ U∈K6(U) ∑ S∈K5(U) η˜(S) = n ∑ S∈K5:D(S)>0 η(S), where η˜(S) = η(S)/D(S) for S ∈ K5 with D(S) > 0. Thus, it is enough to show that ∑ S∈K5(U) η˜(S) ≥ 0 for 6-cliques U containing a bad 5-clique. Claim 6.3.4, Claim 6.3.5 and Claim 6.3.6 verify this inequality. We recall some basic properties of T , S and U . Observe that D−(S) = 0 for S ∈ K5, so D+(S) = D(S). Thus, D˜(S) = ∑ D−(T )−(2−5β). Let T1, . . . , T5 be 4-cliques in S with D(Ti) ≤ D(Ti+1) for 1 ≤ i ≤ 4. Since D−(T ) ≤ β by 66 6.3 Proof of Lemma 6.1.3 definition, we have D˜(S) =  2(5β − 1) if k+3 (S) = 5, 5β − 1 + (D(T1)− (1− 4β)) if k+3 (S) = 4, D(T1) +D(T2)− 2(1− 4β) if k+3 (S) = 3, (6.7) where k+4 (S) is the number of heavy 4-cliques in S. Notice that D(T ) ≥ 1−4β for T ∈ K4 by Lemma 4.1.1 (i). Once again, these formulae will be used repeatedly throughout this section. Now, we now give the formal proof. Proof of Lemma 6.1.3. Define the function η : K5 → R to be η(S) = D˜(S)− 418β − 92 175 ∑ T∈K4(S) D+(T ) D+(T ) + β for S ∈ K5. For a heavy 4-clique T , D(T ) = D+(T ) + β and so only heavy 4-cliques contribute to ∑ T∈K4(S)D+(T )/(D+(T ) + β). A 5-clique S is called bad if η(S) < 0, otherwise it is called good. The sets of bad and good 5-cliques are denoted by Kbad5 and Kgood5 respectively. For S ∈ K5 with D(S) > 0, define η˜(S) to be η(S)/D(S). If ∑ η(S) ≥ 0 with sum over S ∈ K5, then 0 ≤ ∑ S∈K5 η(S) = ∑ S∈K5 D˜(S)− 418β − 92 175 ∑ S∈K5 ∑ T∈K4(S) D+(T ) D+(T ) + β = ∑ S∈K5 D˜(S)− 418β − 92 175 n ∑ T∈K4 D+(T ) ≤(3− 10β)k5 − (1− 4β)βnk4 − ( 1− 4β + 418β − 92 175 ) n ∑ T∈K4 D+(T ) The last inequality is due to Lemma 5.1.3. Thus, we have obtained the inequality in Lemma 6.1.3. Suppose to the contrary that we have ∑ η(S) < 0, so there exists a bad 5- clique S, i.e. η(S) < 0. By Corollary 5.1.2, D˜(S) ≥ 0. Thus, by the definition of η(S), if β ≤ 46/209, then η(S) ≥ 0 for all S ∈ K5. Therefore, for the remainder of this section, we assume that 46/209 ≤ β ≤ 1/4. 67 Chapter 6. kr(n, δ) for 3n/4 < δ ≤ 4n/5 In the next claim, we study the structure of a bad 5-clique S. It turns out that S has similar characteristics to a bad 4-clique from Section 5.3. For example, S has exactly one heavy edge e and every heavy subclique in S contains e. Actually, proving this statement requires a strengthening of Lemma 4.1.2, which we will state in the proof, when it is needed. Claim 6.3.1. Suppose S is a bad 5-clique. Let ∆ = (1− 4β)(1 + ²), ² = 3(209β − 46) 313− 1152β and γ = 3(418β − 92) 175β . Then, the following holds (i) S contains exactly one heavy edge e and every heavy subclique in S contains e. In particular, S has exactly three heavy 4-subcliques. (ii) 0 < D(S) < ∆, (iii) D(T ) +D(T ′) < 2∆, where T and T ′ are the two non-heavy 4-cliques in S, (iv) η(S) ≥ −3(418β − 92)D(S)/175(D(S) + β), (v) η˜(S) ≥ −3(418β − 92)/175(D(S) + β) > −γ. Proof. Let T1, . . . , T5 be 4-cliques in S with D(Ti) ≤ D(Ti+1) for 1 ≤ i ≤ 4. Since S is bad and D˜(S) ≥ 0 by Corollary 5.1.2, D+(T5) > 0. Thus, S is heavy by Lemma 4.1.1 (iii). We separate cases by the number of heavy 4-cliques in S. First, suppose all 4-cliques are heavy. Hence, D˜(S) = 2(5β − 1) by (6.7). Clearly, D+(Ti) ≤ 1− β for 1 ≤ i ≤ 4, so η(S) ≥2(5β − 1)− 418β − 92 175 ∑ T∈K4(S) D+(T ) D+(T ) + β ≥2(5β − 1)− (418β − 92)(1− β) 35 = 418β2 − 160β + 22 35 > 0. This contradicts the assumption that S is bad. Thus, not all 4-cliques in S are heavy. By Lemma 4.1.1 (iii), we see that D+(T ) ≥ D+(S) − β for T ∈ K4(S), so 0 < D(S) = D+(S) ≤ β or else all T ∈ K4(S) are heavy. Also, D+(T ) ≤ D+(S) = D(S) ≤ β. 68 6.3 Proof of Lemma 6.1.3 Suppose all but one of the 4-cliques are heavy, so D˜(S) ≥ 5β − 1 by (6.7). Hence, η(S) ≥5β − 1− 418β − 92 175 ∑ T∈K4(S) D+(T ) D+(T ) + β ≥ 5β − 1− 4(418β − 92)D(S) 175(D(S) + β) ≥5β − 1− 2(418β − 92) 175 = 39β + 9 175 > 0, which contradicts S being bad. Suppose S contains at most two heavy 4-cliques, say k+4 (S) = 3 − i for i ∈ {1, 2}. Recall that D+(T ) ≤ D+(S) = D(S) for T ∈ K4(S), so D˜(S) ≥ iD(S) by Corollary 4.1.3. Thus, we obtain η(S) ≥iD(S)− 418β − 92 175 ∑ T∈K4(S) D+(T ) D+(T ) + β ≥iD(S)− (3− i)(418β − 92)D(S) 175(D(S) + β) η(S) ≥ ( 1− 2(418β − 92) 175β ) D(S) = (184− 661β)D(S) 175β > 0. (6.8) Again, this contradicts the fact that S is bad. Therefore, S has exactly three heavy 4-cliques. This means that T1 and T2 are non-heavy. Hence, D˜(S) = D(T1) +D(T2)− 2(1− 4β) by (6.7). Recall that D(Ti) ≥ D(S) for i = 1, 2. If D(S) ≥ ∆ ≥ 1− 4β, then η(S) =D(T1) +D(T2)− 2(1− 4β)− 418β − 92 175 ∑ 3≤i≤5 D+(Ti) D+(Ti) + β ≥2(D(S)− (1− 4β))− 3(418β − 92)D(S) 175(D(S) + β) ≥2(D(S)− (1− 4β))− 3(418β − 92)D(S) 175(1− 3β) ≥2(1− 4β)²− 3(418β − 92)∆ 175(1− 3β) = 0, so S is good, a contradiction. Thus, (ii) holds. If (iii) is false, then D(T1) + 69 Chapter 6. kr(n, δ) for 3n/4 < δ ≤ 4n/5 D(T2) ≥ 2∆ and so by (6.7) D˜(S) ≥ 2(1− 4β)². Once again, we have η(S) ≥2(1− 4β)²− 418β − 92 175 ∑ 3≤i≤5 D+(Ti) D+(Ti) + β ≥2(1− 4β)²− 3(418β − 92)D(S) 175(D(S) + β) ≥ 2(1− 4β)²− 3(418β − 92)∆ 175(1− 3β) = 0. Thus, (iii) holds. By the definition of η(S), η(S) ≥− 418β − 92 175 ∑ T∈K4(S) D+(T ) D+(T ) + β ≥ −3(418β − 92)D(S) 175(D(S) + β) . Hence, (iv) and (v) holds. Therefore, we are left to prove (i). Note that we have already shown that S contains exactly three heavy 4-cliques. Since a 4-clique containing a heavy edge is heavy by Lemma 4.1.1 (iii), there is at most one heavy edge in S. Thus, it suffices to show that S contains an heavy edge. Suppose the contrary, so S does not contain any heavy edge and D(S) < ∆ by (ii). Let the vertices of S be v1, . . . , v5 and Ti = S\vi for 1 ≤ i ≤ 5. If D˜(S) ≥ D+(T5), then η(S) ≥D+(T5)− 418β − 92 175 ∑ 3≤i≤5 D+(Ti) D+(Ti) + β ≥ ( 1− 3(418β − 92) 175β ) D+(T5) = (276− 1079β)D+(T5) 175β > 0, which contradicts the fact that S is bad. Therefore, it is enough to show that D˜(S) ≥ D+(T5). By (6.7), it is equivalent to show that D(T1) +D(T2) ≥ 2(1− 4β) +D+(T5). (6.9) Let Wi be Ti ∩ T5 for 1 ≤ i ≤ 4. The set of Wi are precisely the 3-cliques in T5. By Lemma 4.1.1 (ii), D(Ti) ≥ D(Wi)− β for 1 ≤ i ≤ 4. Thus, D(W1) +D(W2) ≥ 2(1− 3β) +D+(T5) (6.10) 70 6.3 Proof of Lemma 6.1.3 implies (6.9). By Corollary 4.1.3 taking t = 3 and S = T5, we have D(W1) +D(W2) +D+(W3) +D+(W4) ≥ 2(1− 3β) + 2D+(T5) as D−(W3), D−(W4) ≤ 2β. We may assume that D+(W3) +D+(W4) > D+(T5), otherwise (6.10) holds, which would imply (6.9) and that S is good, a contradic- tion. First suppose that D+(W3) = 0, so D+(W4) > D+(T5). The edges ofW4 are precisely v1v2, v1v3 and v2v3. Again, by Corollary 4.1.3 taking t = 2 and S = W4, we have D(v1v2) +D(v1v3) +D(v2v3) ≥ 2− 3β +D+(W4) ≥ 2− 3β +D+(T5), where the last inequality is due to Lemma 4.1.1 (iii). Since S has no heavy edge, D(v1v2) is at most 3β. Hence, we have D(v1v3) +D(v2v3) ≥ 2(1− 2β) +D+(T5). Notice that, by Lemma 4.1.1 (ii), D(W1) +D(W2) ≥ (D(v2v3)− β) + (D(v1v3)− β) ≥ 2(1− 3β) +D+(T5), so (6.10) holds. By similar argument, we may assume that bothD+(W3) andD+(W4) are strictly positive. We claim that∑ e∈E(W4) D(e) ≥ 1− 2β +D(W4) +D(v1) = 1 +D+(W4) +D(v1). (6.11) Notice that the above statement is a strengthening of Lemma 4.1.2 for t = 2, s = 3 and S = W4, The proof of (6.11) follows easily from the proof of Lemma 4.1.2 by replacing (4.3) with∑ i ini = ∑ v∈V (S) d(v) ≥ 2(1− β)n+ d(v1). Expanding the left hand side of (6.11) yields D(v1v3) +D(v2v3)−D(v1) ≥ 1−D(v1v2) +D+(W4) ≥ 1− 3β +D+(W4). 71 Chapter 6. kr(n, δ) for 3n/4 < δ ≤ 4n/5 By similar argument, D(v1v4) +D(v2v4)−D(v2) ≥ 1− 3β +D+(W3). By the pigeonhole principle, it is easy to see thatD(W1) = D(v2v3v4) ≥ D(v2v3)+ D(v2v4)−D(v2). Similarly, D(W2) ≥ D(v1v3) +D(v1v4)−D(v1). Thus, D(W1) +D(W2) ≥(D(v2v3) +D(v2v4)−D(v2)) + (D(v1v3) +D(v1, v4)−D(v1)) ≥2(1− 3β) +D+(W3) +D+(W4) ≥ 2(1− 3β) +D+(T5). Hence, (6.10) holds, which would lead to a contradiction. The proof of the claim is complete. Since a bad 5-clique S must be heavy by Claim 6.3.1, it is contained in some 6-clique U as D(S) > 0. A 6-clique is called bad if it contains at least one bad 5- clique. We denote the set of bad 6-cliques by Kbad6 . Let S, Sb ∈ K5(U) be distinct such that Sb is a bad 5-clique in a bad 6-clique U . Observe that S ∩ Sb is a 4-clique. Then, by Lemma 4.1.1 and Claim 6.3.1 (ii), we have D(S) ≤ D(S ∩ Sb) = D+(S ∩ Sb) + β ≤ D(Sb) + β < ∆+ β. (6.12) A bad 5-clique S contains a heavy edge by Claim 6.3.1 and so does a bad 6-clique U . We study U according to the number of heavy edges it contains. The next claim shows the relationship between the number of heavy edges and bad 5-cliques in U . The proof is identical to the proof of Claim 5.3.2. Hence, the proof is omitted. Claim 6.3.2. Suppose U ∈ Kbad6 with h ≥ 2 heavy edges and b bad 5-cliques. Then b ≤ 2h/(h − 1) = 2 + 2/(h − 1). Moreover, if there exist two heavy edges sharing a common vertex, then b ≤ 3. ¤ Now, our aim is to show that for a bad 6-clique U , ∑ S∈K5(U) η˜(S) > 0. First of all, for a 5-clique S that contains at least four heavy 4-cliques, we bound η˜(S) below Claim 6.3.3. (i) If S ∈ K5 has exactly four heavy 4-cliques, then η˜(S) ≥ 3γ. 72 6.3 Proof of Lemma 6.1.3 (ii) If all 4-cliques in S ∈ K5 are heavy and D+(S) < ∆+ β, then η˜(S) ≥ γ. Proof. (i) It is enough to show that η(S) ≥ 3γD(S). If D(S) = D+(S) ≤ 1− 4β, then D˜(S) ≥ 5β − 1 by (6.7) and so η(S) ≥5β − 1− 418β − 92 175 ∑ T∈K4(S) D+(T ) D+(T ) + β ≥5β − 1− 4(418β − 92)D(S) 175(D(S) + β) ≥ 5β − 1− 4(418β − 92)(1− 4β) 175(1− 3β) ≥3(1− 4β)γ ≥ 3γD(S). If D(S) = D+(S) > 1 − 4β, then D˜(S) ≥ 5β − 1 + D(S) − (1 − 4β) by (6.7) and Lemma 4.1.1 (iii). Recall that D+(S) ≤ β by Lemma 4.1.1 (iii) as not all 4-cliques in S are heavy. Hence η(S)− 3γD(S) ≥9β − 2 +D(S)− 418β − 92 175 ∑ T∈K4(S) D+(T ) D+(T ) + β − 3γD(S) ≥9β − 2 + (1− 3γ)D(S)− 4(418β − 92)D(S) 175(D(S) + β) ≥9β − 2 + (1− 3γ)(1− 4β)− 2(418β − 92) 175 = 3(5029β2 − 2355β + 276) 175β > 0 as required. (ii) Note that D˜(S) = 2(5β − 1) by (6.7). Hence, η(S) =2(5β − 1)− 418β − 92 175 ∑ T∈K4(S) D+(T ) D+(T ) + β ≥ 2(5β − 1)− (418β − 92)D(S) 35(D(S) + β) >2(5β − 1)− (418β − 92)(∆ + β) 35(∆ + 2β) ≥ (∆ + β)γ > D(S)γ as required. The next two claims consider the case when a bad 6-clique U contains at least two heavy edges, e and e′. 73 Chapter 6. kr(n, δ) for 3n/4 < δ ≤ 4n/5 Claim 6.3.4. Suppose U is a bad 6-clique and there exist two heavy edges e and e′ in U sharing a common vertex. Then ∑ S∈K5(U) η˜(S) > 0. Proof. Suppose U contains b bad 5-cliques and h heavy edges. Clearly, b ≤ 3 by Claim 6.3.2. Hence, ∑ S′∈Kbad5 (U) η˜(S) > −bγ ≥ −3γ by Claim 6.3.1 (v). There are exactly three heavy 5-cliques S containing both e and e′. Each such S contains at least four heavy 4-cliques. Also, D(S) < ∆+ β by (6.12). Thus, η˜(S) > γ by Claim 6.3.3 (ii). Therefore, ∑ S∈K5(U) η˜(S) > 0. Claim 6.3.5. Suppose U is a bad 6-clique. Suppose also that there exist two vertex disjoint heavy edges e and e′ in U . Then ∑ S∈K5(U) η˜(S) > 0. Proof. By Claim 6.3.4, we may assume that any two heavy edges in U are disjoint and so U has at most three heavy edges. If U has three disjoint heavy edges, then every 5-clique in U contains at least two heavy edges. Therefore, no 5-clique in U is bad by Claim 6.3.1 (i). Thus, the heavy edges in U are precisely e and e′. In addition, U has b ≤ 4 bad 4-cliques by Claim 6.3.2. Let S0 be a bad 4-clique in U withD(S0) minimal. Note that ∑ S∈Kbad5 (U) η˜(S) ≥ −bγβ/(D(S0)+β) by Claim 6.3.1 (v). Note that there are two heavy 5-cliques S containing both e and e′. Recall that D(S) ≤ D(S0) + β by (6.12). Therefore, it is sufficient to prove that η(S) > bγβ/2 for each heavy 5-clique S containing both e and e′, because the right hand side of the inequality is at least bγβD(S)/2(D(S0) + β). Since S contains two vertex disjoint heavy edges, all 4-cliques in S are heavy by Lemma 4.1.1. Thus, D˜(S) = 2(5β − 1) by (6.7). Note that for a 4-clique T = S∩S ′ and S ′ ∈ K5(U)\S, D+(T ) ≤ min{D+(S), D+(S ′)} ≤ D+(S ′) = D(S ′) 74 6.3 Proof of Lemma 6.1.3 by Lemma 4.1.1 (iii). Therefore, η(S) =2(5β − 1)− 418β − 92 175 ∑ T∈K4(S) D+(T ) D+(T ) + β ≥2(5β − 1)− 418β − 92 175 ∑ S′∈K5(U)\S D(S ′) D(S ′) + β ≥2(5β − 1)− 418β − 92 175 ( b∆ ∆+ β + (5− b)(∆ + β) ∆ + 2β ) , where the last inequality is due to Claim 6.3.1 (ii) and (6.12). Hence, η(S)− bγβ/2 ≥2(5β − 1)− 418β − 92 175 ( b∆ ∆+ β + (5− b)(∆ + β) ∆ + 2β ) − bγβ/2 ≥2(5β − 1)− 418β − 92 175 ( 4∆ ∆+ β + ∆+ β ∆+ 2β ) − 2γβ > 0 as required. The proof is complete. Now, we look at the case when U ∈ Kbad6 contains only one heavy edge. Claim 6.3.6. Suppose U is a bad 6-clique containing exactly one heavy edge e. Then, U contains at most three bad 5-cliques. Moreover, ∑ S∈K5(U) η˜(S) > 0. Proof. Let u1, . . . , u6 be the vertices of U and u5u6 be the heavy edge. Write Si and ηi to be U − ui and η(Si) respectively for 1 ≤ i ≤ 6. Since a bad 5-clique contains a heavy edge by Claim 6.3.1 (i), if Si is a bad 5-clique, then i ≤ 4. Without loss of generality, S1, . . . , Sb are the bad 5-cliques in U . Similarly, write Ti,j to be U − ui − uj for 1 ≤ i < j ≤ 6. Since Si contains the heavy edge e for 1 ≤ i ≤ 4, Si contains at least three heavy 4-cliques. By Claim 6.3.4, η˜(Si) ≥ γ if Si contains at least four heavy 4-cliques. Recall that ∑ S∈Kbad5 (U) η˜(S) ≥ −bγ by Claim 6.3.1 (v). Thus, we may assume that at most one of S1, . . . , S4 contains at least four heavy 4-cliques and that if there is one it is S4. Otherwise, ∑ S∈K5(U) η˜(S) > 0. Suppose S4 contains exactly four heavy 4-cliques. Claim 6.3.1 (i) implies that S4 is not heavy. Furthermore, η˜(S4) ≥ 3γ by Claim 6.3.3 (i). Since there are at most three bad 4-cliques in U , ∑ S∈K5(U) η˜(S) > 0. 75 Chapter 6. kr(n, δ) for 3n/4 < δ ≤ 4n/5 Suppose all 4-cliques in S4 are heavy, so T4,5 and T4,6 are heavy. For 1 ≤ i ≤ 3, Si contains exactly three heavy 4-cliques, because each contains the heavy edge u5u6. Thus, Ti,5 and Ti,6 are not heavy for 1 ≤ i ≤ 3. This implies both S5 and S6 contains either one or two heavy 4-cliques. By (6.8), it is easy to deduce that η˜(Si) ≥ 184− 661β/175β ≥ γ/2 for i = 5, 6. Note that ∑ S∈Kbad5 (U) η˜(S) ≥ −(b − 1)γβ/(D(S0) + β) + γ by Claim 6.3.1 (v), where S0 is a bad 5-clique with D(S0) minimal and 1 ≤ b ≤ 3. If η˜(S4) ≥ (b − 1)γβ/(D(S0) + β), then ∑ 1≤i≤6 η˜(Si) ≥ 0. Thus, it is sufficient to prove that η(S4) > (b − 1)γβ as D(S4) ≤ D(S0) + β by (6.12). Note that D˜(S4) = 2(5β − 1) by (6.7). For i ∈ [6]\{4}, D+(Ti,4) ≤ D+(Si) = D(Si) by Lemma 4.1.1 (iii). Therefore, η(S4) =2(5β − 1)− 418β − 92 175 ∑ i∈[6]\{4} D+(Ti,4) D+(Ti,4) + β ≥2(5β − 1)− 418β − 92 175 ∑ i∈[6]\{4} D(Si) D(Si) + β ≥2(5β − 1)− 418β − 92 175 ( b∆ ∆+ β + (5− b)(∆ + β) ∆ + 2β ) . The last inequality is due to Claim 6.3.1 (ii) and (6.12). Hence, we have η(S)− (b− 1)γβ ≥2(5β − 1)− 418β − 92 175 ( b∆ ∆+ β + (5− b)(∆ + β) ∆ + 2β ) − (b− 1)γβ ≥2(5β − 1)− 418β − 92 175 ( 3∆ ∆+ β + 2(∆ + β) ∆ + 2β ) − 2γβ > 0 as required. Thus, we may assume that there are exactly three heavy 4-cliques in Si for 1 ≤ i ≤ 4 as each Si contains the heavy edge u5u6. Moreover, D(Si) ≤ β for 1 ≤ i ≤ 4, otherwise all 4-cliques in Si are heavy by Lemma 4.1.1 (iii). For 1 ≤ i ≤ b, D(Ti,5) +D(Ti,6) < 2∆ = 2(1− 4β)(1 + ²) 76 6.3 Proof of Lemma 6.1.3 by Claim 6.3.1 (iii). For b < i ≤ 4, D˜(Si) = D(Ti,5)+D(Ti,6)−2(1−4β) by (6.7). Also D+(Ti,j) ≤ D(Si) for b < i ≤ 4. Thus, D(Ti,5) +D(Ti,6) =ηi + 2(1− 4β) + 418β − 92 175 ∑ T∈K4(S) D+(T ) D+(T ) + β ≤ηi + 2(1− 4β) + γβD(S)/(D(S) + β) ≤ηi + 2(1− 4β) + γβ/2 for b < i ≤ 4. By Corollary 5.1.2 taking t = 4 and S = S5, S6 and adding the two inequalities together, we have 2(2− 5β) ≤ ∑ 1≤i≤4 (D−(Ti,5) +D−(Ti,6)) + 2D−(T5,6) ≤ ∑ 1≤i≤4 (D−(Ti,5) +D−(Ti,6)) + 2β 2(2− 6β) ≤ ∑ 1≤i≤b (D(Ti,5) +D(Ti,6)) + ∑ b −bγ by Claim 6.3.1 (v). Recall that D(Si) ≤ β for i ≤ 4. Hence, it is enough to show that ∑b 0. Thus, we have n ∑ S∈K5 η(S) =n ∑ S∈K4:D(S)>0 η(S) + n ∑ S∈K4:D(S)=0 η(S) ≥ n ∑ S∈K4:D(S)>0 η(S) = ∑ U∈K6 ∑ S∈K5(U) η˜(S) ≥ 0 Therefore, we have proved the inequality in Lemma 6.1.3. Now suppose equality holds. By Claim 6.3.6, Claim 6.3.4 and Claim 6.3.5, no 5-clique is bad. Furthermore, we must have η(S) = 0 for all S ∈ K5. It is easy to check that if the definition of a bad 5-clique includes heavy 5-cliques S with η(S) = 0, then the argument still holds. Thus, we can deduce that G is K6-free. By Theorem 4 taking s = 5 and t = 4, we obtain that (n, β) is feasible, and G ∈ G(n, β). 6.4 Proof of Lemma 6.1.2 In this section, we are going to prove Lemma 6.1.2. We are going to mimic the proof of Theorem 5.2.3 (Section 5.3). Here, T , S and U always denote a 3-clique, 4-clique and 5-clique respectively. We now give an outline of the proof and show that it is not a straightforward generalisation of the proof of Theorem 5.2.3 as we first thought. Again, we define the appropriate function η on 4-cliques such that ∑ S∈K4 η(S) ≥ 0 would imply the inequality in Lemma 6.1.2. Call a 4-clique S bad if η(S) < 0. Claim 6.4.1 identifies the structure of a bad 4-cliques. Our next task is to show that for every 5-clique U containing a bad 4-clique, ∑ S∈K4(U) η˜(S) ≥ 0, where again η˜(S) = η(S)/D(S). However, the above inequality does not always holds as one could construct a 5-clique U such that ∑ S∈K4(U) η˜(S) < 0. Observe that ∑ S∈K4(U) η˜(S) is actually a function on 5-cliques U . For a 5-clique U , define ζ(U) to be ∑ S∈K4(U) η˜(S). It turns out that ∑ U∈K5 ζ(U) ≥ 0 would imply ∑ S∈K4 η(S) ≥ 0. Thus, we consider ζ(U) in the same way we consider η(S), and repeat the same argument on ζ(U). Thus, a 5-clique U is called bad if and only if ζ(U) < 0. It is not surprising that a bad 5-clique is also contained in some 6-clique, which we will 78 6.4 Proof of Lemma 6.1.2 verify in Claim 6.4.3. Finally, in Claim 6.4.6, we show that ∑ U∈K5(W ) ζ˜(U) ≥ 0 for 6-cliques W containing a bad 5-clique, where ζ˜(U) = ζ(U)/D(U) for U ∈ K5 with D(U) > 0. We point out that the main difficulty is to bound D(U) above and below for a bad 5-clique U . Now, we recall some basic facts about degrees of cliques. For a 4-clique S, D˜(S) = ∑ D−(T ) − (2 − 4β + 2D−(S)). If S is heavy, then D−(S) = β by Lemma 4.1.1 (iv). Let T1, . . . , T4 be 3-cliques in S with D(Ti) ≤ D(Ti+1) for 1 ≤ i ≤ 3. Since 1− 3β ≤ D−(T ) ≤ 2β, we have D˜(S) =  2(5β − 1) if k+3 (S) = 4, 5β − 1 + (D(T1)− (1− 3β)) if k+3 (S) = 3, D(T1) +D(T2)− 2(1− 3β) if k+3 (S) = 2, (6.14) where k+3 (S) is the number of 3-cliques in S. We often refer to these formlae throughout this section. Proof of Lemma 6.1.2. Let η : K4 → R be a function such that η(S) = D˜(S) + 13− 47β 15 ∑ T∈K3(S) D+(T ) D+(T ) + 2β − 64β + 4 35 D+(S) for S ∈ K4. Let η˜ : K4 → R be a function such that η˜(S) = η(S)/D(S) for S ∈ K4. Note that D(S) ≥ 1 − 4β > 0 for S ∈ K4 by Lemma 4.1.1 (i), so η˜(S) is well defined. A 4-clique S is called bad if η(S) < 0. Recall that for a heavy 3-clique T , D(T ) = D+(T ) + 2β. If ∑ S∈K4 η(S) ≥ 0, then 0 ≤ ∑ S∈K4 η(S) = ∑ S∈K4 D˜(S) + 13− 47β 15 ∑ S∈K4 ∑ T∈K3 D+(T ) D+(T ) + 2β − 64β + 4 35 ∑ S∈K4 D+(S) = ∑ S∈K4 D˜(S) + 13− 47β 15 n ∑ T∈K3 D+(T )− 64β + 4 35 ∑ S∈K4 D+(S) ≤2k4 + 2 ∑ S∈K4 D+(S)− 2(1− 3β)βnk3 − (1− 3β)n ∑ T∈K3 D+(T ) + 13− 47β 15 n ∑ T∈K3 D+(T )− 64β + 4 35 ∑ S∈K4 D+(S), 79 Chapter 6. kr(n, δ) for 3n/4 < δ ≤ 4n/5 where the last inequality is due to Lemma 5.1.3 with t = 3 and p = 4. Rearranging the above inequality, we obtain the inequality in Lemma 5.2.3. Thus, our aim is to show that ∑ S∈K4 η(S) ≥ 0. Next, we define the functions ζ and ζ˜ on 5-cliques. Let ζ : K5 → R be a function such that ζ(U) = ∑ S∈K4(U) η˜(S) for U ∈ K5. Define ζ˜ : K5 → R to be the function such that ζ˜(U) = ζ(U)/D(U) for U ∈ K5 with D(U) > 0. Analogously, a 5-clique U is called bad if ζ(U) < 0. Before identifying the structure of a bad 4-clique, we give a lower bound on η(S) for S ∈ K4. This lower bound will be used instead of the definition whenever we evaluate η(S) unless stated otherwise. Recall that η(S) = D˜(S) + 13− 47β 15 ∑ T∈K3(S) D+(T ) D+(T ) + 2β − 64β + 4 35 D+(S) for S ∈ K4. By Corollary 5.1.2, D˜(S) ≥ 0 for S ∈ K4, so a bad 4-clique S must be heavy. In addition, Corollary 4.1.3 states that for S ∈ K4 D˜(S) + ∑ T∈K3(S) D+(T ) ≥ 2D+(S). (6.15) Moreover, this implies that a bad 4-clique contains at least one heavy 3-clique or else η(S) ≥ 2D+(S)− (64β+4)D+(S)/35 > 0. Also, (6.15) gives an upper bound on ∑ T∈K3(S)D+(T ). Recall that D+(T ) ≤ D+(S) by Lemma 5.1.3 (iii). Hence η(S) =D˜(S) + 13− 47β 15 ∑ T∈K3(S) D+(T ) D+(T ) + 2β − 64β + 4 35 D+(S) ≥D˜(S) + 13− 47β 15(D+(S) + 2β) ∑ T∈K3(S) D+(T )− 64β + 4 35 D+(S) (6.15) ≥ D˜(S) + 13− 47β 15(D+(S) + 2β) ( 2D+(S)− D˜(S) ) − 64β + 4 35 D+(S) η(S) ≥ ( 1− 13− 47β 15(D+(S) + 2β) ) D˜(S)− ( 64β + 4 35 − 2(13− 47β) 15(D+(S) + 2β) ) D+(S). (6.16) We will refer to this lower bound on η(S) throughout this section. 80 6.4 Proof of Lemma 6.1.2 In the next claim, we identify the structure of a bad 4-clique S. The proof is very similar to Claim 5.3.1. Claim 6.4.1. Suppose S is a bad 4-clique. Let ∆ = 32(1− 4β)(92β − 13) 45β(31− 16β) and γ = 720β2 + 1549β − 416 720β . Then, the following hold: (i) S contains exactly one heavy edge and two heavy 3-cliques, (ii) 0 < D(S) < ∆, (iii) D(T ) +D(T ′) < 2(∆+ β), where T and T ′ are the two non-heavy 3-cliques in S, (iv) η(S) ≥ −γD+(S), (v) η˜(S) ≥ −γ∆/(∆ + β). Proof. First, we show that (ii) implies both (iv) and (v). By (ii), D+(S) < ∆ ≤ β. Recall that D˜(S) ≥ 0 by Corollary 5.1.2, so (6.16) becomes η(S) ≥ ( 1− 13− 47β 15(D+(S) + 2β) ) D˜(S)− ( 64β + 4 35 − 2(13− 47β) 15(D+(S) + 2β) ) D+(S) ≥− ( 64β + 4 35 − 2(13− 47β) 15(D+(S) + 2β) ) D+(S) ≥− ( 64β + 4 35 − 2(13− 47β) 45β ) D+(S) = −γD+(S), so (iv) holds, and (v) easily follows as D(S) = D+(S) + β < ∆+ β. Next, we are going to show that (ii) holds, and S contains two heavy 3-cliques in S. By the discussion earlier, S must contain a heavy 3-clique and S is heavy. We separate cases by the number of heavy 3-cliques in S. First, suppose all 3-cliques are heavy. Hence, D˜(S) = 2(5β − 1) by (6.14). Clearly from the definition D+(S) = D(S)− β ≤ 1− β. By (6.16), we have η(S) ≥2(5β − 1) ( 1− 13− 47β 15(D+(S) + 2β) ) − ( 64β + 4 35 − 2(13− 47β) 15(D+(S) + 2β) ) D+(S). 81 Chapter 6. kr(n, δ) for 3n/4 < δ ≤ 4n/5 We claim the above inequality is strictly positive, so S is good which is a con- tradiction. Notice the right hand side of the inequality is a concave function in D+(S). Hence, it is enough to check the inequality at the boundary points of D+(S). If D+(S) = 0, then η(S) ≥ 0. If D+(S) = 1− β, then η(S) ≥2(5β − 1) ( 1− 13− 47β 15β ) − ( 64β + 4 35 − 2(13− 47β) 15β ) (1− β) = 240β3 + 11439β2 − 3824β + 337 240(1 + β) > 0. Thus, there is at least one 3-clique in S that is not heavy. By Lemma 4.1.1 (iii), we have D+(T ) ≥ D+(S) − β for T ∈ K3(S), so 0 < D+(S) ≤ β or else all 3-cliques in S are heavy. Suppose there are exactly three heavy 3-cliques in S, so D˜(S) ≥ 5β − 1 by (6.14). Hence, by (6.16), we have η(S) ≥(5β − 1) ( 1− 13− 47β 15(D+(S) + 2β) ) − ( 64β + 4 35 − 2(13− 47β) 15(D+(S) + 2β) ) D+(S). Again, we are going to show that the inequality is strictly positive. The right hand side of the inequality is a concave function of D+(S), so it is enough to check at the boundary points. If D+(S) = 0, then the right hand side is positive. If D+(S) = β, then η(S) ≥(5β − 1) ( 1− 13− 47β 45β ) − ( 64β + 4 35 − 2(13− 47β) 45β ) β = 208− 2096β + 5811β2 − 720β3 720β > 0. Thus, S contains less than three heavy 3-cliques. Now suppose, there is only one heavy 3-clique T in S. Since D+(T ) ≤ D+(S) 82 6.4 Proof of Lemma 6.1.2 by Lemma 4.1.1 (iii), (6.15) implies that D˜(S) ≥ D+(S). Thus, (6.16) becomes η(S) ≥ ( 1− 13− 47β 15(D+(S) + 2β) ) D+(S)− ( 64β + 4 35 − 2(13− 47β) 15(D+(S) + 2β) ) D+(S) = 15(15− 16β)D+(S) + 208− 302β − 480β2 240(D+(S) + 2β) D+(S) ≥(208− 302β − 480β 2)D+(S) 240(D+(S) + 2β) > 0, so S is good, which is a contradiction. Therefore, S has exactly two heavy 3-cliques. Let T1 and T2 be the non-heavy 3-cliques in S. Hence, by (6.14) D˜(S) =D(T1) +D(T2)− 2(1− 3β) ≥2(D(S)− (1− 3β)) = 2(D+(S)− (1− 4β)). If D(S) ≥ ∆, then (6.16) becomes η(S) ≥2(D+(S)− (1− 4β)) ( 1− 13− 47β 15(D+(S) + 2β) ) − ( 64β + 4 35 − 2(13− 47β) 15(D+(S) + 2β) ) D+(S) ≥2(D+(S)− (1− 4β)) ( 1− 13− 47β 45β ) − ( 64β + 4 35 − 2(13− 47β) 45β ) D+(S) = 31− 16β 16 D+(S)− 2(1− 4β)(92β − 13) 45β ≥31− 16β 16 ∆− 2(1− 4β)(92β − 13) 45β = 0. This is a contradiction as S is assumed to be bad. Hence, (ii) holds. Furthermore, if D(T1)+D(T2) ≥ 2(∆+β), then by (6.14) D˜(S) ≥ 2(∆− (1− 83 Chapter 6. kr(n, δ) for 3n/4 < δ ≤ 4n/5 4β)). Again, by (6.16) with D+(S) < ∆ ≤ β, η ≥2(∆− (1− 4β)) ( 1− 13− 47β 15(D+(S) + 2β) ) − ( 64β + 4 35 − 2(13− 47β) 15(D+(S) + 2β) ) D+(S) ≥2(∆− (1− 4β)) ( 1− 13− 47β 45β ) − ( 64β + 4 35 − 2(13− 47β) 45β ) ∆ = 0, which is a contradiction. Thus, (iii) holds. Therefore, we are left to prove (i), i.e. that S contains exactly one heavy edge and two heavy 3-cliques. We have already shown that S contains ex- actly two heavy 3-cliques. Since a 3-clique containing a heavy edge is heavy by Lemma 4.1.1 (iii), there is at most one heavy edge in S or else S has more than two heavy 3-cliques. Thus, it is enough to show that S contains exactly one heavy edge. For the remainder of the proof, assume that S does not con- tain any heavy edge and D(S) < ∆. Let T3 and T4 be the heavy 3-cliques in S with D+(T3) ≤ D+(T4) ≤ D+(S) ≤ β. Here, we introduce a lower bound on η(S) which differs from (6.16). Observe that (6.15) also gives an upper bound on D+(S). Then, from the definition of η(S), we have η(S) ≥D˜(S)− 32β + 2 35 D˜(S) + ∑ T∈K3(S) D+(T ) + 13− 47β 15 ∑ T∈K3(S) D+(T ) D+(T ) + 2β = 33− 32β 35 D˜(S)− ∑ T∈K3(S) ( 32β + 2 35 − 13− 47β 15(D+(T ) + 2β) ) D+(T ) ≥33− 32β 35 D˜(S)− 2D+(T4) ( 32β + 2 35 − 13− 47β 45β ) = 33− 32β 35 D˜(S)− 2(288β 2 + 347β − 91) 315β D+(T4). (6.17) Next, we claim that D˜(S) ≥ D+(T4). Let ei = Ti ∩ T4 be an edge of T4 for i = 84 6.4 Proof of Lemma 6.1.2 1, 2, 3. By Corollary 4.1.3 taking S = T4 and t = 2, we obtain D(e1) +D(e2) +D(e3) ≥2− 3β +D(T4) D(e1) +D(e2) ≥2− 4β +D+(T4) as D(e3) ≤ 3β and D−(T4) = 2β. By Lemma 4.1.1 (ii), we get D(T1) +D(T2) ≥ D(e1) +D(e2)− 2β ≥ 2(1− 3β) +D+(T4). Hence, D˜(S) ≥ D+(T4) by (6.14). Therefore, by (6.17) η(S) ≥(33− 32β)D+(T4) 35 − 2(288β 2 + 347β − 91) 315β D+(T4) = 91− 242β − 288β2 105β D+(T4) > 0, which is a contradiction This completes the proof of the claim. Thus, by Claim 6.4.1 (iv), β > 0.241 for the remainder of the proof, else γ < 0 and so all 4-cliques are not bad. If a 4-clique S contains at least three heavy 3-cliques, η˜(S) ≥ 0. In the following claim, we bound η˜(S) away from zero provided D(S) is not too large. Claim 6.4.2. Suppose S is a 4-clique with at least three heavy 3-cliques. If S contains exactly three heavy 3-cliques, then η˜(S) ≥ 4γ∆/(∆ + β) + 3γ(2β − 11(5β − 1)/16)/β. If all 3-cliques in S are heavy and D+(S) ≤ 2β − 11(5β − 1)/16, then η˜(S) ≥ 4γ∆/(∆ + β) + 6γ(2β − 11(5β − 1)/16)/β. Proof. Suppose S contains exactly three heavy 3-cliques. Recall that η(S) = η˜(S)D(S). Since not all 3-cliques in S are heavy, D+(S) ≤ β and D(S) ≤ 2β by 85 Chapter 6. kr(n, δ) for 3n/4 < δ ≤ 4n/5 Lemma 4.1.1 (iii). By (6.16), we obtain η(S) ≥(5β − 1) ( 1− 13− 47β 15(D+(S) + 2β) ) − ( 64β + 4 35 − 2(13− 47β) 15(D+(S) + 2β) ) D+(S) ≥(5β − 1) ( 1− 13− 47β 45β ) − ( 64β + 4 35 − 2(13− 47β) 45β ) β ≥ ( 4γ∆ ∆+ β + 3γ(2β − 11(5β − 1)/16) β ) 2β ≥ ( 4γ∆ ∆+ β + 3γ(2β − 11(5β − 1)/16) β ) D(S). Thus, the first assertion of the claim is true. Now, suppose all 4-cliques in S are heavy and D+(S) ≤ 2β − 11(5β − 1)/16. Note that D˜(S) = 2(5β − 1) by (6.14). Thus, (6.16) becomes η(S) ≥2(5β − 1) ( 1− 13− 47β 15(D+(S) + 2β) ) − ( 64β + 4 35 − 2(13− 47β) 15(D+(S) + 2β) ) D+(S) ≥2(5β − 1) ( 1− 13− 47β 15(4β − 11(5β − 1)/16) ) − ( 64β + 4 35 − 2(13− 47β) 15(4β − 11(5β − 1)/16) ) (2β − 11(5β − 1)/16) ≥ ( 4γ∆ ∆+ β + 3γ(2β − 11(5β − 1)/16) β ) (3β − 11(5β − 1)/16) ≥ ( 4γ∆ ∆+ β + 3γ(2β − 11(5β − 1)/16) β ) D(S) as required. The structure of a bad 5-clique U is identified in the following claim. Recall that a 5-clique U is bad if ζ(U) = ∑ S∈K4(U) η˜(S) < 0. It turns out that a bad 5-clique U has similar structure to a bad 4-clique S, namely both have exactly one heavy edge e, and every heavy subclique contains e. We have shown in Claim 6.4.1 that D+(S) < ∆ and the right hand side tends to zero as β tends to 1/4. However, the upper bound on D+(U) that we obtain does not tend to zero as β tends to 1/4. Claim 6.4.3. Suppose U is a bad 5-clique. Then the following hold, 86 6.4 Proof of Lemma 6.1.2 (i) U contains exactly one heavy edge e and all heavy cliques in U contain e, (ii) 0 < D(U) < β − 11(5β − 1)/16, (iii) D(S) < β − 11(5β − 1)/16 for S ∈ K4(U) not heavy, (iv) ζ(U) > −3γD(U)/(D(U) + β), (v) ζ˜(U) > −3γ/β. Proof. Let u1, . . . , u5 be the vertices of U . Write Si, ηi and η˜i to be U − ui, η(Si) and η˜(Si) respectively for 1 ≤ i ≤ 5. Similarly, we denote by Ti,j, the 3-clique U − ui − uj for 1 ≤ i < j ≤ 5. Since ζ(U) < 0, U contains a bad 4-clique. Without loss of generality, S1 is a bad 4-clique in U . Thus, D+(S1) ≤ ∆ by Claim 6.4.1 (ii). Also, U contains at least one heavy edge, as S1 contains one by Claim 6.4.1 (i). Moreover, ∑ S∈Kbad4 (U) η˜(S) > −bγ∆/(∆+ β) by Claim 6.4.1 (v). For 2 ≤ i ≤ 5, we have D(Si) ≤ D(T1,i) = D+(T1,i) + 2β ≤ D+(S1) + 2β < ∆+ 2β (6.18) by Lemma 4.1.1 and Claim 6.4.1 (ii). Note that D(Si) < ∆ + 2β < 3β − 11(5β − 1)/16. If there exists a Si containing at least three heavy 3-cliques, then η˜(S) ≥ 4γ∆/(∆+β) by Claim 6.4.2, so ζ(U) > 0 as b ≤ 4. This is a contradiction as U is bad. Thus, all Si contain at most two heavy 3-cliques. Hence, D+(Si) ≤ β for 1 ≤ i ≤ 5, by Lemma 4.1.1 (iii). Recall that a 3-clique containing a heavy edge is itself heavy by Lemma 4.1.1 (iii). Therefore, U contains exactly one heavy edge, say u4u5, otherwise there exists a 4-clique containing at least three heavy 3-cliques namely the 4-clique contains two heavy edges. Furthermore, we may assume that S1, . . . , Sb are the bad 4-cliques in U with b ≤ 3. Note thatD(U) = D+(U) ≥ D+(Si) by Lemma 4.1.1 (iii). By Claim 6.4.1 (iv), ζ(U) ≥ ∑ 1≤i≤b η˜i > −γ ∑ 1≤i≤b D+(Si)/(D+(Si) + β) ≥− bγD+(U)/(D+(U) + β) ≥ −3γD(U)/(D(U) + β). Thus, (iv) of the claim is true. Also, (v) is an easy consequence of (iv). 87 Chapter 6. kr(n, δ) for 3n/4 < δ ≤ 4n/5 Next, we are going to show that (iii) implies (i) and (ii). SinceD(U) ≤ D(Si), so (iii) easily implies (ii). If (iii) is true, then neither T4,5, S4 nor S5 is not heavy. Recall that a clique containing a heavy subclique is itself heavy and each Si contains at most two heavy 3-cliques. Therefore, for 1 ≤ i ≤ 3, Ti,4 and Ti,5 are not heavy. Hence, (i) is true. Therefore, it is enough to prove (iii). Suppose D−(T4,5) > D−(S4) + D−(S5) + 11(5β − 1)/16. Recall from the definition of D− that D−(T4,5) ≤ 2β and D−(S4), D−(S5) ≤ β. Thus, at least one of D−(S4) and D−(S5) is strictly less than 2β, i.e. one of S4 and S5 is not heavy. This implies that T4,5 is not heavy by Lemma 4.1.1 (iii). If S4 is not heavy, then by Lemma 4.1.1 (i) we have D(S4) +D−(S5) + 11(5β − 1)/16 −bγ∆/(∆ + β). Since U is bad, ∑b −γ∆/(∆+β) by Claim 6.4.1. Hence, ζ˜(U) ≥ 3γ/β. Suppose Si contains at most two heavy 3-cliques for 1 ≤ i ≤ 5. Recall that D(S) ≤ D(U) ≤ 2β − c, so D+(Si) ≤ β − c for 1 ≤ i ≤ 5. If D−(T4,5) > D−(S4) + D−(S5) + c, then T4,5 is not heavy and one of S4 and S5 is also not heavy. By (6.19), we have D(Si) < β − c for i = 4, 5, which contradicts the hypothesis of the claim. Finally, suppose D−(T4,5) ≤ D−(S4)+D−(S5)+c. Let b be the number of bad 4-cliques in U . Without loss of generality, we may assume that S1, . . . , Sb are the bad 4-cliques in U if b > 0. By the same argument in the proof of Claim 6.4.3, we obtain (6.22). Note that D+(Si) ≤ β − c for 1 ≤ i ≤ 3. For b < i ≤ 3, the equivalent version of (6.21) is D(Ti,4) +D(Ti,5) ≤ 2(1− 3β) + 45β 92β − 13 (η(Si) + γ(β − c)) . 90 6.4 Proof of Lemma 6.1.2 Thus, we have the following stronger version of (6.22): 5(5β − 1)/8 ≤ 2b(∆− (1− 4β)) + 45β 92β − 13 ∑ b 0. The next claim shows the relationship between the number of heavy edges and bad 5-cliques in a 6-clique. In fact, the statement is identical to Claim 6.3.2. Hence, the proof is omitted. Claim 6.4.5. Suppose W is a 6-clique containing h ≥ 2 heavy edges and b bad 5-cliques. Then b ≤ 2h/(h − 1) = 2 + 2/(h − 1). Moreover, if there exist two heavy edges sharing a common vertex, then b ≤ 3. ¤ Now we show that for every 6-clique W , ∑ U∈K5(W ) ζ˜(U) ≥ 0. Claim 6.4.6. Suppose W is a 6-clique. Then ∑ U∈K5(W ) ζ˜(U) ≥ 0. Proof. We may assume that W contains at least one bad 5-clique or there is nothing to prove. Since a bad 5-clique contains a heavy edge by Claim 6.4.3 (i), 91 Chapter 6. kr(n, δ) for 3n/4 < δ ≤ 4n/5 W also contains at least one heavy edge. We claim thatD(U) ≤ 2β−11(5β−1)/16 for all 5-cliques in W . If U is bad, then it is true by Claim 6.4.3 (ii). If U is not bad, D(U) ≤ D(U ∩ U b) = β +D+(U ∩ U b) ≤ D+(U b) < 2β − 11(5β − 1)/16 (6.24) where U b is a bad 5-clique inW . We separate cases by the number of heavy edges in W . First, suppose W contains two heavy edges e and e′. If e and e′ share a common vertex, there are at most three bad 5-cliques in W by Claim 6.4.5. Thus, ∑ U∈Kbad5 (W ) ζ˜(U) > −9γ/β by Claim 6.4.3 (v). Note that there are three 5-cliques U containing both e and e′. Thus, it is enough to show that ζ˜(U) ≥ 3γ/β for each such U . Within U , there exists a 4-clique S containing both e and e′. Hence, S contains at least three heavy 3-cliques. By Claim 6.4.2, η˜(S) ≥ 4γ∆/(∆ + β) + 3γ(2β − 11(5β − 1)/16). There are at most four bad 4-cliques S ′ in U with η˜(S ′) ≥ −γ∆/(∆ + β) by Claim 6.4.1 (v). This implies ζ(U) ≥ 3γ(2β − 11(5β − 1)/16)/β, i.e. ζ˜(U) ≥ 3γ/β as required. If e and e′ are vertex disjoint, there are at most four bad 5-cliques in W by Claim 6.4.5. Thus, ∑ U∈Kbad5 (W ) ζ˜(U) > −12γ/β. Note that there are two 5-cliques U containing both e and e′. Thus, it is enough to show that ζ˜(U) ≥ 6γ/β for such U . Within U , there exists a 4-clique S containing both e and e′. Moreover, all 3-cliques in S are heavy. Thus, η˜(S) ≥ 4γ∆/(∆ + β) + 6γ(2β − 11(5β − 1)/16) by Claim 6.4.2. By a similar argument, ζ˜(U) ≥ 6γ/β. Suppose W contains exactly one heavy edge. Let w1, . . . , w6 be the vertices of W and w5w6 be the heavy edge. Write Ui = W − wi for 1 ≤ i ≤ 6. Since a bad 5-clique contains a heavy edge by Claim 6.4.3 (i), if Ui is a bad 5-clique, then i ≤ 4. Without loss of generality, U1, . . . , Ub are the bad 5-cliques inW . Similarly, denote by Si,j the 4-clique W −wi−wj for 1 ≤ i < j ≤ 6, so ∑ U∈K5(W ) ζ˜(U) ≥ 0. Let g be the number of 5-cliques which satisfy the hypothesis of Claim 6.4.4. Clearly if Ui satisfies the hypothesis of Claim 6.4.4 then Ui is not bad, so b < i ≤ 4. In addition, if b ≤ g then∑U∈K5(W ) ζ˜(U) > 0 by Claim 6.4.3 (v) and Claim 6.4.4. As a consequence, g ≤ 1, and if g = 1 then we may assume that U4 is such a 92 6.4 Proof of Lemma 6.1.2 5-clique. Therefore for 1 ≤ i ≤ 4− g, D(Si,5) +D(Si,6) ≤ 2(β − 11(5β − 1)/16) by Claim 6.4.3 (iii) and Claim 6.4.4. By applying Corollary 5.1.2 to both U5 and U6 taking t = 4, and adding the two inequalities together, we obtain 2(2− 5β) ≤ ∑ 1≤i≤4 (D−(Si,5) +D−(Si,6)) + 2D−(S5,6) 2(2− 6β) ≤ ∑ 1≤i≤4−g (D(Si,5) +D(Si,6)) + ∑ 4−g 0. The inequality follows from Claim 6.4.6. The proof of Lemma 6.1.2 is complete. 93 Chapter 6. kr(n, δ) for 3n/4 < δ ≤ 4n/5 94 Chapter 7 kr(n, δ) for δ > 4n/5 In this chapter, we look at Conjecture 3.1.1 for p ≥ 5. As we have mentioned after Corollary 5.2.2 in Section 5.2.1, it is more difficult to prove Conjecture 3.1.1 for β = 1/p− ² than for β = 1/(p+1)+ ², with small ² > 0 depending on p. This is because in order to prove the case β = 1/p − ², we require a generalisation of the proof of Theorem 5.2.3. Without such generalisation, we are going to prove the following theorem. Theorem 7.a. Let 0 < β < 1/5 and p = dβ−1e − 1. Suppose G is a graph of order n with minimum degree (1− β)n. Then ks(G) gs(β)ns ≥ kt(G) gt(β)nt for r(β) ≤ t < s ≤ p+1. Moreover, the following three statements are equivalent: (i) Equality holds for some r(β) ≤ t < s ≤ p+ 1. (ii) Equality holds for all r(β) ≤ t < s ≤ p+ 1. (iii) The pair (n, β) is feasible and G is a member of G(n, β). The definition of r(β) is given in Section 7.1. One important fact of r(β) is that for each integer p there exists βp > 1/(p + 1) such that r(βp) = 2 for 1/(p + 1) ≤ β < βp. Hence, Theorem 1.2.4 (stated below) follows easily from Theorem 7.a as k2(n, (1− β)n) ≥ (1− β)n2/2. 95 Chapter 7. kr(n, δ) for δ > 4n/5 Theorem 1.2.4. For positive integers p, there exists 1/(p+ 1) < βp ≤ 1/p such that for all 1/(p+ 1) ≤ β < βp and integers n, δ = (1− β)n and r, kr(n, δ) ≥ gr(β)nr holds. Moreover, for 3 ≤ r ≤ p+ 1 equality holds if and only if (n, β) is feasible, and the extremal graphs are members of G(n, β). In Section 7.2, we evaluate kp+1(n, (1 − β)n), that is, the largest r such that kr(n, (1− β)n) > 0. Theorem 7.b. Let 0 < β < 1 and p = dβ−1e − 1. Suppose G is a graph of order n with minimum degree (1− β)n. Then, for any integer 2 ≤ t ≤ p, kp+1(G) gp+1(β)np+1 ≥ kt(G) gt(β)nt . Moreover, for t = 2, equality holds if and only if (n, β) is feasible and G is a member of G(n, β). The main idea is to bound ∑ T∈Kt(S)D−(T ) above and below for S ∈ Ks, where s is no longer always equal to t+ 1 (as in Corollary 5.1.2). 7.1 kr(n, δ) for δ > 4n/5 In this section, our aim is to prove Theorem 7.a. The proof closely follows Sec- tion 5.2.1. First, we are going to generalise Lemma 5.2.1. Before stating the lemma, we are going to define At(β) and Bt(β) for β < 1/5. They will be used as the coefficients for the terms involving D+. We stress that neither At(β) nor Bt(β) defined below is optimal, but they are chosen for their nice expressions. Let 0 < β < 1/5 and p = dβ−1e − 1 as before. For 2 ≤ t ≤ p, define At(β) =(t− 1)((p+ 1)β − 1)Ct(β), and Bt(β) =((p+ 1)β − 1)Ct(β), 96 7.1 kr(n, δ) for δ > 4n/5 where Cj(β) satisfies the recurrence Ct(β) + 1 = (p− t+ 1)βCt−1(β), (7.1) with the initial condition Cp(β) = 0 for 0 < β < 1/5. Explicitly, Cp−j(β) = 1 j!βj ∑ 0≤i 1/(p+ 1). Next, we state an analogue of Lemma 5.2.1 with the additional condition that r(β) ≤ t ≤ p. Its proof is very similar to the proof of Lemma 5.2.1. The condition r(β) ≤ t ≤ p allows us to use (7.3). Lemma 7.1.1. Let 0 < β < 1/5 and p = dβ−1e − 1. Let t be an integer with r(β) ≤ t ≤ p. Suppose G is a graph of order n with minimum degree (1 − β)n and S ∈ Kt+1(G). Then D˜(S) +Bt(β) ∑ T∈Kt(S) D+(T ) D(T ) ≥ At+1(β)D+(S). (7.4) 97 Chapter 7. kr(n, δ) for δ > 4n/5 Moreover, if equality holds, then S is not heavy and d(v) = (1−β)n for all v ∈ S. Proof. First we show (7.4) holds. Fix β and write At, Bt and Ct for At(β), Bt(β) and Ct(β) respectively. Corollary 5.1.2 states that D˜(S) ≥ 0, so we may assume that S is heavy or else 7.4 holds. Recall that Corollary 4.1.3 states D˜(S) + ∑ T∈Kt(S) D+(T ) ≥ (t− 1)D+(S). (7.5) If S does not contain a heavy t-clique, then (7.3) becomes D˜(S) ≥ (t− 1)D+(S) ≥ D+(S) ≥ At+1D+(S), where the last inequality follows from (7.3) if t < p and Ap+1 = 0. Therefore, we may assume that S contains at least one heavy t-clique. Let T0 ∈ Kt(S) with D(T0) = max{D(T ) : T ∈ Kt(S)}. By substituting (7.5) into (7.4), it is sufficient to show that f = ( 1− Bt D(T0) ) D˜(S)− ( At − (t− 1)Bt D(T0) ) D+(S) is non-negative. As S is heavy, we have explicitly that D˜(S) = ∑ T∈Kt(S) D−(T )− (2− (t+ 1)β + (t− 1)(p− t)β). (7.6) First suppose thatD+(S) ≤ 1−pβ. Since T0 is assumed to be heavy, D(T0) > (p− t+1)β > Bt by Lemma 4.1.1 (iv) and (7.3). On the other hand, Lemma 4.1.1 (ii) gives D(T0) ≤ D(S) + β = (p− t+ 1)β +D+(S) ≤ 1− (t− 1)β. Hence, D(T0)At − (t− 1)Bt ≤(1− (t− 1)β)At − (t− 1)Bt =− (t− 1)2((p+ 1)β − 1)Ct < 0. Thus, At− (t− 1)Bt/D(T0) < 0. Therefore, f > 0 by considering the coefficients of D˜(S) and D+(S). Hence, we may assume D+(S) > 1 − pβ. We address different cases separately depending on the number of heavy t-cliques in S. Suppose all t-cliques are heavy. Thus, D˜(S) = 2((p+1)β−1) by (7.6), because 98 7.1 kr(n, δ) for δ > 4n/5 D−(T ) = (p − t + 1)β for all T ∈ Kt(S) by Lemma 4.1.1 (iv). Furthermore, we may assume that 2((p + 1)β − 1) ≤ (t − 1)D+(S), otherwise (7.4) is true as D˜(S) = 2((p+1)β−1) ≥ (t−1)D+(S) ≥ D+(S) ≥ AtD+(S) by (7.3). Note that D(T0) ≤ 1 and D+(S) = D(S)− (p− t)β ≤ 1− (p− t)β. Thus, f =2((p+ 1)β − 1) ( 1− Bt D(T0) ) − ( At − (t− 1)Bt D(T0) ) D+(S) ≥2((p+ 1)β − 1)(1−Bt)− (At − (t− 1)Bt)D+(S) by (7.2) ≥ 2((p+ 1)β − 1)(1−Bt) by (7.3) > 2((p+ 1)β − 1)(1− (p− t)β) > 0, which implies (7.4). Thus, we may assume that there is at least one t-clique T in S that is not heavy. We further claim thatD+(S) ≤ β, soD+(T ) ≤ β. Otherwise, Lemma 4.1.1 (iii) implies D+(T ) > 0 for all T ∈ Kt(S), which is a contradiction. Suppose there are at most t− 2 heavy t-cliques in S, sayprecisely t− 1− i of them for 1 ≤ i ≤ t−2. Note that D˜(S) ≥ iD+(S) by (7.5) and Lemma 4.1.1 (iii). Hence f ≥ ( 1− Bt D(T0) ) iD+(S)− ( At − (t− 1)Bt D(T0) ) D+(S) ≥ ( 1 + (t− 2)Bt D(T0) − At ) D+(S) ≥ (1− At)D+(S) (7.3) > 0, so (7.4) holds. Now suppose there are either t − 1 or t heavy t-cliques in S. We are going to show that in both cases D˜(S) ≥ 2(D+(S) − (1 − pβ)). First, assume that S has t− 1 heavy t-cliques. Let T1 and T2 be the two non-heavy t-cliques in S. By Lemma 4.1.1 (iii), D−(Ti) = D(Ti) ≥ D(S) = D+(S)+(p−t)β > 0 for i ∈ {1, 2}. Thus, (7.6) becomes D˜(S) = ∑ D−(T )− (2− (t+ 1)β + (t− 1)(p− t)β) ≥2(D+(S)− (1− pβ)). Secondly, assume that all but one of the t-cliques in S are heavy. Recall that since not all t-cliques in S are heavy, D+(S) ≤ β by Lemma 4.1.1 (iii). Let T1 be the 99 Chapter 7. kr(n, δ) for δ > 4n/5 non-heavy t-clique in S. By Lemma 4.1.1 (i) we have D(T1) ≥ D(S)− (s− t)β = D+(S) + (p− t)β > 1− tβ. By (7.6), D˜(S) ≥ (p+ 1)β − 1 +D+(S)− (1− pβ) ≥ 2(D+(S)− (1− pβ)). Recall that our aim is to show f ≥ 0. By substituting D˜(S) ≥ 2(D+(S) − (1− pβ)) and multiplying both side by D(T0), it is enough to show that D(T0)f ≥2(D(T0)−Bt)(D+(S)− (1− pβ))− (D(T0)At − (t− 1)Bt)D+(S) =2(D(T0)−Bt)(D+(S)− (1− pβ)) + (1−D(T0))D+(S)At by (7.2) =2((p− t+ 1)β +D+(T0)−Bt)(D+(S)− (1− pβ)) + (1− (p− t+ 1)β −D+(T0))D+(S)At is non-negative for 0 < D+(T0) ≤ D+(S) and 1 − pβ ≤ D+(S) ≤ β. By consid- ering the Hessian matrix, we deduce that all stationary points are saddle points. Thus, it enough to check the inequality on the boundary. In fact, it is sufficient to check at the extreme values of D+(T0) and D+(S), because say if D+(T0) is fixed, then we take the extremal values of D+(S), and if D+(T ) = D+(S), then the above inequality is a concave function. If D+(T0) = 0 and D+(S) = 1 − pβ, we have D(T0)f ≥(1− (p− t+ 1)β)(1− pβ)At > 0. If D+(T0) = 0 and D+(S) = β, we have D(T0)f ≥2((p− t+ 1)β −Bt)((p+ 1)β − 1) + (1− (p− t+ 1)β)βAt by (7.3) > 2β((p+ 1)β − 1) + (1− (p− t+ 1)β)βAt > 0. If D+(T0) = D+(S) = 1 − pβ, D(T0)f ≥ (t − 1)β(1 − pβ)At > 0. Finally, 100 7.1 kr(n, δ) for δ > 4n/5 if D+(T0) = D+(S) = β, D(T0)f ≥2((p− t+ 2)β −Bt)((p+ 1)β − 1) + (1− (p− t+ 2)β)βAt by (7.3) > 2((p+ 1)β − 1)β + (1− (p− t+ 2)β)βAt > 0. It can be checked that if equality holds, then D+(S) = 0, so S is not heavy. Thus, D+(T ) = 0 for T ∈ Kt(S) by Lemma 4.1.1. Furthermore, equality in (7.5) implies equality in Corollary 4.1.3 asD+(T ) = 0 = D+(S). Hence, d(v) = (1−β)n for v ∈ S. This completes the proof of the lemma. Now, we are going to prove Theorem 7.a. The proof is the same as the the proof of Theorem 4 with an additional argument that deals with the D+ terms. Proof of Theorem 7.a. Fix β and we write At, Bt, Ct and gt for At(β), Bt(β), Ct(β) and gt(β) respectively. Actually, we are going to show that ks gsns ≥ kt gtnt + 1− tβ −Bt (1− tβ)(p− t+ 1)βgtnt ∑ T∈Kt D+(T ), (7.7) for r(β) ≤ t < s ≤ p+ 1. Observe that 1− tβ −Bt > 1− pβ > 0 by (7.3), so the above inequality implies inequality in the theorem. Moroever, it is sufficient to prove the case when s = t+ 1. We proceed by induction on t from above. Lemma 7.1.1 (after rearrangement) gives a lower bound on D˜(S) for S ∈ Kt+1. In addition, Lemma 5.1.3 gives a upper bound on ∑ S∈Kt+1 D˜(S). Thus, we have( t− 1 + (p− 2t+ 2)(t+ 1)β)kt+1 + (t− 1− At) ∑ S∈Kt+1 D+(S) ≥ (1− tβ)(p− t+ 1)βnkt + (t− 1)(t+ 2)kt+2 n + (1− tβ −Bt)n ∑ T∈Kt D+(T ) (7.8) for r(β) ≤ t ≤ p. Suppose t = p. Recall that by definition gp+1(β) = (1− (p− 1)β)(1− pβ)βp−1/2 and gp+2(β) = 0. 101 Chapter 7. kr(n, δ) for δ > 4n/5 Thus, (4.7) with t = p becomes gp+1(β) = (1− pβ)β p− 1− (p+ 1)(p− 2)β gp(β). By (7.8) with t = p, we have (p− 1− (p− 2)(p+ 1)β)kp+1 ≥ (1− pβ)βnkp + (1− pβ −Bp)n ∑ S∈Kp D+(T ) kp+1 gp+1(β)np+1 ≥ kp gp(β)np + 1− pβ −Bp (1− pβ)βgp(β)np ∑ T∈Kp D+(T ) Hence, (7.7) is true for t = p. Suppose 2 ≤ t < p − 1, so by the induction hypothesis (7.8) becomes (t− 1 + (t+ 1)(p− 2t+ 2)β)kt+1 + (t− 1− At) ∑ S∈Kt+1 D+(S) ≥(1− tβ)(p+ 1− t)βnkt + (t− 1)(t+ 2)kt+2 n + (1− tβ −Bt)n ∑ T∈Kt D+(T ) ≥(1− tβ)(p+ 1− t)βnkt + (1− tβ −Bt)n ∑ T∈Kt D+(T ) +(t− 1)(t+ 2)gt+2(β)  kt+1 gt+1(β) + 1− (t+ 1)β −Bt+1 (1− (t+ 1)β)(p− t)βgt+1(β) ∑ S∈Kt+1 D+(S)  . (7.9) Notice that if we ignore terms with D+, the inequality above is identical to (4.11) in the proof of Theorem 4. It turns out that if we rearrange (7.9) in the same way as in the proof of Theorem 4, then we would obtain (7.7) with an additional term c ∑ D+(S), where c is a constant depending on p, t and β. Therefore, it is sufficient to show that the terms with ∑ D+(S) in (7.9) can be removed, which is equivalent to showing (t− 1)(t+ 2)gt+2(1− (t+ 1)β −Bt+1) (1− (t+ 1)β)(p− t)βgt+1 − (t− 1− At). (7.10) is non-negative. By (4.6), (t+2)gt+2(β) ≥ (1− (t+1)β)gt+1(β). Hence, (7.10) is 102 7.1 kr(n, δ) for δ > 4n/5 at least (t− 1)(1− (t+ 1)β −Bt+1) (p− t)β − (t− 1− At) = (t− 1)(1− (t+ 1)β − ((p+ 1)β − 1)Ct+1) (p− t)β − (t− 1)(1− ((p+ 1)β − 1)Ct) = (t− 1)((p+ 1)β − 1) (p− t)β ((p− t)βCt − Ct+1 − 1) by (7.1) = 0. Hence, we can remove the terms with ∑ D+(S) and so (7.7) holds. The proof of inequality in the theorem is complete. If equality holds in Theorem 7.a, then equality holds in (7.7). Moreover,∑ D+(T ) must be zero as (1 − tβ − Bt) > 0. Therefore, G is heavy-free, so we are done by Theorem 4. It is easy to see that Theorem 7.a implies Theorem 1.2.4 as r(β) = 2 for 1/(p+ 1) ≤ β < βp. Recall that βp is not optimal. Ideally, we want to generalise Theorem 5.2.3 and show that kp+1 gp+1(β)np+1 ≥ kp gp(β)np + 1− pβ − B˜p(β) (1− pβ)βgp(β)np ∑ T∈Kp D+(T ) (7.11) for some B˜p(β) ≥ 0. Then, we can redefine Ct(β) for 2 ≤ t ≤ p with the initial condition that B˜p(β) = ((p+ 1)β − 1)Ct(β). As a consequence, we would obtain a better βp. However, as we saw in Chapter 6, it is unlikely that we would obtain βp = 1/p just by proving (7.11). In fact, defining At(β) and Bt(β) for a general β is where the main difficulty lies in proving Conjecture 3.1.1. In fact, by analysing the proof of Theorem 7.a, one can obtain a set of inequalities that needs to be satisfied by At(β) and Bt(β) for 2 ≤ t ≤ p. Thus, one can determine the functions At(β) and Bt(β). However, in the proof of Theorem 5.2.3, there are many computations in the proof of Theo- rem 5.2.3, (even more in proof of Lemma 6.1.2 in Section 6.4). Determining that whether At(β) and Bt(β) satisfy all the required inequalities is difficult as both At(β) and Bt(β) are likely to involve binomial coefficients. Therefore, what we 103 Chapter 7. kr(n, δ) for δ > 4n/5 mean is that the main obstacle in proving Conjecture 3.1.1 is to define functions At(β) and Bt(β), which have nice expressions to work with. 7.2 Counting (p + 1)-cliques In this section, we are going to prove Theorem 7.b. This is equivalent to show- ing that Conjecture 3.1.1 holds when r = p + 1, that is, kp+1(n, (1 − β)n) ≥ gp+1(β)n p+1. In all previous sections, our aim is to bound ∑ S∈Ks ∑ T∈Kt(S)D−(T ) with s = t + 1 above and below using Corollary 5.1.2 and Proposition 3.3.1 respec- tively. In this section, s is no longer always equal to (t + 1). A lower bound on ∑ S∈Ks ∑ T∈Kt(S)D−(T ) can be obtained using Lemma 4.1.2 and mimicking the proof of Lemma 5.1.1. Note that∑ S∈Ks ∑ T∈Kt(S) D−(T ) = ∑ T∈Kt f(T )D−(T ), where f(T ) is the number of s-cliques containing a t-clique T . In order to bound∑ S∈Ks ∑ T∈Kt(S)D−(T ) above, an obvious approach would be to apply Propo- sition 3.3.1 to ∑ T∈Kt f(T )D−(T ). However, f(T ) is not a two-valued function for G ∈ G(n, β) and s > t + 1 even if (n, β) is feasible. Thus, the upper bound obtained by Proposition 3.3.1 is unlikely be sharp. The following observation allows us to overcome this problem. For s = t+ 2, observe that 2 ∑ S∈Kt+2 ∑ T∈Kt(S) D−(T ) = ∑ S∈Kt+2 ∑ U∈Kt+1(S) ∑ T∈Kt(U) D−(T ) =n ∑ U∈Kt+1 D(U) ∑ T∈Kt(U) D−(T ). 104 7.2 Counting (p+ 1)-cliques Note that ∑ D−(T ) is two-valued for G ∈ G(n, β) and (n, β) feasible. Explicitly∑ T∈Kt(U) D−(T ) = { 2(1− tβ) if |V (U) ∩ V0| = 0, 1 (1− tβ)(t+ 2)(t+ 1) + ((p+ 1)β − 1)t(t− 1) if |V (U) ∩ V0| = 2. Hence, this suggests that ∑ S∈Ks ∑ S′∈Ks−1(S′) · · · ∑ T ′∈Kt+1(U) ∑ T∈Kt(T ′)D−(T ) may be more appropriate than ∑ S∈Kt+2 ∑ T∈Kt(S)D−(T ). For positive integers t ≤ s, define the function φst : Ks → R to be φst(S) = { D−(S) if t = s, and∑{φs−1t (U) : U ∈ Ks−1(S)} if t < s for S ∈ Ks. Note that φst(S) = (s− t)! ∑ T∈Kt(S)D−(T ), because each T ∈ Kt(S) misses s−t vertices of S, so each T appears exactly (s−t)! times in the summation. For G ∈ G(n, β) with (n, β) feasible, φst(S) = { (s− t)!(1− tβ) if |V (S) ∩ V0| = 0, 1 (1− tβ)s!/t! + ((p+ 1)β − 1)(s− 2)!/(t− 2)! if |V (S) ∩ V0| = 2 for S ∈ Ks. We define the function Φst to be analogous of D−. Define Φst(S) = min{φst(S), ϕst} for S ∈ Ks and 2 ≤ t ≤ s ≤ p+ 1, where ϕst = (1− tβ)s!/t! + ((p+ 1)β − 1)(s− 2)!/(t− 2)!. In the next lemma, we investigate the lower bound on Φst(S) for S ∈ Ks. Lemma 7.2.1. Let 0 < β < 1 and p = dβ−1e − 1. Let s and t be integers with 2 ≤ t ≤ s ≤ p+1. Suppose G is a graph of order n with minimum degree (1−β)n. Then, Φst(S) ≥ (1− tβ)s!/t! + ( D−(S)− (1− sβ) ) (s− 2)!/(t− 2)! for S ∈ Ks. Proof. We fix β and t and proceed by induction on s. This inequality holds in 105 Chapter 7. kr(n, δ) for δ > 4n/5 the trivial cases s = t and s = t + 1 by Corollary 5.1.2. Suppose that s ≥ t + 2 and that the lemma is true for t, . . . , s− 1. Hence φst(S) = ∑ T∈Ks−1(S) φs−1t (T ) ≥ ∑ T∈Ks−1(S) Φs−1t (T ) ≥ ∑ T∈Ks−1(S) [ (1− tβ)(s− 1)!/t! + (D−(T )− (1− (s− 1)β))(s− 3)!/(t− 2)!] =(1− tβ)s!/t! +  ∑ T∈Ks−1(S) D−(T )− s(1− (s− 1)β)  (s− 3)!/(t− 2)! ≥(1− tβ)s!/t! + (2− sβ + (s− 2)D−(S)− s(1− (s− 1)β))(s− 3)!/(t− 2)! =(1− tβ)s!/t! + (D−(S)− (1− sβ))(s− 2)!/(t− 2)!, where the last inequality comes from Corollary 5.1.2 with t = s − 1. The right hand side is increasing in D−(S). In addition, the right hand side equals to ϕst only if D−(S) = (p− s+ 1)β. Thus, the proof of the lemma is complete. Now, we bound ∑ S∈Ks Φ s t(S) from above using Proposition 3.3.1 to obtain the next lemma. The proof is essentially a straightforward application of Propo- sition 3.3.1 with an algebraic check. Lemma 7.2.2. Let 0 < β < 1 and p = dβ−1e − 1. Let s and t be integers with 2 ≤ t ≤ s ≤ p+1. Suppose G is a graph of order n with minimum degree (1−β)n. Then, ∑ S∈Ks Φst(S) ≤ϕs−1t sks + 2((p+ 1)β − 1) s−1∑ i=t+1 ( (i− 3)! (t− 2)!kin s−i s−1∏ j=i (1− jβ) ) + ((t+ 1)kt+1 − (p− t+ 1)βktn)ns−t−1 s−1∏ j=t (1− jβ). Proof. Fix β and t. We proceed by induction on s. Suppose s = t + 1. Note that Φt+1t (S) ≤ ∑ T∈Kt(S)D−(T ). By Proposition 3.3.1, taking A = Kt, f = D−, 106 7.2 Counting (p+ 1)-cliques g = D, m = 1− tβ and M = (p− t+ 1)β,∑ S∈Kt+1 Φt+1t (S) ≤ ∑ S∈Kt+1 ∑ T∈Kt(S) D−(T ) = n ∑ T∈Kt D(T )D−(T ) ≤(p− t+ 1)βn ∑ T∈Kt D(T ) + (1− tβ)n ∑ T∈Kt D−(T )− (1− tβ)(p− t+ 1)βnkt ≤(t+ 1)(1− (p− 2t+ 1)β)kt+1 − (1− tβ)(p− t+ 1)βnkt. Hence the lemma is true for s = t+1. Now assume that s ≥ t+2 and the lemma is true up to s − 1. By Proposition 3.3.1 taking A = Kt, f = Φs−1t , g = D, M = ϕs−1t and m = 1− (s− 1)β, we have∑ S∈Ks Φst(S) = n ∑ T∈Ks−1 D(T )Φs−1t (T ) ≤ϕs−1t ∑ T∈Ks−1 nD(T ) + (1− (s− 1)β)n ∑ T∈Ks−1 Φs−1t (T )− ϕs−1t (1− (s− 1)β)nks−1 =ϕs−1t sks + (1− (s− 1)β)n ∑ T∈Ks−1 Φs−1t (T )− ϕs−1t (1− (s− 1)β)nks−1 ≤ϕs−1t sks − ( ϕs−1t − (s− 1)ϕs−2t ) (1− (s− 1)β)nks−1 + 2((p+ 1)β − 1) s−2∑ i=t+1 ( (i− 3)! (t− 2)!kin s−i s−1∏ j=i (1− jβ) ) + ((t+ 1)kt+1 − (p− t+ 1)βktn)ns−t−1 s−1∏ j=t (1− jβ). The last inequality is due to the induction hypothesis on ∑ Φs−1t (T ). In addition, it is easy to show that (s− 1)ϕs−2t − ϕs−1t = 2((p+ 1)β − 1)(s− 4)!/(t− 2)!. Thus, the proof of the lemma is complete. Now we are ready to prove Theorem 7.b. The proof is very similar to the proof of Theorem 4 with lots of algebraic checks. Proof of Theorem 7.b. We fix β and write gt to be gt(β). We proceed by induction 107 Chapter 7. kr(n, δ) for δ > 4n/5 on t from above. The theorem is true for t = p by Theorem 7.a as r(β) ≤ p. Hence, we may assume t < p. Recall thatD− is a zero function onKp+1. Summing Lemma 7.2.1 taking s = p+ 1 over S ∈ Kp+1 yields∑ S∈Kp+1 Φp+1t (S) ≥ ((1− tβ)(p+ 1)!/t!− (1− (p+ 1)β)(p− 1)!/(t− 2)!) kp+1. (7.12) By Lemma 7.2.2 and the induction hypothesis, ∑ Φp+1t (S) ≤ϕpt (p+ 1)kp+1 + 2((p+ 1)β − 1) p∑ i=t+1 ( (i− 3)! (t− 2)!kin p+1−i p∏ j=i (1− jβ) ) + ((t+ 1)kt+1 − (p− t+ 1)βnkt)np−t p∏ j=t (1− jβ) ≤ϕpt (p+ 1)kp+1 + 2((p+ 1)β − 1) kp+1 gp+1 p∑ i=t+1 ( gi (i− 3)! (t− 2)! p∏ j=i (1− jβ) ) + ( (t+ 1) kp+1 gp+1 gt+1 − (p− t+ 1)βnkt ) np−t p∏ j=t (1− jβ) Thus, after substituting the inequality into (7.12) and rearranging, we have λtkp+1 ≥ (p− t+ 1)βktnp−t+1 ∏p j=t(1− jβ), where λt =(t+ 1)gt+1 p∏ j=t (1− jβ) + 2((p+ 1)β − 1) (t− 2)! ( (p− 2)!gp+1 + p∑ i=t+1 (i− 3)!gi p∏ j=i (1− jβ) ) . Hence, it is enough to show that λt = (p− t+ 1)βgt ∏p j=t(1− jβ); that is, ((p− t+ 1)βgt − (t+ 1)gt+1) p∏ j=t (1− jβ) = 2((p+ 1)β − 1) (t− 2)! ( (p− 2)!gp+1 + p∑ i=t+1 (i− 3)!gi p∏ j=i (1− jβ) ) . (7.13) 108 7.2 Counting (p+ 1)-cliques We prove (7.13) by induction on t from above. By (4.7) with t = p, the left hand side of (7.13) becomes (βgp − (p+ 1)gp+1) (1− pβ) = ( p− 1− (p+ 1)(p− 2)β 1− pβ − (p+ 1) ) (1− pβ)gp+1 =2((p+ 1)β − 1)gp+1. Thus, (7.13) is true for t = p. Suppose t < p. Notice that the right hand side of (7.13) is equal to 2((p+ 1)β − 1) (t− 2)! ( (p− 2)!gp+1 + p∑ i=t+1 (i− 3)!gi p∏ j=i (1− jβ) ) =(t− 1)2((p+ 1)β − 1) (t− 1)! ( (p− 2)gp+1 + p∑ i=t+2 (i− 3)gi p∏ j=i (1− jβ) ) + 2((p+ 1)β − 1)gt+1 p∏ j=t+1 (1− jβ) by (7.13) = (t− 1) ((p− t)βgt+1 − (t+ 2)gt+2) p∏ j=t+1 (1− jβ) + 2((p+ 1)β − 1)gt+1 p∏ j=t+1 (1− jβ) = ( ((p− t+ 2)(t+ 1)β − 2)gt+1 − (t− 1)(t+ 2)gt+2 ) p∏ j=t+1 (1− jβ) = ( (t− 1 + (p− 2t+ 2)(t+ 1)β)gt+1 − (t− 1)(t+ 2)gt+2 ) p∏ j=t+1 (1− jβ) − (t+ 1)gt+1 p∏ j=t (1− jβ) by (4.7) = ((p− t+ 1)βgt − (t+ 1)gt+1) p∏ j=t (1− jβ). Hence, (7.13) is true for 2 ≤ t ≤ p. Therefore, the equality of the theorem is true. Now suppose that equality holds, so equality holds in (7.12). Therefore, D(S) = D−(S) = 0 for all S ∈ Kp+1. Thus, G is Kp+2-free. By Theorem 4 109 Chapter 7. kr(n, δ) for δ > 4n/5 (n, β) is feasible and G ∈ G(n, β). This completes the proof of the theorem. 110 Chapter 8 Further directions In this chapter, we discuss variants of kr(n, δ). In the next section, we discuss kregr (n, δ), that is, an analogue of kr(n, δ) for regular graphs. In Section 8.2, we show that if (n, β) is not feasible, then kr(n, (1− β)n) ≤ gr(β)nr + o(nr). Thus, the lower bound on kr(n, (1 − β)n) given in Conjecture 3.1.1 is asymptotically sharp. In Section 8.3, we take a brief look at the natural opposite problem, that is, determining the maximum number of r-cliques in graphs of order n with maximum degree ∆. Finally, in Section 8.4, we replace the condition on the minimum degree by the minimum ∑ v∈V (e) d(v) over all edges e. 8.1 Cliques in regular graphs, kregr (n, δ) Recall that kregr (n, δ) is the minimum number of r-cliques in δ-regular graphs of order n. In Chapter 2, we evaluated k3(n, δ) for 2n/5 < δ ≤ n/2. We would like to extend the result for δ > n/2. Since G is δ-regular, n or δ is even. Recall that G(n, β) is conjectured to be extremal for kr(n, (1−β)n) if (n, β) is feasible. Moreover, all graphs in G(n, β) are in fact regular graphs. Thus, if (n, β) is feasible, then Conjecture 3.1.1 would imply that kregr (n, (1 − β)n) = gr(β)nr and G(n, β) is the extremal family. Therefore, it is natural to conjecture that G(n, β) is also the extremal family for kregr (n, (1−β)n) when (n, β) is not feasible 111 Chapter 8. Further directions with n or δ even. In summary, we conjecture the following for regular graphs. Conjecture 8.1.1. Let 0 < β < 1 and p = dβ−1e − 1. Let n and βn be positive integers not both odd. Then, for any positive integer r kregr (n, (1− β)n) = gr(β)nr + ( p− 1 r − 3 ) βr−3kreg3 (n ′, δ′)nr−3, holds, where n′ = (1−(p−1)β)n and δ′ = (1−pβ)n. Moreover, when the equality holds and 2 ≤ r ≤ p+ 1, the extremal graphs are members of G(n, β). Notice that δ′ ≤ n′/2. Thus, kreg3 (n′, δ′) was investigated in Chapter 2. Recall that kreg3 (n ′, δ′) > 0 only if n′ is odd. By the construction from Chapter 2, kregr (n ′, δ′) ≤ δ′(3δ′ − n′ − 1)/4, which is of order n2. Therefore, the difference between kregr (n, δ) and kr(n, δ) is of order at most n r−1. Hence, kregr (n, δ) and kr(n, δ) are asymptotically the same. 8.2 (n, β) not feasible Equality holds in Conjecture 3.1.1 (that is kr(n, (1− β) = gr(β)nr,) only if (n, β) is feasible. In this section, we discuss the situation when (n, β) is not feasible. Our aim is to show that kr(n, (1− β)n) ≤ gr(β)nr + o(nr) for (n, β) not feasible. From the definition of feasibility, we can deduce that if (n, β) is not feasible, then (a) both n and (1− β)n are odd, or (b) (1− (p− 1)β)n is odd.. Condition (a) means that G(n, β) is not well defined, because all graphs in G(n, β) are (1− β)n-regular graphs of order n. Condition (b) says that even if G(n, β) is well defined, then G[V0] is not necessarily triangle-free by a theorem of Andra´sfai, Erdo˝s and So´s [3], (Theorem 2.1.1), because G[V0] is regular with |V0| = (1− (p− 1)β)n odd. In fact, (a) is a subcase of (b), as βn is even. Suppose that n and (1− β)n are not both odd. By the construction of G(n, β) and the discussion in the previous section, we have kr(n, (1−β)n) ≤ kregr (n, (1−β)n) ≤ gr(β)nr+o(nr). However, this does not deal with the case when both n and (1− β)n are odd. 112 8.2 (n, β) not feasible Let n and βn be positive integers. Recall that p = dβ−1e − 1, so 1/(p+ 1) ≤ β < 1/p. We now define a family G ′(n, β) of graphs such that each member G′ can be obtained by the construction below. We define the graph G′ = (V,E) with the following properties. There is a partition of V into V0, V1, . . . , Vp−1 with |V0| = (1− (p− 1)β)n and |Vi| = βn for i = 1, . . . , p− 1. For 0 ≤ i < j ≤ p− 1, G′[Vi, Vj] is a complete bipartite graph. For 1 ≤ j ≤ p − 1, G′[Vj] is empty. For i = 0, G′[V0] is an edge minimal triangle-free graph of order (1− (p− 1)β)n with minimum degree (1 − pβ)n. Then, G ′(n, β) is the set of the graphs which can be obtained by the above construction. Observe that G ′(n, β) is defined as long as both n and (1 − β)n are positive integers, whereas G(n, β) requires n and (1 − β)n to not both be odd. The structures of the members of G(n, β) and G ′(n, β) are similar. Note that if (n, β) is feasible, then G(n, β) = G ′(n, β). However, for (n, β) not feasible with n and (1− β)n not both odd, members of G ′(n, β) are not necessarily regular, but members of G ′(n, β) are. Let G′ ∈ G ′(n, β). Suppose (n, β) is not feasible, so |V0| is odd. Recall that G′[V0] is triangle-free with minimum degree (1− pβ)n. If G′[V0] is bipartite, then e(G′[V0]) = (1−pβ)n(|V0|+1)/2 by considering the larger partition class. Hence, e(G′[V0]) ≤ ((1− (p− 1)β)n+ 1)(1− pβ)n/2. Therefore, there are( p− 1 r ) βrnr + ( p− 1 r − 1 ) (1− (p− 1)β)βr−1nr + ( p− 1 r − 2 ) βr−2nr−2e(G′[V0]) ≤gr(β)nr + ( p− 1 r − 2 ) βr−2(1− pβ)nr−1/2 r-cliques in G′ ∈ G ′(n, β). This means that if (n, β) is not feasible, then kr(n, (1− β)n) is also at most gr(β)n r + θ(nr−1). However, we are unable to determine kr(n, (1 − β)n) if (n, β) not feasible. For example, pick n and β such that the integers k and l, where 4k + 2l + 1 = |V0| = (1 − (p − 1)β)n and 2k = δ(G[V0]) = (1 − pβ)n, satisfy the hypothesis of Theorem 2.1.2. Since δ(G[V0]) > 2|V0|/5, G′[V0] is bipartite by Theorem 2.1.1 for G′ ∈ G ′(n, β). Thus, e(G′[V0]) = (n′ + 1)(1 − β′)n′/2. Depending on r, G(n, β) would be preferred over G ′(n, β). Thus, it is possible that there exists a class of intermediate extremal families of graphs depending on r, β and n, which achieve 113 Chapter 8. Further directions kr(n, β). 8.3 Maximum number of cliques Recall that kr(n, δ) is the minimum number of r-cliques in graphs of order n with minimum degree δ. Now, we ask the natural opposite question. Let hr(n,∆) be the maximum number of r-cliques in graphs for a given n and maximum degree ∆. The graph complement of G ∈ G(n, β) is a natural candidate for hr(n, βn − 1). It turns out that this is true for r = 3, because the following theorem of Goodman[23] states that the sum of triangles in a graph and its complement is completely determined by its degree sequence. Theorem 8.3.1 (Goodman [23]). Suppose G is a graph of order n. Then k3(G) + k3(G) = 1 2 ∑ v∈V (G) ( d(v)− n− 1 2 )2 + n(n− 1)(n− 5) 24 . Therefore, evaluating h3(n, βn−1) is equivalent to evaluating k3(n, (1−β)n). In particular, for 1/(p+ 1) ≤ β ≤ 1/p, h3(n, βn− 1) ≤ ((1− 2β)n+ 1)2n/8 + n(n− 1)(n− 5)/24− g3(β)n3. Next, we look at hr(n,∆) for r ≥ 4. Thomason [41] showed that kr(G)+kr(G) for r ≥ 4 is not uniquely determined by it degree sequences, even if kt(G) and kt(G) are known for all t < r. Nevertheless, it is natural to assume that the extremal graph for hr(n, βn− 1) is {G : G ∈ G(n, β)}. Conjecture 8.3.2. Let 0 < β < 1 and p = dβ−1e − 1. Let n and βn be positive integers. Let G ∈ G(n, β) Then, hr(n, βn − 1) ≤ kr(G) for positive integers r. Moreover, for 3 ≤ r ≤ p+1 equality holds if and only if (n, β) is feasible and the extremal graphs are the complements of the members of G(n, β). As mentioned in the introduction (Chapter 1), determining the upper bound on kr(G) for given e is a special case of the Kruskal-Katona Theorem. Hence, hr(n,∆) can also be viewed as a variant of the Kruskal-Katona Theorem. 114 8.4 A degree sum condition Notice that in all the evaluations of k3(n, δ), we need to know that values of kr(n, δ) for 3 < r ≤ p+1 (e.g. Theorem 4). Thus, k3(n, δ) is considered to be the most difficult case. Hence, if we can solve h3(n, βn−1) for all 0 ≤ β ≤ 1, then we have k3(n, (1− β)n). It would lead to a new approach to prove Conjecture 3.1.1. 8.4 A degree sum condition Let T be a t-clique. Denote by σ(T ) the sum of the degrees of the vertices in T . Define σt(G) to be the minimal σ(T ) for all T ∈ Kt(G). Clearly, δ(G) ≥ (1−β)n implies σt(G) ≥ t(1− β)n for all t. We would like to replace the condition on the minimum degree with σt(G) ≥ t(1 − β)n. We further restrict to the case when r > t and conjecture that the same result holds. Conjecture 8.4.1. Let 0 < β < 1 and p = dβ−1e−1. Let r and t be integers with 1 ≤ t < r. Let n and βn be positive integers. Suppose G is a graph of order n with σt(G) = t(1− β)n. Then, kr(G) ≥ gs(β)nr holds. Moreover, equality holds if and only if (n, β) is feasible and the extremal graphs are members of G(n, β). We could try to tackle this conjecture by the same method as before, replacing the assumption of δ(G) = (1 − β)n by σt(G) ≥ t(1 − β)n. We hope that the corresponding result would also be true. However, Lemma 4.1.1 (i) holds, but not (ii). Lemma 4.1.1 (ii) states that D(S) ≥ D(T ) − (s − t)β for S ∈ Ks(G), T ∈ Kt(S) and s ≤ t. Suppose s = t+1 and all but one vertices of S join to every other vertex and the remaining vertices have degree (1− tβ)n+ t. Then, clearly D(S) = 1− tβ < D(T )− β, where T is the set of vertices with degree n− 1. The correct analogue of Lemma 4.1.1 (ii) would be D(S) ≥ D(T ) −max{r, s − t}β. Nevertheless, one can check that all the remaining results in both Section 3.3, Section 4.1 and Section 4.2 hold by examining the proof. In summary, we can prove the conjecture for p = 2 (i.e. σ2(G) ≤ 4n/3) and for Kp+2-free graphs. 115 Chapter 8. Further directions Theorem 8.4.2 (A degrees sum condition of Theorem 3). Let 1/3 < β < 1/2. Suppose G is a graph of order n with σ2(G) = 2(1− β)n. Then k3(G) ≥ (1− 2β)βnk2(G). Furthermore, equality holds if and only if (n, β) is feasible and G is a member of G(n, β). Theorem 8.4.3 (A degrees sum condition of Theorem 4). Let 0 < β < 1 and p = dβ−1e−1. Let r and t be integers with r ≤ t. Suppose G is a Kp+2-free graph of order n with σr(G) = r(1− β)n. Then, kr(G) ≥ gr(β)nr (8.1) holds. Moreover, equality holds if and only if (n, β) is feasible and the extremal graphs are members of G(n, β). Once again, the difficulties lie in handling the heavy cliques. Since we have a weaker version of Lemma 4.1.1 (ii), our argument might not hold even for the case p = 3. Nevertheless, by modifying the arguments in Section 7.1, one would hope that there exists a constant βp,t > 1/(p+1) depending only on p and t, such that Conjecture 8.4.1 holds for 1/(p + 1) < β < βp,t. The proof of Conjecture 3.1.1 could be modified to prove Conjecture 8.4.1. 116 Chapter 9 Constrained Ramsey numbers for rainbow matching 9.1 Introduction A k-edge colouring of a graph G is an edge colouring of G with exactly k colours. A graph G is monochromatic if all its edges have the same colour. For integers s and t, the Ramsey number R(s, t) is the minimum numberN such that for every 2- edge colouring ofKN with two colours, say with colours red and blue, there is a red monochromaticKs or a blue monochromaticKt. The existence of R(s, t) was first proved by Ramsey [38] and rediscovered by Erdo˝s and Szekeres [16]. Similarly, R(s1, . . . , sk) is the minimum number N such that every k-edge colouring of KN with colours c1, . . . , ck contains a monochromatic copy of Ksi of colour ci for some i. If si = s for i = 1, . . . , k, we simply write Rk(s). If an edge colouring of KN uses infinitely many colours, then it is possible to avoid monochromatic Ks for s ≥ 3. Nevertheless, there exists a well-structured edge coloured complete subgraph inKN . For example, there may exist a complete subgraph that is rainbow (i.e every edge has a distinct colour). If we let the vertices of G be v1, . . . , vn, then a lexicographically coloured (or colexicographically coloured) G is an edge colouring such that the edge vivj has colour ci for i < 117 Chapter 9. Constrained Ramsey numbers j (or i > j respectively) with ci distinct. A lexicographically coloured finite graph becomes colexicographically coloured if the ordering on the vertex set is reversed, and vice versa. Erdo˝s and Rado [18] proved that for every n ≥ 3, there exists an integer N(n) such that every edge colouring of KN contains a complete subgraphKn with one of the mentioned edge colourings. This result is also known as the canonical Ramsey theorem. Theorem 9.1.1 (Canonical Ramsey Theorem [18]). For every positive integer s, there exists an integer N(s) > 0 with the following property. For each integer N ≥ N(s) and every edge colouring of KN , there exists a Ks in KN such that it is either monochromatic, rainbow, lexicographically coloured or colexicographically coloured. The Ramsey number R(G,H) for graphs G and H is the minimum num- ber N such that every 2-edge colouring of KN , with colours red and blue say, contains a red monochromatic G or a blue monochromatic H. Similarly, we de- fine R(G1, . . . , Gk) and Rk(G). For a graph G and an edge colouring of KN with N sufficiently large, by the canonical Ramsey theorem we can deduce that there exists a subgraph isomorphic to G with one of the four stated edge colourings. Recall that both lexicographically and colexicographically colourings depend on the ordering of the vertex set. Thus, they are not preserved under vertex re- labelling, so we focus our attentions to monochromatic and rainbow subgraphs. The constrained Ramsey number f(S, T ) of graphs S and T is the minimum num- ber N such that any edge colouring of KN with any number of colours contains a monochromatic S or a rainbow T . It is also called the rainbow Ramsey number or the monochromatic-rainbow Ramsey number in literature. However, f(S, T ) does not exist for every choice of S and T . Using the canonical Ramsey theorem, it is easy to characterise the pairs (S, T ) for which f(S, T ) exists. For the sake of completeness, we give the proof below. Proposition 9.1.2. For graphs S and T , f(S, T ) exists if and only if S is a star or T is acyclic. Proof. First we show that if S is a star or T is acyclic, then f(S, T ) exists. Consider an edge colouring of KN with vertex set {v1, . . . , vN} with N sufficiently 118 9.1 Introduction large. By the canonical Ramsey theorem, there exists a complete subgraph Kn that is well-coloured. If it is monochromatic or rainbow, we are done providing that n ≥ max{|S|, |T |}. Without loss of generality, we may assume that Kn that is lexicographically coloured. Otherwise, reverse the ordering of vertex set. If S is a star, then we are done by considering the centre of the star to be the smallest element in Kn. Hence, we may assume S is not a star and T is acyclic. We are going to show that there exists an ordering of the vertex set V (T ) such that if T is lexicographically coloured then T is rainbow. It is enough to show that such a vertex ordering exists for T connected, so T is a tree. First, we root T at an arbitrary vertex. Order the vertex set of T such that if vi is at a level larger than vj, then i ≤ j. It is easy to verify that if T is lexicographic coloured, then T is rainbow. Thus, there exists a monochromatic S or a rainbow T in Kn, so f(S, T ) exists. Finally, suppose neither S is a star nor T is acyclic. We are going to show that there is no monochromatic S nor rainbow T in a lexicographic coloured of KN for all N . Since T is not acyclic, T contains a cycle. However no cycle in KN is rainbow (nor monochromatic), so there does not exist a rainbow T in KN . By similar argument, we may assume that S is also acyclic. Since S is not a star, there exist two vertex disjoint edges in S. Observe that any two vertex disjoint edges have different colours in KN . Therefore, KN does not contain a monochromatic S. This completes the proof. From now on, we assume that either S is a star or T is acyclic. Thus, f(S, T ) exists. Notice that f(S, T ) is at least Rt−1(S), where t = e(T ). This is because by definition of Rt−1(S), there exists a (t − 1)-edge colouring C of KRt−1(S)−1 without a monochromatic S. Since C uses at most t − 1 colours, no subgraphs isomorphic to T are rainbow. Various people studied f(S, T ) for different cases of S and T . Alon, Jiang, Miller and Pritikin [2] studied the case when S is a star and T is a complete graph and evaluated that f(K1,s, Kt) = Θ((s−1)t3/ ln t). Notice that f(K1,s, T ) is very closely related to an (s−1)-good colouring. An edge colouring is called m-good, if for every vertex v there are at mostm different coloured edges incident to v. Thus, f(K1,s, T ) is the minimum number N such that every (s−1)-good colouring ofKN 119 Chapter 9. Constrained Ramsey numbers contains a rainbow T . On the other hand, f(S,K1,t) is the local (t− 1)-Ramsey number of a graph T that was first introduced by Gya´rfa´s, Lehel, Schelp and Tuza [26]. The local (t− 1)-Ramsey number of a graph T is the Ramsey number of T restricted to edge colourings for which to each vertex v there are at most t−1 edges with distinct colours incident to v. Jamison, Jiang, Ling [28] studied f(S, T ) when S and T are both trees. Further, they conjectured that if S and T are paths of lengths s and t respectively, then f(Ps+1, Pt+1) = Θ(st). Wagner [46] showed this is f(Ps+1, Pt+1) ≤ O(s2t), and later on, Loh and Sudakov [32] showed that f(Ps+1, Pt+1) ≤ O(st log t). Gya´rfa´s, Lehel and Schelp [25] and independently Thomason and Wagner [43] showed that f(G,Pt+1) is equal to Rt−1(G) for t ≤ 4. 9.2 Rainbow matching f (S, tK2) From now on, T is a t-matching tK2, that is t vertex disjoint edges. As mentioned above f(S, tK2) ≥ Rt−1(S). Let C be an edge colouring of a complete graph containing a rainbow (t − 1)K2 but not a rainbow tK2. Clearly, after removing the vertices of the rainbow (t − 1)K2, the resulting graph has at most t − 1 colours. Moreover, the colours in the resulting graph are precisely the colours in the rainbow (t − 1)K2. Hence, it is an easy exercise to show that f(S, tK2) ≤ Rt−1(S)+2t−2 for t ≥ 3, which was first proved by Truszczyn´ski [44]. Therefore, f(S, tK2) is asymptotically equal to Rt−1(S) providing Rt−1(S) is not linear in t. Next suppose that S is also a matching but of size s. Cockayne and Lorimer [11] evaluated Rt−1(sK2). In fact, they evaluated R(s1K2, . . . , skK2) for positive in- tegers s1, . . . , sk. Theorem 9.2.1 (Cockayne and Lorimer [11]). Let s1, . . . , sk be positive integers. Then, R(s1K2, . . . , skK2) = max{s1, . . . , sk}+ 1 + k∑ i=1 (si − 1). In particular, Rk(sK2) = (s− 1)(k + 1) + 2. Hence, f(sK2, tK2) ≥ Rt−1(sK2) = (s− 1)t+ 2. Bialostocki and Voxman [4] showed that if s = t ≥ 3, then equality holds. Later, Eroh [20] extended the result 120 9.2 Rainbow matching f(S, tK2) to s > t ≥ 2 and conjectured that the equality holds for all s ≥ 3 and t ≥ 2. Eroh [21] also investigated the case when S is a star. We are going to generalise their results and evaluate f(S, tK2) exactly for almost all graphs S and all integers t ≥ 2. From now on, we say that two graphs G and H are disjoint to mean vertex disjoint. We state Theorem 1.3.2 below. Theorem 1.3.2. Suppose S is a graph of order at least 5 and Rk+1(S) ≥ Rk(S)+3 for all positive integers k. Then, f(S, tK2) = Rt−1(S) for all integers t ≥ 2. Here, we give an outline of the proof. Suppose the theorem is false for some t > 2. Let t > 2 be the minimal counterexample and N = Rt−1(S). Hence, there exists an edge colouring C of KN that contains neither a monochromatic S nor a rainbow tK2. By the minimal counterexample, there exists a rainbow (t− 1)K2, say W = {ei : 1 ≤ i ≤ t− 1} in G. For a subgraph G ⊂ KN , the colour set C(G) is defined to be the set of colours C(e) for e ∈ E(G). Without loss of generality, C(W ) = {ci : 1 ≤ i ≤ t−1} with C(ei) = ci for 1 ≤ i ≤ t−1. Since N = Rt−1(S) and C does not contain a monochromatic S, C uses at least t colours and so there exists an edge f1 of colour not in C(W ). Also, V (f1)∩ V (W ) 6= ∅ or else W + f1 forms a rainbow tK2. Assume that V (f1) ∩ V (e1) 6= ∅ and V (f1) ∩ V (ei) = ∅ for 2 ≤ i ≤ t− 1. If there exists an edge f2 of colour c1 disjoint from both f1 and e1, then V (f2) ∩ V (ei) 6= ∅ for some i, else f1, f2, e2, e3, . . . , et−1 form a rainbow tK2. Also, assume that V (f2) ∩ V (ei) = ∅ for all i except i = 2. Repeat this argument and during each step we always assume that there exists an edge fi with the following properties. The edge fi is coloured ci−1 and it is disjoint from ej unless j = i. Moreover, the set of fi are disjoint. The edge ft is disjoint from W ∪ {fi : 1 ≤ i ≤ t − 1}. More importantly, {fi : 1 ≤ i ≤ t} is a rainbow tK2, which is a contradiction. In our assumption, C(fi) = ci for all i, but it is not always true. This problem can be overcome if we relax the condition to C(fi) = cj for j ≤ i. However, it is possible that |V (fi) ∩ V (W )| = 2, that is, there exists j1 6= j2 such that |V (ej1) ∩ V (fi)| = 1 = |V (ej2) ∩ V (fi)|. Thus, our principle is to always pick fi such that |V (fi) ∩ V (W )| is minimal. We now give a formal argument of the proof. Proof of Theorem 1.3.2. LetN beRt−1(S). From our previous observation, f(S, tK2) ≥ N . Hence, it is sufficient to show that f(S, tK2) ≤ N . 121 Chapter 9. Constrained Ramsey numbers First we consider the case t = 2. Let C be an edge colouring of K|S| that does not contain a rainbow copy of 2K2. Suppose there exists a path P with three vertices whose edge colours are distinct. Since |S| ≥ 5, there is an edge e disjoint from P . Then, there exists a rainbow 2K2 in P ∪ {e}, contradicting the assumption on C. Hence, K|S| is monochromatic, so f(S, 2K2) = |S| = R1(S) and the theorem is true for t = 2. Suppose the theorem is false and let t > 2 be the minimal counterexample. Let C be an edge colouring of KN that contains neither a monochromatic S nor a rainbow tK2. First, we show that there always exists at least one candidate for fi in the claim below. The claim below states that given a vertex set U not too large containing a rainbow matching pK2, we can always find an edge e disjoint from U coloured by a member of C(pK2). The proof of the claim follows easily from the proof of Lemma 2.2 in [20]. Claim 9.2.2. Let U ⊂ V (KN) satisfy |U | ≤ 3p for positive integer p < t. Suppose U contains a rainbow pK2 with colours c1, . . . , cp. Then, there exists an edge e in KN with V (e) ∩ U = ∅ and C(e) ∈ {c1, . . . , cp}. Proof of Claim. Since |U | ≤ 3p = Rt−1(S)− (Rt−1(S)− 3p) ≤ Rt−1(S)−Rt−p−1(S) = Rt−1(S)− f(S, (t− p)K2), we may assume there exists a rainbow copy of (t − p)K2 in the graph induced by the vertex set V (KN)\U . If C((t − p)K2) ∩ {c1, . . . , cp} = ∅, then (t − p)K2 together with the rainbow pK2 in U forms a rainbow tK2. Thus, the claim is true. Next, we set up notation to keep track of the fi. Let A be the subset of {0, 1, 2}t\{1, 2}t consisting of sequences a = (a1, . . . , at), whose zeros all come at the end; that is, ai = 0 implies ai+1 = 0 for 1 ≤ i ≤ t. Let z(a) = min{i : ai = 0}. Thus, ai 6= 0 for i < z(a) and ai = 0 for i ≥ z(a). We say that a ∈ A is a matching sequence if (a) there exists a set W = {ei : 1 ≤ i ≤ t − 1} of independent edges which is rainbow coloured, that is, W is a rainbow (t− 1)K2; 122 9.2 Rainbow matching f(S, tK2) (b) there exists a sequence f1, . . . fz, z = z(a), of independent edges not in W with |V (fi) ∩W | = ai for 1 ≤ i ≤ z; (c) for every edge ei ∈W , 1 ≤ i ≤ t−1, there exists at most one fj, 1 ≤ j ≤ z, such that V (ei) ∩ V (fj) 6= ∅; (d) C(f1) /∈ {C(ei) : ei ∈W}; (e) for 2 ≤ i ≤ z, C(fi) ∈ {C(ej) : ej ∈ Wi−1} where Wi−1 is the set of edges ej ∈ W that share a vertex with one of f1, . . . , fi−1. Notice that if the all-zero sequence is a matching sequence then we are done, becauseW +f1 is a rainbow copy of tK2. To show that matching sequences exist, let B be the set of initial sequences from the sequences in A, that is, B is the subset of {Λ} ∪⋃tk=0{0, 1, 2}k ∪ A consisting of sequences b = (b1, . . . , bl) whose zeros all come at the end, if any, (where Λ is the empty sequence of length 0). For b = (b1, . . . , bl) ∈ B, define z(b) = min{i : bi = 0}, if this set is non-empty, and otherwise define z(b) = l. We say that b = (b1, . . . , bl) ∈ B is a partial matching sequence if it also satisfies properties (a)− (e). We claim that every partial matching sequence can be extended to a matching sequence (and, in particular, matching sequences exist because Λ ∈ B). Let b be a partial matching sequence of length l. If l = t, b is also a matching sequence. Thus, it is enough to show that b can be extended to a partial matching sequence of length l + 1 for 1 ≤ l < t. First, suppose that b is the empty sequence. There exists a rainbow (t − 1)K2 in KN as N ≥ f(S, (t − 1)K2); call it W . Since N = f(S, tK2) = Rt−1(S), there are at least t colours in KN . Therefore, there exists an edge f1 not in W with C(f1) 6= C(ei) for 1 ≤ i ≤ t − 1. Hence, this defines a partial matching sequence of length 1. Now, suppose b = (b1, . . . , bl) with 1 ≤ l < t and W and f1, . . . , fz and z = z(b) are defined by properties (a)− (e). If bl = 0, then (b1, . . . , bl, 0, . . . , 0) is a matching sequence with the same W and f1, . . . , fz. If bl 6= 0, z = l. Let U = V (Wl) ∪ ⋃l i=1 V (fi). Observe that |U | ≤ 3|Wl|/2, and Wl is rainbow coloured from the construction. There exists an edge fl+1 independent ofWl with C(fl+1) ∈ C(Wl) by Claim 9.2.2. Thus, there exists a partial matching sequence (b1, . . . , bl, bl+1) with bl+1 = |V (fl+1)∩W |. This proves the claim. 123 Chapter 9. Constrained Ramsey numbers Let AM be this set of matching sequences. Let a = (a1, . . . , at) be the lex- icographically minimal element of AM . Thus, for any (a′1, . . . , a′t) ∈ AM\{a}, al < a ′ l where l = min{i : ai 6= a′i}. Define W , f1, . . . , fz with z = z(a) satisfy- ing (a)− (e). Recall that we always choose fi with |V (fi) ∩ V (W )| minimal. As mentioned before, if a is the all-zero sequence, we are done. But if a is not the all zero sequence, properties (c) and (e) imply there exists integers j < t+ 1 and l < z with C(fz) = C(ej) and |V (fl) ∩ V (ej)| = al 6= 0. Set W ′ = W − ej + fz. We define b = (a1, . . . , al−1, al− 1). This is a partial matching sequence with W ′, f1, . . . , fl. By the previous claim, b extends to a matching sequence a ′. But a′ is lexicographically less than a contradicting the choice of a. This completes the proof of the theorem. 9.3 Consequences of Theorem 1.3.2 First, we are going to identify those graphs that fail to satisfy the hypothesis of Theorem 1.3.2. Proposition 9.3.1. Let S be a graph of order at least 5 with no isolated vertex. If Rk+1(S) < Rk(S) + 3 for some positive integers k, then S is bipartite and one of its vertex classes has size at most 3. Proof. Fix k and let N = Rk(S) − 1. Let C be a k-edge colouring of KN that does not contain a monochromatic S. If S is not bipartite, then define an edge colouring of K2N as follows: take two copies of KN each with edge colouring C and join the vertices between the two copies with a new colour. Since S is bipartite, there is no monochromatic S in K2N . Therefore, Rk+1(S) ≥ 2N + 1 = 2Rk(S) − 1 ≥ Rk(S) + |S| − 1 > Rk(S) + 3. Suppose that S is bipartite with each vertex class of size of at least 4. We add three new vertices x, y, z,to KN and join x, y, z to all other vertices (including x, y, z) with a new colour. It is easy to see that the resulting graph does not contain a monochromatic S, so Rk+1(S) ≥ Rk(S) + 3. From the proof of Theorem 1.3.2, we can deduce the following result. 124 9.3 Consequences of Theorem 1.3.2 Corollary 9.3.2. Let S be a graph with no isolated vertex satisfying one of the following: (i) S is not bipartite and |S| ≥ 5, or (ii) S is bipartite with each vertex classes of size at least 4, or (iii) S is bipartite and e(S) > 12. Then, there exists an integer t0(S) such that f(S, tK2) = Rt−1(S) for all t ≥ t0(S). Proof. By Proposition 9.3.1 and Theorem 1.3.2, the corollary is true for (i) and (ii) with t0(S) = 1. Suppose S satisfies (iii). We may also assume that one of its vertex classes has size at most 3, or else S satisfies (ii). Since e(S) > 12, ∆(S) ≥ 5 and so K1,5 ⊂ S. By a result of Burr and Roberts [8], Rk(K1,5) ≥ 4k+1 and so Rk(S) ≥ 4k + 1. Suppose f(S, 2K2) = R1(S) + c for some constant c. By mimicking the proof of Theorem 1.3.2, we can deduce that Rt−1(S) ≤ f(S, tK2) ≤ Rt−1(S)+max{0, c+2−t} for t ≥ 2. Thus, f(S, tK2) = Rt−1(S) for t ≥ c+2. Now we apply Theorem 1.3.2 to graphs G with known Rk(S). Unfortunately, the only graphs with known Rk(S) are star and matching. For S a matching, Rk(S) is already mentioned before(see Theorem 9.2.1). For S is star, Burr and Roberts [8] proved that Rk(K1,s) = { (s− 1)k + 1 if s is even and k is odd, (s− 1)k + 2 otherwise. Hence, together with Theorem 1.3.2, we have the following corollary. Corollary 9.3.3. For any integers s ≥ 4 and t ≥ 2, f(sK2, tK2) = (s− 1)t+ 2. 125 Chapter 9. Constrained Ramsey numbers For any integers s ≥ 5 and t ≥ 2, f(K1,s, tK2) = { (s− 1)(t− 1) + 1 if s is even and t is odd, (s− 1)(t− 1) + 2 otherwise. 2 This corollary improves both results of Eroh [21, 20]. Unfortunately, we are unable to prove f(3K2, tK2) = 2t + 2 as conjectured by Eroh. Instead, we have managed to show a weaker result. Proposition 9.3.4. For any positive integer t ≥ 3, f(3K2, tK2) ≤ 3t− 1. Proof. We proceed by induction on t. Bialostocki and Voxman [4] proved the case for t = 3. Thus, we may assume t > 3. Let N = 3t − 1. Let C be an edge colouring of KN with neither a monochromatic 3K2 nor a rainbow tK2. Let c1, c2, . . . be the colours of C. For an integer i, Gi denotes the subgraph induced by the edges with colour ci. Clearly, Gi does not contain a copy of 3K2. Modifying the proof of Claim 9.2.2, we have the following claim. Claim 9.3.5. For any edge e and vertex v, there exists an edge e′ independent of e and v with C(e) = C(e′). Now we claim that Gi is either a subgraph of K5 if it is connected or else it is isomorphic to two disjoint triangles. First suppose Gi is connected. We say a path in Gi is maximal if it cannot be extended to a longer path. Since Gi is 3K2-free, no path has length greater than 4. By Claim 9.3.5, any edge of e in Gi can be extended to a 2K2. Hence, all maximal paths have length exactly 4. Let p1p1 . . . p5 be a maximal path in Gi. In fact, p1p5 is also an edge in Gi by Claim 9.3.5 taking e = p2p3 and v = p4. Hence, p1p2 . . . p5 forms a 5-cycle in Gi. Thus, Gi is a subgraph of K5, for otherwise, there exists a 3K2 in Gi. Next, suppose Gi is not connected. It is easy to see that Gi has exactly two components with each component being either a star or a triangle. Suppose one of the components is a star. By taking the centre of the star as v and any edge in the other component as e, we obtain a contradiction to Claim 9.3.5. Hence, Gi is an union of two disjoint triangles. In summary, Gi is either a subgraph of K5 or isomorphic to 2K3. 126 9.3 Consequences of Theorem 1.3.2 Since N > f(3K2, (t − 1)K2), there is a rainbow (t − 1)K2, W := {xiyi : C(xiyi) = ci for 1 ≤ i ≤ t − 1}. Let H = KN\V (W ). Clearly, |H| = t + 1 and e(H) = t(t + 1)/2. Notice that H is coloured only with colours c1, . . . , ct−1, or else there exists a rainbow tK2. Also, Hi is a subgraph of a triangle, so e(Hi) ≤ 3 for 1 ≤ i ≤ t − 1. The number of colours used in H is at least e(H)/3 = t(t + 1)/6 > t− 1 as t > 3. This is a contradiction and completes the proof of the proposition. So far, the rainbow subgraph is always a matching. We would like to know whether f(S, T ) = Rt−1(S) is still true for T with a similar structure to a match- ing. It turns out that this is true if T = P3 ∪ (t− 2)K2 or T = P4 ∪ (t− 3)K2. Corollary 9.3.6. For a graph S and an integer t, f(S, P3 ∪ (t− 2)K2) ≤ max{f(S, tK2), 2t+ 1} if t ≥ 2, f(S, P4 ∪ (t− 3)K2) ≤ f(S, tK2) if t ≥ 3. Moreover, if S satisfies the hypothesis in Theorem 1.3.2, then equality holds. Proof. First, we evaluate f(S, P3 ∪ (t − 2)K2). It is easy to see that f(S, P3) = |S| ≤ f(S, 2K2), so it is true for t = 2. Thus, we may assume that t ≥ 3. Let N = max{f(S, tK2), 2t+ 1}. Consider an edge colouring C of KN without a monochromatic S. Since N ≥ f(S, tK2), there exists a rainbow tK2, say {xiyi : C(xiyi) = ci for 1 ≤ i ≤ t}. Let w be a vertex not in {xi, yi : 1 ≤ i ≤ t}. Note C(xiw) = ci for i = 1, . . . t, otherwise there exists a rainbow P3 ∪ (t − 2)K2. However, x1wx2 ∪ {xiyi : 3 ≤ i ≤ t} is a rainbow P3 ∪ (t − 2)K2. This is a contradiction and proves the first assertion of the corollary. Now suppose that N = f(S, tK2) with t ≥ 3. Let C be an edge colouring of KN without a monochromatic S. We are going to show that there exists a rainbow P4 ∪ (t− 3)K2. There exists a rainbow tK2, {xiyi : C(xiyi) = ci for 1 ≤ i ≤ t}. Clearly, if the graph induced by xi, yi, xj, yj contains an edge not coloured by either ci nor cj for some 1 ≤ i < j ≤ t, then there exists a rainbow P4∪(t−3)K2. Actually, it is sufficient to show that there exists a rainbow P4 with colours c1, c2, c3 in {x1, x2, x3, y1, y2, y3}. Without loss of generality, C(x1x2) = c1. Then 127 Chapter 9. Constrained Ramsey numbers y2y3 must be coloured by c2. If C(x1x3) = c1, x1x3y3y2 is rainbow. If C(x1x3) = c3, x3x1x2y2 is rainbow. Hence, the proof is complete. 128 Bibliography [1] R. Ahlswede and G. O. H. Katona, Graphs with maximal number of adjacent pairs of edges, Acta Math. Acad. Sci. Hungar. 32 (1978), 97–120. [2] N. Alon, T. Jiang, Z. Miller, and D. Pritikin, Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints, Random Struc- tures Algorithms 23 (2003), 409–433. [3] B. Andra´sfai, P. Erdo˝s, and V. T. So´s, On the connection between chromatic number, maximal clique and minimal degree of a graph, Discrete Math. 8 (1974), 205–218. [4] A. Bialostocki and W. Voxman, Generalizations of some Ramsey-type theo- rems for matchings, Discrete Math. 239 (2001), 101–107. [5] B. Bolloba´s, On complete subgraphs of different orders, Math. Proc. Cam- bridge Philos. Soc. 79 (1976), 19–24. [6] Be´la Bolloba´s, Extremal graph theory, London Mathematical Society Mono- graphs, vol. 11, Academic Press Inc. [Harcourt Brace Jovanovich Publishers], London, 1978. [7] S. Brandt, On the structure of dense triangle-free graphs, Combin. Probab. Comput. 8 (1999), 237–245. [8] S. A. Burr and J. A. Roberts, On Ramsey numbers for stars, Utilitas Math. 4 (1973), 217–220. [9] C. C. Chen, G. P. Jin, and K. M. Koh, Triangle-free graphs with large degree, Combin. Probab. Comput. 6 (1997), 381–396. 129 BIBLIOGRAPHY [10] L. H. Clark, R. C. Entringer, and L. A. Sze´kely, An inequality for degree sequences, Discrete Math. 103 (1992), 293–300. [11] E. J. Cockayne and P. J. Lorimer, The Ramsey number for stripes, J. Austral. Math. Soc. 19 (1975), 252–256. [12] D. Conlon, A new upper bound for diagonal ramsey numbers, Ann. of Math., 170 (2009), 941–960. 170 (2009), 941–960. [13] K. Ch. Das, Maximizing the sum of the squares of the degrees of a graph, Discrete Math. 285 (2004), 57–66. [14] D. de Caen, An upper bound on the sum of squares of degrees in a graph, Discrete Math. 185 (1998), 245–248. [15] P. Erdo˝s, On the number of complete subgraphs contained in certain graphs, Magyar Tud. Akad. Mat. Kutato´ Int. Ko¨zl. 7 (1962), 459–464. [16] , On the structure of linear graphs, Israel J. Math. 1 (1963), 156–160. [17] , On the number of complete subgraphs and circuits contained in graphs., Cˇasopis Peˇst. Mat. 94 (1969), 290–296. [18] P. Erdo¨s and R. Rado, A combinatorial theorem, J. London Math. Soc. 25 (1950), 249–255. [19] P. Erdo˝s and M. Simonovits, On a valence problem in extremal graph theory, Discrete Math. 5 (1973), 323–334. [20] L. Eroh, Constrained Ramsey numbers of matchings, J. Combin. Math. Com- bin. Comput. 51 (2004), 175–190. [21] , Rainbow Ramsey numbers of stars and matchings, Bull. Inst. Com- bin. Appl. 40 (2004), 91–99. [22] D. C. Fisher, Lower bounds on the number of triangles in a graph, J. Graph Theory 13 (1989), 505–512. 130 BIBLIOGRAPHY [23] A. W. Goodman, Triangles in a complete chromatic graph, J. Austral. Math. Soc. Ser. A 39 (1985), 86–93. [24] R. L. Graham and V. Ro¨dl, Numbers in Ramsey theory, Surveys in combi- natorics 1987 (New Cross, 1987), London Math. Soc. Lecture Note Ser., vol. 123, Cambridge Univ. Press, Cambridge, 1987, pp. 111–153. [25] A. Gya´rfa´s, J. Lehel, and R. H. Schelp, Finding a monochromatic subgraph or a rainbow path, J. Graph Theory 54 (2007), 1–12. [26] A. Gya´rfa´s, J. Lehel, R. H. Schelp, and Zs. Tuza, Ramsey numbers for local colorings, Graphs Combin. 3 (1987), 267–277. [27] R. Ha¨ggkvist, Odd cycles of specified length in nonbipartite graphs, Graph theory (Cambridge, 1981), North-Holland Math. Stud., vol. 62, North- Holland, Amsterdam, 1982, pp. 89–99. [28] R. E. Jamison, T. Jiang, and A. C. H. Ling, Constrained Ramsey numbers of graphs, J. Graph Theory 42 (2003), 1–16. [29] G. P. Jin, Triangle-free graphs with high minimal degrees, Combin. Probab. Comput. 2 (1993), 479–490. [30] G. Katona, A theorem of finite sets, Theory of graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, pp. 187–207. [31] J.B. Kruskal, The number of simplices in a complex, Mathematical optimiza- tion techniques, University of California Press, Berkeley, 1963. [32] P-S Loh and B. Sudakov, Constrained Ramsey numbers, Combin. Probab. Comput. 18 (2009), 247–258. [33] L. Lova´sz and M. Simonovits, On the number of complete subgraphs of a graph. II, Studies in pure mathematics, Birkha¨user, Basel, 1983, pp. 459– 495. [34] W. Mantel, Problem 28, solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W.A. Wythoff, Wiskundige Opgaven 10 (1907), 60–61. 131 BIBLIOGRAPHY [35] V. Nikiforov, The number of cliques in graphs of given order and size, https://umdrive.memphis.edu/vnikifrv/public/pdfs/Ni07n.pdf, Preprint. [36] , The sum of the squares of degrees: sharp asymptotics, Discrete Math. 307 (2007), 3187–3193. [37] D. Olpp, A conjecture of Goodman and the multiplicities of graphs, Australas. J. Combin. 14 (1996), 267–282. [38] F.P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. 30 (1929), 264–286. [39] A. A. Razborov, Flag algebras, J. Symbolic Logic 72 (2007), 1239–1282. [40] , On the minimal density of triangles in graphs, Combin. Probab. Comput. 17 (2008), 603–618. [41] A. Thomason, On finite Ramsey numbers, European J. Combin. 3 (1982), 263–273. [42] , An upper bound for some Ramsey numbers, J. Graph Theory 12 (1988), 509–517. [43] A. Thomason and P. Wagner, Complete graphs with no rainbow path, J. Graph Theory 54 (2007), 261–266. [44] M. Truszczyn´ski, Generalized local colorings of graphs, J. Combin. Theory Ser. B 54 (1992), 178–188. [45] P. Tura´n, Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok 48 (1941), 436–452. [46] P. Wagner, An upper bound for constrained Ramsey numbers, Combin. Probab. Comput. 15 (2006), 619–626. 132