Premium
The Fano Plane and the Strong Independence Ratio in Hypergraphs of Maximum Degree 3
Author(s) -
Henning Michael A.,
Löwenstein Christian
Publication year - 2016
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21993
Subject(s) - combinatorics , mathematics , hypergraph , independence number , cardinality (data modeling) , degree (music) , upper and lower bounds , fano plane , independent set , enhanced data rates for gsm evolution , plane (geometry) , rank (graph theory) , independence (probability theory) , discrete mathematics , graph , geometry , physics , statistics , mathematical analysis , telecommunications , computer science , acoustics , data mining
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.