EPSRC Reference: 
EP/V002279/1 
Title: 
Matchings and tilings in graphs 
Principal Investigator: 
Treglown, Dr A C 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
School of Mathematics 
Organisation: 
University of Birmingham 
Scheme: 
Standard Research 
Starts: 
04 January 2021 
Ends: 
03 January 2024 
Value (£): 
313,311

EPSRC Research Topic Classifications: 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 

Summary on Grant Application Form 
Graph theory concerns the mathematical study of networks (such as computer networks, social networks and biological networks). Graphs consist of a set of vertices and a set of edges connecting some pairs of these vertices. In a realworld network it is often important to pair off resources. For example, one might wish to assign workers to different tasks, or donors to suitable patients. In the graph setting, these are examples of matching problems (a matching is a collection of disjoint edges in a graph). A perfect matching in a graph is a collection of disjoint edges that cover all the vertices in the graph. Perfect matchings in graphs are wellunderstood in the sense that one can efficiently determine (via an algorithm of Edmonds) whether a graph contains a perfect matching.
It is also natural to consider generalisations of the notion of a matching. For example, one may seek to split a workforce into collections of teams of a given size. This is an example of a perfect tiling problem in a graph. Alternatively, one may wish to assign employees to specific jobs based in various different locations. This is an example of a perfect matching problem in a 3partite 3graph (i.e. now edges consist of three, not two vertices).
In stark contrast to perfect matchings in graphs, it is believed that there is no efficient algorithm for finding such perfect tilings in graphs, nor for finding perfect matchings in 3graphs (and more generally in kgraphs for any whole number at least 3). Indeed, these are examples of NPcomplete problems; so finding such efficient algorithms would resolve one of the Millennium Prize Problems.
As such, an emergent research direction is to find general conditions that force a kgraph to contain a perfect matching, or force a graph to contain a perfect tiling. Underlying this approach are methods that often centre on the randomlike behaviour of dense graphs and kgraphs.
There are two key goals underpinning the research proposal. First, the project focuses on finding general classes of kgraphs where one can efficiently determine whether the kgraph contains a perfect matching. Second, we will investigate sufficient conditions that force a perfect tiling, as well as establishing how far away graphs of a given density can be from containing a perfect tiling. In particular, we will study perfect tilings in vertex ordered graphs (i.e. the vertices now have some given ordering). Unfortunately, some of the key randomlike properties of dense graphs do not extend to vertex ordered graphs. Thus, an aim of the project is to develop novel approaches that will in turn give us a better understanding of such properties in the ordered setting.

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 