**Date & Time:** Friday, September 12, 2014, 14:00-15:00.

**Venue:** Room No. 216

**Title:** An extremal problem in Graph theory and hardness of additive approximation for edge deletion problems

**Speaker:** Niranjan Balachandran, IIT Bombay

**Abstract:** We discuss a result of Alon, Shapira, and Sudakov in which they
prove a generalization of Turan's theorem and the Erdos-Stone-Simonovits theorem for the case of graphs with large minimum degree,
and as a consequence give a precise characterization of those monotone
properties P for which it is NP-HARD to approximate the number of
edges that need to be deleted from a given graph up to an order of
$O(n^{2-\delta})$ for any $\delta>0$.