The Fano Plane and the Strong Independence Ratio in Hypergraphs of Maximum Degree 3

Michael A. Henning, Christian Löwenstein

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


A set S of vertices in a hypergraph H is strongly independent if no two vertices in S belong to a common edge. The strong independence number of H, denoted α(H), is the maximum cardinality of a strongly independent set in H. The rank of H is the size of a largest edge in H. The hypergraph H is k-uniform if every edge of H has size k. The transversal number, denoted τ(H), of H is the minimum number of vertices that intersect every edge. Our main result is that for all K ≥ 2, the strong independence ratio of a hypergraph H with rank k and maximum degree 3 satisfies α(H)/n(H) ≥ 3/7K and this bound is achieved for all k ≡ 0(mod 3). In particular, this bound is achieved for the Fano plane. As an application of our result, we show that if H is a k-uniform hypergraph on n vertices with m edges and with maximum degree 3 and n3 vertices of degree 3, then τ (H) ≤ (2n + km)/(3k) - 2n3/(7k2). This improves a result due to Chvátal and McDiarmid [Combinatorica 12 (1992), 19–26] who proved that τ (H) ≤ (n + ⌊K/2⌋ m)/(⌊3K/2⌋) in the case when K ≥ 2 is even and H has maximum degree 3.

Original languageEnglish
Pages (from-to)196-208
Number of pages13
JournalJournal of Graph Theory
Issue number2
Publication statusPublished - 1 Oct 2016


  • Fano plane
  • hypergraph
  • strong independence
  • transversal

ASJC Scopus subject areas

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'The Fano Plane and the Strong Independence Ratio in Hypergraphs of Maximum Degree 3'. Together they form a unique fingerprint.

Cite this