Independence in Uniform Linear Triangle-free Hypergraphs

2015/07/15 by Borowiecki, Piotr, Gentner, Michael, Löwenstein, Christian +1
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1507.04323

Abstract

The independence number α(H) of a hypergraph H is the maximum cardinality of a set of vertices of H that does not contain an edge of H. Generalizing Shearer's classical lower bound on the independence number of triangle-free graphs (J. Comb. Theory, Ser. B 53 (1991) 300-307), and considerably improving recent results of Li and Zang (SIAM J. Discrete Math. 20 (2006) 96-104) and Chishti et al. (Acta Univ. Sapientiae, Informatica 6 (2014) 132-158), we show that α(H)≥ ∑_{u∈ V(H)}f_r(d_H(u)) for an r-uniform linear triangle-free hypergraph H with r≥ 2, where f_r(0)amp;=amp;1, and
f_r(d)amp;=amp;(1+((r-1)d²-d)f_r(d-1))/(1+(r-1)d²) for d≥ 1.

Related

• On independent sets in hypergraphs
• An Efficiently Computable Lower Bound for the Independence Number of Hypergraphs
• Independent Sets in Hypergraphs
• New lower bounds for the independence number of sparse graphs and hypergraphs
• New results on k-independence of hypergraphs