EPSRC Reference: 
EP/S00100X/1 
Title: 
Approximate structure in large graphs and hypergraphs 
Principal Investigator: 
Osthus, Professor D 
Other Investigators: 

Researcher CoInvestigators: 

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: 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 

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 nonbinary 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 socalled 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 nonacademic 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 