En théorie des graphes, le lemme de régularité de Szemerédi ou simplement lemme de régularité, est un résultat de partitionnement de graphe. Il exprime qu'un graphe assez grand peut toujours être découpé en un petit nombre de morceaux de telle sorte que les arêtes entre ces morceaux se comportent de façon très régulière.

Définitions des objets Soient un graphe non orienté, et deux sous-ensembles de sommets (non nécessairement disjoints). La densité d'arêtes du couple est la quantité suivante :

où désigne l'ensemble des arêtes reliant un sommet de à un sommet de .

Pour tout , un couple est dit -régulier si pour tous et tels que et on a :

Enfin, une partition de l'ensemble des sommets est dite -régulière si : pour tout , ; Tous les couples , à l'exception de au plus, sont -réguliers.

Énoncé Le lemme de régularité peut alors s'énoncer ainsi. :

Variantes 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)..

Lien avec les graphes aléatoires 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.. 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..

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

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

Il est notamment utilisé en test de propriétéVoir par exemple : ..

Notes et références

Voir aussi .

Articles connexes Demi-graphe

Liens externes

Catégorie:Théorème de la théorie des graphes