Théorème de Hales-Jewett
# Théorème de Hales-Jewett

En mathématiques, le théorème de Hales-Jewett est un résultat combinatoire fondamental de la théorie de Ramsey, nommé d'après Alfred W. Hales et Robert I. Jewett. Il concerne la dimension dans laquelle des objets de cette dimension doivent nécessairement présenter une certaine régularité dans leur structure combinatoire : il est impossible que de tels objets soient « complètement aléatoires ».

## Description informelle

Une description géométrique informelle du théorème est la suivante : pour tous entiers positifs n et c, il existe un nombre H tel que si les cellules d'un cube de côté n en dimension H sont colorées en c couleurs, il existe une ligne, une colonne ou une diagonale (dans un sens précisé ci-dessous) de longueur n dont toutes les cellules sont de la même couleur. En d'autres termes, la généralisation du jeu de morpion ou tic-tac-toe en dimension supérieure, et multi-joueurs, ne peut pas se terminer par un match nul, quelle que soit la taille de n, quel que soit le nombre c de joueurs, et quel que soit l'ordre des joueurs, à la seule condition qu'il soit joué sur un plateau de dimension H suffisamment élevée. Par un argument de vol de stratégie (en) standard, on peut alors conclure que si deux joueurs alternent, alors le premier joueur possède une stratégie gagnante lorsque H est suffisamment grand, bien qu'aucun algorithme pratique pour obtenir cette stratégie ne soit connu.

## Énoncé formel

Soit $W_{n}^{H}$ l'ensemble des mots de longueur H sur un alphabet de n lettres ; c'est-à-dire l'ensemble des suites de longueur H à éléments dans {1, 2, ..., n }. C'est cet ensemble qui est l'hypercube objet du théorème.

Un mot variable $w(x)$ sur $W_{n}^{H}$ est un mot de longueur H qui contient une élément spécial x à la place d'au moins une des lettres. Les mots $w(1),w(2)\ldots ,w(n)$ obtenus en remplaçant toutes les instances de l'élément spécial x respectivement par 1, 2, ..., n, forment une droite combinatoire dans l'espace $W_{n}^{H}$ ; les droites combinatoires correspondent aux lignes, aux colonnes et à (certaines des) diagonales de l'hypercube. Le théorème de Hales-Jewett s'énonce alors comme suit :

Théorème de Hales-Jewett — Pour des entiers positifs donnés n et c, il existe un entier positif H, dépendant de n et c, tel que pour toute partition de $W_{n}^{H}$ en c parties, il y a au moins une partie qui contient une droite combinatoire .

Si on identifie les joueurs à la couleur de leurs pions, le théorème assure l'existence d'une droite combinatoire monochrome.

## Exemple

Soient n = 3, H = 2 et c = 2. L'hypercube $W_{n}^{H}$, dans ce cas, est simplement de le plateau du morpion usuel, avec ses neuf positions :

    11 12 13 21 22 23 31 32 33

Un exemple de droite combinatoire est le mot $2x$, qui correspond à la droite 21, 22, 23 ; une autre droite combinatoire est $xx$, qui est la droite 11, 22, 33. (la droite 13, 22, 31, bien qu'une droite valide pour le morpion, n'est pas représenté par une droite combinatoire). Dans ce cas particulier, le théorème de Hales-Jewett ne s'applique pas ; il est possible de diviser le plateau du morpion en deux ensembles, par exemple {11, 22, 23, 31} et {12, 13, 21, 32, 33}, dont aucun ne contient une droite combinatoire (et correspondrait à un match nul au jeu de tic-tac-toe). D'un autre côté, si on augmente H à 8 par exemple (de sorte que le plateau est maintenant en dimension huit, avec 3 $^8$ = 6561 positions), et si on divise ce plateau en deux ensembles (les "zéros" et les "croix"), alors l'un des deux ensembles doit contenir une droite combinatoire (c'est-à-dire qu'un mouvement gagnant est possible dans cette variante du tic-tac-toe).

## Liens avec d'autres théorèmes

L'énoncé admet le corollaire suivant : si A est l'ensemble des nombres à huit chiffres dont les chiffres sont tous soit 1, 2, 3 (donc A contient des nombres tels que 11333233), et si on colorie A avec deux couleurs, alors A contient au moins une progression arithmétique de longueur trois, dont tous les éléments sont de la même couleur Une formulation plus générale montre que le théorème de Hales-Jewett généralise le de van der Waerden.

Tout comme le théorème de van der Waerden a une « version en densité » plus forte dans le théorème de Szemerédi, le théorème de Hales-Jewett a également une version en densité. Dans cette version renforcée du théorème de Hales-Jewett, au lieu de colorer tout l'hypercube $W_{n}^{H}$ en c couleurs, on donne un sous-ensemble arbitraire A de l'hypercube $W_{n}^{H}$ avec une densité donnée 0 < δ < 1. Le théorème dit que si H est suffisamment grand en fonction de n et de δ, alors l'ensemble A doit nécessairement contenir une droite combinatoire complète.

Le théorème de Hales-Jewett avec densité a été prouvé à l'origine par Furstenberg et Katznelson en utilisant la théorie ergodique. En 2009, le projet Polymath a développé une nouvelle $preuve^,$ du théorème Hales-Jewett en densité, sur la base d'idées tirées de la preuve du théorème des coins (en). Dodos, Kanellopoulos et Tyros ont donné une version simplifiée de la preuve du Polymath.

Le théorème de Hales–Jewett est généralisé par le théorème de Graham–Rothschild (en) sur des cubes combinatoires en dimension supérieure.

