Lemme de régularité de Szemerédi

Soit G un graphe non orienté, X et Y deux sous-ensembles de sommets (non nécessairement disjoints). La densité du couple (X,Y) est la quantité suivante :

${\displaystyle d(X,Y):={\frac {\left|E(X,Y)\right|}{\left|X\right|\left|Y\right|}}}$,

où E(X,Y) désigne l'ensemble des arêtes reliant un sommet de X à un sommet de Y.

Pour tout ε > 0, un couple (X,Y) est dit ε-pseudo aléatoire, si pour tous les sous-ensembles A de X et B de Y, tels que : ${\displaystyle |A|\geq \varepsilon |X|}$ et${\displaystyle |B|\geq \varepsilon |Y|}$, on a :

${\displaystyle \left|d(X,Y)-d(A,B)\right|\leq \varepsilon .}$

Enfin, une partition de l'ensemble des sommets V₁, ..., V_k est dite ε-régulière si :

• pour tout i, j : ||V_i| − |V_j|| ≤ 1;
• Toutes les paires V_i, V_j, i < j, à l'exception de εk², sont ε-pseudo-aléatoires.

Le lemme de régularité peut alors s'énoncer ainsi[1] :

« Pour tout ε > 0 et tout entier positif m, il existe un entier M tel que si G est un graphe contenant M arêtes, il existe un entier k compris entre m et M tel qu'on puisse faire une k-partition ε-régulière des sommets de G. »

Il existe plusieurs variantes du résultat, par exemple on peut avoir les classes de même taille exactement, si on autorise une classe spéciale qui ne respecte pas la condition de régularité (dont on peut assurer la petite taille)[1] - [2].

Le lemme de régularité permet de dire, que les grands graphes peuvent dans certains cas être vu comme des graphes aléatoires d'un certain type. Plus précisément, tout graphe est approché par une union d'un nombre constant de graphes bipartis[3]. En ce sens, il aide parfois à montrer des résultats sur des graphes arbitraires quand le résultat est vérifié pour les graphes aléatoires[4].

Le lemme a d'abord été montré par Endre Szemerédi en 1975[5], comme une étape dans sa démonstration du résultat appelé aujourd'hui théorème de Szemerédi sur les progressions arithmétiques[6]. Il a ensuite montré le résultat pour les graphes généraux[7].

Le lemme permet de montrer le théorème d'Erdős-Stone et des résultats en théorie des graphes extrémaux[2].

Il est notamment utilisé en test de propriété[8].

• Cet article est partiellement ou en totalité issu de l'article intitulé « Théorème de Szemerédi » (voir la liste des auteurs).

• David Conlon et Jacob Fox, « Bounds for graph regularity and removal lemmas », Geometric and Functional Analysis, vol. 22,‎ 2012, p. 1191–1256 (arXiv 1107.4829).

• Demi-graphe

• Terence Tao, « The spectral proof of the Szemeredi regularity lemma », sur What's new