534:, two of these elements must fall into the same class. Suppose for instance 111112 and 112222 fall into class (5), thus 11111211, 11111222, 11222211, 11222222 are crosses and 11111233, 11222233 are noughts. But now consider the position 11333233, which must be filled with either a cross or a nought. If it is filled with a cross, then the combinatorial line 11xxx2xx is filled entirely with crosses, contradicting our hypothesis. If instead it is filled with a nought, then the combinatorial line 11xxx233 is filled entirely with noughts, again contradicting our hypothesis. Similarly if any other two of the above seven elements of
135:
1245:
463:
two of them must be filled with the same symbol. Since any two of these positions are part of a combinatorial line, the third element of that line must be occupied by the opposite symbol (since we are assuming that no combinatorial line has all three elements filled with the same symbol). In other
379:
to, say, 8 (so that the board is now eight-dimensional, with 3 = 6561 positions), and partition this board into two sets (the "noughts" and "crosses"), then one of the two sets must contain a combinatorial line (i.e. no draw is possible in this variant of
362:
A typical combinatorial line would be the word 2x, which corresponds to the line 21, 22, 23; another combinatorial line is xx, which is the line 11, 22, 33. (Note that the line 13, 22, 31, while a valid line for the game
546:
fall into the same class. Since we have a contradiction in all cases, the original hypothesis must be false; thus there must exist at least one combinatorial line consisting entirely of noughts or entirely of crosses.
458:
board, for instance "132113??" gives such a board. For each such board "abcdef??", we consider the positions "abcdef11", "abcdef12", "abcdef22". Each of these must be filled with either a nought or a cross, so by the
641:
of length three, all of whose elements are the same color. This is simply because all of the combinatorial lines appearing in the above proof of the Hales–Jewett theorem, also form arithmetic progressions in
514:
into six classes, corresponding to each of the above six possibilities. (If an element abcdef obeys multiple possibilities, we can choose one arbitrarily, e.g. by choosing the highest one on the above list).
454:
and assume that neither the set of noughts nor the set of crosses contains a combinatorial line. If we fix the first six elements of such a string and let the last two vary, we obtain an ordinary
450:
is a string of eight numbers from 1 to 3, e.g. 13211321 is an element of the hypercube. We are assuming that this hypercube is completely filled with "noughts" and "crosses". We shall use a
404: = 8 discussed above. The idea is to reduce this task to that of proving simpler versions of the Hales–Jewett theorem (in this particular case, to the cases
371:
board into two sets, e.g. {11, 22, 23, 31} and {12, 13, 21, 32, 33}, neither of which contain a combinatorial line (and would correspond to a draw in the game of
665:, the Hales–Jewett theorem also has a density version. In this strengthened version of the Hales–Jewett theorem, instead of coloring the entire
367:, is not considered a combinatorial line.) In this particular case, the Hales–Jewett theorem does not apply; it is possible to divide the
1412:
114:
are playing, and no matter which player plays each turn, provided only that it is played on a board of sufficiently high dimension
1152:
1005:
1056:
Dodos, Pandelis; Kanellopoulos, Vassilis; Tyros, Konstantinos (2014). "A simple proof of the density Hales–Jewett theorem".
898:
1288:
1116:
1111:
992:. Bolyai Society Mathematical Studies. Vol. 21. Budapest: János Bolyai Mathematical Society. pp. 659–687.
43:, concerning the degree to which high-dimensional objects must necessarily exhibit some combinatorial structure.
1117:
A blog post by Steven
Landsburg discussing how the proof of this theorem was improved collaboratively on a blog
735:
646:. A more general formulation of this argument can be used to show that the Hales–Jewett theorem generalizes
654:
647:
464:
words, for each choice of "abcdef" (which can be thought of as an element of the six-dimensional hypercube
1224:
122:, one can thus conclude that if two players alternate, then the first player has a winning strategy when
1298:
812:
428: = 6). One can prove the general case of the Hales–Jewett theorem by similar methods, using
1417:
1145:
1058:
662:
984:
Gowers, William
Timothy (2010). "Polymath and the density Hales-Jewett theorem". In Bárány, Imre;
764:
1407:
727:
developed a new proof of the density Hales–Jewett theorem based on ideas from the proof of the
638:
451:
429:
1351:
1308:
1105:
947:
1324:
1229:
1169:
1138:
1089:
1042:
1015:
970:
919:
875:
825:
786:
719:
The density Hales–Jewett theorem was originally proved by
Furstenberg and Katznelson using
531:
460:
126:
is sufficiently large, though no practical algorithm for obtaining this strategy is known.
518:
Now consider the seven elements 111111, 111112, 111122, 111222, 112222, 122222, 222222 in
82:
colors, there must be one row, column, or certain diagonal (more details below) of length
8:
1345:
1283:
1214:
845:
587:
1067:
1029:
Ajtai, Miklós; Szemerédi, Endre (1974). "Sets of lattice points that form no squares".
923:
893:
889:
863:
739:
583:
230:
985:
777:
759:
247:; combinatorial lines correspond to rows, columns, and (some of the) diagonals of the
1001:
927:
119:
1376:
1234:
1112:
Science News article on the collaborative proof of the density Hales-Jewett theorem
1077:
993:
956:
907:
853:
772:
731:. Dodos, Kanellopoulos, and Tyros gave a simplified version of the Polymath proof.
724:
40:
1204:
1199:
1085:
1038:
1011:
997:
966:
915:
871:
821:
782:
728:
46:
An informal geometric statement of the theorem is that for any positive integers
36:
1244:
961:
942:
625:
be the set of all eight-digit numbers whose digits are all either 1, 2, 3 (thus
1177:
720:
591:
1121:
621:
Observe that the above argument also gives the following corollary: if we let
289:
parts, there is at least one part that contains an entire combinatorial line.
1401:
32:
28:
1366:
800:
1081:
1381:
1361:
1303:
1192:
1161:
804:
575:
455:
381:
372:
368:
364:
319:
251:. The Hales–Jewett theorem then states that for given positive integers
172:. This set forms the hypercube that is the subject of the theorem. A
99:
20:
134:
1356:
1329:
1259:
911:
867:
650:. Indeed the Hales–Jewett theorem is substantially a stronger theorem.
558: = 4. If one extends the above argument to general values of
704:
with some given density 0 < δ < 1. The theorem states that if
666:
500:
436:
248:
858:
840:
387:
1371:
551:
1072:
1386:
1339:
1275:
1187:
643:
86:
all of whose cells are the same color. In other words, assuming
1182:
1130:
1219:
1209:
221:) obtained by replacing all instances of the special element
554:
was somewhat wasteful; in fact the same theorem holds for
392:
We now prove the Hales–Jewett theorem in the special case
1125:
896:(1991). "A density version of the Hales–Jewett theorem".
841:"Primitive recursive bounds for van der Waerden numbers"
495:
abcdef12 and abcdef22 are crosses; abcdef32 is a nought.
492:
abcdef11 and abcdef22 are crosses; abcdef33 is a nought.
489:
abcdef11 and abcdef12 are crosses; abcdef13 is a nought.
1055:
716:
must necessarily contain an entire combinatorial line.
594:, and is still the best known bound in general for the
486:
abcdef12 and abcdef22 are noughts; abcdef32 is a cross.
483:
abcdef11 and abcdef22 are noughts; abcdef33 is a cross.
480:
abcdef11 and abcdef12 are noughts; abcdef13 is a cross.
164:
letters; that is, the set of sequences of {1, 2, ...,
888:
205:
in place of at least one of the letters. The words
805:"The first nontrivial Hales-Jewett number is four"
616:
106:players cannot end in a draw, no matter how large
943:"A new proof of the density Hales–Jewett theorem"
940:
629:contains numbers such as 11333233), and we color
582:given by the above argument grows as fast as the
388:Proof of Hales–Jewett theorem (in a special case)
94:are fixed, the higher-dimensional, multi-player,
16:Fundamental combinatorial result of Ramsey theory
1399:
574: = 2 (which corresponds to two-player
799:
1028:
476:), there are six (overlapping) possibilities:
1146:
758:Hales, Alfred W.; Jewett, Robert I. (1963).
757:
1153:
1139:
499:Thus we can partition the six-dimensional
1071:
960:
857:
776:
686:colors, one is given an arbitrary subset
133:
734:The Hales–Jewett is generalized by the
1400:
983:
838:
375:). On the other hand, if we increase
98:-in-a-row generalization of a game of
1134:
708:is sufficiently large depending on
129:
13:
318:in this case is just the standard
259:, there exists a positive integer
14:
1429:
1099:
778:10.1090/S0002-9947-1963-0143712-1
760:"Regularity and positional games"
271:, such that for any partition of
201:but includes the special element
1413:Theorems in discrete mathematics
1289:Harary's generalized tic-tac-toe
1243:
1160:
617:Connections with other theorems
570:will grow very fast; even when
1122:Higher-Dimensional Tic-Tac-Toe
1049:
1022:
977:
934:
899:Journal d'Analyse Mathématique
882:
832:
793:
751:
156:be the set of words of length
110:is, no matter how many people
1:
745:
138:Combinatorical line in a cube
998:10.1007/978-3-642-14444-8_21
384:). For a proof, see below.
322:board, with nine positions:
58:such that if the cells of a
7:
962:10.4007/annals.2012.175.3.6
10:
1434:
1299:Strategy-stealing argument
941:D. H. J. Polymath (2012).
120:strategy-stealing argument
1317:
1252:
1241:
1168:
1059:Int. Math. Res. Not. IMRN
803:; Tressler, Eric (2014).
736:Graham–Rothschild theorem
655:van der Waerden's theorem
648:van der Waerden's theorem
839:Shelah, Saharon (1988).
738:, on higher-dimensional
1031:Stud. Sci. Math. Hungar
765:Trans. Amer. Math. Soc.
639:arithmetic progression
637:contains at least one
633:with two colors, then
452:proof by contradiction
430:mathematical induction
160:over an alphabet with
139:
78:cube are colored with
1309:Paper-and-pencil game
1124:| Infinite Series by
948:Annals of Mathematics
137:
1294:Hales–Jewett theorem
1230:Ultimate tic-tac-toe
1108:- begins on slide 57
712:and δ, then the set
532:pigeonhole principle
461:pigeonhole principle
435:Each element of the
304:= 2. The hypercube
25:Hales–Jewett theorem
1215:Quantum tic-tac-toe
1082:10.1093/imrn/rnt041
894:Katznelson, Yitzhak
890:Furstenberg, Hillel
846:J. Amer. Math. Soc.
740:combinatorial cubes
663:Szemerédi's theorem
596:Hales–Jewett number
588:primitive recursive
416: = 2 and
1352:Three men's morris
912:10.1007/BF03041066
584:Ackermann function
292:For example, take
231:combinatorial line
140:
54:there is a number
1395:
1394:
1325:Nine men's morris
1106:Full proof of HJT
1066:(12): 3340–3352.
1007:978-963-9453-14-2
990:An irregular mind
690:of the hypercube
360:
359:
197:still has length
118:. By a standard
27:is a fundamental
1425:
1418:Positional games
1284:Kaplansky's game
1253:Related concepts
1247:
1235:Wild tic-tac-toe
1155:
1148:
1141:
1132:
1131:
1094:
1093:
1075:
1053:
1047:
1046:
1026:
1020:
1019:
986:Solymosi, József
981:
975:
974:
964:
955:(3): 1283–1327.
938:
932:
931:
886:
880:
879:
861:
836:
830:
829:
813:Ars Combinatoria
809:
797:
791:
790:
780:
755:
725:Polymath Project
723:. In 2009, the
703:
702:
681:
680:
644:decimal notation
590:bound is due to
545:
544:
529:
528:
513:
512:
475:
474:
449:
448:
424: = 6,
420: = 2,
412: = 2,
408: = 2,
400: = 2,
396: = 3,
325:
324:
317:
316:
284:
283:
246:
245:
225:with 1, 2, ...,
196:
195:
155:
154:
130:Formal statement
41:Robert I. Jewett
1433:
1432:
1428:
1427:
1426:
1424:
1423:
1422:
1398:
1397:
1396:
1391:
1313:
1248:
1239:
1205:Order and Chaos
1200:Number Scrabble
1164:
1159:
1102:
1097:
1054:
1050:
1027:
1023:
1008:
982:
978:
939:
935:
887:
883:
859:10.2307/1990952
837:
833:
807:
798:
794:
756:
752:
748:
729:corners theorem
701:
696:
695:
694:
679:
674:
673:
672:
659:density version
657:has a stronger
619:
543:
540:
539:
538:
527:
524:
523:
522:
511:
508:
507:
506:
473:
470:
469:
468:
447:
444:
443:
442:
390:
315:
310:
309:
308:
282:
277:
276:
275:
263:, depending on
244:
239:
238:
237:
194:
189:
188:
187:
153:
148:
147:
146:
132:
37:Alfred W. Hales
17:
12:
11:
5:
1431:
1421:
1420:
1415:
1410:
1393:
1392:
1390:
1389:
1384:
1379:
1374:
1369:
1364:
1359:
1354:
1349:
1342:
1337:
1336:
1335:
1327:
1321:
1319:
1315:
1314:
1312:
1311:
1306:
1301:
1296:
1291:
1286:
1281:
1273:
1256:
1254:
1250:
1249:
1242:
1240:
1238:
1237:
1232:
1227:
1222:
1217:
1212:
1207:
1202:
1197:
1196:
1195:
1185:
1180:
1178:3D tic-tac-toe
1174:
1172:
1166:
1165:
1158:
1157:
1150:
1143:
1135:
1129:
1128:
1119:
1114:
1109:
1101:
1100:External links
1098:
1096:
1095:
1048:
1021:
1006:
976:
933:
881:
852:(3): 683–697.
831:
792:
771:(2): 222–229.
749:
747:
744:
721:ergodic theory
697:
675:
618:
615:
592:Saharon Shelah
541:
525:
509:
497:
496:
493:
490:
487:
484:
481:
471:
445:
389:
386:
358:
357:
354:
351:
347:
346:
343:
340:
336:
335:
332:
329:
311:
278:
240:
190:
149:
131:
128:
15:
9:
6:
4:
3:
2:
1430:
1419:
1416:
1414:
1411:
1409:
1408:Ramsey theory
1406:
1405:
1403:
1388:
1385:
1383:
1380:
1378:
1375:
1373:
1370:
1368:
1365:
1363:
1360:
1358:
1355:
1353:
1350:
1348:
1347:
1343:
1341:
1338:
1333:
1332:
1331:
1328:
1326:
1323:
1322:
1320:
1318:Similar games
1316:
1310:
1307:
1305:
1302:
1300:
1297:
1295:
1292:
1290:
1287:
1285:
1282:
1280:
1278:
1274:
1272:
1270:
1266:
1262:
1258:
1257:
1255:
1251:
1246:
1236:
1233:
1231:
1228:
1226:
1223:
1221:
1218:
1216:
1213:
1211:
1208:
1206:
1203:
1201:
1198:
1194:
1191:
1190:
1189:
1186:
1184:
1181:
1179:
1176:
1175:
1173:
1171:
1167:
1163:
1156:
1151:
1149:
1144:
1142:
1137:
1136:
1133:
1127:
1123:
1120:
1118:
1115:
1113:
1110:
1107:
1104:
1103:
1091:
1087:
1083:
1079:
1074:
1069:
1065:
1061:
1060:
1052:
1044:
1040:
1036:
1032:
1025:
1017:
1013:
1009:
1003:
999:
995:
991:
987:
980:
972:
968:
963:
958:
954:
950:
949:
944:
937:
929:
925:
921:
917:
913:
909:
906:(1): 64–119.
905:
901:
900:
895:
891:
885:
877:
873:
869:
865:
860:
855:
851:
848:
847:
842:
835:
827:
823:
819:
815:
814:
806:
802:
801:Hindman, Neil
796:
788:
784:
779:
774:
770:
767:
766:
761:
754:
750:
743:
741:
737:
732:
730:
726:
722:
717:
715:
711:
707:
700:
693:
689:
685:
678:
671:
668:
664:
660:
656:
651:
649:
645:
640:
636:
632:
628:
624:
614:
612:
608:
604:
601: =
600:
597:
593:
589:
586:. The first
585:
581:
577:
573:
569:
565:
561:
557:
553:
548:
537:
533:
521:
516:
505:
502:
494:
491:
488:
485:
482:
479:
478:
477:
467:
462:
457:
453:
441:
438:
433:
431:
427:
423:
419:
415:
411:
407:
403:
399:
395:
385:
383:
378:
374:
370:
366:
355:
352:
349:
348:
344:
341:
338:
337:
333:
330:
327:
326:
323:
321:
314:
307:
303:
299:
295:
290:
288:
281:
274:
270:
266:
262:
258:
254:
250:
243:
236:
233:in the space
232:
228:
224:
220:
216:
212:
208:
204:
200:
193:
186:
182:
178:
175:
174:variable word
171:
167:
163:
159:
152:
145:
136:
127:
125:
121:
117:
113:
109:
105:
101:
97:
93:
89:
85:
81:
77:
73:
69:
65:
62:-dimensional
61:
57:
53:
49:
44:
42:
38:
34:
33:Ramsey theory
30:
29:combinatorial
26:
22:
1367:Connect Four
1344:
1334:Tic-Stac-Toe
1293:
1276:
1268:
1264:
1260:
1063:
1057:
1051:
1034:
1030:
1024:
989:
979:
952:
946:
936:
903:
897:
884:
849:
844:
834:
817:
811:
795:
768:
763:
753:
733:
718:
713:
709:
705:
698:
691:
687:
683:
676:
669:
658:
652:
634:
630:
626:
622:
620:
610:
606:
602:
598:
595:
579:
571:
567:
563:
559:
555:
549:
535:
519:
517:
503:
498:
465:
439:
434:
425:
421:
417:
413:
409:
405:
401:
397:
393:
391:
376:
361:
312:
305:
301:
297:
293:
291:
286:
279:
272:
268:
264:
260:
256:
252:
241:
234:
226:
222:
218:
214:
210:
206:
202:
198:
191:
184:
180:
176:
173:
169:
168:} of length
165:
161:
157:
150:
143:
141:
123:
115:
111:
107:
103:
95:
91:
87:
83:
79:
75:
71:
67:
63:
59:
55:
51:
47:
45:
35:named after
24:
18:
1382:Toss Across
1304:Futile game
1193:Treblecross
1162:Tic-tac-toe
820:: 385–390.
576:tic-tac-toe
456:tic-tac-toe
382:tic-tac-toe
373:tic-tac-toe
369:tic-tac-toe
365:tic-tac-toe
320:tic-tac-toe
100:tic-tac-toe
21:mathematics
1402:Categories
1357:Nine Holes
1330:Score Four
746:References
550:The above
530:. By the
213:(2), ...,
31:result of
1073:1209.4986
928:123036744
667:hypercube
501:hypercube
437:hypercube
300:= 2, and
249:hypercube
229:, form a
1372:Connect6
1170:Variants
1037:: 9–11.
988:(eds.).
653:Just as
552:argument
1387:Pentago
1340:Gobblet
1188:Notakto
1090:3217664
1043:0369299
1016:2815619
971:2912706
920:1191743
876:0929498
868:1990952
826:3186481
787:0143712
609:,
566:, then
183:) over
1346:Quarto
1183:Gomoku
1088:
1041:
1014:
1004:
969:
926:
918:
874:
866:
824:
785:
578:) the
23:, the
1271:-game
1220:Renju
1210:Pente
1068:arXiv
924:S2CID
864:JSTOR
808:(PDF)
682:into
296:= 3,
285:into
209:(1),
102:with
74:×...×
1362:Achi
1279:game
1064:2014
1002:ISBN
562:and
267:and
255:and
142:Let
90:and
50:and
39:and
1377:OXO
1225:SOS
1126:PBS
1078:doi
994:doi
957:doi
953:175
908:doi
854:doi
818:113
773:doi
769:106
661:in
613:).
356:33
345:23
334:13
19:In
1404::
1086:MR
1084:.
1076:.
1062:.
1039:MR
1033:.
1012:MR
1010:.
1000:.
967:MR
965:.
951:.
945:.
922:.
916:MR
914:.
904:57
902:.
892:;
872:MR
870:.
862:.
843:.
822:MR
816:.
810:.
783:MR
781:.
762:.
742:.
432:.
353:32
350:31
342:22
339:21
331:12
328:11
1277:n
1269:k
1267:,
1265:n
1263:,
1261:m
1154:e
1147:t
1140:v
1092:.
1080::
1070::
1045:.
1035:9
1018:.
996::
973:.
959::
930:.
910::
878:.
856::
850:1
828:.
789:.
775::
714:A
710:n
706:H
699:n
692:W
688:A
684:c
677:n
670:W
635:A
631:A
627:A
623:A
611:c
607:n
605:(
603:H
599:H
580:H
572:c
568:H
564:c
560:n
556:H
542:3
536:W
526:3
520:W
510:3
504:W
472:3
466:W
446:3
440:W
426:H
422:c
418:n
414:H
410:c
406:n
402:H
398:c
394:n
377:H
313:n
306:W
302:c
298:H
294:n
287:c
280:n
273:W
269:c
265:n
261:H
257:c
253:n
242:n
235:W
227:n
223:x
219:n
217:(
215:w
211:w
207:w
203:x
199:H
192:n
185:W
181:x
179:(
177:w
170:H
166:n
162:n
158:H
151:n
144:W
124:H
116:H
112:c
108:n
104:c
96:n
92:c
88:n
84:n
80:c
76:n
72:n
70:×
68:n
66:×
64:n
60:H
56:H
52:c
48:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
