Repository logo
 

Cliques in graphs


Type

Thesis

Change log

Authors

Lo, Allan 

Abstract

The main focus of this thesis is to evaluate kr(n,δ), the minimal number 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 structures 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 krreg(n,δ) be the analogous version of kr(n,δ) for regular graphs. Notice that there exist n and δ such that kr(n,δ)=0 but krreg(n,δ)>0. For example, a theorem of Andr{'a}sfai, Erd{\H{o}}s and S{'o}s states that any triangle-free graph of order n with minimum degree greater than 2n/5 must be bipartite. Hence k3(n,⌊n/2⌋)=0 but k3reg(n,⌊n/2⌋)>0 for n odd. I have evaluated the exact value k3reg(n,δ) for δ between 2n/5+12n/5 and n/2 and determined the structure of these extremal 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 monochromatic 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.

Description

Date

Advisors

Keywords

Extremal Graph Theory, Cliques, Minimum degree

Qualification

Doctor of Philosophy (PhD)

Awarding Institution

University of Cambridge