A Regularity Lemma with Modifications

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.