Hypergraph decompositions and their applications | Research seminar in Discrete Mathematics

Abstract

Many combinatorial objects can be thought of as a hypergraph decomposition, i.e. a partition of(the edge set of) one hypergraph into (the edge sets of) copies of some other hypergraphs. Folexample, a Steiner Triple System is equivalent to a decomposition of a complete graph intctriangles. In general, Steiner Systems are equivalent to decompositions of complete uniformhypergraphs into other complete uniform hypergraphs (of some specified sizes). The ExistenceConjecture for Combinatorial Designs, which l proved in 2014, states that, bar finitely manyexceptions, such decompositions exist whenever the necessary `divisibility conditions' hold. l alscobtained a generalisation to the quasirandom setting, which implies an approximate formula for thenumber of designs; in particular, this resolved Wilson's Coniecture on the number of Steiner TripleSystems. A more general result that l proved in 2018 on decomposing lattice-valued vectorsindexed by labelled complexes provides many further existence and counting results for a widerange of combinatorial objects, such as resolvable designs (the generalised form of kirkman'sSchoolgirl Problem), whist tournaments or generalised Sudoku squares. In this talk, l plan toillustrate these results and discuss some recent and ongoing developments.

Speaker Intro

Peter Keevash is a Professor of Mathematics at the University of Oxford and a Fellow ofMansfield College. He has also held positions at Queen Mary University of London and CaliforniaInstitute of Technology, and received degrees from Cambridge and Princeton. His research is inCombinatorics and is best known for his solution to the Existence Conjecture for CombinatorialDesigns. He received the European Prize in Combinatorics in 2009 and the Whitehead Prize in2015, and was a speaker at the 2018 International Congress of Mathematicians.