The existence of designs

Abstract

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.

Version 4 (the decennial edition) incorporates referee comments, additional exposition and a brief review of subsequent work

References in corpus (2)

• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Polynomial-time perfect matchings in dense hypergraphs

Cited by in corpus (49)

• Distance-regular graphs
• Edge-decompositions of graphs with high minimum degree
• The existence of designs II
• Fractional Clique Decompositions of Dense Graphs and Hypergraphs
• On putative q-Analogues of the Fano Plane and Related Combinatorial Structures
• Pseudorandom hypergraph matchings
• Hypergraph $F$-designs for arbitrary $F$
• Packing degenerate graphs
• The existence of designs via iterative absorption: hypergraph $F$-designs for arbitrary $F$
• Random Simplicial Complexes: Models and Phenomena
• Constructions of Pairs of Orthogonal Latin Cubes
• Perfect Packings in Quasirandom Hypergraphs II
• Combinatorial designs, difference sets and bent functions as perfect colorings of graphs and multigraphs
• Clique decompositions of multipartite graphs and completion of Latin squares
• A Ramsey Class for Steiner Systems
• Ringel's tree packing conjecture in quasirandom graphs
• Sign rank versus VC dimension
• Codegree conditions for tiling complete $k$-partite $k$-graphs and loose cycles
• A blow-up lemma for approximate decompositions
• Turán numbers of hypergraph trees
• Triangle-free Subgraphs of Hypergraphs
• Kalai's conjecture in $r$-partite $r$-graphs
• New bounds on the size of Nearly Perfect Matchings in almost regular hypergraphs
• $d$-cluster-free sets with a given matching number
• On Perfect Matchings in $k$-complexes
• A lower bound for the $n$-queens problem
• Fractional triangle decompositions in graphs with large minimum degree
• Reconstruction of hypergraphs from line graphs and degree sequences
• Triangle Decompositions of Planar Graphs
• On the size-Ramsey number of hypergraphs
• On Connectivity of the Facet Graphs of Simplicial Complexes
• Packing without some pieces
• On Optimal Locally Repairable Codes with Super-Linear Length
• Enclosings of Decompositions of Complete Multigraphs in $2$-Edge-Connected $r$-Factorizations
• On partial Steiner $(n,r,\ell )$-system process
• A spectral characterisation of t-designs and its applications
• Ramsey theorem for designs
• Threefold triple systems with nonsingular $N_2$
• Factorization of Platonic Polytopes into canonical spheres
• Transitive bounded-degree 2-expanders from regular 2-expanders
• On Optimal Locally Repairable Codes and Generalized Sector-Disk Codes
• On the packing for triples
• $\left(n,k,k-1\right)$-Steiner Systems in Random Hypergraphs
• Triangulating Almost-Complete Graphs
• Betti numbers of complexes with highly Connected links
• Generalized laminar families and certain forbidden matrices
• Mutually orthogonal latin squares with large holes
• Bounding the Number of Hyperedges in Friendship $r$-Hypergraphs
• On the number of matroids compared to the number of sparse paving matroids