New results on k-independence of hypergraphs

2018/03/09 by Zhang, Lei, Chang, An
#05C65 #05C69 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1803.03393

Abstract

Let H=(V,E) be an s-uniform hypergraph of order n and k≥ 0 be an integer. A k-independent set S⊆ H is a set of vertices such that the maximum degree in the hypergraph induced by S is at most k. Denoted by α_k(H) the maximum cardinality of the k-independent set of H. In this paper, we first give a lower bound of α_k(H) by the maximum degree of H. Furthermore, we prove that α_k(H)≥ (s(k+1)n)/(2d+s(k+1)) where d is average degree of H, and k≥ 0 is an integer.

Related

• New approach to the k-independence number of a graph
• On independent sets in hypergraphs
• Independence in Uniform Linear Triangle-free Hypergraphs
• On independent sets in uncrowded uniform hypergraphs
• An Efficiently Computable Lower Bound for the Independence Number of Hypergraphs