Cliques in graphs

The main focus of this thesis is to evaluate k_r(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 n²/4 edges. Hence, a triangle-free graph has minimum degree at most $n/2$, so if k₃(n,δ) =0 then δ \le n/2. For n/2 \leq δ \leq 4n/5, I have evaluated k_r(n,δ) and determined the structures of the extremal graphs. For δ \ge 4n/5, I give a conjecture on k_r(n,δ), as well as the structures of these extremal graphs. Moreover, I have proved various partial results that support this conjecture. Let k_r^reg(n, δ) be the analogous version of k_r(n,δ) for regular graphs. Notice that there exist $n$ and δ such that k_r(n, δ) =0 but k_r^reg(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 k₃(n, \lfloor n/2 \rfloor) =0 but k₃^reg(n, \lfloor n/2 \rfloor) >0 for $n$ odd. I have evaluated the exact value k₃^reg(n, δ) for δ between $2n/5+12 \sqrt{n}/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 R_k(G) of a graph $G$ is the minimum number $N$, such that any edge colouring of K_N 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 K_N 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,tK₂) =R_t-1(G) for $t \geq 2$.

Name dc:type.qualificationname

Doctor of Philosophy (PhD)

Level dc:type.qualificationlevel

Doctoral

Grantor dc:publisher.institution

University of Cambridge

Year dc:date.issued

2010

Author dc:creator

• Lo, Allan

• Extremal Graph Theory
• Cliques
• Minimum degree

Licence

• https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/e7f4b77c-d568-46ad-a04a-8e8576fc4f23/download
• https://www.rioxx.net/licenses/all-rights-reserved/

Language dc:language

eng

DOI dc:identifier.doi

https://doi.org/10.17863/CAM.16216

OAI identifier oai:identifier

oai:www.repository.cam.ac.uk:1810/237438