The existence of designs

2014/01/15 by Peter Keevash, Keevash, Peter · 22 citations
Engineering · Mathematics · Computer Science · #graph theory and CDMA systems #Limits and Structures in Graph Theory #Coding theory and cryptography

paper · pdf · doi:10.48550/arxiv.1401.3665

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.

Cited by

• Entropy methods in combinatorics
• On the Hypergraph Nash-Williams' Conjecture
• Quantitative Frameproof Codes and Hypergraphs
• Codegree conditions for tiling complete k-partite k-graphs and loose cycles
• On fractional triangle decompositions of random graphs
• The existence of designs via iterative absorption: hypergraph F-designs for arbitrary F
• EA(q)-additive Steiner 2-designs
• Transitive bounded-degree 2-expanders from regular 2-expanders
• Threefold triple systems with nonsingular N₂
• Sign rank versus VC dimension
• Refined Absorption: A New Proof of the Existence Conjecture and its Applications to Extremal and Probabilistic Design Theory
• Ringel's tree packing conjecture in quasirandom graphs
• Privately Estimating Black-Box Statistics
• Mutually orthogonal latin squares with large holes
• A spectral characterisation of t-designs and its applications
• Parities in random Latin squares
• The Erd\Hos Matching Conjecture and concentration inequalities
• Beyond Nash-Williams: Counterexamples to Clique Decomposition Thresholds for All Cliques Larger than Triangles
• On Optimal Locally Repairable Codes with Super-Linear Length
• Erdős meets Nash-Williams
• New bounds for linear arboricity and related problems
• Fractional triangle decompositions in graphs with large minimum degree

Related

• The existence of designs II
• Counting designs
• A short proof of the existence of designs
• Minimalist designs
• q-analogs of group divisible designs