Transversals in 4-uniform linear hypergraphs

Michael A. Henning, Anders Yeo

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 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
JournalJournal of Combinatorial Mathematics and Combinatorial Computing
VolumeCXVI
Pages (from-to)111-142
ISSN0835-3026
Publication statusPublished - Feb 2021

Bibliographical note

Publisher Copyright:
© 2021 Charles Babbage Research Centre. All rights reserved.

Keywords

  • Affine plane
  • Hypergraph
  • Linear hypergraph
  • Transversal

Fingerprint

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

Cite this