stringtranslate.com

Теорема Хейлса–Джеветта

В математике теорема Хейлза–Джуэтт [1] является фундаментальным комбинаторным результатом теории Рамсея, названной в честь Альфреда У. Хейлза и Роберта И. Джуэтта , касающейся степени, в которой многомерные объекты обязательно должны демонстрировать некоторую комбинаторную структуру.

Неформальное геометрическое утверждение теоремы заключается в том, что для любых положительных целых чисел n и c существует число H такое, что если ячейки куба размером n × n × n ×...× n размером H раскрашены в c цветов, то должна быть одна строка, столбец или определенная диагональ (подробнее ниже) длины n, все ячейки которой имеют один цвет. Другими словами, предполагая, что n и c фиксированы, многомерное, многопользовательское, n -в-ряд обобщение игры в крестики-нолики с c игроками не может закончиться вничью, независимо от того, насколько велико n , независимо от того, сколько людей c играет, и независимо от того, какой игрок делает каждый ход, при условии, что игра происходит на доске достаточно большой размерности H. Таким образом, с помощью стандартного аргумента о краже стратегии можно заключить, что если два игрока ходят по очереди, то у первого игрока есть выигрышная стратегия, когда H достаточно велико, хотя неизвестен ни один практический алгоритм получения этой стратегии.

Официальное заявление

Комбинаторная линия в кубе

Пусть WН
нбудет множеством слов длины H над алфавитом с n буквами; то есть множеством последовательностей {1, 2, ..., n } длины H . Это множество образует гиперкуб, который является предметом теоремы. Переменное слово w ( x ) над WН
нвсе еще имеет длину H, но включает специальный элемент x вместо по крайней мере одной из букв. Слова w (1), w (2), ..., w ( n ), полученные путем замены всех экземпляров специального элемента x на 1, 2, ..., n , образуют комбинаторную строку в пространстве WН
н; комбинаторные линии соответствуют строкам, столбцам и (некоторым) диагоналям гиперкуба . Теорема Хейлса–Джеветта утверждает, что для данных положительных целых чисел n и c существует положительное целое число H , зависящее от n и c , такое, что для любого разбиения WН
нна c частей, существует по крайней мере одна часть, содержащая целую комбинаторную строку.

Например, возьмем n = 3, H = 2 и c = 2. Гиперкуб WН
нв данном случае это просто стандартная доска для игры в крестики-нолики с девятью позициями:

Типичной комбинаторной линией будет слово 2x, которое соответствует линии 21, 22, 23; другой комбинаторной линией является xx, которая является линией 11, 22, 33. (Обратите внимание, что линия 13, 22, 31, хотя и является допустимой линией для игры в крестики-нолики , не считается комбинаторной линией.) В этом конкретном случае теорема Хейлза–Джеветта неприменима; можно разделить доску для игры в крестики-нолики на два множества, например {11, 22, 23, 31} и {12, 13, 21, 32, 33}, ни одно из которых не содержит комбинаторной линии (и будет соответствовать ничьей в игре в крестики-нолики ). С другой стороны, если мы увеличим H , скажем, до 8 (так что доска станет восьмимерной, с 3 · 8 = 6561 позицией), и разделим эту доску на два множества («крестики-нолики» и «нолики»), то одно из двух множеств должно содержать комбинаторную линию (т. е. в этом варианте крестиков-ноликов ничья невозможна ). Доказательство см. ниже.

Доказательство теоремы Хейлза–Джеветта (в частном случае)

Теперь докажем теорему Хейлза–Джеветта в частном случае n  = 3, c  = 2, H  = 8, обсуждаемом выше. Идея состоит в том, чтобы свести эту задачу к доказательству более простых версий теоремы Хейлза–Джеветта (в данном конкретном случае к случаям n  = 2, c  = 2, H  = 2 и n  = 2, c  = 6, H  = 6). Общий случай теоремы Хейлза–Джеветта можно доказать аналогичными методами, используя математическую индукцию .

Каждый элемент гиперкуба W8
3представляет собой строку из восьми чисел от 1 до 3, например, 13211321 является элементом гиперкуба. Мы предполагаем, что этот гиперкуб полностью заполнен «ноликами» и «крестиками». Мы воспользуемся доказательством от противного и предположим, что ни множество ноликов, ни множество крестиков не содержат комбинаторной строки. Если мы зафиксируем первые шесть элементов такой строки и позволим последним двум меняться, мы получим обычную доску для игры в крестики-нолики , например, «132113??» дает такую ​​доску. Для каждой такой доски «abcdef??» мы рассматриваем позиции «abcdef11», «abcdef12», «abcdef22». Каждая из них должна быть заполнена либо ноликом, либо крестиком, поэтому по принципу ящика две из них должны быть заполнены одним и тем же символом. Поскольку любые две из этих позиций являются частью комбинаторной строки, третий элемент этой строки должен быть занят противоположным символом (поскольку мы предполагаем, что ни одна комбинаторная строка не имеет всех трех элементов, заполненных одним и тем же символом). Другими словами, для каждого выбора "abcdef" (который можно рассматривать как элемент шестимерного гиперкуба W6
3), существует шесть (перекрывающихся) возможностей:

  1. abcdef11 и abcdef12 — нолики; abcdef13 — крестик.
  2. abcdef11 и abcdef22 — нолики; abcdef33 — крестик.
  3. abcdef12 и abcdef22 — нолики; abcdef32 — крестик.
  4. abcdef11 и abcdef12 — крестики; abcdef13 — ноль.
  5. abcdef11 и abcdef22 — крестики; abcdef33 — ноль.
  6. abcdef12 и abcdef22 — крестики; abcdef32 — ноль.

Таким образом, мы можем разбить шестимерный гиперкуб W6
3на шесть классов, соответствующих каждой из шести приведенных выше возможностей. (Если элемент abcdef подчиняется нескольким возможностям, мы можем выбрать одну произвольно, например, выбрав наивысшую из приведенного выше списка).

Теперь рассмотрим семь элементов 111111, 111112, 111122, 111222, 112222, 122222, 222222 в W6
3. По принципу ящика два из этих элементов должны попадать в один и тот же класс. Предположим, например, что 111112 и 112222 попадают в класс (5), таким образом, 11111211, 11111222, 11222211, 11222222 являются крестами, а 11111233, 11222233 являются нулями. Но теперь рассмотрим позицию 11333233, которая должна быть заполнена либо крестом, либо нулем. Если она заполнена крестом, то комбинаторная строка 11xxx2xx полностью заполнена крестами, что противоречит нашей гипотезе. Если вместо этого она заполнена нулем, то комбинаторная строка 11xxx233 полностью заполнена нулями, что снова противоречит нашей гипотезе. Аналогично, если любые другие два из указанных выше семи элементов W6
3попадают в тот же класс. Поскольку во всех случаях мы имеем противоречие, исходная гипотеза должна быть ложной; таким образом, должна существовать по крайней мере одна комбинаторная линия, состоящая полностью из нулей или полностью из крестиков.

Приведенный выше аргумент был несколько расточительным; на самом деле та же теорема справедлива для H  = 4. [2] Если расширить приведенный выше аргумент на общие значения n и c , то H будет расти очень быстро; даже когда c  = 2 (что соответствует игре в крестики-нолики с двумя игроками ), H , заданная приведенным выше аргументом, растет так же быстро, как функция Аккермана . Первая примитивная рекурсивная граница принадлежит Сахарону Шелаху [ 3] и до сих пор является самой известной границей в целом для числа Хейлза–Джеветта H  =  H ( n ,  c ).

Связи с другими теоремами

Обратите внимание, что приведенный выше аргумент также дает следующее следствие: если мы допустим, что A будет множеством всех восьмизначных чисел, все цифры которых равны 1, 2, 3 (таким образом, A содержит такие числа, как 11333233), и мы раскрасим A двумя цветами, то A будет содержать по крайней мере одну арифметическую прогрессию длины три, все элементы которой имеют один и тот же цвет. Это просто потому, что все комбинаторные линии, появляющиеся в приведенном выше доказательстве теоремы Хейлза–Джеветта, также образуют арифметические прогрессии в десятичной записи . Более общая формулировка этого аргумента может быть использована для того, чтобы показать, что теорема Хейлза–Джеветта обобщает теорему ван дер Вардена . Действительно, теорема Хейлза–Джеветта является существенно более сильной теоремой.

Так же, как теорема Ван дер Вардена имеет более сильную версию плотности в теореме Семереди , теорема Хейлза–Джеветта также имеет версию плотности. В этой усиленной версии теоремы Хейлза–Джеветта вместо того, чтобы раскрашивать весь гиперкуб WН
нв c цветов, дано произвольное подмножество A гиперкуба WН
нс некоторой заданной плотностью 0 < δ < 1. Теорема утверждает, что если H достаточно велико в зависимости от n и δ, то множество A обязательно должно содержать целую комбинаторную линию.

Теорема плотности Хейлза–Джеветта была первоначально доказана Фюрстенбергом и Кацнельсоном с использованием эргодической теории . [4] В 2009 году проект Polymath разработал новое доказательство [5] [6] теоремы плотности Хейлза–Джеветта, основанное на идеях из доказательства теоремы об углах . [7] Додос, Канеллопулос и Тирос дали упрощенную версию доказательства Polymath. [8]

Теорема Хейлза–Джуэтт обобщается теоремой Грэма–Ротшильда на многомерных комбинаторных кубах .

Ссылки

  1. ^ Хейлз, Альфред В.; Джуэтт, Роберт И. (1963). «Регулярность и позиционные игры». Trans. Amer. Math. Soc. 106 (2): 222–229. doi : 10.1090/S0002-9947-1963-0143712-1 . MR  0143712.
  2. ^ Хиндман, Нил ; Тресслер, Эрик (2014). «Первое нетривиальное число Хейлза-Джуэтт равно четырем» (PDF) . Ars Combinatoria . 113 : 385–390. MR  3186481.
  3. ^ Shelah, Saharon (1988). «Примитивные рекурсивные границы для чисел Ван дер Вардена». J. Amer. Math. Soc. 1 (3): 683–697. doi : 10.2307/1990952 . JSTOR  1990952. MR  0929498.
  4. ^ Фюрстенберг, Хиллель ; Кацнельсон, Ицхак (1991). «Плотностная версия теоремы Хейлза–Джеветта». Journal d'Analyse Mathématique . 57 (1): 64–119. doi :10.1007/BF03041066. MR  1191743. S2CID  123036744.
  5. ^ DHJ Polymath (2012). «Новое доказательство теоремы плотности Хейлза–Джеветта». Annals of Mathematics . 175 (3): 1283–1327. doi : 10.4007/annals.2012.175.3.6 . MR  2912706.
  6. ^ Гауэрс, Уильям Тимоти (2010). «Эрудит и теорема Хейлса-Джветта о плотности». В Барани Имре; Солимоси, Йожеф (ред.). Нестандартный ум . Общество математических исследований Боляи. Том. 21. Будапешт: Математическое общество Яноша Бойяи. стр. 659–687. дои : 10.1007/978-3-642-14444-8_21. ISBN 978-963-9453-14-2. МР  2815619.
  7. ^ Айтай, Миклош; Семереди, Эндре (1974). «Наборы точек решетки, не образующие квадратов». Стад. наук. Математика. Венгрия . 9 :9–11. МР  0369299.
  8. ^ Додос, Панделис; Канеллопулос, Василис; Тирос, Константинос (2014). «Простое доказательство теоремы плотности Хейлза–Джеветта». Int. Math. Res. Not. IMRN . 2014 (12): 3340–3352. arXiv : 1209.4986 . doi :10.1093/imrn/rnt041. MR  3217664.

Внешние ссылки