Hypergraph matchings

Description: Matching theory is a large field with many directions of research, both in practical algorithms and combinatorial theory. It provides a rich and flexible setting that incorporates many mathematical problems, often in unexpected ways. It has also occupied a fundamental position in Operations Research and Theoretical Computer Science, through the design of numerous algorithms, and the foundations of complexity theory (hypergraph matching was one of Karp's original list of NP-complete problems). Many of its questions require hypergraph versions of known results for graphs, which are currently unknown - this project will address some of these important open problems. The primary impact lies in contributing to the research environment in Combinatorics within the UK, thus maintaining its excellent international standing, and also developing the base on which numerous other fields of research build when finding applications of the underlying mathematical theory.

Aims and objectives: This project aims to obtain hypergraph generalisations of results on matchings in graphs, in various settings, such as deterministic or random, and within several themes, including obtaining extremal results and understanding typical structures. As such, it seeks to push back the boundary of knowledge in several directions of current research in combinatorics, and is aligned with important trends in the field, such as refining extremal results to obtain structural results, and transferring ideas from dense settings to settings that are sparse (and often random).

Novelty of the research methodology: The research methodology seeks to build on and further develop two important and very recent ideas that have sparked much exciting progress in Extremal Combinatorics, namely Randomised Algebraic Construction and Iterative Absorption. Randomised Algebraic Construction was developed in 2014 by Keevash to prove the Existence Conjecture for Combinatorial Designs. Iterative Absorption, as applied by Kuhn and Osthus, and many of their collaborators, represents the most recent refinement of the Absorbing Method of Rodl, Rucinski and Szemeredi, and had spectacular success in proving a range of conjectures in Combinatorics (and also a new proof of the Existence of Designs by Glock, Kuhn, Lo and Osthus).

Alignment: This project falls within the EPSRC "Logic and Combinatorics" research area within "Mathematical Sciences". It is related to the Digital Economy Theme, through the interface of Combinatorics with Theoretical Computer Science, which has been repeatedly identified as a priority area for mathematical research in the UK, for example by the 2010 International Review of Mathematical Sciences.