## Abstract

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 language | English |
---|---|

Pages (from-to) | 217-228 |

Number of pages | 12 |

Journal | European Journal of Combinatorics |

Volume | 34 |

Issue number | 2 |

DOIs | |

Publication status | Published - Feb 2013 |

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics