Show simple item record

dc.contributor.advisorThomason, Andrew
dc.contributor.authorLo, Allan
dc.date.accessioned2011-06-03T11:07:04Z
dc.date.available2011-06-03T11:07:04Z
dc.date.issued2010-10-12
dc.identifier.otherPhD.33599
dc.identifier.urihttp://www.dspace.cam.ac.uk/handle/1810/237438
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/237438
dc.description.abstractThe 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$.en_GB
dc.language.isoenen_GB
dc.rightsAll Rights Reserveden
dc.rights.urihttps://www.rioxx.net/licenses/all-rights-reserved/en
dc.subjectExtremal Graph Theoryen_GB
dc.subjectCliquesen_GB
dc.subjectMinimum degreeen_GB
dc.titleCliques in graphsen_GB
dc.typeThesisen_GB
dc.type.qualificationlevelDoctoral
dc.type.qualificationnameDoctor of Philosophy (PhD)
dc.publisher.institutionUniversity of Cambridgeen_GB
dc.publisher.departmentDepartment of Pure Mathematics and Mathematical Statisticsen_GB
dc.identifier.doi10.17863/CAM.16216


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record