Lower bounds on Tuza constants for transversals in linear uniform hypergraphs

Michael A. Henning*, Anders Yeo

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-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
JournalDiscrete Applied mathematics
Volume304
Pages (from-to)12-22
ISSN0166-218X
DOIs
Publication statusPublished - 15. Dec 2021

Bibliographical note

Publisher Copyright:
© 2021 Elsevier B.V.

Keywords

  • Affine plane
  • Hypergraph
  • Linear hypergraph
  • Transversal

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