Approximate structure in large graphs and hypergraphs

The study of graphs and other related combinatorial structures provides the theoretical foundation for the analysis of many networks arising in biology, theoretical computer science, big data analysis, scheduling and communication. In the simplest case, these networks give rise to a graph which consists of vertices, with suitable pairs of these vertices connected by edges. Hypergraphs arise when modelling non-binary relationships: instead of pairs we can also connect triples or larger vertex sets by a single hyperedge.

In many situations, the graphs or hypergraphs under consideration are huge, and it is hopeless to analyze them directly. However, an increasingly successful approach (both from a structural and algorithmic perspective) has been to consider approximations and then transfer knowledge about the approximate setting back to the original one. In this project, we will focus on `approximate' information gained by considering fractional solutions as well as hypergraph containers.

Approximation via fractional solutions: Combinatorial problems can frequently be viewed as integer programs, where it is often intractable to find the optimum solution. Finding a fractional solution (possibly on the same input, but often on a much smaller input) can be much simpler, and the goal is then to infer a good (approximate) solution to the original problem from this. We will develop a systematic approach in the setting of designs, latin squares and decomposition problems, as well as hypergraph matchings.

Approximations via containers: Many important problems involving e.g. number theory, colourings, random graphs, extremal combinatorics and coding theory can be formulated in terms of independent sets in suitably defined hypergraphs. The recently emerged method of hypergraph containers allows the succinct `approximation' of the collection of independent sets of a suitable given hypergraph by so-called containers. However, there are important problems where the general approach seems natural but the method currently fails e.g. because the number of containers is too large to be useful and so new ideas are required. We will develop an appropriate approach to solve such problems on the enumeration and typical structure of graphs satisfying given constraints.

Graphs and hypergraphs and other discrete structures underpin much of digital technology and society. Often, these (hyper)-graphs are extremely large, and determining their features directly is not feasible. This makes it important to develop the theory which describes the properties of such large networks and structures.

Attaining the objectives would significantly advance the respective areas and thus have considerable direct impact.
Indeed, they consist of central questions which would have been considered out of reach until recently, making the project very timely. For example, Objective F1 would form an essentially best possible generalization of Kirkman's theorem on Steiner triple systems (which dates back to the 19th century). Similarly, resilience (investigated as part of Objective F5) is a key property of many networks, but no rigorous results exist in the hypergraph setting so far.
As another example, Objective C1 would unify and generalize a number of difficult results on typical properties of induced-H-free graphs which have been proven over the past few decades.

Moreover, reaching the goals of the project will involve the development of tools and methods (in particular new ways of deriving fractional solutions and transferring these to the original problem; more general settings for container approximations). These should lead to further progress on related problems (some of these problems are mentioned in the pathways to impact document, the case for support and the beneficiaries summary).

The project has connections to several areas, including number theory, probability, design theory, as well as theoretical computer science. Correspondingly, this will ensure that its impact will not be restricted to a single area. The connection to computer science provides another opportunity for enhancing the impact of the project via the Alan Turing Institute (which the University of Birmingham is about to join). Indeed, the underlying theme of the project (i.e. the derivation of results based on the succinct representation of key features of a graph or hypergraph) is clearly related to the big data challenge, which forms a particular focus of the institute.

The Combinatorics, Probability and Algorithms group at the University of Birmingham offers a vibrant research environment. This will also enhance the professional development of the PDRA (as well as the PhD student) associated with the project. In particular, the frequent research visitors to the group will aid dissemination and thus enhance its impact.

I will make use of appropriate opportunities for supporting the dissemination and wider impact of the project, by giving talks to a broad range of researchers, by publishing in high-profile venues (again in a broad range of areas), by organizing a workshop, by personal interactions as well as making the results available online as soon as possible.