EPSRC logo

Details of Grant 

EPSRC Reference: EP/V048287/1
Title: Ramsey theory: an extremal perspective
Principal Investigator: Lo, Dr SA
Other Investigators:
Treglown, Dr A C
Researcher Co-Investigators:
Project Partners:
Department: School of Mathematics
Organisation: University of Birmingham
Scheme: Standard Research
Starts: 01 January 2022 Ends: 31 December 2024 Value (£): 313,513
EPSRC Research Topic Classifications:
Logic & Combinatorics
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
23 Feb 2021 EPSRC Mathematical Sciences Prioritisation Panel February 2021 Announced
Summary on Grant Application Form
The underlying motto of Ramsey theory is that "total disorder is impossible". This means that in a large mathematical structure we can find some unavoidable, non-random, substructure. For instance, the van der Waerden theorem dating from 1927 states that, in any partition of the whole numbers into two sets, one of the sets must contain a long arithmetic progression. Ramsey-type theorems also have roots in different branches of mathematics, and the theory developed from them has influenced diverse areas such as number theory, logic, probability theory, geometry and theoretical computer science.

The study of Ramsey theoretic questions has been especially fruitful in the context of graphs and hypergraphs. Here graphs consist of vertices and every pair of them may be joined by an edge. They are often used for studying social, infrastructure, telecommunication and biological networks. A typical Ramsey-type problem in graphs is to seek a monochromatic copy of a predetermined graph G in any red/blue-edge-colouring of a complete graph on n vertices. From the classical Ramsey theorem from 1930, we know that this statement holds providing n (the number of vertices in the complete graph) is sufficiently large. Determining the smallest such n, which is called the Ramsey number, is one of the most notorious open problem in combinatorics. When G is a complete graph on t vertices (with every pair of vertices joined by an edge), the Ramsey number is exponential in t. On the other hand, a conjecture of Burr and Erdos from 1973 states that if G is sparse, then its Ramsey number is only linear in the number of vertices. Tackling this conjecture has resulted in the development of powerful techniques and this conjecture has only been confirmed by a recent breakthrough of Lee.

However, much less is known for Ramsey theory for hypergraphs and in fact, only a handful of Ramsey numbers are known in this setting. Hypergraphs are natural generalisations of graphs, where edges consist of more than two vertices (rather than two as in the case of graphs). Hypergraphs are often used to model more complicated networks with non-binary relationships, for example, for chemical reactions and machine learning. However, hypergraphs behave very differently to graphs and many core techniques in graph theory have yet (or even fail) to extend to the hypergraph setting. For instance, depending on the sparseness being considered, the Ramsey number of a sparse hypergraph may be linear or exponential in term on the number of vertices.

The proposed research has three main strands. Firstly, to classify the families of sparse hypergraphs that have linear Ramsey numbers. Secondly, to study the behaviour of Ramsey numbers for hypergraphs with small expansion property. Thirdly, to develop a unified approach to the construction of monochromatic cycle partitions of edge-coloured hypergraphs. We anticipate that our methods (including a novel 'blueprint' approach to finding the required structures) will have further applications to related areas such as extremal hypergraph theory.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.bham.ac.uk