Transversals in 4-uniform hypergraphs

Michael A. Henning, Anders Yeo

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

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
JournalElectronic Journal of Combinatorics
Volume23
Issue number3
DOIs
Publication statusPublished - 30 Sept 2016

Keywords

  • Hypergraph
  • Transversal

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Transversals in 4-uniform hypergraphs'. Together they form a unique fingerprint.

Cite this