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$.