Explicit Constructions of Rödl's Asymptotically Good Packings and Coverings (Q4500423)

A \(t\)-\((v,k,\lambda)\) packing design (covering design) \(D\) is a collection of \(k\)-element sets, called blocks, out of a \(v\)-set such that each \(t\)-subset of the \(v\)-set is contained in at most (at least) \(\lambda\) blocks. In the sequel we assume that \(\lambda = 1\), and define the density of such a design as \(|D|\left(k t\right)/\left(v t\right)\) (so the density is at most 1 for packing designs and at least 1 for covering designs). \textit{V. Rödl} [Eur. J. Comb. 6, 69-78 (1985; Zbl 0565.05016)] proved that for fixed \(k\) and \(t\), there exist sequences of packing and covering designs whose densities tend to 1 as \(v\) tends to infinity. Rödl's argument is purely probabilistic; several authors have later presented algorithms for explicitly constructing such sequences. The current paper presents an explicit deterministic construction that evaluates the \(i\)th member of a sequence \(F\) in time polynomial in the encoding length of \(i\) (which is \(O(\log |F|)\)).