Теорема Рамсея - Ramseys theorem - Wikipedia

В комбинаторная математика, Теорема Рамсея, в одном из теоретико-графовый форм, заявляет, что можно найти монохромные клики в любом маркировка краев (с цветами) достаточно большого полный график. Чтобы продемонстрировать теорему для двух цветов (например, синего и красного), пусть р и s быть любыми двумя положительными целые числа.^[1] Теорема Рамсея утверждает, что существует наименьшее положительное целое число р(р, s) для которого каждая сине-красная окраска кромки полный график на р(р, s) вершины содержит синюю клику на р вершины или красная клика на s вершины. (Здесь р(р, s) означает целое число, которое зависит от обоих р и s.)

Теорема Рамсея является основополагающим результатом комбинаторики. Первая версия этого результата была доказана Ф. П. Рэмси. Это положило начало комбинаторной теории, которая теперь называется Теория Рамсея, ищущий регулярность среди беспорядка: общие условия существования субструктур с регулярными свойствами. В этом приложении речь идет о существовании монохроматические подмножества, то есть, подмножества соединенных кромок одного цвета.

Расширение этой теоремы применимо к любому конечному числу цветов, а не только к двум. Точнее, теорема утверждает, что для любого заданного количества цветов c, и любые заданные целые числа п₁, …, п_c, есть номер, р(п₁, …, п_c) такая, что если ребра полного графа порядка р(п₁, ..., п_c) окрашены c разные цвета, то для некоторых я от 1 до c, он должен содержать полный подграф порядка п_я чьи края все цветные я. В приведенном выше частном случае c = 2 (и п₁ = р и п₂ = s).

Примеры

р(3, 3) = 6

Двусторонняя маркировка K₅ без монохроматического K₃

Предположим, что ребра полного графа на 6 вершинах окрашены в красный и синий цвета. Выберите вершину, v. Есть 5 ребер, инцидентных v и так (по принцип голубятни ) как минимум 3 из них должны быть одного цвета. Не теряя общий смысл мы можем принять не менее 3 таких ребер, соединяющих вершину, v, в вершины, р, s и т, синие. (Если нет, поменяйте местами красный и синий в дальнейшем.) Если любой из ребер, (р, s), (р, т), (s, т), тоже синие, то у нас есть полностью синий треугольник. Если нет, то все три ребра красные, и у нас есть полностью красный треугольник. Поскольку этот аргумент работает для любой раскраски, любой K₆ содержит монохромный K₃, и поэтому р(3, 3) ≤ 6. Популярная версия этого называется теорема о друзьях и незнакомцах.

Альтернативное доказательство работает двойной счет. Это выглядит следующим образом: подсчитайте количество упорядоченных троек вершин, Икс, у, z, такое, что край, (ху), красный, а край, (yz), синий. Во-первых, любая заданная вершина будет серединой либо 0 × 5 = 0 (все ребра из вершины одного цвета), либо 1 × 4 = 4 (четыре - одного цвета, одна - другого цвета), либо 2 × 3 = 6 (три одного цвета, два другого цвета) таких троек. Следовательно, таких троек не более 6 × 6 = 36. Во-вторых, для любого немонохроматического треугольника (xyz) таких троек ровно две. Следовательно, немонохроматических треугольников не более 18. Таким образом, по крайней мере 2 из 20 треугольников в K₆ однотонные.

И наоборот, можно 2-раскрасить K₅ без создания монохромных K₃, показывая, что р(3, 3)> 5. Единственное^[2] окраска показана справа. Таким образом р(3, 3) = 6.

Задача доказать, что р(3, 3) ≤ 6 было одной из проблем Математический конкурс Уильяма Лоуэлла Патнэма в 1953 году, а также на венгерской математической олимпиаде в 1947 году.

Разноцветный пример: р(3, 3, 3) = 17

Единственные две 3-раскраски K₁₆ без монохроматического K₃. Раскрученная раскраска (вверху) и закрученная раскраска (внизу).

Многоцветное число Рамси - это число Рамси, состоящее из 3 или более цветов. Есть (с точностью до симметрии) только два нетривиальных многоцветных числа Рамсея, точное значение которых известно, а именно р(3, 3, 3) = 17 и р(3, 3, 4) = 30.^[3]

Предположим, что у нас есть раскраска ребер полного графа в 3 цвета: красный, зеленый и синий. Предположим далее, что в раскраске ребер нет одноцветных треугольников. Выберите вершину v. Рассмотрим множество вершин, у которых есть красный край к вершине v. Это называется красной окрестностью v. Красный район v не может содержать никаких красных ребер, так как иначе был бы красный треугольник, состоящий из двух конечных точек этого красного ребра и вершины v. Таким образом, индуцированная раскраска ребер в красной окрестности точки v имеет края, окрашенные только в два цвета, а именно в зеленый и синий. С р(3, 3) = 6, красная окрестность v может содержать не более 5 вершин. Точно так же зеленые и синие районы v может содержать не более 5 вершин каждая. Поскольку каждая вершина, кроме v сам находится в одном из красных, зеленых или синих кварталов v, весь полный граф может иметь не более 1 + 5 + 5 + 5 = 16 вершин. Таким образом, мы имеем р(3, 3, 3) ≤ 17.

Чтобы увидеть это р(3, 3, 3) ≥ 17, достаточно провести раскраску ребер на полном графе по 16 вершинам в 3 цвета, избегая одноцветных треугольников. Оказывается, таких раскрасок ровно две на K₁₆, так называемые раскрученные и скрученные раскраски. Обе раскраски показаны на рисунках справа, причем раскрученная раскраска вверху, а закрученная раскраска внизу.

Граф Клебша

Если мы выберем любой цвет из раскрученной или скрученной раскраски на K₁₆, и рассмотрим граф, ребрами которого являются именно те ребра, которые имеют указанный цвет, мы получим Граф Клебша.

Известно, что есть ровно две окраски краев с 3 цветами на K₁₅ которые избегают монохроматических треугольников, которые можно построить, удалив любую вершину из раскрученных и скрученных раскрасок на K₁₆, соответственно.

Также известно, что существует ровно 115 раскрасок краев с 3 цветами на K₁₄ которые избегают монохроматических треугольников, при условии, что мы рассматриваем окраску краев, которая отличается перестановкой цветов, как одинаковую.

Доказательство

2-х цветный корпус

Теорема для двухцветного случая может быть доказана следующим образом: индукция на р + s.^[4] Из определения ясно, что для всех п, р(п, 2) = р(2, п) = п. Это запускает индукцию. Докажем, что р(р, s) существует, найдя для него явную оценку. По индуктивному предположению р(р − 1, s) и р(р, s − 1) существовать.

Лемма 1. р(р, s) ≤ р(р − 1, s) + р(р, s − 1):

Доказательство. Рассмотрим полный граф на р(р − 1, s) + р(р, s − 1) вершины, края которых раскрашены в два цвета. Выберите вершину v из графа, а оставшиеся вершины разделим на две наборы M и N, такое, что для каждой вершины ш, ш в M если (v, ш) синий, а ш в N если (v, ш) красный. Поскольку на графике р(р − 1, s) + р(р, s − 1) = |M| + |N| + 1 вершин, то либо |M| ≥ р(р − 1, s) или же |N| ≥ р(р, s − 1). В первом случае, если M имеет красный K_s затем следует исходный график, и мы закончили. Иначе M имеет синий K_р−1 и так M ∪ {v} имеет синий K_р по определению M. Последний случай аналогичен. Таким образом, утверждение верно, и мы завершили доказательство для двух цветов.

В этом двухцветном случае, если р(р − 1, s) и р(р, s − 1) оба четные, индукционное неравенство можно усилить до:^[5]

р(р, s) ≤ р(р − 1, s) + р(р, s − 1) − 1.

Доказательство. Предполагать п = р(р − 1, s) и q = р(р, s − 1) оба четные. Позволять т = п + q − 1 и рассмотрим двухцветный граф т вершины. Если ${\displaystyle d_{i}}$ степень ${\displaystyle i}$-й вершине в графе, то согласно Лемма о рукопожатии, ${\displaystyle \textstyle \sum _{i=1}^{t}d_{i}}$ даже. При условии т нечетное, должно быть четное ${\displaystyle d_{i}}$. Предполагать ${\displaystyle d_{1}}$даже, M и N - вершины, инцидентные вершине 1 в синем и красном подграфе соответственно. Тогда оба ${\displaystyle |M|=d_{1}}$ и ${\displaystyle |N|=t-1-d_{1}}$ четные. Согласно Принцип голубятни, либо ${\displaystyle |M|\geq p-1}$, или же ${\displaystyle |N|\geq q}$. С ${\displaystyle |M|}$ четно, а ${\displaystyle p-1}$ нечетно, первое неравенство можно усилить, поэтому либо ${\displaystyle |M|\geq p}$ или же ${\displaystyle |N|\geq q}$. Предполагать ${\displaystyle |M|\geq p=R(r-1,s)}$. Тогда либо M подграф имеет красный ${\displaystyle K_{s}}$ и доказательство завершено, или на нем синий ${\displaystyle K_{r-1}}$ который вместе с вершиной 1 образует синий ${\displaystyle K_{r}}$. Дело ${\displaystyle |N|\geq q=R(r,s-1)}$ обрабатывается аналогично.

Случай большего количества цветов

Лемма 2. Если c> 2, то р(п₁, …, п_c) ≤ р(п₁, …, п_c−2, р(п_c−1, п_c)).

Доказательство. Рассмотрим полный граф р(п₁, …, п_c−2, р(п_c−1, п_c)) вершины и раскрасьте его края в c цвета. Теперь дальтоник и притворись, что c - 1 и c одного цвета. Таким образом, график теперь (c - 1) -окрашенный. Из-за определения р(п₁, …, п_c−2, р(п_c−1, п_c)) такой граф содержит либо K_пя монохроматически окрашенный в цвет я для некоторого 1 ≤ я ≤ c - 2 или а K_{р(пc − 1, пc)}-окрашен в «размытый цвет». В первом случае мы закончили. В последнем случае мы снова восстанавливаем зрение и видим из определения р(п_c−1, п_c) мы должны иметь либо (c - 1) -монохромный K_пc−1 или c-монохромный K_пc. В любом случае доказательство завершено.

Из леммы 1 следует, что любой R (г, с) конечно. Правая часть неравенства леммы 2 выражает число Рамсея для c цвета в терминах чисел Рамсея для меньшего количества цветов. Поэтому любой р(п₁, …, п_c) конечна для любого количества цветов. Это доказывает теорему.

Числа Рамсея

Цифры р(р, s) в теореме Рамсея (и их расширение на более чем два цвета) известны как числа Рамсея. Число Рамсея, р(м, п), дает решение проблемы вечеринки, которое просит минимальное количество гостей, р(м, п), который необходимо пригласить, чтобы хотя бы м будут знать друг друга или хотя бы п не узнаем друг друга. На языке теории графов число Рамсея - это минимальное количество вершин, v = р(м, п), такие, что все неориентированные простые графы порядка v, содержат клику порядка м, или независимый набор порядка п. Теорема Рамсея утверждает, что такое число существует для всех м и п.

По симметрии верно, что р(м, п) = р(п, м). Верхняя граница для р(р, s) можно извлечь из доказательства теоремы, а другие аргументы дают оценки снизу. (Первая экспоненциальная нижняя оценка была получена Пол Эрдёш с использованием вероятностный метод.) Однако существует огромный разрыв между самыми точными нижними границами и самыми строгими верхними границами. Также очень мало цифр р и s для которых мы знаем точное значение р(р, s).

Вычисление нижней границы L за р(р, s) обычно требует отображения синей / красной окраски графика K_L−1 без синего K_р подграф и нет красного K_s подграф. Такой контрпример называется График Рамсея. Брендан МакКей поддерживает список известных графов Рамсея.^[6] Верхние границы зачастую установить значительно труднее: нужно либо проверить все возможные раскраски, чтобы подтвердить отсутствие контрпримера, либо представить математический аргумент в пользу его отсутствия.

Вычислительная сложность

Erds просит нас представить инопланетную силу, намного более мощную, чем мы, приземляющуюся на Земле и требующую ценности р(5, 5) или они уничтожат нашу планету. В этом случае, утверждает он, мы должны собрать все наши компьютеры и всех наших математиков и попытаться найти ценность. Но предположим, что вместо этого они просят р(6, 6). В таком случае, считает он, мы должны попытаться уничтожить пришельцев.

— Джоэл Спенсер^[7]

Сложной компьютерной программе не нужно рассматривать все раскраски по отдельности, чтобы удалить их все; тем не менее, это очень сложная вычислительная задача, с которой существующее программное обеспечение может справиться только с небольшими размерами. Каждый полный график K_п имеет 1/2п(п − 1) ребер, так что всего будет c^{п(п − 1)/2} графики для поиска (для c цвета) при использовании грубой силы.^[8] Следовательно, сложность поиска всех возможных графов (через грубая сила ) является О (c^п2) за c раскраски и самое большее п узлы.

Ситуация вряд ли улучшится с появлением квантовые компьютеры. Самый известный алгоритм^{[нужна цитата ]} показывает только квадратичное ускорение (см. Алгоритм Гровера ) относительно классических компьютеров, так что время вычисления все еще экспоненциальный по количеству цветов.^[9]

Известные ценности

Как описано выше, р(3, 3) = 6. Легко доказать, что р(4, 2) = 4, и, в более общем плане, р(s, 2) = s для всех s: график на s − 1 узлы со всеми краями, окрашенными в красный цвет, служат контрпримером и доказывают, что р(s, 2) ≥ s; среди раскрасок графа на s узлов, раскраска со всеми краями, окрашенными в красный цвет, содержит s-узел красный подграф, а все остальные раскраски содержат 2-узел синий подграф (то есть пара узлов, соединенных синим ребром.)

Используя индукционные неравенства, можно заключить, что р(4, 3) ≤ р(4, 2) + р(3, 3) − 1 = 9, и поэтому р(4, 4) ≤ р(4, 3) + р(3, 4) ≤ 18. Есть только два (4, 4, 16) графики (то есть 2-раскраски полного графа на 16 узлы без 4-узел красный или синий полные подграфы) среди 6.4 × 10²² разные 2-краски 16-узловые графы, и только один (4, 4, 17) график ( Граф Пэли порядка 17) среди 2.46 × 10²⁶ раскраски.^[6] (Это было доказано Эвансом, Пулхэмом и Шиханом в 1979 году.) Отсюда следует, что р(4, 4) = 18.

Дело в том, что р(4, 5) = 25 был впервые основан Бренданом Маккеем и Станислав Радзишовский в 1995 г.^[10]

Точная стоимость р(5, 5) неизвестно, хотя известно, что он находится между 43 (Джеффри Эксу (1989)^[11]) и 48 (Ангельтвейт и Маккей (2017)^[12]) (включительно).

В 1997 году Маккей, Радзишовски и Эксу использовали методы компьютерной генерации графов, чтобы предположить, что р(5, 5) = 43. Им удалось построить ровно 656 (5, 5, 42) графов, приходящих к одному и тому же набору графов разными путями. Ни один из 656 графиков не может быть расширен до (5, 5, 43) график.^[13]

За р(р, s) с р, s > 5, доступны только слабые оценки. Нижние оценки для р(6, 6) и р(8, 8) не совершенствовались с 1965 и 1972 годов соответственно.^[3]

р(р, s) с р, s ≤ 10 показаны в таблице ниже. Если точное значение неизвестно, в таблице перечислены наиболее известные границы. р(р, s) с р, s < 3 даны р(1, s) = 1 и р(2, s) = s для всех значений s.

Стандартным обзором развития исследований чисел Рамсея является Динамический опрос 1 из Электронный журнал комбинаторики, к Станислав Радзишовский, который периодически обновляется.^[3] Если не указано иное, записи в таблице ниже взяты из издания за март 2017 г. (Обратите внимание на тривиальную симметрию по диагонали, поскольку р(р, s) = р(s, р).)

Значения / известные ограничивающие диапазоны для чисел Рамсея р(р, s) (последовательность A212954 в OEIS )

s р	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2		2	3	4	5	6	7	8	9	10
3			6	9	14	18	23	28	36	40–42
4				18	25[10]	36–41	49–61	59[14]–84	73–115	92–149
5					43–48	58–87	80–143	101–216	133–316	149[14]–442
6						102–165	115[14]–298	134[14]–495	183–780	204–1171
7							205–540	217–1031	252–1713	292–2826
8								282–1870	329–3583	343–6090
9									565–6588	581–12677
10										798–23556

Асимптотика

Неравенство р(р, s) ≤ р(р − 1, s) + р(р, s − 1) может применяться индуктивно, чтобы доказать, что

${\displaystyle R(r,s)\leq {\binom {r+s-2}{r-1}}.}$

В частности, этот результат из-за Erds и Секереш, означает, что когда р = s,

${\displaystyle R(s,s)\leq [1+o(1)]{\frac {4^{s-1}}{\sqrt {\pi s}}}.}$

Экспоненциальная нижняя граница,

${\displaystyle R(s,s)\geq [1+o(1)]{\frac {s}{{\sqrt {2}}e}}2^{s/2},}$

был дан Эрдёшем в 1947 году и сыграл важную роль в введении им вероятностного метода. Очевидно, что между этими двумя границами существует огромный разрыв: например, для s = 10, это дает 101 ≤ р(10, 10) ≤ 48620. Тем не менее, коэффициенты экспоненциального роста для любого из пределов до настоящего времени не были улучшены и все еще остаются на уровне 4 и √2 соответственно. Не существует известной явной конструкции, дающей экспоненциальную нижнюю оценку. Наиболее известные нижняя и верхняя границы диагональных чисел Рамсея в настоящее время равны

${\displaystyle [1+o(1)]{\frac {{\sqrt {2}}s}{e}}2^{\frac {s}{2}}\leq R(s,s)\leq s^{-(c\log s)/(\log \log s)}4^{s},}$

из-за Спенсер и Конлон соответственно.

Для недиагональных чисел Рамсея р(3, т), известно, что они порядочные ${\displaystyle {\tfrac {t^{2}}{\log t}}}$; то же самое можно сказать и о том, что наименьшее возможное число независимости в п-вертекс граф без треугольников является

${\displaystyle \Theta \left({\sqrt {n\log n}}\right).}$

Верхняя оценка для р(3, т) дан кем-то Аджтай, Komlós, и Семереди, нижняя оценка была первоначально получена Ким, и был улучшен Гриффитсом, Моррис, Физ Понтиверос и Бохман и Кееваш, анализируя процесс без треугольников. В более общем смысле, для недиагональных чисел Рамсея р(s, т), с s фиксированный и т растет, наиболее известные границы

${\displaystyle c'_{s}{\frac {t^{\frac {s+1}{2}}}{(\log t)^{{\frac {s+1}{2}}-{\frac {1}{s-2}}}}}\leq R(s,t)\leq c_{s}{\frac {t^{s-1}}{(\log t)^{s-2}}},}$

благодаря Бохману и Кеевашу и Аджтай, Komlós и Семереди соответственно.

Расширения теоремы

Бесконечные графы

Еще один результат, также обычно называемый Теорема Рамсея, применяется к бесконечным графам. В контексте, где также обсуждаются конечные графы, ее часто называют «бесконечной теоремой Рамсея». Поскольку интуиция, обеспечиваемая графическим представлением графа, уменьшается при переходе от конечных графов к бесконечным, теоремы в этой области обычно формулируются следующим образом: теоретико-множественный терминология.^[15]

Теорема. Позволять Икс быть неким бесконечным множеством и раскрасить элементы Икс^(п) (подмножества Икс размера п) в c разные цвета. Тогда существует бесконечное подмножество M из Икс такой, что размер п подмножества M все одного цвета.

Доказательство: Доказательство проводится индукцией по п, размер подмножеств. За п = 1, это утверждение эквивалентно тому, что если вы разделите бесконечное множество на конечное число множеств, то одно из них будет бесконечным. Это очевидно. Предполагая, что теорема верна для п ≤ р, мы доказываем это для п = р + 1. Учитывая c-раскрашивание (р + 1) -элементные подмножества Икс, позволять а₀ быть элементом Икс и разреши Y = Икс \ {а₀}. Затем мы индуцируем c-крашивание р-элементные подмножества Y, просто добавив а₀ для каждого р-элементное подмножество (чтобы получить (р + 1) -элементное подмножество Икс). По предположению индукции существует бесконечное подмножество Y₁ из Y так что каждый р-элементное подмножество Y₁ окрашивается в тот же цвет в индуцированной раскраске. Таким образом, есть элемент а₀ и бесконечное подмножество Y₁ так что все (р + 1) -элементные подмножества Икс состоящий из а₀ и р элементы Y₁ иметь такой же цвет. По тому же аргументу существует элемент а₁ в Y₁ и бесконечное подмножество Y₂ из Y₁ с такими же свойствами. Индуктивно получаем последовательность {а₀, а₁, а₂,…} Такие, что цвет каждого (р + 1) -элементное подмножество (а_я(1), а_я(2), …, а_я(р + 1)) с я(1) < я(2) < ... < я(р + 1) зависит только от значения я(1). Далее, существует бесконечно много значений я(п) такой, что этот цвет будет таким же. Возьми это а_я(п)Чтобы получить желаемый монохромный набор.

Более сильная, но несбалансированная бесконечная форма теоремы Рамсея для графов, Теорема Эрдеша – Душника – Миллера., утверждает, что каждый бесконечный граф содержит либо счетно бесконечный независимый набор или бесконечная клика одного и того же мощность как исходный график.^[16]

Бесконечная версия подразумевает конечное

Можно вывести конечную теорему Рамсея из бесконечной версии с помощью доказательство от противного. Предположим, что конечная теорема Рамсея неверна. Тогда существуют целые числа c, п, Т так что для каждого целого числа k, существует c-крашивание ${\displaystyle [k]^{(n)}}$ без монохромного набора размеров Т. Позволять C_k обозначить c-краски ${\displaystyle [k]^{(n)}}$ без монохромного набора размеров Т.

Для любого k, ограничение раскраски в C_k+1 к ${\displaystyle [k]^{(n)}}$ (игнорируя цвет всех наборов, содержащих k + 1) раскраска в C_k. Определять ${\displaystyle C_{k}^{1}}$ быть раскраской в C_k которые являются ограничениями раскраски в C_k+1. С C_k+1 не пусто, ни ${\displaystyle C_{k}^{1}}$.

Аналогично ограничение любой раскраски в ${\displaystyle C_{k+1}^{1}}$ в ${\displaystyle C_{k}^{1}}$, позволяющий определить ${\displaystyle C_{k}^{2}}$ как набор всех таких ограничений непустой набор. Продолжая так, определим ${\displaystyle C_{k}^{m}}$ для всех целых чисел м, k.

Теперь для любого целого k, ${\displaystyle C_{k}\supseteq C_{k}^{1}\supseteq C_{k}^{2}\supseteq \cdots }$, и каждый набор не пуст. Более того, C_k конечно как ${\displaystyle |C_{k}|\leq c^{\frac {k!}{n!(k-n)!}}}$. Отсюда следует, что пересечение всех этих множеств непусто, и пусть ${\displaystyle D_{k}=C_{k}\cap C_{k}^{1}\cap C_{k}^{2}\cap \cdots }$. Тогда каждая раскраска в D_k ограничение раскраски в D_k+1. Следовательно, неограничивая раскраску в D_k к окраске в D_k+1, и продолжая это делать, строят раскраску ${\displaystyle \mathbb {N} ^{(n)}}$ без какого-либо монохромного набора размеров Т. Это противоречит бесконечной теореме Рамсея.

Если принять подходящую топологическую точку зрения, этот аргумент становится стандартным. аргумент компактности показывающий, что бесконечная версия теоремы влечет конечную версию.^[17]

Гиперграфы

Теорема распространяется также на гиперграфы. An м-гиперграф - это граф, «ребрами» которого являются множества м вершины - в нормальном графе ребро - это набор из 2 вершин. Полная формулировка теоремы Рамсея для гиперграфов состоит в том, что для любых целых чисел м и c, и любые целые числа п₁, …, п_c, есть целое число р(п₁, …, п_c;c, м) такие, что если гиперребра полного м-гиперграф порядка р(п₁, …, п_c;c, м) окрашены c разные цвета, то для некоторых я от 1 до c, гиперграф должен содержать полную под-м-гиперграф порядка п_я чьи гиперребра все цвета я. Эта теорема обычно доказывается индукцией по м, «гипер-сущность» графа. Базовый случай доказательства м = 2, что в точности соответствует приведенной выше теореме.

Направленные графы

Также можно определить числа Рамсея для направленный графики; они были введены П. Эрдёш и Л. Мозер (1964 ). Позволять р(п) быть наименьшим числом Q такой, что любой полный граф с односторонними дугами (также называемый «турниром») и ≥Q узлы содержат ациклический (также называемый "переходным") п-узел субтурнир.

Это аналог ориентированного графа того, что (выше) было названо р(п, п; 2) наименьшее число Z такое, что любая 2-раскраска ребер полного ООНориентированный граф с ≥Z узлов, содержит монохроматический полный граф на n узлах. (Направленный аналог двух возможных дуг цвета это два направления для дуг аналог «монохроматического» - «все дуги-стрелки указывают в одну сторону»; т.е. "ациклический".)

У нас есть р(0) = 0, р(1) = 1, р(2) = 2, р(3) = 4, р(4) = 8, р(5) = 14, р(6) = 28 и 32 ≤р(7) ≤ 54.^[18]

Отношение к аксиоме выбора

В обратная математика, существует значительная разница в силе доказательства между версией теоремы Рамсея для бесконечных графов (случай п = 2) и для бесконечных мультиграфов (случай п ≥ 3). Мультиграфическая версия теоремы по силе эквивалентна аксиома арифметического понимания, сделав его частью подсистемы ACA₀ из арифметика второго порядка, один из большая пятерка подсистем в обратной математике. Напротив, по теореме Дэвид Ситапун, графовая версия теоремы слабее, чем ACA₀, и (объединяя результаты Seetapun с другими) он не попадает в одну из больших пяти подсистем.^[19] Над ZF однако графическая версия эквивалентна классической Лемма Кёнига.^[20]

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

• Кардинал Рэмси
• Теорема Пэрис – Харрингтона
• Сим (игра с карандашом)
• Бесконечная теория Рамсея
• Число Ван дер Вардена
• Рэмси игра
• Теорема Эрдеша – Радо

Примечания

1. Некоторые авторы ограничивают значения больше единицы, например (Бруальди 2010 ) и (Гарари 1972 ), тем самым избегая обсуждения раскраски ребер графа без ребер, в то время как другие перефразируют утверждение теоремы так, чтобы оно требовалось, в простой график, либо р-клика или s-независимый набор, видеть (Валовой 2008 ) или же (Эрдеш и Секереш, 1935 г. ). В таком виде более естественно рассматривать графы с одной вершиной.
2. с точностью до автоморфизмов графа
3. Радзишовский, Станислав (2011). «Маленькие числа Рэмси». Динамические опросы. Электронный журнал комбинаторики. Дои:10.37236/21.
4. Делай, Норман (2006). «Партийные проблемы и теория Рамсея» (PDF). Austr. Математика. Soc. Вестник. 33 (5): 306–312.
5. "Партийные знакомства".
6. «Графики Рэмси».
7. Джоэл Х. Спенсер (1994), Десять лекций о вероятностном методе, СИАМ, п.4, ISBN  978-0-89871-325-1
8. 2.6 Теория Рамсея из освещенной математики
9. Ван, Хэфэн (2016). «Определение чисел Рамсея на квантовом компьютере». Физический обзор A. 93 (3): 032301. arXiv:1510.01884. Bibcode:2016PhRvA..93c2301W. Дои:10.1103 / PhysRevA.93.032301.
10. Брендан Д. Маккей, Станислав П. Радзишовский (май 1995 г.). "р(4,5) = 25" (PDF). Журнал теории графов. 19 (3): 309–322. Дои:10.1002 / jgt.3190190304.
11. Экзу, Джеффри (март 1989). "Нижняя граница для р(5, 5)". Журнал теории графов. 13 (1): 97–98. Дои:10.1002 / jgt.3190130113.
12. Виглейк Ангельтвейт; Брендан Маккей (2017). "${\displaystyle R(5,5)\leq 48}$". arXiv:1703.08768v2 [math.CO ].
13. Брендан Д. Маккей, Станислав П. Радзишовский (1997). "Подграф подсчета тождеств и чисел Рамсея" (PDF). Журнал комбинаторной теории. 69 (2): 193–209. Дои:10.1006 / jctb.1996.1741.
14. Экзу, Джеффри; Татаревич, Милош (2015). «Новые нижние границы для 28 классических чисел Рамси». Электронный журнал комбинаторики. 22 (3): 3. arXiv:1504.02403. Bibcode:2015arXiv150402403E. Дои:10.37236/5254.
15. Мартин Гулд. "Теория Рэмси" (PDF).
16. Душник, Бен; Миллер, Э. У. (1941). «Частично заказанные наборы». Американский журнал математики. 63 (3): 600–610. Дои:10.2307/2371374. HDL:10338.dmlcz / 100377. JSTOR  2371374. МИСТЕР  0004862.. См., В частности, теоремы 5.22 и 5.23.
17. Дистель, Рейнхард (2010). «Глава 8, Бесконечные графы». Теория графов (4-е изд.). Гейдельберг: Springer-Verlag. С. 209–2010. ISBN  978-3-662-53621-6.
18. Смит, Уоррен Д .; Экзу, Джефф, Частичный ответ на загадку № 27: количество, похожее на Рамси, получено 2020-06-02
19. Хиршфельдт, Денис Р. (2014). Нарезка правды. Серия конспектов лекций Института математических наук Национального университета Сингапура. 28. World Scientific.
20. Лолли, Габриэле (октябрь 1977 г.). «О теореме Рамсея и аксиоме выбора». Журнал формальной логики Нотр-Дам. 18 (4): 599–601. Дои:10.1305 / ndjfl / 1093888126. ISSN  0029-4527.

Рекомендации

• Айтай, Миклош; Комлош, Янош; Семереди, Эндре (1980), «Заметка о числах Рэмси», J. Combin. Теория Сер. А, 29 (3): 354–360, Дои:10.1016/0097-3165(80)90030-8.
• Бохман, Том; Кееваш, Питер (2010), "Ранняя эволюция H-свободного процесса", Изобретать. Математика., 181 (2): 291–336, arXiv:0908.0429, Bibcode:2010InMat.181..291B, Дои:10.1007 / s00222-010-0247-х
• Бруальди, Ричард А. (2010), Вводная комбинаторика (5-е изд.), Прентис-Холл, стр. 77–82, ISBN  978-0-13-602040-0
• Конлон, Дэвид (2009), "Новая верхняя оценка диагональных чисел Рамсея", Анналы математики, 170 (2): 941–960, arXiv:математика / 0607788v1, Дои:10.4007 / аннал 2009.170.941, МИСТЕР  2552114.
• Эрдеш, Пол (1947), «Некоторые замечания по теории графов», Бык. Амер. Математика. Soc., 53 (4): 292–294, Дои:10.1090 / S0002-9904-1947-08785-1.
• Эрдеш, П.; Мозер, Л. (1964), «О представлении ориентированных графов в виде объединения порядков» (PDF), Мадьяр Тудоманьос Академия, Математикаи Кутато Интезетенек Кезлеменьей, 9: 125–132, МИСТЕР  0168494
• Эрдеш, Пол; Секерес, Джордж (1935), «Комбинаторная задача геометрии» (PDF), Compositio Mathematica, 2: 463–470, Дои:10.1007/978-0-8176-4842-8_3, ISBN  978-0-8176-4841-1.
• Exoo, G. (1989), "Нижняя оценка R (5,5)", Журнал теории графов, 13: 97–98, Дои:10.1002 / jgt.3190130113.
• Грэм, Р.; Ротшильд, В .; Спенсер, Дж. Х. (1990), Теория Рэмси, Нью-Йорк: Джон Уайли и сыновья.
• Гросс, Джонатан Л. (2008), Комбинаторные методы с компьютерными приложениями, CRC Press, стр. 458, г. ISBN  978-1-58488-743-0
• Харари, Фрэнк (1972), Теория графов, Addison-Wesley, pp. 16–17, ISBN  0-201-02787-9
• Рэмси, Ф. П. (1930), «К проблеме формальной логики», Труды Лондонского математического общества, 30: 264–286, Дои:10.1112 / плмс / с2-30.1.264.
• Спенсер, Дж. (1975), «Теорема Рамсея - новая нижняя оценка», J. Combin. Теория Сер. А, 18: 108–115, Дои:10.1016/0097-3165(75)90071-0.
• Бянь, Чжэнбин; Чудак, Фабиан; Макреди, Уильям Дж .; Кларк, Лейн; Гайтан, Франк (2013), "Экспериментальное определение чисел Рамсея", Письма с физическими проверками, 111 (13): 130505, arXiv:1201.1842, Bibcode:2013ПхРвЛ.111м0505Б, Дои:10.1103 / PhysRevLett.111.130505, PMID  24116761.

внешняя ссылка

• "Теорема Рамсея", Энциклопедия математики, EMS Press, 2001 [1994]
• Рэмси @ Home это распределенных вычислений проект, предназначенный для поиска новых нижних оценок для различных чисел Рамсея с использованием множества различных методов.
• В Электронный журнал комбинаторики динамический обзор малых чисел Рамсея (Станислав Радзишовский)
• Число Рэмси - из MathWorld (содержит оценки снизу и сверху до R (19, 19))
• Число Рэмси - Джеффри Эксу (Содержит R (5, 5)> 42 контр-доказательство)