Properties of extremal and random hypergraphs

This research proposal addresses fundamental questions in the field of combinatorics, a branch of mathematics devoted to the study of discrete structures. One key concept in combinatorics is the notion of a graph. This is an abstract representation of a network, consisting of points called vertices, some pairs of which are connected by lines called edges. Graphs can be used to model all kinds of real-world networks, both physical (e.g. telephone networks, road networks) and abstract (e.g. social networks, food chains), and consequently are exceptionally useful in applications. However, for many purposes it is unduly restrictive to only allow connections of pairs of vertices; this observation leads to the more general notion of a hypergraph, in which we allow edges of three or more vertices. This definition gives a highly versatile concept, with a wide range of applications within mathematics and other areas. The usefulness of this definition is the motivation for this research project, the main focus of which is to study two important characteristics of hypergraphs.

The first characteristic we study is that of edit distance. This is a simple metric which, given two graphs or hypergraphs with the same vertices, provides a measure of how similar or different they are. Measuring distance like this arises naturally in many settings, for example in the study of metabolic pathways or phylogenetic trees in Biology. Our focus is on how far (in terms of edit distance) a hypergraph can be from hypergraphs satisfying a hereditary property. Here a hereditary property means a property such that even if we delete some vertices from the hypergraph then the part of the hypergraph which remains still satisfies the property; most useful characteristics of graphs and hypergraphs yield properties of this type. For graphs, a seminal theorem of Alon and Stav states that the maximum distance is attained by a random graph, in which we fix a set of vertices and add edges between each pair at random with a given probability and independently of other edges. By contrast, very little is known about this problem in the case of hypergraphs; our principal goal here is to understand this case and develop a theory of edit distances in hypergraphs which generalises the theory for graphs.

The other characteristic which we study is whether a large hypergraph contains within it a large fixed structure. More precisely we seek to find conditions on the hypergraph which ensure that it contains this structure. One simple possible structure we could ask for is a large collection of non-overlapping edges; we call this a matching. Many important questions from diverse areas of mathematics and other disciplines can be rephrased in terms of finding matchings in hypergraphs, and consequently mathematicians have developed some understanding of conditions which ensure a matching of a given size (though many important questions remain open). However, for connected structures (in which we can get from any edge to any other edge by a sequence of overlapping edges) we know far less. In recent work the PI and his co-authors developed new techniques for finding large connected structures in hypergraphs, and a key goal of this project is to further develop these techniques and to use them to solve a range of open problems in this area.

The objectives of this project are widely viewed as important fundamental questions. Theoretical advances in similar areas of mathematics often bear fruit over very long time-frames to provide vital applications in ways which would have seemed unimaginable at the time that the research was carried out, and such applications cannot be reliably predicted. For example, the hypergraph regularity method was originally introduced to give a new proof of Szemerédi's theorem on arithmetic progressions, but has since found numerous important applications such as for property-testing. Moreover, the broad topics of this proposal have already proved to be useful in other disciplines.

For example, edit distances between graphs in which vertices represent genes and edges correspond to interactions between pairs of genes play an important role in the study of metabolic networks in biology, whilst edit distances in certain auxiliary bipartite graphs have been used to identify consensus trees in the study of phylogenetics in evolutionary biology. Hypergraphs are mathematical objects which generalise the notion of a graph in a way which allows more complex interrelations between objects to be studied, as we are no longer restricted only to representing connections or relations just between pairs of objects. In principle the additional complexities of hypergraphs should therefore allow the representation of more complex real-world scenarios. A key objective of this research proposal is to develop a good understanding of edit distances in hypergraphs to generalise that for the graph case to provide the underlying theory for applications of this form.

Likewise, the problem of embedding matchings in hypergraphs has found numerous applications in mathematics and elsewhere, such as for the distributed storage allocation problem. A key obstacle to providing a general theory of embeddings in hypergraphs has been the difficulty of handling connected structures. A major goal of this project is to overcome this obstacle by developing methods for embedding large connected structures in hypergraphs. As well as enabling the solution of important open problems in combinatorics, this would provide a more general embedding tool for use in applications.

This project will also strengthen the links between the extremal combinatorics and theoretical computer science communities in the UK, which has been recognised as a pressing need in various reports into the UK scientific community, including the 2004 and 2010 IRMS, the 2012 EPSRC Pure Maths Workshop, and the 2016 EPSRC Community Overview. Indeed, this proposal addresses significant questions in both fields, and the methods used are directly relevant to both areas. To help maximise the impact in this direction, this project includes funds for a 3-day workshop to bring together leading experts working at the intersection of these two fields to exchange knowledge and develop new collaborations. Beyond this, this proposal will contribute to the mathematical development of talented early-career mathematicians, through my role as a mentor to the postdoctoral research associate and PhD students under my supervision. At a more junior level, I will run a series of outreach events for 14-18-year-old school students based around topics from this project, aiming to inspire the participants to pursue further study in mathematics or theoretical computer science.