Combinatorial applications of containers
Lead Research Organisation:
University of Cambridge
Department Name: Pure Maths and Mathematical Statistics
Abstract
The student will study combinatorial questions, principally in graph theory, with a particular eye on the development and application of the newly discovered theory of containers. This theory has led to many recent advances but developments and improvements in the methods would be of great value.
People |
ORCID iD |
| Freddie Illingworth (Student) |
 http://orcid.org/0000-0001-5350-2379
|
Studentship Projects
| Project Reference | Relationship | Related To | Start | End | Student Name |
|---|---|---|---|---|---|
| EP/N509620/1 | 01/10/2016 | 30/09/2022 | |||
| 2114463 | Studentship | EP/N509620/1 | 01/10/2018 | 30/09/2021 | Freddie Illingworth |
| Description | The focus of this research was on the structure of graphs (networks) where every vertex (node) has lots of neighbours -- a `dense' graph. In particular, we consider dense graphs with certain local properties and ask what information can be deduced about the macroscopic global structure of the graph. Examples of local properties covered include not containing some fixed small graph, for example, not containing a triangle. The macroscopic global structure we are looking for is a partition of the whole graph into a small number of parts such that each part has vanishingly few edges inside it. This is related to the chromatic number of the graph -- the fewest colours required to colour a graph so that adjacent vertices have distinct colours. We determined the smallest density which guarantees that graphs satisfying the local property must also satisfy this global property. |
| Exploitation Route | The study of graphs satisfying local properties has a rich history with applications in number theory, cryptography and computer science. The results here answer a very natural question which is applicable in many cases. |
| Sectors | Digital/Communication/Information Technologies (including Software),Other |
| URL | https://arxiv.org/abs/2102.11104 |
| Description | Chromatic numbers of triangle-free graphs |
| Organisation | University of Colorado Boulder |
| Country | United States |
| Sector | Academic/University |
| PI Contribution | Research time as part of a collaboration with Ewan Davies |
| Collaborator Contribution | Research time |
| Impact | Collaborated with Ewan Davies of CU Boulder at the Sparse Graphs Coalition Entropy compression workshop to improve the upper bound for the list-chromatic number of triangle-free graph on n vertices. We have improved this upper bound from order sqrt(n) to order sqrt(n/log(n)) which is tight up to a constant. |
| Start Year | 2021 |