Seminar at SMU 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.