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
*