Partial Steiner systems and matchings in hypergraphs
For t < k, a (t, k) T-system is a k-uniform hypergraph H such that any two distinct edges of H have at most t-1 vertices in common. Clearly, any (t, k)-system on n vertices has at most ((n)(t))/((k)(t)) edges. It was proved by Rodl that there are (t, k)-systems on n vertices with (1-o(1))((n)(t))/((k)(t)) edges. Then stronger results and generalizations were obtained by several authors. In particular, Grable proved that every D-regular k-uniform hypergraph on N vertices with codegree of size o(D/k log N) contains a matching that covers all but at most N((kC log N)/D)(1/(2k-1+o(1))) of its vertices. In this article, we give a simple proof of the original result of Rodl and improve Grable's result for hypergraphs with bounded codegrees. The proof of the second result is based on the bound of Alon, Kim, and Spencer on matchings in linear hypergraphs. (C) 1998 John Wiley & Sons, Inc.
steiner systems hypergraph matchings