Transversals in 4-uniform linear hypergraphs

Michael A. Henning, Anders Yeo

Research output: Contribution to journalArticlepeer-review


Let H be a hypergraph of order nH= |V(/H)| and size mH= |E(H)|. The transversal number τ (H) of a hypergraph 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. For k ≥ 2, let Lkdenote the class of k-uniform linear hypergraphs. We consider the problem of determining the best possible constants qk(which depends only on k) such that τ(H) < qk{nH+mH) for all H ∈ Lk. It is known that q2= 1/3 and q3= 1/4. In this paper we show that q4= 1/5, which is better than for non-linear hypergraphs. Using the affine plane AG(2,4) of order 4, we show there are a large number of densities of hypergraphs H ∈ L4such that τ(H) ≈ 1/5{nH+ mH).

Original languageEnglish
Pages (from-to)111-142
Number of pages32
JournalJournal of Combinatorial Mathematics and Combinatorial Computing
Publication statusPublished - Feb 2021


  • Affine plane
  • Hypergraph
  • Linear hypergraph
  • Transversal

ASJC Scopus subject areas

  • General Mathematics


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

Cite this