More-than-nearly-perfect packings and partial designs (Q1125617): Difference between revisions

The main result of this paper says that if \(H\) is a \(D\)-regular \(k\)-uniform hypergraph on \(n\) vertices with maximum codegree \(C\) such that \(kC\log n\ll D\) then \(H\) contains a packing with at most \[ n\left({kC\log n}\over D\right)^{1/(2k-1+o(1))} \] uncovered vertices. This is an improved analysis of the Pippenger-Spencer theorem for the special case that \(H\) is regular. The proof is a probabilistic argument. It is based on a Talagrand-type inequality and Rödl's nibble technique. The main result is applied to the problem of finding partial Steiner systems. Earlier results in this direction are improved, too.