Théorème de Szemerédi

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant les mathématiques
Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En mathématiques, le théorème de Szemerédi[1],[2] est la conjecture d'Erdős-Turán démontrée par Endre Szemerédi en 1975.

Énoncé[modifier | modifier le code]

Soient k un entier positif et 0 < δ ≤ 1/2. Alors il existe un entier N = N(k,δ) tel que tout sous-ensemble de {1 ; … ; N} d'au moins δN éléments contienne une progression arithmétique de longueur k.

Bornes sur N[modifier | modifier le code]

À l'heure actuelle, on ne sait qu'encadrer la valeur de N, dans le cas général le meilleur encadrement connu est celui-ci :

C^{\log(1/\delta)^{k-1}} \leq N(k,\delta) \leq 2^{2^{\delta^{-2^{2^{k+9}}}}}. La borne inférieure est due à Behrend et Rankin (en)[3], la borne supérieure a été étudiée par Gowers.

Dans le cas où k=3 nous avons la majoration suivante, due à Bourgain[4] :

N(3,\delta) \leq C^{\delta^{-2}\log(1/\delta)}.

Historique[modifier | modifier le code]

Le cas k=3 a été démontré en 1953 par Klaus Roth[5], en adaptant la méthode du cercle de Hardy-Littlewood. Cependant sa méthode ne se généralisait pas à tous les cas, et il a fallu attendre 1969 pour que Szeremédi démontre le cas k=4. En 1972, Roth étend à son tour sa méthode au cas k=4, et le cas général est finalement démontré par Szeremédi en 1975. Depuis, ce théorème a connu de nombreuses démonstrations faisant appel à divers domaines des mathématiques[6].

Ce théorème est un cas particulier de la conjecture d'Erdős sur les progressions arithmétiques, dont un autre cas résolu est le théorème de Green-Tao.

Application à la théorie des graphes : le lemme de régularité de Szemerédi[modifier | modifier le code]

En théorie des graphes, ce théorème est souvent utilisé sous la forme suivante, couramment appelée « Lemme de régularité de Szemerédi ». Il est notamment utilisé en test de propriété[7].

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 :

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

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 ε-régulier, si pour tous les sous-ensembles A de X et B de Y, tels que : |A| \ge \varepsilon |X| et|B| \ge \varepsilon |Y|, on a :

\left| d(X,Y) - d(A,B) \right| \le \varepsilon.

Le lemme de régularité peut alors s'énoncer ainsi (bien qu'il en existe de nombreuses variantes) :

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

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

  1. Jean-Paul Thouvenot, « La démonstration de Furstenberg du théorème de Szemerédi sur les progressions arithmétiques », Séminaire Bourbaki, no 518,‎ , p. 221-232 (lire en ligne)
  2. Endre Szemerédi, « On sets of integers containing no k elements in arithmetic progression », Acta Arithmetica, no 27,‎ , p. 199–245 (lire en ligne).
  3. (en) Robert A. Rankin, « Sets of integers containing not more than a given number of terms in arithmetical progression », Proc. Roy. Soc. Edinburgh Sect. A, vol. 65,‎ , p. 332–344
  4. (en) Jean Bourgain, « On triples in arithmetic progression », Geom. Func. Anal., vol. 9,‎ , p. 968–984
  5. (en) K. F. Roth, « On certain sets of integers, I », J. London Math. Soc., vol. 28,‎ , p. 104-109
  6. Dans son post du 13/02/2010 (en) sur son blog, Terence Tao n'en recense pas moins de 16.
  7. Voir par exemple : Alon Noga, Fischer Eldar, Newman Ilan et Shapira Asaf, « A combinatorial characterization of the testable graph properties: it’s all about regularity », dans Proc. of STOC 2006,‎ , p. 251-260.

Articles connexes[modifier | modifier le code]