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 7 kand this bound is achieved for all k ≡ 0 ( mod3 ) . 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 n3vertices of degree 3, then τ ( H ) ≤ ( 2 n + k m ) / ( 3 k ) − 2 n3 / ( 7 k 2 ) . This improves a result due to Chvátal and McDiarmid [Combinatorica 12 (1992), 19–26] who proved that τ ( H ) ≤ ( n + k 2 m ) / (3 k 2 )in the case when k ≥ 2 is even and H has maximum degree 3.