New Bounds on the Independence Number of Hypergraphs

A subset of vertices in a hypergraph H is an independent set if it contains no edge of H. The independence number, (H), of H is the maximum cardinality of an independent set in H. Our main result is an improvement of a lower bound for the independence number of 2-uniform hypergraphs due to Henning and L¨owenstein (2014) who proved that if H is a connected 2-uniform hypergraph of order n and size m and H does not belong to a specific family of hypergraphs, then (H) 2 3n 􀀀 14 m. Further they characterize the hypergraphs H for which (H) 2 3n 􀀀 1 4m. In this paper we improve aforesaid bound for connected 2-uniform hypergraphs of maximum degree at least four. Also we characterize all connected 2-uniform hypergraphs acheiving equality for this bound.