Théorème de Hales-Jewett
![Cliquez sur l'image pour voir les détails concernant l'auteur, la licence et la page d'origine de l'image](http://upload.wikimedia.org/wikipedia/commons/thumb/9/98/Line_in_combinatorics.png/220px-Line_in_combinatorics.png)
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 »[1].
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 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 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 sur est un mot de longueur H qui contient une élément spécial x à la place d'au moins une des lettres. Les mots 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 ; 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 en c parties, il y a au moins une partie qui contient une droite combinatoire[2] .
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 , 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 , qui correspond à la droite 21, 22, 23 ; une autre droite combinatoire est , 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 en c couleurs, on donne un sous-ensemble arbitraire A de l'hypercube 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[3]. En 2009, le projet Polymath a développé une nouvelle preuve[4],[5] 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 [6]. Dodos, Kanellopoulos et Tyros ont donné une version simplifiée de la preuve du Polymath[7].
Le théorème de Hales–Jewett est généralisé par le théorème de Graham–Rothschild sur des cubes combinatoires en dimension supérieure.
Notes et références
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Hales–Jewett theorem » (voir la liste des auteurs).
- Hales et Jewett, « Regularity and positional games », Trans. Amer. Math. Soc., vol. 106, no 2, , p. 222–229 (DOI 10.1090/S0002-9947-1963-0143712-1, MR 0143712).
- Ronald L. Graham, Bruce L. Rothschild et Joel H. Spencer, Ramsey Theory, Wiley-Interscience, , 2e éd. (ISBN 978-0-471-50046-9), p. 36.
- Furstenberg et Katznelson, « A density version of the Hales–Jewett theorem », Journal d'Analyse Mathématique, vol. 57, no 1, , p. 64–119 (DOI 10.1007/BF03041066, MR 1191743).
- D. H. J. Polymath, « A new proof of the density Hales–Jewett theorem », Annals of Mathematics, vol. 175, no 3, , p. 1283–1327 (DOI 10.4007/annals.2012.175.3.6, MR 2912706).
- William Timothy Gowers, « Polymath and the density Hales-Jewett theorem », dans Imre Bárány et József Solymosi, An irregular mind, vol. 21, Budapest, coll. « Bolyai Society Mathematical Studies », , 659–687 p. (ISBN 978-963-9453-14-2, DOI 10.1007/978-3-642-14444-8_21, MR 2815619)
- soit d'une confusion entre les modèles
{{article encyclopédique}}
et{{article}}
- soit d'une confusion entre les paramètres
périodique
etéditeur
.
Merci de consulter la documentation des modèles et de corriger l'article. - soit d'une confusion entre les modèles
- Ajtai et Szemerédi, « Sets of lattice points that form no squares », Stud. Sci. Math. Hungar., vol. 9, , p. 9–11 (MR 0369299)
- Dodos, Kanellopoulos et Tyros, « A simple proof of the density Hales–Jewett theorem », International Mathematics Research Notices, vol. 2014, no 12, , p. 3340–3352 (DOI 10.1093/imrn/rnt041, MR 3217664, arXiv 1209.4986).
Liens externes