| EPSRC Reference: |
EP/P032125/1 |
| Title: |
The sparse hypergraph regularity method |
| Principal Investigator: |
Allen, Professor P |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Mathematics |
| Organisation: |
London School of Economics & Pol Sci |
| Scheme: |
First Grant - Revised 2009 |
| Starts: |
01 January 2018 |
Ends: |
31 December 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 two-body 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 multi-body 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 well-known 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 number-theoretic 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 non-academic 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 |