Теорема Хейлза – Джеветта - Hales–Jewett theorem

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

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

Более формально, пусть WпЧАС быть набором слов длины ЧАС над алфавитом с п письма; то есть набор последовательностей {1, 2, ..., п} длины ЧАС. Этот набор образует гиперкуб, о котором идет речь в теореме. А переменное слово ш(Икс) над WпЧАС все еще имеет длину ЧАС но включает специальный элемент Икс вместо хотя бы одной из букв. Слова ш(1), ш(2), ..., ш(п), полученные заменой всех экземпляров специального элемента Икс с 1, 2, ..., п, сформировать комбинаторная линия в пространстве WпЧАС; комбинаторные линии соответствуют строкам, столбцам и (некоторым) диагоналям гиперкуб. Затем теорема Хейлза – Джеветта утверждает, что для заданных натуральных чисел п и c, существует натуральное число ЧАС, в зависимости от п и c, что для любого разбиения WпЧАС в c частей, есть по крайней мере одна часть, которая содержит всю комбинаторную строку.

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

111213
212223
313233

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

использованная литература

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

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