Théorème de Szemerédi

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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

Énoncé[modifier | modifier le code]

Soit k un entier positif et 0 < δ ≤ 1/2. Alors il existe un entier N = N(k,\delta)\, tel que pour tout sous-ensemble de {1,...N} d'au moins δN éléments, ce sous-ensemble 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)[2], la borne supérieure a été étudiée par Gowers.

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

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[4], 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[5].

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é[6].

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,‎ 1978, p. 221-232 (lire en ligne)
  2. (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,‎ 1962, p. 332–344
  3. (en) Jean Bourgain, « On triples in arithmetic progression », Geom. Func. Anal., vol. 9,‎ 1999, p. 968–984
  4. (en) K. F. Roth, « On certain sets of integers, I », J. London Math. Soc., vol. 28,‎ 1953, p. 104-109
  5. Dans son post du 13/02/2010 (en) sur son blog, Terence Tao n'en recense pas moins de 16.
  6. 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,‎ 2006, p. 251-260.

Articles connexes[modifier | modifier le code]