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.

Publications

10 25 50
publication icon
Freddie Illingworth (2020) The chromatic profile of locally bipartite graphs in arXiv

publication icon
Freddie Illingworth (2021) Minimum degree stability of H-free graphs in arXiv

publication icon
Freddie Illingworth (2021) The chromatic profile of locally colourable graphs in arXiv

publication icon
Illingworth F (2021) Graphs with no Induced $K_{2, t}$ in The Electronic Journal of Combinatorics

publication icon
Illingworth F (2021) Graphs with no induced K-2,K-t

publication icon
Illingworth F (2022) The chromatic profile of locally bipartite graphs in Journal of Combinatorial Theory, Series B

publication icon
Illingworth F (2021) The Chromatic Structure of Dense Graphs

publication icon
Illingworth F (2020) The chromatic profile of locally bipartite graphs

Studentship Projects

Project Reference Relationship Related To Start End Student Name
EP/N509620/1 30/09/2016 29/09/2022
2114463 Studentship EP/N509620/1 30/09/2018 29/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