Transversals in 4-uniform hypergraphs

Michael A Henning, Anders Yeo

Research output: Contribution to journalJournal articleResearchpeer-review

72 Downloads (Pure)

Abstract

Let H be a 4-uniform hypergraph on n vertices. The transversal number τ (H) of H is the minimum number of vertices that intersect every edge. The result in [J. Combin. Theory Ser. B 50 (1990), 129-133] by Lai and Chang implies that τ (H) ≤ 7n/18 when H is 3-regular. The main result in [Combinatorica 27 (2007), 473-487] by Thomassé and Yeo implies an improved bound of τ (H) ≤ 8n/21. We provide a further improvement and prove that τ (H) ≤ 3n/8, which is best possible due to a hypergraph of order eight. More generally, we show that if H is a 4-uniform hypergraph on n vertices and m edges with maximum degree ∆(H) ≤ 3, then τ (H) ≤ n/4 + m/6, which proves a known conjecture. We show that an easy corollary of our main result is that if H is a 4-uniform hypergraph with n vertices and n edges, then τ (H) ≤ 3/ 7 n, which was the main result of the Thomassé-Yeo paper [Combinatorica 27 (2007), 473-487].

Original languageEnglish
JournalThe Electronic Journal of Combinatorics
Volume23
Issue number3
ISSN1097-1440
Publication statusPublished - 2016

    Fingerprint

Keywords

  • Hypergraph
  • Transversal

Cite this