EPSRC Reference: 
EP/P032125/1 
Title: 
The sparse hypergraph regularity method 
Principal Investigator: 
Allen, Dr P 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Mathematics 
Organisation: 
London School of Economics & Pol Sci 
Scheme: 
First Grant  Revised 2009 
Starts: 
01 October 2017 
Ends: 
30 September 2019 
Value (£): 
98,016

EPSRC Research Topic Classifications: 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 

Summary on Grant Application Form 
The broad aim of this project is to further our structural understanding of hypergraphs. To explain the concept of a hypergraph, we begin with graphs. A graph is an abstract structure which models twobody interactions, such as friendship in a social network, links in a physical network or street map, and so on. Pairs that interact are said to form an edge. We have a good understanding of how graphs behave, and in fact this underpins a large fraction of today's economy. To give just one prominent example, Google's success is mainly down to combinatorial optimisation  algorithms on graphs. In particular the PageRank algorithm, which got the company started, came from academic research into graph theory. One of the most important toolboxes in the branch of graph theory that studies extremal properties of graphs is the regularity method.
A graph cannot model multibody interactions. The abstract structure which does this is a hypergraph, where edges can contain more than two entities, and we do not have a good understanding of hypergraphs. There are some good theoretical reasons for this coming from Theoretical Computer Science: briefly, many fundamental computational problems on graphs are known to be soluble easily, whereas there are strong indications the same is not true for the hypergraph equivalents. But this is certainly not the whole story. One aspect where the deficiency can be overcome comes from extremal combinatorics. There is a regularity method for hypergraphs, but the development is not complete and the existing theory is very hard to apply. Part of this project is to complete the development and to simplify the theory in a way that allows for easy application, matching the state of the graph version.
A second part of this project  intimately linked with the above  is to develop a 'sparse version' of the hypergraph regularity theory. This is an attempt to address a general problem with the original regularity method: it only works for graphs which are 'dense', that is, where a significant fraction of pairs in the system are edges. This assumption is not the case for many real world examples, and it is also not the case for (hyper)graphs coming from probabilistic combinatorics, or from other areas of mathematics. The aim of this part of the project is to be able to deal with systems which are sparse, but 'look random'. At this stage in our understanding, it is not possible to avoid this last assumption. To give an example of where one can apply such a theory, the prime numbers 'look random', but they also thin out as one looks at larger and larger numbers  they are sparse. Some of the most wellknown problems in mathematics come from the prime numbers: how often do we find pairs of primes that differ by two? are all even numbers the sum of two primes? can we find 1,000,000 primes which form a sequence with equal gaps between each consecutive pair? The last of these problems was spectacularly solved by Green and Tao: we can. Recently, Conlon, Fox and Zhao explained that the solution really splits up into a numbertheoretic part and a part which is pure combinatorics  in fact, a problem which a rather basic sparse hypergraph regularity theory solves. Developing a full version of the same will thus bear fruit in the theory of prime numbers as well as discrete mathematics.
The final part of the project is to study the structure of paths and cycles in hypergraphs. These are again very well understood in graphs, and this understanding is a backbone of many more sophisticated proofs, including those using the regularity method. In hypergraphs, again we do not understand them well, and again obtaining such an understanding will complement work on the hypergraph regularity method perfectly.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

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.lse.ac.uk 