Теорема Грэма–Ротшильда

В математике теорема Грэма–Ротшильда — это теорема, которая применяет теорию Рамсея к комбинаторике слов и комбинаторных кубов . Она названа в честь Рональда Грэма и Брюса Ли Ротшильда , которые опубликовали ее доказательство в 1971 году. ^[1] Благодаря работе Грэма, Ротшильда и Клауса Либа  [нем.] в 1972 году она стала частью основ структурной теории Рамсея . ^[2] Частный случай теоремы Грэма–Ротшильда мотивирует определение числа Грэма , числа, которое было популяризировано Мартином Гарднером в Scientific American ^[3] и занесено в Книгу рекордов Гиннесса как самое большое число, когда-либо встречавшееся в математическом доказательстве. ^[4]

Теорема включает в себя наборы строк , все имеющие одинаковую длину , над конечным алфавитом , вместе с группой, действующей на алфавит. Комбинаторный куб - это подмножество строк, определяемое ограничением некоторых позиций строки, чтобы они содержали фиксированную букву алфавита, и ограничением других пар позиций, чтобы они были равны друг другу или были связаны друг с другом действием группы. Это определение может быть определено более формально с помощью помеченного параметрического слова , строки с подстановочными символами в позициях, которые не ограничены содержанием фиксированной буквы, и с дополнительными метками, описывающими, какие подстановочные символы должны быть равны или связаны действием группы. Размерность комбинаторного куба - это количество свободных выборов, которые могут быть сделаны для этих подстановочных символов. Комбинаторный куб размерности один называется комбинаторной линией. ^[4]${\displaystyle n}$

Например, в игре крестики-нолики девять клеток доски крестики-нолики могут быть заданы строками длины два по трехсимвольному алфавиту {1,2,3} ( декартовы координаты клеток), а выигрышные линии из трех клеток образуют комбинаторные линии. Горизонтальные линии получаются путем фиксации -координаты (вторая позиция строки длины два) и предоставления -координаты для свободного выбора, а вертикальные линии получаются путем фиксации -координаты и предоставления -координаты для свободного выбора. Две диагональные линии доски крестики-нолики могут быть заданы параметрическим словом с двумя подстановочными символами, которые либо ограничены равными (для главной диагонали ), либо ограничены связанными групповым действием, которое меняет местами символы 1 и 3 (для побочной диагонали ). ^[5]${\displaystyle у}$${\displaystyle x}$${\displaystyle x}$${\displaystyle у}$

Множество всех комбинаторных кубов размерности , для строк длины над алфавитом с групповым действием , обозначается . Подкуб комбинаторного куба — это другой комбинаторный куб меньшей размерности, который образует подмножество набора строк в большем комбинаторном кубе. Подкубы комбинаторного куба также могут быть описаны естественным действием композиции над словами-параметрами, полученным путем замены символов одного слова-параметра на подстановочные знаки другого. ^[4]${\displaystyle д}$${\displaystyle n}$${\displaystyle А}$${\displaystyle G}$${\displaystyle [A,G]{\tбином {n}{d}}}$

С указанными выше обозначениями теорема Грэма–Ротшильда принимает в качестве параметров алфавит , групповое действие , конечное число цветов и два измерения комбинаторных кубов и с . Она утверждает, что для каждой комбинации , , , , и существует длина строки такая, что если каждому комбинаторному кубу в назначен один из цветов, то существует комбинаторный куб во всех -мерных подкубах которого назначен один и тот же цвет. ^[5]${\displaystyle А}$${\displaystyle G}$${\displaystyle r}$${\displaystyle м}$${\displaystyle к}$${\displaystyle м>к}$${\displaystyle А}$${\displaystyle G}$${\displaystyle r}$${\displaystyle м}$${\displaystyle к}$${\displaystyle n\geq m}$${\displaystyle [A,G]{\tbinom {n}{k}}}$${\displaystyle r}$${\displaystyle [A,G]{\tбином {n}{м}}}$${\displaystyle к}$

Известна также бесконечная версия теоремы Грэма–Ротшильда. [ ^6]

Частным случаем теоремы Грэма–Ротшильда с , и тривиальным групповым действием является теорема Хейлза–Джеветта , утверждающая, что если все достаточно длинные строки над заданным алфавитом раскрашены, то существует одноцветная комбинаторная прямая. ^[5]${\displaystyle м=1}$${\displaystyle к=0}$

Число Грэма является границей для теоремы Грэма–Ротшильда с , , , , и нетривиальным групповым действием. Для этих параметров набор строк длины над двоичным алфавитом описывает вершины -мерного гиперкуба , каждые две из которых образуют комбинаторную линию. Набор всех комбинаторных линий можно описать как ребра полного графа на вершинах. Теорема утверждает, что для достаточно высокой размерности , когда этому набору ребер полного графа назначены два цвета, существует монохроматическая комбинаторная плоскость: набор из четырех вершин гиперкуба, которые принадлежат общей геометрической плоскости и имеют все шесть ребер, назначенных одному и тому же цвету. Число Грэма является верхней границей для этого числа , вычисляемого с помощью повторного возведения в степень; считается, что оно значительно больше наименьшего, для которого утверждение теоремы Грэма–Ротшильда верно. ^[4]${\displaystyle |А|=2}$${\displaystyle r=2}$${\displaystyle м=2}$${\displaystyle к=1}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$