dc.contributor.advisor Thomason, Andrew dc.contributor.author Lo, Allan dc.date.accessioned 2011-06-03T11:07:04Z dc.date.available 2011-06-03T11:07:04Z dc.date.issued 2010-10-12 dc.identifier.other PhD.33599 dc.identifier.uri http://www.dspace.cam.ac.uk/handle/1810/237438 dc.identifier.uri https://www.repository.cam.ac.uk/handle/1810/237438 dc.description.abstract The main focus of this thesis is to evaluate $k_r(n,\delta)$, the minimal number of $r$-cliques in graphs with $n$ vertices and minimum degree~$\delta$. A fundamental result in Graph Theory states that a triangle-free graph of order $n$ has at most $n^2/4$ edges. Hence, a triangle-free graph has minimum degree at most $n/2$, so if $k_3(n,\delta) =0$ then $\delta \le n/2$. For $n/2 \leq \delta \leq 4n/5$, I have evaluated $k_r(n,\delta)$ and determined the structures of the extremal graphs. For $\delta \ge 4n/5$, I give a conjecture on $k_r(n,\delta)$, 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, \delta)$ be the analogous version of $k_r(n,\delta)$ for regular graphs. Notice that there exist $n$ and $\delta$ such that $k_r(n, \delta) =0$ but $k_r^{reg}(n, \delta) >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_3(n, \lfloor n/2 \rfloor) =0$ but $k_3^{reg}(n, \lfloor n/2 \rfloor) >0$ for $n$ odd. I have evaluated the exact value $k_3^{reg}(n, \delta)$ for $\delta$ between $2n/5+12 \sqrt{n}/5$ and $n/2$ and determined the structure of these extremal graphs. en_GB 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_2) =R_{t-1}(G)$ for $t \geq 2$. dc.language.iso en en_GB dc.rights All Rights Reserved en dc.rights.uri https://www.rioxx.net/licenses/all-rights-reserved/ en dc.subject Extremal Graph Theory en_GB dc.subject Cliques en_GB dc.subject Minimum degree en_GB dc.title Cliques in graphs en_GB dc.type Thesis en_GB dc.type.qualificationlevel Doctoral dc.type.qualificationname Doctor of Philosophy (PhD) dc.publisher.institution University of Cambridge en_GB dc.publisher.department Department of Pure Mathematics and Mathematical Statistics en_GB dc.identifier.doi 10.17863/CAM.16216
﻿