Теорема Рамсея

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

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

Расширение этой теоремы применимо к любому конечному числу цветов, а не только к двум. Точнее, теорема утверждает, что для любого заданного количества цветов существует число R ₍ n 1 _{c и любых целых чисел n 1 , …, nc} , … , nc ₎ такое что _, если ребра Полный граф порядка R ( n ₁ , …, раскрашен _в nc ) c разных цветов, то для некоторого i от 1 до c он должен содержать полный подграф порядка n _i, все ребра которого имеют цвет i . В частном случае, приведенном выше, c = 2 (и n ₁ = r и n ₂ = s ).

Примеры

Р (3, 3) = 6

2-цветное футлярное доказательство без слов
есть как минимум 3 ребра одного цвета (пунктирно-фиолетовые) В соответствии с принципом «ячейки» из произвольной вершины v . Назвав 3 вершины, завершающие эти ребра, r , s и t , если бы ребро rs , st или tr (сплошной черный) имело этот цвет, это завершило бы треугольник с помощью v . Но если нет, то каждый из них должен быть противоположного цвета, образуя треугольник первым . этого цвета

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

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

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

И наоборот, можно раскрасить K ₅ в два цвета , не создавая монохроматического K ₃ , показывая, что R (3, 3) > 5 . Уникальный раскраска показана справа. Таким образом R (3, 3) = 6 .

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

Многоцветный пример: R (3, 3, 3) = 17

Единственные две 3-раскраски К ₁₆ без одноцветного К ₃ с точностью до изоморфизма и перестановки цветов: раскрученная (левая) и скрученная (правая) раскраски.

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

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

Чтобы увидеть, что R (3, 3, 3) = 17 , достаточно нарисовать раскраску ребер на полном графе из 16 вершин тремя цветами, избегающую одноцветных треугольников. Оказывается, таких раскрасок на K16 ровно две так _, называемые раскрученная и крученая раскраски. Обе раскраски показаны на рисунках справа: раскрученная раскраска слева, а скрученная раскраска справа.

Граф Клебша

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

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

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

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

2-цветный футляр

Теорему для двухцветного случая можно доказать индукцией по r + s . Из определения ясно, что для всех R n ( n , 2) = R (2, n ) = n . Это запускает индукцию. Мы доказываем, что R ( r , s ) существует, находя для него явную оценку. По индуктивному предположению R ( r − 1, s ) и R ( r , s − 1) существуют.

Лемма 1. $R(r,s)\leq R(r-1,s)+R(r,s-1).$

Доказательство. Рассмотрим полный граф на R ( r − 1, s ) + R ( r , s − 1) вершин, ребра которого раскрашены в два цвета. Выберите вершину v из графа и разделите оставшиеся вершины на два множества M и N так, чтобы для каждой вершины w если w находился в M, ребро ( vw ) синее, и w было в N , если ( vw ) красное. . Поскольку график имеет $R(r-1,s)+R(r,s-1)=|M|+|N|+1$ вершин, то отсюда следует, что либо $|M|\geq R(r-1,s)$ или $|N|\geq R(r,s-1).$ В первом случае, если M имеет красный K _s , то же самое имеет и исходный граф, и мы закончили. В противном случае M имеет синий K _{r − 1} , и поэтому $M\cup \{v\}$ имеет синий K _r по определению M . Последний случай аналогичен. Таким образом, утверждение верно, и мы завершили доказательство для двух цветов.

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

$R(r,s)\leq R(r-1,s)+R(r,s-1)-1.$

Доказательство . Предположим, что p = R ( r − 1, s ) и q = R ( r , s − 1) четные. Пусть t = p + q − 1 и рассмотрим двухцветный граф из t вершин. Если d _i — степень i -й вершины в синем подграфе, то по лемме о рукопожатии , $\textstyle \sum _{i=1}^{t}d_{i}$ четный. Учитывая, что t нечетное, должно быть четное d _i . Без ограничения общности предположим, что d ₁ четно и что M и N — вершины, инцидентные вершине 1 в синем и красном подграфах соответственно. Тогда оба $|M|=d_{1}$ и $|N|=t-1-d_{1}$ четные. По принципу Pigeonhole либо $|M|\geq p-1,$ или $|N|\geq q.$ С $|M|$ четно, а p – 1 нечетно, первое неравенство можно усилить, так что либо $|M|\geq p$ или $|N|\geq q.$ Предполагать $|M|\geq p=R(r-1,s).$ Тогда либо подграф M имеет красный K _s и доказательство завершено, либо у него есть синий K _{r – 1} , который вместе с вершиной 1 образует синий K _r . Дело $|N|\geq q=R(r,s-1)$ лечится аналогично.

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

Лемма 2. Если c > 2 , то $R(n_{1},\dots ,n_{c})\leq R(n_{1},\dots ,n_{c-2},R(n_{c-1},n_{c})).$

Доказательство. Рассмотрим полный граф $R(n_{1},\dots ,n_{c-2},R(n_{c-1},n_{c}))$ вершины и раскрасьте их края c цветами. Теперь «станьте дальтоником» и представьте, что c − 1 и c — один и тот же цвет. Таким образом, граф теперь ( c − 1) -цветный. В связи с определением $R(n_{1},\dots ,n_{c-2},R(n_{c-1},n_{c})),$ граф содержит либо K _{n i,} одноцветно окрашенный в цвет i некоторого 1 ⩽ i ⩽ c - 2 , либо K _{R ( nc для - 1 , nc такой )} -раскрашенный в «размытый цвет». В первом случае мы закончили. В последнем случае мы снова прозреваем и видим, что из определения R ( n _{c − 1} , n _c ) мы должны иметь либо a ( c − 1) -монохром K _{n c - 1} , либо c -монохром K _{n в} . В любом случае доказательство завершено.

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

Числа Рэмзи

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

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

Вычисление нижней границы L для R ( r , s ) обычно требует демонстрации синей/красной раскраски графа K _{L −1} без синего подграфа K _r и красного подграфа K _s . Такой контрпример называется графом Рамсея . Брендан Маккей ведет список известных графов Рэмси. Верхние оценки зачастую установить значительно сложнее: нужно либо проверить все возможные раскраски, чтобы подтвердить отсутствие контрпримера, либо привести математическое обоснование его отсутствия.

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

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

— Джоэл Спенсер

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

Ситуация вряд ли улучшится с появлением квантовых компьютеров . Один из самых известных алгоритмов поиска неструктурированных наборов данных демонстрирует только квадратичное ускорение (см. алгоритм Гровера ) по сравнению с классическими компьютерами, так что время вычислений по-прежнему экспоненциально зависит от количества узлов.

Известные значения

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

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

Тот факт, что R (4, 5) = 25, был впервые установлен Бренданом Маккеем и Станиславом Радзишовским в 1995 году.

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

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

Для R ( r , s ) с r , s > 5 доступны только слабые оценки. Нижние границы для R (6, 6) и R (8, 8) не улучшались с 1965 и 1972 годов соответственно.

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

Стандартным обзором развития исследований чисел Рамсея является Динамический обзор 1 Электронного журнала комбинаторики Станислава Радзишовского , который периодически обновляется. Если не указано иное, записи в таблице ниже взяты из издания за январь 2021 года. (Обратите внимание, что существует тривиальная симметрия по диагонали, поскольку R ( r , s ) = R ( s , r ) .)

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

с р	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–41
4				18	25	36–40	49–58	59 –79	73–106	92–136
5					43–48	59 –85	80–133	101–194	133–282	149 –381
6						102–161	115 –273	134 –427	183–656	204–949
7							205–497	219–840	252–1379	292–2134
8								282–1532	329–2683	343–4432
9									565–5366	581–9797
10										798–17730

Асимптотика

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

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

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

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

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

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

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

$[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},$

благодаря Спенсеру и Конлону соответственно; препринт 2023 года Кампоса, Гриффитса, Морриса и Сахасрабуде утверждает, что добился экспоненциального прогресса, используя алгоритмическую конструкцию, основанную на графовой структуре, называемой « книгой », улучшение верхней границы

$R(s,s)\leq (4-\varepsilon )^{s}{\text{ and }}R(s,t)\leq e^{-\delta t+o(s)}{\binom {s+t}{t}}.$

с $\varepsilon =2^{-7}$ и $\delta =50^{-1}$ где считается, что эти параметры могут быть оптимизированы, в частности $\varepsilon$.

Для недиагональных чисел Рамсея R (3, t ) известно, что они имеют порядок т ² / журнал т ; это можно сформулировать эквивалентно тому, что наименьшее возможное число независимости в с n вершинами графе без треугольников равно

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

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

$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}}}.$

Для $s=4$ границы становятся $c'_{s}t^{\frac {5}{2}}(\log t)^{-2}\leq R(4,t)\leq c_{s}t^{3}(\log t)^{-2}$, но препринт 2023 года улучшил нижнюю границу до $c'_{s}t^{3}(\log t)^{-4}$ что решает вопрос об Эрдёше, который предложил 250 долларов за доказательство того, что нижний предел имеет форму $c'_{s}t^{3}(\log t)^{-d}$.

Рэмси

Существует менее известный, но интересный аналог теоремы Рамсея для индуцированных подграфов . Грубо говоря, теперь вместо поиска монохроматического подграфа нам необходимо найти монохроматический индуцированный подграф. В этом варианте уже недостаточно ограничивать наше внимание полными графами , поскольку существование полного подграфа не подразумевает существование индуцированного подграфа. Качественная формулировка теоремы в следующем разделе была впервые независимо доказана Эрдёшем , Хайналом и Посой , Дойбером и Рёдлем в 1970-х годах. С тех пор было проведено много исследований по получению точных оценок индуцированных чисел Рамсея.

Заявление

Пусть H — граф на n вершинах. Тогда существует граф G такой, что любая раскраска ребер G в два цвета содержит монохроматическую индуцированную копию H ( подграф G такой, что он изоморфен H т.е. индуцированный и его ребра одноцветны). Наименьшее возможное число вершин графа G — это индуцированное число Рамсея r _ind ( H ) .

Иногда мы рассматриваем и асимметричный вариант проблемы. Мы определяем r _ind ( X , Y ) как наименьшее возможное количество вершин графа G такое, что каждая раскраска ребер G с использованием только красного или синего цвета содержит красный индуцированный подграф X или синий индуцированный подграф Y .

История и границы

Как и в случае с теоремой Рамсея, априори неясно, существуют ли индуцированные числа Рамсея для каждого графа H . В начале 1970-х годов Эрдеш , Хайнал и Поса , Дойбер и Рёдль независимо друг от друга доказали, что это так. Однако первоначальные доказательства давали ужасные ограничения (например, башни двоек ) на индуцированные числа Рамсея. Интересно задаться вопросом, можно ли достичь лучших границ. В 1974 году Пол Эрдеш предположил, что существует константа c такая, что каждый граф H на k вершинах удовлетворяет условию r _ind ( H ) ≤ 2 ^ск . Если эта гипотеза верна, она будет оптимальной до константы c, поскольку полный граф достигает нижней границы этого вида (фактически это то же самое, что и числа Рамсея). Однако на данный момент эта гипотеза все еще остается открытой.

В 1984 году Эрдеш и Хайнал заявили, что доказали связь.

$r_{\text{ind}}(H)\leq 2^{2^{k^{1+o(1)}}}.$

Однако это все еще было далеко от экспоненциальной границы, предполагаемой Эрдёшем. Лишь в 1998 году крупный прорыв был достигнут Кохаякавой , Премелем и Рёдлем, которые доказали первую почти экспоненциальную оценку r _ind ( H ) ≤ 2. ^{ск (журнал k ) 2} для некоторой постоянной c . Их подход заключался в том, чтобы рассмотреть подходящий случайный граф, построенный на проективных плоскостях , и показать, что он обладает желаемыми свойствами с ненулевой вероятностью. Идея использования случайных графов на проективных плоскостях ранее также использовалась при изучении свойств Рамсея относительно раскрасок вершин и индуцированной проблемы Рамсея на ограниченной степени графах H .

Граница Кохаякавы, Премеля и Рёдля оставалась лучшей общей оценкой за десятилетие. В 2008 году Фокс и Судаков предоставили явную конструкцию индуцированных чисел Рамсея с той же оценкой. Фактически они показали, что каждый ( n , d ,λ) -граф G с малым λ и подходящим d содержит индуцированную монохроматическую копию любого графа на k вершинах в любой раскраске ребер G в два цвета. В частности, для некоторой константы c граф Пэли на n ≥ 2 ^{ск журнал 2 к} вершин таков, что все его раскраски ребер в два цвета содержат индуцированную монохроматическую копию каждого k графа -вершин.

В 2010 году Конлон , Фокс и Судаков смогли улучшить оценку до r _ind ( H ) ≤ 2. ^{ск журнал к} , что остается лучшей на данный момент верхней границей для общих индуцированных чисел Рамсея. Как и в предыдущей работе 2008 года, они показали, что каждый ( n , d ,λ) -граф G с малым λ и плотностью ребер 1 ⁄ 2 содержит индуцированную монохроматическую копию каждого графа на k вершинах в любой раскраске ребер в два цвета. В настоящее время гипотеза Эрдеша о том, что r _ind ( H ) ≤ 2 ^ск остается открытой и является одной из важных проблем экстремальной теории графов .

Что касается нижних оценок, в целом известно немногое, за исключением того факта, что индуцированные числа Рамсея должны быть по крайней мере соответствующими числами Рамсея. Для некоторых частных случаев получены некоторые нижние оценки (см. «Особые случаи»).

Особые случаи

Хотя общие оценки индуцированных чисел Рамсея экспоненциальны по размеру графа, их поведение сильно отличается на специальных классах графов (в частности, на разреженных). Многие из этих классов индуцировали числа Рамсея, полиномиальные по числу вершин.

Если H — цикл , путь или звезда на k вершинах, известно, что r _ind ( H ) линеен по k .

Если H — дерево с k вершинами, то известно, что r _ind ( H ) = O ( k ² бревно ² к ) . Также известно, что r _ind ( H ) суперлинейен ) (т. е. r _ind ( H ) = ω( k ) . Обратите внимание, что это контрастирует с обычными числами Рамсея, где гипотеза Берра–Эрдёша (теперь доказанная) говорит нам, что r ( H ) линейно (поскольку деревья 1- вырождены ).

Для графов H с числом вершин k и ограниченной степенью Δ было высказано предположение, что r _ind ( H ) ≤ cn ^{д (Д)} , для некоторой постоянной d, зависящей только от ∆ . Этот результат был впервые доказан Лучаком и Рёдлем в 1996 году, когда d (Δ) росла как башня из двоек высотой O (Δ ² ) . С тех пор были получены более разумные оценки для d (∆) . В 2013 году Конлон, Фокс и Чжао показали, используя лемму о подсчете для разреженных псевдослучайных графов , что r _ind ( H ) ≤ cn ^2Д+8 , где показатель степени максимально приближен к постоянным множителям.

Обобщения

Подобно числам Рамсея, мы можем обобщить понятие индуцированных чисел Рамсея на гиперграфы и многоцветные настройки.

Больше цветов

Мы также можем обобщить индуцированную теорему Рамсея на многоцветный случай. Для графов H ₁ , H ₂ , …, H _r определите r _ind ( H ₁ , H ₂ , …, H _r ) как минимальное количество вершин в графе G такое, что любая раскраска ребер G в r цвета содержат индуцированный подграф, изоморфный H _i , где все ребра окрашены в i -й цвет для некоторого 1 ≤ i ≤ r . Пусть r _ind ( H ; q ) := r _ind ( H , H , …, H ) ( q копий H ).

Можно получить оценку для r _ind ( H ; q ) , которая примерно представляет собой башню из двух высотой ~ log q, итеративно применяя оценку к двухцветному случаю. Самая известная на данный момент оценка принадлежит Фоксу и Судакову, которая достигает r _ind ( H ; q ) ≤ 2 ^{ск 3} , где k — количество вершин H , а c — константа, зависящая только от q .

Гиперграфики

Мы можем расширить определение индуцированных чисел Рамсея на d -однородные гиперграфы, просто заменив слово «граф» в утверждении на «гиперграф» . Более того, мы можем определить многоцветную версию индуцированных чисел Рамсея так же, как и в предыдущем подразделе.

Пусть H — d -однородный гиперграф с k вершинами. Определим функцию башни t _r ( x ), полагая t ₁ ( x ) = x и для i ≥ 1 , t _{i +1} ( x ) = 2 ^{т _я ( х )} . Используя метод контейнера гиперграфа, Конлон, Делламоника, Ла Флер, Рёдль и Шахт смогли показать, что для d ≥ 3, q ​​≥ 2 , r _ind ( H ; q ) ≤ t _d ( ck ) для некоторой константы c, зависящей только от д и q . В частности, этот результат отражает наиболее известную оценку обычного числа Рамсея при d = 3 .

теоремы

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

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

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

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

Более сильная, но несбалансированная бесконечная форма теоремы Рэмси для графов, теорема Эрдеша-Душника-Миллера , утверждает, что каждый бесконечный граф содержит либо счетное бесконечное независимое множество, либо бесконечную клику той же мощности , что и исходный граф.

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

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

Для любого k ограничение раскраски Ck _{в +1} на [ k ] ^{( н )} (игнорируя цвет всех множеств, содержащих k + 1 ) является раскраской в ​​C _k . Определять $C_{k}^{1}$— to be the colourings in раскраски в C _k , являющиеся ограничениями раскрасок в C _{k +1} . Поскольку C _{k +1} не пуст, то и $C_{k}^{1}$‍ .

Similarly, the restriction of any colouring in Аналогично ограничение любой окраски в $C_{k+1}^{1}$находится is in в $C_{k}^{1}$, , allowing one to define позволяющий определить $C_{k}^{2}$как as the set of all such restrictions, a non-empty set. Continuing so, define множество всех таких ограничений, непустое множество. Продолжая так, определим $C_{k}^{m}$для for all integers всех целых чисел m , k .

Теперь для любого целого k числа

$C_{k}\supseteq C_{k}^{1}\supseteq C_{k}^{2}\supseteq \cdots$

и каждое множество непусто. Более того, C _k конечен, поскольку

$|C_{k}|\leq c^{\frac {k!}{n!(k-n)!}}$

Отсюда следует, что пересечение всех этих множеств непусто и пусть

$D_{k}=C_{k}\cap C_{k}^{1}\cap C_{k}^{2}\cap \cdots$

каждая раскраска в Dk _Тогда является ограничением раскраски в Dk _{1 +} . Следовательно, ограничивая раскраску в D _k раскраской в ​​D _{k +1} и продолжая делать это, можно построить раскраску $\mathbb {N} ^{(n)}$ без какого-либо монохроматического набора размера T . Это противоречит бесконечной теореме Рамсея.

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

Гиперграфики

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

Для m = 3 мы знаем точное значение одного нетривиального числа Рамсея, а именно R (4, 4; 3) = 13 . Этот факт был установлен Бренданом Маккеем и Станиславом Радзишовским в 1991 году. Кроме того, имеем: R (4, 5; 3) ≥ 35 , R (4, 6; 3) ≥ 63 и R (5, 5; 3) ≥ 88 .

Ориентированные графы

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

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

Имеем R (0) = 0 , R (1) = 1 , R (2) = 2 , R (3) = 8 = 4 , R (4) , R (5) = 14 , R (6) = 28. , и 34 ≤ R (7) ≤ 47 .

Неисчисляемые кардиналы

Основная статья: Исчисление разделов

С точки зрения исчисления разделов теорему Рамсея можно сформулировать как $\aleph _{0}\rightarrow (\aleph _{0})_{k}^{n}$ для всех конечных n и k . Вацлав Серпинский показал, что теорема Рамсея не распространяется на графы размера $\aleph _{1}$ показав это $2^{\aleph _{0}}\nrightarrow (\aleph _{1})_{2}^{2}$. В частности, гипотеза континуума предполагает, что $\aleph _{1}\nrightarrow (\aleph _{1})_{2}^{2}$. Стево Тодорчевич что на самом деле в ZFC показал , $\aleph _{1}\nrightarrow [\aleph _{1}]_{\aleph _{1}}^{2}$, гораздо более сильное утверждение, чем $\aleph _{1}\nrightarrow (\aleph _{1})_{2}^{2}$. Джастин Т. Мур еще больше укрепил этот результат. С положительной стороны, кардинал Рэмси , $\kappa$, — большой кардинал, аксиоматически определенный для удовлетворения соответствующей формулы: $\kappa \rightarrow (\kappa )_{2}^{<\omega }$. Существование кардиналов Рэмси не может быть доказано в ZFC.

аксиомой

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

См. также

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

Ссылки

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

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

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