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