{"id":{"repo_id":"cambridge","oai_identifier":"oai:www.repository.cam.ac.uk:1810/237438"},"canonical_url":"https://search.dev.ndltd.org/etd/cambridge/oai:www.repository.cam.ac.uk:1810/237438","repository":{"repo_id":"cambridge","name":"Cambridge University","base_url":"https://api.repository.cam.ac.uk/server/oai/request"},"display":{"title":"Cliques in graphs","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. 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$.","abstract_html":"The main focus of this thesis is to evaluate <span class=\"etd-inline-math\">k<sub>r</sub>(n,&delta;)</span>, the minimal number of $r$-cliques in graphs with $n$ vertices and minimum degree~<span class=\"etd-inline-math\">&delta;</span>. A fundamental result in Graph Theory states that a triangle-free graph of order $n$ has at most <span class=\"etd-inline-math\">n<sup>2</sup>/4</span> edges. Hence, a triangle-free graph has minimum degree at most $n/2$, so if <span class=\"etd-inline-math\">k<sub>3</sub>(n,&delta;) =0</span> then <span class=\"etd-inline-math\">&delta; \\le n/2</span>. For <span class=\"etd-inline-math\">n/2 \\leq &delta; \\leq 4n/5</span>, I have evaluated <span class=\"etd-inline-math\">k<sub>r</sub>(n,&delta;)</span> and determined the structures of the extremal graphs. For <span class=\"etd-inline-math\">&delta; \\ge 4n/5</span>, I give a conjecture on <span class=\"etd-inline-math\">k<sub>r</sub>(n,&delta;)</span>, as well as the structures of these extremal graphs. Moreover, I have proved various partial results that support this conjecture. Let <span class=\"etd-inline-math\">k<sub>r</sub><sup>reg</sup>(n, &delta;)</span> be the analogous version of <span class=\"etd-inline-math\">k<sub>r</sub>(n,&delta;)</span> for regular graphs. Notice that there exist $n$ and <span class=\"etd-inline-math\">&delta;</span> such that <span class=\"etd-inline-math\">k<sub>r</sub>(n, &delta;) =0</span> but <span class=\"etd-inline-math\">k<sub>r</sub><sup>reg</sup>(n, &delta;) &gt;0</span>. For example, a theorem of Andr{\\&#x27;a}sfai, Erd{\\H{o}}s and S{\\&#x27;o}s states that any triangle-free graph of order $n$ with minimum degree greater than $2n/5$ must be bipartite. Hence <span class=\"etd-inline-math\">k<sub>3</sub>(n, \\lfloor n/2 \\rfloor) =0</span> but <span class=\"etd-inline-math\">k<sub>3</sub><sup>reg</sup>(n, \\lfloor n/2 \\rfloor) &gt;0</span> for $n$ odd. I have evaluated the exact value <span class=\"etd-inline-math\">k<sub>3</sub><sup>reg</sup>(n, &delta;)</span> for <span class=\"etd-inline-math\">&delta;</span> 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 <span class=\"etd-inline-math\">R<sub>k</sub>(G)</span> of a graph $G$ is the minimum number $N$, such that any edge colouring of <span class=\"etd-inline-math\">K<sub>N</sub></span> 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 <span class=\"etd-inline-math\">K<sub>N</sub></span> 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$, <span class=\"etd-inline-math\">f(G,tK<sub>2</sub>) =R<sub>t-1</sub>(G)</span> for $t \\geq 2$.","abstract_has_math":true,"creators":["Lo, Allan"],"institution":"University of Cambridge","degree_name":"Doctor of Philosophy (PhD)","degree_level":"Doctoral","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2010,"date_issued":"2010-10-12","date_published":"2010-10-12","updated_at":"2026-07-22T22:24:14Z","subjects":["Extremal Graph Theory","Cliques","Minimum degree"],"languages":["eng"],"rights":[],"rights_urls":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/e7f4b77c-d568-46ad-a04a-8e8576fc4f23/download","https://www.rioxx.net/licenses/all-rights-reserved/"],"identifier_entries":[]},"links":{"outbound_url":"https://doi.org/10.17863/CAM.16216","outbound_label":"DOI","outbound_source":"dc:identifier.doi"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Lo, Allan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2010-10-12"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Cambridge"]},{"key":"dc:relation.isreferencedby.uri","label":"Dc Relation Isreferencedby URI","values":["http://www.dspace.cam.ac.uk/handle/1810/237438","https://www.repository.cam.ac.uk/handle/1810/237438"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["Doctoral"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["Doctor of Philosophy (PhD)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Extremal Graph Theory","Cliques","Minimum degree"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/e7f4b77c-d568-46ad-a04a-8e8576fc4f23/download","https://www.rioxx.net/licenses/all-rights-reserved/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.doi","label":"DOI","values":["10.17863/CAM.16216"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/48548527-b2c4-4f8e-95bc-272d39c8b842/download"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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$."]},{"key":"dc:format.checksum.md5","label":"Dc Format Checksum Md5","values":["65098484fede078b19e2ad77aeea2c5f","48dcdf38f646da27e5e4bc6c1893d4fc"]},{"key":"dc:title","label":"Title","values":["Cliques in graphs"]}]}],"canonical_facts":{"dc:creator":["Lo, Allan"],"dc:date.issued":["2010-10-12"],"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. 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:format.checksum.md5":["65098484fede078b19e2ad77aeea2c5f","48dcdf38f646da27e5e4bc6c1893d4fc"],"dc:identifier.doi":["10.17863/CAM.16216"],"dc:identifier.uri":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/48548527-b2c4-4f8e-95bc-272d39c8b842/download"],"dc:language":["eng"],"dc:publisher.institution":["University of Cambridge"],"dc:relation.isreferencedby.uri":["http://www.dspace.cam.ac.uk/handle/1810/237438","https://www.repository.cam.ac.uk/handle/1810/237438"],"dc:rights":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/e7f4b77c-d568-46ad-a04a-8e8576fc4f23/download","https://www.rioxx.net/licenses/all-rights-reserved/"],"dc:subject":["Extremal Graph Theory","Cliques","Minimum degree"],"dc:title":["Cliques in graphs"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["Doctoral"],"dc:type.qualificationname":["Doctor of Philosophy (PhD)"]},"updated_at":"2026-07-22T22:24:14Z"}