Partial steiner systems and matchings in hypergraphs

A. V. Kostochka, V. Rödl

Research output: Contribution to journalArticlepeer-review


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 (nt)/(kt) edges. It was proved by Rödl that there are (t, k)-systems on n vertices with (1 - o(1))(nt)/(kt) 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 Rödl 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.

Original languageEnglish (US)
Pages (from-to)335-347
Number of pages13
JournalRandom Structures and Algorithms
Issue number3-4
StatePublished - 1998
Externally publishedYes


  • Hypergraph matchings
  • Steiner systems

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


Dive into the research topics of 'Partial steiner systems and matchings in hypergraphs'. Together they form a unique fingerprint.

Cite this