2026-09-22T13:05:32Zhttps://api.repository.cam.ac.uk/server/oai/request

oai:www.repository.cam.ac.uk:1810/2374382024-06-27T12:32:35Zcom_1810_213747com_1810_256064col_1810_213748

Cliques in graphs 10.17863/CAM.16216 Lo, Allan 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. 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$. University of Cambridge 2010-10-12 Thesis Doctoral Doctor of Philosophy (PhD) eng http://www.dspace.cam.ac.uk/handle/1810/237438 https://www.repository.cam.ac.uk/handle/1810/237438 https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/48548527-b2c4-4f8e-95bc-272d39c8b842/download 65098484fede078b19e2ad77aeea2c5f https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/e7f4b77c-d568-46ad-a04a-8e8576fc4f23/download 48dcdf38f646da27e5e4bc6c1893d4fc https://www.rioxx.net/licenses/all-rights-reserved/ Extremal Graph Theory Cliques Minimum degree