Upper transversals in hypergraphs

Michael A. Henning, Anders Yeo

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


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, Hr,k , of order n and a function f(r,k) of r and k satisfying ϒk(Hr,k )<(1+ε)⋅f(r,k)⋅nr−k+1.

Original languageEnglish
Pages (from-to)1-12
Number of pages12
JournalEuropean Journal of Combinatorics
Publication statusPublished - May 2019

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Upper transversals in hypergraphs'. Together they form a unique fingerprint.

Cite this