Transversals and matchings in 3-uniform hypergraphs

In this paper we study transversals and matchings in 3-uniform hypergraphs. For r≥2r≥2, let HH be a rr-uniform hypergraph, and so every edge in HH has size rr. A transversal (or hitting set or vertex cover) in HH is a set of vertices in HH that has a nonempty intersection with every edge of HH, while the transversal number τ(H)τ(H) of HH is the minimum size of a transversal in HH. Let α′(H)α′(H) be the size of a maximum matching in HH. We observe that τ(H)≤rα′(H). We define HH to be kk-special if HH is a connected hypergraph with no isolated vertex satisfying α′(H)=kα′(H)=k and τ(H)=rα′(H). We remark that 11-special hypergraphs include all projective planes, which are very well studied. Let nr(k)nr(k) denote the maximum order of a kk-special rr-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 n2(k)=2k+1n2(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≥1k≥1 and r≥3r≥3, we have nr(k)≤kr+rr. Hanson and Toft [D. Hanson, B. Toft, On the maximum number of vertices in nn-uniform cliques, Ars Combin. 16A (1983) 205–216] showed that n3(1)=7n3(1)=7 and n4(1)=16n4(1)=16. In this paper we show that for all k≥2k≥2, we have 3k+3≤n3(k)≤3k+43k+3≤n3(k)≤3k+4.