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.
Another recent result, due to Ferber, Hod, Krivelevich and Sudakov @cite_22 gives a short probabilistic construction of almost Steiner systems', in which every @math -subset is covered by either one or two @math -subsets.
@cite_22
1991434971
A partial Steiner system Sp(t, k, n) is a collection of k-subsets (i.e. subsets of size k) of n element set such that every t-subset is contained in at most one k-subset. To avoid trivial cases, we assume 2 ⩾ t < k < n. It is easy to see that the size of a partial Steiner system Sp(t, k, n) is at most (tn) (kt). Confirming a conjecture of Erdos and Hanani [5], Rodl [19] proved that for fixed positive integers t and k, there is a partial Steiner system Sp(t, k, n) of size at least (1 − o(1)) ( nt)( kt) where o(1) goes to 0 as n goes to infinity. Grable [7] found an explicit bound of the o(1) term above and it was improved by Kostochka and Rodl [15] to n−1 ((kt)+o(1)−1). All proofs used Rodl's nibble method. We also use the method to improve the bound to O(( log nn) k − t(( kt)−1) for 2 ⩾ t < k — 2. (For t = k — 1, slightly better bounds were already known. See [2].) We believe that the nibble method gives no better bound up to a logarithmic factor.