Upper transversals in hypergraphs

Michael A. Henning*, Anders Yeo

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

10 Downloads (Pure)

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, 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
JournalEuropean Journal of Combinatorics
Volume78
Pages (from-to)1-12
Number of pages12
ISSN0195-6698
DOIs
Publication statusPublished - May 2019

Fingerprint

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

Cite this