Report

Teaser, summary, work performed and final results

Periodic Reporting for period 2 - CC (Combinatorial Construction)

Teaser

\"Combinatorial Construction is a mathematical challenge with many applications. Examples include the construction of networks that are very sparse but highly connected, or codes that can correct many transmission errors with little overhead in communication costs. For a...

Summary

\"Combinatorial Construction is a mathematical challenge with many applications. Examples include the construction of networks that are very sparse but highly connected, or codes that can correct many transmission errors with little overhead in communication costs. For a general class of combinatorial objects, and some desirable property, the fundamental question in Combinatorial Construction is to demonstrate the existence of an object with the property, preferably via an explicit algorithmic construction. Thus it is ubiquitous in Computer Science, including applications to expanders, sorting networks, distributed communication, data storage, codes, cryptography and derandomisation. In popular culture it appears as the unsolved \"\"lottery problem\"\" of determining the minimum number of tickets that guarantee a prize. In 2014 I proved the Existence Conjecture for combinatorial designs, via a new method of Randomised Algebraic Constructions; this result has already attracted considerable attention in the mathematical community. The significance is not only in the solution of a problem posed by Steiner in 1852, but also in the discovery of a powerful new method, that promises to have many further applications in Combinatorics, and more widely in Mathematics and Theoretical Computer Science. The aim of this project is to resolve many other problems of combinatorial construction.

\"

Work performed

Significant progress has been achieved on all 4 objectives of the project. The first objective is to develop the method of Randomised Algebraic Construction. This has been achieved by two papers, one refining and simplifying my original proof of the Existence Conjecture, and the second greatly generalising it to encompass many new applications. This also makes progress on the second objective, which is a unifying framework for the existence of perfect matchings in sparse graphs. Further progress on this objective has been achieved by a series of papers working towards Ryser\'s Conjecture. Within the third objective, which is the theory of random independent sets and matchings in hypergraphs, we have developed new techniques for approximations of partition functions. The fourth objective, a structural characterisation of isoperimetry in Hamming spaces, has been very substantially addressed by several papers, including stability results for the vertex-isoperimetric and edge-isoperimetric inequalities.

Final results

\"We expect to find many further applications of the main result in our paper \"\"The existence of designs II\"\" - indeed, we are close to completing a paper with such an application. Our new methods for matchings in edge-coloured graphs show promise of developing improved bounds on Ryser\'s Conjecture. We expect to find further applications of perturbation methods from Statistical Mechanics to develop the probabilistic theory of rigid combinatorial structures. We intend to develop our tools for establishing stability in isoperimetric problems, to obtain stronger understanding from both the combinatorial and Fourier-analytic perspectives, and so make progress on the Kahn-Kalai conjecture.
\"