Seminar at SMU Delhi
March 20, 2013 (Wednesday) ,
3:30 PM at Webinar
Indian Statistical Institute, Delhi
New lower bounds for the independence number of sparse graphs and hypergraphs
Abstract of Talk
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
. Our proof technique is an extension of a method of Caro and Wei
[1,3], and we also give a short proof of the main result of  using this
approach. As by-products, we also obtain some non-trivial identities
involving binomial coefficients, which may be of independent interest.
This is joint work with Dhruv Mubayi and C. R. Subramanian.