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

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 n₃ vertices of degree 3, then τ (H) ≤ (2n + km)/(3k) - 2n₃/(7k²). 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.