Transversals and matchings in 3-uniform hypergraphs

Michael A. Henning, Anders Yeo

Research output: Contribution to journalArticlepeer-review

20 Citations (Scopus)


In this paper we study transversals and matchings in 3-uniform hypergraphs. For r ≥ 2, let H be a r-uniform hypergraph, and so every edge in H has sizer. A transversal (or hitting set or vertex cover) in H is a set of vertices in H that has a nonempty intersection with every edge of H, while the transversal number τ (H) of H is the minimum size of a transversal in H. Let α' (H) be the size of a maximum matching in H. We observe that τ (H) ≤ rα' (H) We define H to be k-special if H is a connected hypergraph with no isolated vertex satisfying α' (H) = k and τ (H) = rα' (H) We remark that 1-special hypergraphs include all projective planes, which are very well studied. Let n r (k) denote the maximum order of a k-special r-uniform hypergraph. As a consequence of a result due to Gallai [T.Gallai, Neuer Beweis eines Tutteschen Satzes, Magyar Tud. Akad. Mat. Kutató Int. Közl. 8 (1963) 135-139] we have n 2 (k) = 2k + 1. Lovász [L.Lovász, On minimax theorems of combinatorics (Doctoral thesis, in Hungarian), Mat. Lapok (NS) 26 (1975) 209-264] showed that for k ≥ 1 and r ≥ 3, we have nr(k)≤kr+rr. Hanson and Toft [D.Hanson, B.Toft, On the maximum number of vertices in n-uniform cliques, Ars Combin. 16A (1983) 205-216] showed that n 3 (1) = 7 and n 4 (1) = 16. In this paper we show that for all k ≥ 2, we have 3k + 3 ≤ n 3 (k) ≤ 3k + 4.

Original languageEnglish
Pages (from-to)217-228
Number of pages12
JournalEuropean Journal of Combinatorics
Issue number2
Publication statusPublished - Feb 2013

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Transversals and matchings in 3-uniform hypergraphs'. Together they form a unique fingerprint.

Cite this