Lower bounds on Tuza constants for transversals in linear uniform hypergraphs

Michael A. Henning, Anders Yeo

Research output: Contribution to journalArticlepeer-review

Abstract

Let H be a hypergraph of order nH=|V(H)| and size mH=|E(H)|. The transversal number τ(H) of H is the minimum number of vertices that intersect every edge of H. A linear hypergraph is one in which every two distinct edges intersect in at most one vertex. A k-uniform hypergraph has all edges of size k. Let Lk be the class of k-uniform linear hypergraphs. In this paper we study the problem of determining or estimating the best possible constants qk (which depends only on k) such that τ(H)≤qk(nH+mH) for all H∈Lk. We establish lower bounds on qk for all k≥2. For all k≥2 and for all 0<a<1, we show that qk≥a(1−a)k∕((1−a)k+aln(e∕a)), where here ln denotes the natural logarithm to the base e.

Original languageEnglish
Pages (from-to)12-22
Number of pages11
JournalDiscrete Applied Mathematics
Volume304
DOIs
Publication statusPublished - 15 Dec 2021

Keywords

  • Affine plane
  • Hypergraph
  • Linear hypergraph
  • Transversal

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Lower bounds on Tuza constants for transversals in linear uniform hypergraphs'. Together they form a unique fingerprint.

Cite this