Theoretical Statistics and Mathematics Unit, ISI Delhi

March 20, 2013 (Wednesday) ,
3:30 PM at Webinar

Speaker:
Kunal Dutta,
Indian Statistical Institute, Delhi

Title:
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
[2]. 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 [2] 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.