Lemme de régularité de Szemerédi

Un article de Wikipédia, l'encyclopédie libre.

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[modifier | modifier le code]

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 :

,

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 : et, on a :

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

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

Énoncé[modifier | modifier le code]

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

Variantes[modifier | modifier le code]

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

Lien avec les graphes aléatoires[modifier | modifier le code]

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

Histoire et extensions[modifier | modifier le code]

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

Applications[modifier | modifier le code]

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

Notes et références[modifier | modifier le code]

  1. ↑ a et b Miklós Simonovits, « Regularity Lemmas and Extremal Graph Theory (Lecture on Endre Szemerédi’s 70th birthday) ».
  2. ↑ a et b John Adrian Bondy et U.S.R. Murty (trad. de l'anglais par Frédéric Havet), Théorie des Graphes, (lire en ligne [PDF]).
  3. ↑ Tibor Szabó, « Graphs & Algorithms: Advanced Topics: Szemerédi’s regularity lemma ».
  4. ↑ « Szemerédi’s regularity lemma », sur matheuscmss.wordpress.com, .
  5. ↑ « Szemerédi's Regularity lemma », sur Abel prize.
  6. ↑ Endre Szemerédi, « On sets of integers containing no k elements in arithmetic progression », Acta Arithmetica, no 27,‎ , p. 199–245 (lire en ligne)
  7. ↑ Endre Szemerédi, « Regular partitions of graphs », dans Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), vol. 260, Paris, CNRS, (MR 540024), p. 399-401.
  8. ↑ Voir par exemple : Noga Alon, Eldar Fischer, Ilan Newman et Asaf Shapira, « A combinatorial characterization of the testable graph properties: it’s all about regularity », dans Proc. of STOC 2006, , p. 251-260.

Voir aussi[modifier | modifier le code]

Article lié[modifier | modifier le code]

Lien externe[modifier | modifier le code]

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Lemme_de_régularité_de_Szemerédi&oldid=210900410 ».