Partial steiner systems and matchings in hypergraphs

A. V. Kostochka, V. Rödl

Research output: Contribution to journalArticlepeer-review

Abstract

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
Volume13
Issue number3-4
DOIs
StatePublished - 1998
Externally publishedYes

Keywords

  • Hypergraph matchings
  • Steiner systems

ASJC Scopus subject areas

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

Fingerprint

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

Cite this