Embeddings in hypergraphs

The field of Combinatorics has seen a dramatic surge in prominence in recent years due to its extensive connections with other areas of mathematics and applications to other scientific disciplines. It is the foundation for much of Theoretical Computer Science, and so has underpinned the 'digital revolution' which has radically transformed our daily lives. Moreover, advances in both Physics and Biology have shown that much of the world around us is discrete in nature, and that combinatorial tools are crucial for increasing our understanding.

More specifically, this proposal relates to embeddings in hypergraphs: when is it possible to find some structure within a given hypergraph? A simple example is the matching problem: given some hypergraph G, what is the largest set M of edges of G we can choose so that no vertex of G lies in more than one member of M? Or put more simply: how many people can be allocated into compatible groups, given some constraints (represented by hyperedges) on which combinations of people can be grouped together? Such problems are often very simple to state but provide a general framework for many important questions from a diverse range of mathematical subjects including Optimisation, Number Theory, Probability Theory, Geometry, Algebra and Topology. Further afield, the matching problem is a fundamental problem of Theoretical Computer Science (one of Karp's original NP-complete problems), with important applications in that field, such as for distributed storage allocation and graph colouring. It also has significant connections to Statistical Physics and Computational Chemistry.

Until now, such problems have been poorly understood for hypergraphs (whereas much more is known for the graph case), a difficulty which is intrinsically connected to the computational intractability of the problem. However, recent advances and novel techniques developed over the past few years, including some of my own work, have opened up many new approaches in this area; crucial long-standing conjectures which had seen very little progress for many years are seeing major steps forward towards their solutions. The thesis of this proposal is that these advances, taken together, form the beginnings of a general theory of embeddings in hypergraphs. My aim is to further develop this theory, which will include the solution of several key problems in this area.

I am keen to ensure that the potential impact of this project is realised to the fullest possible extent, in the following ways.

Firstly, my aim is that the legacy of this project will be a long-term boost to the UK scientific community at the intersection of Combinatorics and Theoretical Computer Science. In recent years this has been frequently identified as a weakness in the UK academic landscape (for example, in the 2004 and 2010 IRMS, and the 2012 EPSRC Pure Maths Workshop). Promoting this exciting area of research is something that I will keep in mind throughout all public dissemination of the research. In particular, I will organise a one-day workshop for UK researchers in this area, with the aim of highlighting current research progress and encouraging broader research collaborations outside the confines of this specific project.

At a less advanced level, I will run a series of master classes for 14-18 year old school students on materials related to this project. I see this as an ideal time for such community activities due to the increased focus on computer science among this age group, with a new computer science curriculum to be introduced in UK schools this autumn, and with initiatives such as the Raspberry Pi enjoying widespread popularity. The goal of these masterclasses will be to inspire interested students to develop their interests in mathematics and computer science to the fullest extent. Crucially, I hope to demonstrate the extent to which mathematics and computer science are inter-connected, counteracting the too-frequent tendency of students in the UK education system to view separate subjects as distinct and unrelated.

This project will also contribute to the mathematical development of talented early-career mathematicians, through my role as a mentor to the postdoctoral research associate and my supervisory responsibilities for at least two PhD students (each of whom I hope will contribute to the outlined research programme).

Advances in Mathematics often take many years to bear fruit in applications relevant to our daily lives, and these applications are often surprising and totally unforeseen. However, there are a number of applications towards which we can expect the proposed research to contribute. For example, recent research has highlighted the strong connections between hypergraph matching problems and the distributed storage allocation problem: a better understanding of hypergraph matchings, such as the theory outlined in this proposal, would hopefully allow for significantly improved solutions for the latter problem to be obtained in less time.