A Regularity Lemma with Modifications

Computer Science/Discrete Mathematics Seminar II
Topic:A Regularity Lemma with Modifications
Speaker:Guy Moshkovitz
Affiliation:Member, School of Mathematics
Date:Tuesday, January 29
Time/Room:10:30am - 12:30pm/Simonyi Hall 101
Video Link:https://video.ias.edu/csdm/2019/0129-GuyMoshkovitz

Given an arbitrary graph, we show that if we are allowed to modify (say) 1% of the edges then it is possible to obtain a much smaller regular partition than in Szemeredi's original proof of the regularity lemma. Moreover, we show that it is impossible to improve upon the bound we obtain. 

The upper bound can be used to reprove a famous result of Fox on the removal lemma [Ann. of Math. '11], whereas the lower bound served as a key step towards the solution of the optimality question for the hypergraph regularity lemma. Time permitting, we will give detailed sketches of both the upper and lower bound proofs. 

Joint work with Asaf Shapira.