EPSRC logo

Details of Grant 

EPSRC Reference: EP/S00100X/1
Title: Approximate structure in large graphs and hypergraphs
Principal Investigator: Osthus, Professor D
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: School of Mathematics
Organisation: University of Birmingham
Scheme: Standard Research
Starts: 01 October 2018 Ends: 30 September 2021 Value (£): 327,343
EPSRC Research Topic Classifications:
Logic & Combinatorics
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
06 Jun 2018 EPSRC Mathematical Sciences Prioritisation Panel June 2018 Announced
Summary on Grant Application Form
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.

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.bham.ac.uk