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 language | English (US) |
---|---|
Pages (from-to) | 335-347 |
Number of pages | 13 |
Journal | Random Structures and Algorithms |
Volume | 13 |
Issue number | 3-4 |
DOIs | |
State | Published - 1998 |
Externally published | Yes |
Keywords
- Hypergraph matchings
- Steiner systems
ASJC Scopus subject areas
- Software
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics