EPSRC Reference: 
EP/M011771/1 
Title: 
Embeddings in hypergraphs 
Principal Investigator: 
Mycroft, Dr R 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
School of Mathematics 
Organisation: 
University of Birmingham 
Scheme: 
First Grant  Revised 2009 
Starts: 
30 March 2015 
Ends: 
29 March 2017 
Value (£): 
98,059

EPSRC Research Topic Classifications: 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 
Panel Date  Panel Name  Outcome 
10 Sep 2014

EPSRC Mathematics Prioritisation Panel Sept 2014

Announced


Summary on Grant Application Form 
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 NPcomplete 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 longstanding 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.

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 