В математике теорема Грэма – Ротшильда - это теорема, которая применяет теорию Рамсея к комбинаторике слов и комбинаторных кубов . Он назван в честь Рональда Грэма и Брюса Ли Ротшильда , опубликовавших его доказательство в 1971 году. [1] Благодаря работе Грэма, Ротшильда и Клауса Либа в 1972 году он стал частью основ структурной теории Рамсея . [2] Частный случай теоремы Грэма – Ротшильда мотивирует определение числа Грэма, числа , которое было популяризировано Мартином Гарднером.в журнале Scientific American [3] и занесен в Книгу рекордов Гиннеса как самое большое число, когда-либо появлявшееся в математических доказательствах. [4]
Задний план
В теореме используются наборы строк одинаковой длины., над конечным алфавитом вместе с группой, действующей в алфавите. Комбинаторный куб - это подмножество строк, определяемое путем ограничения некоторых позиций строки, чтобы они содержали фиксированную букву алфавита, и путем ограничения других пар позиций, чтобы они были равны друг другу или были связаны друг с другом действием группы. Это определение может быть определено более формально с помощью помеченного слова параметра , строки с подстановочными знаками в позициях, которые не ограничены, чтобы содержать фиксированную букву, и с дополнительными метками, описывающими, какие подстановочные знаки должны быть равны или связаны действием группы. Размерность комбинаторного куба - это количество возможных вариантов выбора для этих подстановочных знаков. Комбинаторный куб размерности один называется комбинаторной линией. [4]
Например, в игре крестики-нолики , девять клеток в крестики-нолики борту могут быть заданы строки длины два более трех символов алфавита {1,2,3} (в декартовы координаты на ячейки), а выигрышные линии трех ячеек образуют комбинаторные линии. Горизонтальные линии получаются закреплением-координата (вторая позиция строки длины два) и позволяя -координата выбирается свободно, а вертикальные линии получаются фиксацией -координировать и позволить -координация выбирается свободно. Две диагональные линии доски для игры в крестики-нолики могут быть указаны параметрическим словом с двумя подстановочными знаками, которые либо должны быть равны (для главной диагонали ), либо связаны групповым действием, которое меняет местами 1 и 3 символа (для антидиагонали ). [5]
Множество всех комбинаторных кубов размерности , для струн длиной над алфавитом с групповым действием , обозначается . Подкуб комбинаторной куба является еще одним комбинаторной куб меньшего размера , который образует подмножество множества строк в большей комбинаторной куб. Подкубы комбинаторного куба также можно описать естественным действием композиции на слова параметров, полученным путем замены символов одного слова параметра на символы подстановки другого. [4]
Заявление
В приведенных выше обозначениях теорема Грэма – Ротшильда принимает в качестве параметров алфавит , групповое действие , конечное количество цветов , и два измерения комбинаторных кубов а также с участием . В нем говорится, что для каждой комбинации, , , , а также , существует длина строки такой, что если каждый комбинаторный куб в назначается один из цветов, то существует комбинаторный куб в все чьи -мерным субкубам присваивается один цвет. [5]
Известна также бесконечная версия теоремы Грэма – Ротшильда. [6]
Приложения
Частный случай теоремы Грэма – Ротшильда с , , а тривиальным действием группы является теорема Хейлза – Джеветта , утверждающая, что если все достаточно длинные строки в данном алфавите раскрашены, то существует одноцветная комбинаторная линия. [5]
Число Грэма является оценкой теоремы Грэма – Ротшильда с, , , , и нетривиальное групповое действие. Для этих параметров набор строк длины над двоичным алфавитом описывает вершины -мерный гиперкуб , каждые два из которых образуют комбинаторную линию. Множество всех комбинаторных прямых можно описать как ребра полного графа по вершинам. Теорема утверждает, что для достаточно большой размерности, всякий раз, когда этому набору ребер полного графа присвоены два цвета, существует монохроматическая комбинаторная плоскость: набор из четырех вершин гиперкуба, которые принадлежат общей геометрической плоскости и все шесть ребер имеют одинаковый цвет. Число Грэма - это верхняя граница этого числа., рассчитывается с использованием повторного возведения в степень; считается, что он значительно больше самого маленькогодля которого верно утверждение теоремы Грэма – Ротшильда. [4]
Рекомендации
- ^ Грэм, RL ; Ротшильд, Б.Л. (1971), "Теорема Рамсея дляпараметрические множества», Труды Американского математического общества , 159 : 257-292, DOI : 10,2307 / 1996010 , MR 0284352
- ^ Graham, RL ; Leeb, K .; Rothschild, BL (1972), «Теорема Рамсея для класса категории», Труды Национальной академии наук Соединенных Штатов Америки , 69 : 119-120, DOI : 10.1073 / pnas.69.1.119 , MR 0306009; полная версия в Graham, RL ; Leeb, K .; Rothschild, BL (1972), "Теорема Рамсея для класса категории", Успехи математических наук , 8 (3): 417-433, DOI : 10,1016 / 0001-8708 (72) 90005-9
- ^ Гарднер, Мартин (ноябрь 1977 г.), «В котором соединение наборов точек линиями ведет к различным (и отклоняющимся) путям», Mathematical Games , Scientific American , 237 (5): 18–28, doi : 10.1038 / Scientificamerican1177-18; пересмотрен и переиздан в The Colossal Book of Mathematics: Classic Puzzles, Paradoxes and Problems (2001)
- ^ а б в г ПРОМЭЛ, Hans Jürgen (2002), "Большие цифры, стрелки нотация Кнута и теория Рамсея", синтезированное , 133 (1-2): 87-105, DOI : 10,1023 / A: 1020879709125 , JSTOR 20117296 , MR 1950045
- ^ а б в Промель, Ханс Юрген (2013), Теория Рамсея для дискретных структур , Springer International Publishing, стр. 41–51, DOI : 10.1007 / 978-3-319-01315-2; см., в частности, главу 3 «Определения и основные примеры» (стр. 33–39, doi : 10.1007 / 978-3-319-01315-2_3 ) для определения слов параметров и комбинаторных кубов, глава 4 «Теорема Хейлза – Джуэтта» (стр. 41–51, doi : 10.1007 / 978-3-319-01315-2_4 ) для примера с крестиками-ноликами и главу 5 «Теорема Грэма – Ротшильда» (стр. 53–59, doi : 10.1007 / 978-3-319-01315-2_5 ) для самой теоремы Грэма – Ротшильда
- ^ Карлсон, Тимоти Дж .; Хиндман, Нил; Strauss, Dona (2006), "О инфинитарной расширение наборов параметров Graham-Rothschild теорема", Труды Американского математического общества , 358 (7): 3239-3262, DOI : 10,1090 / S0002-9947-06-03899-2 , Руководство по ремонту 2216266