text: 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.
  @cite_33: Abstract We show that if a collection of hypergraphs (1) is uniform (every edge contains exactly k vertices, for some fixed k), (2) has minimum degree asymptotic to the maximum degree, and (3) has maximum codegree (the number of edges containing a pair of vertices) asymptotically negligible compared with the maximum degree, then the chromatic index is asymptotic to the maximum degree. This means that the edges can be partitioned into packings (or matchings), almost all of which are almost perfect. We also show that the edges can be partitioned into coverings, almost all of which are almost perfect. The result strengthens and generalizes a result due to Frankl and Rodl concerning the existence of a single almost perfect packing or covering under similar circumstances. In particular, it shows that the chromatic index of a Steiner triple-system on n points is asymptotic to n 2 , resolving a long-standing conjecture.
  @cite_46: 
  @cite_28: Let H be a (k+1)-uniform, D-regular hypergraph on n vertices and let (H) be the minimum number of vertices left uncovered by a matching in H. Cj(H), the j-codegree of H, is the maximum number of edges sharing a set of j vertices in common. We prove a general upper bound on (H), based on the codegree sequence C2 (H), C3 (H),…. Our bound improves and generalizes many results on the topic, including those of Grable, Alon, Kim, and Spencer, and Kostochka and Rodl. It also leads to a substantial improvement in several applications. The key ingredient of the proof is the so-called polynomial technique, which is a new and useful tool to prove concentration results for functions with large Lipschitz coefficient. This technique is of independent interest. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 29–63, 2000
  @cite_1: (n) of the n vertices. Here we show, in particular, that regular uniform hypergraphs for which the ratio of degree to maximum codegree is ( ), for some ɛ>0, have packings which cover all but ( ) vertices, where α=α(ɛ)>0.
  @cite_3: 
  @cite_6: 
  @cite_19: Abstract It is proved that asymptotically good coverings of l-tuples of an n-element set by k-tuples exist for k = o(n) and slowly increasing l. On the other hand, it is noted that for l = o(k) asymptotically good packings do not exist if k > c√n for some constant c > 1 and exist for slowly increasing l if k
  @cite_15: Suppose we are given a bipartite graph with vertex set X, Y, |X| = n , |Y| = N , each point in X (Y) has degree D(d) fixed, respectively, moreover, each pair of points x, x' ∈ X has at most D (log n) 3 (common) neighbours. Let t (X, Y) denote the minimum number of vertices of Y needed to cover all vertices of X. We prove (Theorem 1.1) that t (X, Y) d n tends to 1 as n tends to infinity. This result has many applications: Theorem [5]. Suppose k > r > 1 are fixed, n → ∞. Then there exists a collection of (1 + o (1)) × ( n r ) ( k r ) k -subsets of an n -set so that each r -subset is contained in at least one member of the collection. Analogues and strengthenings of this result are deduced. E.g. for vector spaces, orthogonal or simplectic geometries, random collections of k -sets with constant probabilities, etc. Theorem 3.3. Suppose G is a graph on v vertices and e edges and ℛ is a random graph on n vertices and edge probability e ( v 2 ). Then there exists a collection of (1 + o (1))( n 2 ) ( v 2 ) induced subgraphs of ℛ on v vertices, isomorphic to G and such that each edge (non-edge) of ℛ is covered by an edge (non-edge) of a graph in the collection.
  @cite_10: 
  @cite_25: It is shown that under certain side conditions the natural random greedy algorithm almost always provides an asymptotically optimal packing of disjoint hyperedges from a hypergraph H.
  @cite_12: 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.
summary: As a weaker version of the Existence Conjecture, Erd o s and Hanani @cite_6 posed the question of the existence of asymptotically optimal Steiner systems; equivalently, finding @math edge-disjoint @math 's in @math . This was proved by R "odl @cite_3 , by developing a new semi-random construction method known as the nibble', which has since had a great impact on Combinatorics (see e.g. @cite_15 @cite_1 @cite_10 @cite_12 @cite_46 @cite_19 @cite_33 @cite_25 @cite_28 for related results and improved bounds). It will also play an important role in this paper.