{"id":{"repo_id":"cambridge","oai_identifier":"oai:www.repository.cam.ac.uk:1810/365520"},"canonical_url":"https://search.dev.ndltd.org/etd/cambridge/oai:www.repository.cam.ac.uk:1810/365520","repository":{"repo_id":"cambridge","name":"Cambridge University","base_url":"https://api.repository.cam.ac.uk/server/oai/request"},"display":{"title":"Results in Ramsey theory and extremal graph theory","abstract":"In 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(F_n)$ of the fan graph $F_n$, 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(F_n) \\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 $Q_n$. Huang showed that every induced subgraph of the hypercube with $2^{n-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 $Q_n$ with $p2^n$ 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}$.","abstract_html":"In 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 <span class=\"etd-inline-math\">R(F<sub>n</sub>)</span> of the fan graph <span class=\"etd-inline-math\">F<sub>n</sub></span>, a graph consisting of $n$ triangles which all share a common vertex. Chen, Yu and Zhao showed that <span class=\"etd-inline-math\">\\frac{9}{2}n-5 \\leq R(F<sub>n</sub>) \\leq \\frac{11}{2}n+6</span>. 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 <span class=\"etd-inline-math\">Q<sub>n</sub></span>. Huang showed that every induced subgraph of the hypercube with <span class=\"etd-inline-math\">2<sup>n-1</sup>+1</span> 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 <span class=\"etd-inline-math\">Q<sub>n</sub></span> with <span class=\"etd-inline-math\">p2<sup>n</sup></span> vertices, we find a simple lower bound that holds for all $p$, and substantially improve this bound in the range $\\frac{1}{2} &lt; p &lt; \\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}$.","abstract_has_math":true,"creators":["Metrebian, Robert"],"institution":"University of Cambridge","degree_name":"Doctor of Philosophy (PhD)","degree_level":"Doctoral","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Bollobas, Bela"],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-08-01","date_published":"2023-08-01","updated_at":"2026-07-22T22:24:17Z","subjects":["Combinatorics","Extremal graph theory","Graph colouring","Mathematics","Pure Mathematics","Ramsey theory"],"languages":["eng"],"rights":[],"rights_urls":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/c77adbe0-9da4-4aeb-9be9-50f87837a9f9/download","https://www.rioxx.net/licenses/all-rights-reserved/"],"identifier_entries":[]},"links":{"outbound_url":"https://doi.org/10.17863/CAM.106774","outbound_label":"DOI","outbound_source":"dc:identifier.doi"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Bollobas, Bela"]},{"key":"dc:contributor.sponsor","label":"Sponsor","values":["Trinity Internal Graduate Studentship"]},{"key":"dc:creator","label":"Author","values":["Metrebian, Robert"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.issued","label":"Date","values":["2023-08-01"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Cambridge"]},{"key":"dc:relation.isreferencedby.uri","label":"Dc Relation Isreferencedby URI","values":["https://www.repository.cam.ac.uk/handle/1810/365520"]},{"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":["Combinatorics","Extremal graph theory","Graph colouring","Mathematics","Pure Mathematics","Ramsey theory"]}]},{"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/c77adbe0-9da4-4aeb-9be9-50f87837a9f9/download","https://www.rioxx.net/licenses/all-rights-reserved/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.doi","label":"DOI","values":["https://doi.org/10.17863/CAM.106774"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/5317011a-a864-482d-a193-8ac9dcffd59e/download"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["In 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(F_n)$ of the fan graph $F_n$, 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(F_n) \\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 $Q_n$. Huang showed that every induced subgraph of the hypercube with $2^{n-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 $Q_n$ with $p2^n$ 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}$."]},{"key":"dc:format.checksum.md5","label":"Dc Format Checksum Md5","values":["87eda9de84448d1f82354d60eee3eb5f","54bf3edcf7e033b664cda9ed62737143"]},{"key":"dc:title","label":"Title","values":["Results in Ramsey theory and extremal graph theory"]}]}],"canonical_facts":{"dc:contributor.advisor":["Bollobas, Bela"],"dc:contributor.sponsor":["Trinity Internal Graduate Studentship"],"dc:creator":["Metrebian, Robert"],"dc:date.issued":["2023-08-01"],"dc:description.abstract":["In 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(F_n)$ of the fan graph $F_n$, 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(F_n) \\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 $Q_n$. Huang showed that every induced subgraph of the hypercube with $2^{n-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 $Q_n$ with $p2^n$ 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}$."],"dc:format.checksum.md5":["87eda9de84448d1f82354d60eee3eb5f","54bf3edcf7e033b664cda9ed62737143"],"dc:identifier.doi":["https://doi.org/10.17863/CAM.106774"],"dc:identifier.uri":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/5317011a-a864-482d-a193-8ac9dcffd59e/download"],"dc:language":["eng"],"dc:publisher.institution":["University of Cambridge"],"dc:relation.isreferencedby.uri":["https://www.repository.cam.ac.uk/handle/1810/365520"],"dc:rights":["https://apollo8-f-pro.lib.cam.ac.uk/bitstreams/c77adbe0-9da4-4aeb-9be9-50f87837a9f9/download","https://www.rioxx.net/licenses/all-rights-reserved/"],"dc:subject":["Combinatorics","Extremal graph theory","Graph colouring","Mathematics","Pure Mathematics","Ramsey theory"],"dc:title":["Results in Ramsey theory and extremal graph theory"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["Doctoral"],"dc:type.qualificationname":["Doctor of Philosophy (PhD)"]},"updated_at":"2026-07-22T22:24:17Z"}