Hypergraphs with large transversal number

Michael A. Henning, Anders Yeo

Research output: Contribution to journalArticlepeer-review

23 Citations (Scopus)

Abstract

For κ ≥ 2, let H be a k-uniform hypergraph on n vertices and m edges. The transversal number τ (H) of H is the minimum number of vertices that intersect every edge. We consider the following question: Is τ (H) ≤ n/k + m/6? For κ ≥ 4, we show that the inequality in the question does not always hold. However, the examples we present all satisfy Δ(H) ≥ 4. A natural question is therefore whether τ (H) ≤ n/κ + m/6 holds when Δ(H) ≤ 3. Although we do not know the answer, we prove that the bound holds when Δ(H) ≤ 2, and for that case we characterize the hypergraphs for which equality holds. Furthermore, we prove that the bound holds when κ κ = 2 (with no restriction on the maximum degree), and again there we characterize the hypergraphs for which equality holds. Chvátal and McDiarmid [V. Chvátal, C. McDiarmid, Small transversals in hypergraphs, Combinatorica 12 (1992) 19-26] proved that the bound holds for κ = 3 (again with no restriction on the maximum degree). We characterize the extremal hypergraphs in this case.

Original languageEnglish
Pages (from-to)959-966
Number of pages8
JournalDiscrete Mathematics
Volume313
Issue number8
DOIs
Publication statusPublished - 2013

Keywords

  • Affine plane
  • Hypergraph
  • Transversal

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Hypergraphs with large transversal number'. Together they form a unique fingerprint.

Cite this