Transversals and matchings in 3-uniform hypergraphs

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 size  r . 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 ) = 2 k + 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 n r ( k ) ≤ k r + r r . 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 3 k + 3 ≤ n 3 ( k ) ≤ 3 k + 4 .