The existence of designs

By Peter Keevash. 2014

338 citations recorded by the source corpus.

We prove the existence conjecture for combinatorial designs, answering a question of Steiner from 1853. More generally, we show that the natural divisibility conditions are sufficient for clique decompositions of simplicial complexes that satisfy a certain pseudorandomness condition. As a further generalisation, we obtain the same conclusion only assuming an extendability property and the existence of a robust fractional clique decomposition.

Subfields: Artificial Intelligence, Discrete Mathematics and Combinatorics, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/5e25ae93b14186333b6ef1466523269eba0edbab

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Allan Siu Lun Lo
2. Deryk Osthus
3. D. Kühn
4. Stefan Glock
5. Yi Zhao
6. Matthew Kwan
7. Alexander Vardy
8. E. Arıkan

In Discrete Mathematics and Combinatorics

1. Peter Keevash
2. Matthew Kwan
3. Deryk Osthus
4. D. Kühn
5. Yi Zhao
6. Allan Siu Lun Lo
7. Stefan Glock
8. Tuvi Etzion

In Electrical and Electronic Engineering

1. Peter Keevash
2. Matthew Kwan
3. Deryk Osthus
4. D. Kühn
5. Allan Siu Lun Lo
6. Stefan Glock
7. Yi Zhao
8. Michael Braun

Citations in the corpus

• EXISTENCE OF $q$ -ANALOGS OF STEINER SYSTEMS (2013, background): “Keevash recently announced a resolution of this problem: his breakthrough paper [29] moreover shows that Steiner systems S(t, k, n) exist for all t < k and all sufficiently large integers n that satisfy the necessary divisibility conditions.”
• The Existence of Designs via Iterative Absorption: Hypergraph 𝐹-designs for Arbitrary 𝐹 (2016, methodology): “The approach in [23] involved randomised algebraic constructions and yielded a far-reaching generalisation to block designs in quasirandom r-graphs.”
• The existence of designs II (2018, background): “, so that no two shall walk twice abreast. The general problem is to determine when one can find designs that are ‘resolvable’: the set of blocks can be partitioned into perfect matchings. Recall from [15] that a set Sof q-subsets of an n-set Xis a design with parameters (n,q,r,λ) if every r-subset o”
• Recent advances on Dirac-type problems for hypergraphs (2015, background): “Many open problems in combinatorics can be formulated as a problem of finding perfect matchings in hypergraphs, e.g., Ryser’s conjecture that every Latin square of odd order has a transversal, and the existence of combinatorial designs (recently solved by Keevash [41]).”
• Almost all Steiner triple systems have perfect matchings (2016, background): “However, the Steiner triple systems obtainable by Keevash’s construction comprise a negligible proportion of the set of Steiner triple systems, and a somewhat more delicate approach is required to study a uniformly random Steiner triple system.”
• The existence of designs via iterative absorption (2016, methodology): “We also note that, in a similar way as discussed in [21, 22], the results of this paper can be combined with ‘counting versions’ of the Rödl nibble (or corresponding random greedy processes) to obtain lower bounds on the number of designs with given parameters.”
• A proof of Ringel’s conjecture (2020, background): “It was resolved only very recently in spectacular work by Keevash [13] (see the subsequent work of [10] for an alternative proof of this result).”