Matchings and tilings in graphs

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 real-world 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 well-understood 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 3-partite 3-graph (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 3-graphs (and more generally in k-graphs for any whole number at least 3). Indeed, these are examples of NP-complete 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 k-graph to contain a perfect matching, or force a graph to contain a perfect tiling. Underlying this approach are methods that often centre on the random-like behaviour of dense graphs and k-graphs.

There are two key goals underpinning the research proposal. First, the project focuses on finding general classes of k-graphs where one can efficiently determine whether the k-graph 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 random-like 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.

The main immediate impact of this project will be to the academic community working in the study of graph matchings and tilings, a subject in extremal combinatorics with particular connections to theoretical computer science.

The proposed objectives are widely viewed as fundamental questions in extremal combinatorics. For example, the topic of perfect matching in hypergraphs is one of the most intensively studied branches of extremal combinatorics. Results related to Objective A1 have been obtained by leading mathematicians including Noga Alon, Peter Frankl, Peter Keevash, Daniela Kühn, Deryk Osthus, Vojtech Rödl, Andrzej Rucinski, Mathias Schacht and Benny Sudakov.

To tackle the objectives in Programme B of the proposal we will transfer and develop methods from the (unordered) graph setting into the ordered graph setting. In particular, Szemerédi's regularity lemma has hundreds of applications in the study of graphs, but some of its key properties do not extend to the ordered setting. We will refine the regularity method so that it is broadly applicable to vertex ordered graphs. Thus, progress here is likely to have impact on the research of other mathematicians working in this area.

Moreover, the research programme will lay the ground for future work: Programme A considers the problem of finding classes of k-graphs where one can efficiently determine whether the k-graph has a perfect matching. Leading on from this, it is natural to consider the analogous problem for k-partite k-graphs; indeed, such k-graphs naturally arise when studying job and resource assignment. Similarly, with the methods we will develop, there is significant scope to go beyond Programme B. For example, it is natural to seek minimum degree conditions that force other (non-connected) spanning structures in vertex ordered graphs, as well as considering analogous questions in the setting of edge ordered graphs.

An important route to maintaining and enhancing the strength of UK research is to develop stronger links with international research centres of excellence. The University of Birmingham has identified the strategic alliance with the University of Illinois at Urbana-Champaign as a platform to achieve this. Through collaborative research visits we will help develop this partnership.

The project will help to maintain and strengthen the United Kingdom's research capacity at the interface of extremal combinatorics and theoretical computer science. To facilitate this, we will organise a one-day workshop on complexity questions arising in extremal combinatorics, with the aim of fostering future collaborations between combinatorialists and theoretical computer scientists.

Another pathway to enhance the impact of this project is by nurturing early-career research talent. The postdoctoral research assistant associated with the project, as well as the PhD students we supervise, will gain expertise in an area of research of significant importance to the UK research landscape; a theory that has numerous real-world applications in job and resource assignment. We will additionally support the PDRA and our PhD students to find suitable follow-up research positions.

A workforce highly skilled in the mathematical sciences is crucial to the health of the economy. For example, a Deloitte report estimated that the contribution of the mathematical sciences to the UK economy in 2010 was around £208 billion in terms of Gross Value Added. However, an International Survey of Adult Skills led the OECD to conclude that "The talent pool of highly skilled adults in England and Northern Ireland is likely to shrink relative to that of other countries". Through the outreach activities associated with the proposal we aim to inspire young people to study mathematics further and ultimately have careers that make use of their mathematical skills.