Abstract
dc:description.abstractIn this thesis, we study several combinatorial problems in which we aim to find upper or lower bounds on a certain quantity relating to graphs. The first problem is in Ramsey theory, while the others are in extremal graph theory. In Chapter 2, which is joint work with Vojtěch Dvořák, we consider the Ramsey number R(Fn) of the fan graph Fn, a graph consisting of $n$ triangles which all share a common vertex. Chen, Yu and Zhao showed that \frac{9}{2}n-5 \leq R(Fn) \leq \frac{11}{2}n+6. We build on the techniques that they used to prove the upper bound of $\frac{11}{2}n+6$, and adopt a more detailed approach to examining the structure of the graph. This allows us to improve the upper bound to $\frac{31}{6}n+15$. In Chapter 3, we work on a problem in graph colouring. Petruševski and Škrekovski recently introduced the concept of odd colouring, and the odd chromatic number of a graph, which is the smallest number of colours in an odd colouring of that graph. They showed that planar graphs have odd chromatic number at most $9$, and this bound was improved to $8$ by Petr and Portier. We consider the odd chromatic number of toroidal graphs, which are graphs that embed into a torus. By using the discharging method, along with detailed analysis of a remaining special case, we show that toroidal graphs have odd chromatic number at most $9$. In Chapter 4, which is joint work with Victor Souza, we consider a problem in the hypercube graph Qn. Huang showed that every induced subgraph of the hypercube with 2n-1+1 vertices has maximum degree at least $\lceil\sqrt{n}\rceil$, which resolved a major open problem in computer science known as the Sensitivity Conjecture. Huang asked whether analogous results could be obtained for larger induced subgraphs. For induced subgraphs of Qn with p2n vertices, we find a simple lower bound that holds for all $p$, and substantially improve this bound in the range $\frac{1}{2} < p < \frac{2}{3}$ by analysing the local structure of the graph. We also find constructions of subgraphs achieving the simple lower bound asymptotically when $p = 1-\frac{1}{r}$.
Degree
thesis:*- Name dc:type.qualificationname
- Doctor of Philosophy (PhD)
- Level dc:type.qualificationlevel
- Doctoral
- Grantor dc:publisher.institution
- University of Cambridge
- Year dc:date.issued
- 2023
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Metrebian, Robert
- Advisor dc:contributor.advisor
-
- Bollobas, Bela
Subjects
dc:subject × 6Rights
dc:rightsIdentifiers
dc:identifier.*- DOI dc:identifier.doi
- https://doi.org/10.17863/CAM.106774
- OAI identifier oai:identifier
- oai:www.repository.cam.ac.uk:1810/365520