The sparse hypergraph regularity method

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.

Graphs provide a general abstract framework for modelling two-body interactions. Such interactions play a role in a wide range of areas. Chemical bonds are often interactions between two atoms, giving molecular graphs. Friendship between people is binary, giving rise to social networks. Links between places make a street map, between connected devices form the internet, and between web pages are the world wide web, all of which are well modelled by graphs. Our basic understanding of graph theory underpins much of the technology and tools that make modern life possible. To give a particularly striking example, the study of spectral graph theory, the understanding of graph properties using tools from linear algebra, began as a purely academic field of study in the 1950s. It developed steadily, primarily as a branch of pure mathematics with not much thought to applications. Then in 1996 its methods inspired the PageRank algorithm which set Google on the path to the company it is today.

This proposal is to develop our structural understanding of hypergraphs. Hypergraphs generalise graphs, allowing us to model multi-body interactions. Molecular graphs do not correctly model aromaticity; this phenomenon is an interaction of multiple atoms. Chemical reaction networks in bioinformatics typically involve several molecules entering into each reaction. When one is confronted with the task of pulling useful information from a mass of big data, simple correlations may be quite easy to find; correlations involving multiple factors are harder. Finally, many parts of today's technology are based on classical combinatorial optimisation solutions, but the problems solved are often not quite what we would like to solve. For example, we would like to match people to jobs, or schedule meetings - the simple versions of these problems are modelled by graphs and can be solved efficiently. But in practice, there are always more constraints. A couple want jobs, but the jobs should not be on different continents. We would like to schedule a series of meetings to resolve a dispute, but some pairs of people should not attend the same meeting. These constraints are naturally formulated as optimisation problems on hypergraphs, and here there is an uneasy tension between the theory and practice. In theory, we believe these problems cannot be solved efficiently. In practice, we have methods which work well for some problems, and it is often not very clear why, or why we cannot solve other problems well in practice. To do better in practice, we surely need to understand the underlying structure better. This proposal is aimed at contributing to that understanding. We are very much in the early stages, and a substantial time-lapse between theoretical effort and practical output (as with spectral graph theory and PageRank) is to be expected; one can only hope that the payoff will be comparable.

Within mathematics, the situation is much clearer. The proposed research will be immediately useful within discrete mathematics. In other parts of mathematics, whenever one is working with a structure that exhibits random-like characteristics, it may be possible to apply the theory I propose to develop. Most prominently, the study of additive patterns in the prime numbers is an example of multi-party interactions in a sparse pseudorandom system. Prime number theory is a very active topic in mathematics, with work driven by the goal of solving famous open problems such as the twin prime conjecture or Goldbach's conjecture, and with several recent breakthroughs. At a more general level, `working with a random-like structure' describes a major part of modern mathematics. The sum-product phenomenon, the infamous abc conjecture in number theory, and Weil's bound from algebraic geometry, are all good examples.

Outside of mathematics, the research is directly relevant in theoretical computer science, in particular in the areas of algorithm design and property testing.