---
tag: A3309CW2QV
kind: statement
role: lemma
name: Strong regularity lemma
sources:
  - wikipedia: en:1962417@r1368655010
    locator: Szemerédi regularity lemma, section Strong regularity lemma
    note: adopted
    mention: wikipedia://en/1962417#D5QJ
    sections: [Statement]
inventory: [5WXDHHE95F]
---

## Statement

The strong regularity lemma is a stronger variation of the regularity lemma proven by Alon, Fischer, Krivelevich, and Szegedy in 2000. Intuitively, it provides information between non-regular pairs and could be applied to prove the induced graph removal lemma.

A partition is equitable if the sizes of any two sets differ by at most $1$. By equitizing in each round of iteration, the proof of regularity lemma could be accustomed to prove the equitable version of regularity lemma. And by replacing the regularity lemma with its equitable version, the proof above could prove the equitable version of strong regularity lemma where $\mathcal{P}$ and $\mathcal{Q}$ are equitable partitions.