## Abstract

A set S of vertices in a hypergraph H is a transversal if it has a nonempty intersection with every edge of H. For k≥1, if H is a hypergraph with every edge of size at least k, then a k-transversal in H is a transversal that intersects every edge of H in at least k vertices. In particular, a 1-transversal is a transversal. The upper k-transversal number ϒ_{k}(H) of H is the maximum cardinality of a minimal k-transversal in H. We obtain asymptotically best possible lower bounds on ϒ_{k}(H) for uniform hypergraphs H. More precisely, we show that for r≥2 and for every integer k∈[r], if H is a connected r-uniform hypergraph with n vertices, then ϒ_{k}(H)>[Formula presented]nr−k+1. For r>k≥1 and ε>0, we show that there exist infinitely many r-uniform hypergraphs, H_{r,k}
^{∗}, of order n and a function f(r,k) of r and k satisfying ϒ_{k}(H_{r,k}
^{∗})<(1+ε)⋅f(r,k)⋅nr−k+1.

Original language | English |
---|---|

Journal | European Journal of Combinatorics |

Volume | 78 |

Pages (from-to) | 1-12 |

Number of pages | 12 |

ISSN | 0195-6698 |

DOIs | |

Publication status | Published - May 2019 |