New Lower Bounds for the Independence Number of Sparse Graphs and Hypergraphs
Kunal Dutta, Dhruv Mubayi, Charumathi Raghu Subramanian · SIAM Journal on Discrete Mathematics · 2012
We obtain new lower bounds for the independence number of $K_r$-free graphs and linear $k$-uniform hypergraphs in terms of the degree sequence. This answers some old questions raised by Caro and Tuza [J. Graph Theory, 15 (1991), pp. 99--107]. Our proof technique is an extension of a method of Caro [New Results on the Independence Number, Technical report, Tel Aviv University, 1979] and Wei [A Lower Bound on the Stability Number of a Simple Graph, TM 81-11217-9, Bell Laboratories, Berkley Heights, NJ, 1981], and we also give a new short proof of the main result of Caro and Tuza using this approach. As byproducts, we also obtain some nontrivial identities involving binomial coefficients, which may be of independent interest.