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

Высказывание в математической комбинаторике

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

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

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

Примеры

Р(3, 3) = 6

2-цветное доказательство случая без слов .

Из-за принципа ящика, есть по крайней мере 3 ребра одного цвета (пунктирный фиолетовый) из произвольной вершины v . Называя 3 вершины, заканчивающие эти ребра x , y и z , если ребро xy , yz или zx (сплошной черный) имело этот цвет, это завершило бы треугольник с v . Но если нет, каждое должно быть противоположно окрашено, завершая треугольник xyz этого цвета.

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

Предположим, что ребра полного графа на 6 вершинах окрашены в красный и синий цвета. Выберите вершину v . Имеется 5 ребер, инцидентных v , и поэтому (по принципу ящика ) по крайней мере 3 из них должны быть одного цвета. Без потери общности мы можем предположить, что по крайней мере 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 ₅ в 2 цвета , не создавая ни одного монохромного K ₃ , показывая, что R (3, 3) > 5 . Уникальная раскраска ^[b] показана справа. Таким образом, R (3, 3) = 6 .

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

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

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

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

Предположим, что у нас есть раскраска ребер полного графа с использованием 3 цветов: красного, зеленого и синего. Предположим далее, что раскраска ребер не имеет одноцветных треугольников. Выберите вершину 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 вершинами в 3 цвета, которая избегает одноцветных треугольников. Оказывается, что существует ровно две таких раскраски на K ₁₆ , так называемые нескрученная и скрученная раскраски. Обе раскраски показаны на рисунках справа, с нескрученной раскраской слева, а скрученной справа.

Граф Клебша

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

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

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

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

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

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

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

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

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

Корпус большего количества цветов

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

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

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

числа Рамсея

Числа 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 . Такой контрпример называется графом Рамсея . Брендан Маккей ведет список известных графов Рамсея. ^[4] Верхние границы часто значительно сложнее установить: нужно либо проверить все возможные раскраски, чтобы подтвердить отсутствие контрпримера, либо представить математический аргумент в пользу его отсутствия.

Сложность вычислений

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

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

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

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

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

Как описано выше, 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) + R (3, 4) ≤ 18. Существует только два графа (4, 4, 16) (то есть 2-раскраски полного графа на 16 узлах без 4-узловых красных или синих полных подграфов) среди 6,4 × 10 ²² различных 2-раскрасок 16-узловых графов и только один граф (4, 4, 17) ( граф Пейли порядка 17) среди 2,46 × 10 ²⁶ раскрасок. ^[4] (Отсюда следует, что R (4, 4) = 18 .

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

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

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

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

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

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

Асимптотика

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

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

В частности, этот результат, полученный Эрдёшем и Секерешем , подразумевает, что когда r = 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 ≤ R (10, 10) ≤ 48,620 . Тем не менее, экспоненциальные факторы роста любой из границ не были улучшены в течение длительного времени, и для нижней границы она по-прежнему составляет √ 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},}$

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

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

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

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

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

Верхняя граница для R (3, t ) дана Ajtai , Komlós , и Szemerédi , ^[19] нижняя граница была первоначально получена Kim , ^[20] и неявная константа была улучшена независимо Fiz Pontiveros, Griffiths и Morris , ^[21] и Bohman и Keevash , ^[22] путем анализа процесса без треугольников. Кроме того, изучение более общего " процесса без H " установило наиболее известные асимптотические нижние границы для общих недиагональных чисел Рамсея, ^[23] R ( s , t )

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

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

Индуцированный Рэмси

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

Заявление

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

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

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

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

В 1984 году Эрдёш и Хайнал заявили, что они доказали связь ^[32]

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

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

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

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

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

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

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

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

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

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

Обобщения

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

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

Мы также можем обобщить индуцированную теорему Рамсея на многоцветную раскраску. Для графов 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 ^{ck 3} , где k — число вершин H , а c — константа, зависящая только от q . ^[39]

Гиперграфы

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

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

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

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

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

Теорема. Пусть будет некоторое бесконечное множество и раскрасим элементы (подмножества размера ) в разные цвета. Тогда существует некоторое бесконечное подмножество такое , что подмножества размера все имеют один и тот же цвет. ${\displaystyle X}$ ${\displaystyle [X]^{n}}$ ${\displaystyle X}$ ${\displaystyle n}$ ${\displaystyle c}$ ${\displaystyle M}$ ${\displaystyle X}$ ${\displaystyle n}$ ${\displaystyle 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 )} , чтобы получить желаемый монохромный набор.

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

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

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

Для любого k ограничение раскраски в C _{k +1} до [ 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}}$ для всех целых чисел 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} , и продолжая делать так, можно построить раскраску без какого-либо монохроматического множества размера T . Это противоречит бесконечной теореме Рамсея. ${\displaystyle \mathbb {N} ^{(n)}}$

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

Гиперграфы

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

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

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

Также возможно определить числа Рамсея для ориентированных графов; они были введены П. Эрдёшем и Л. Мозером (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) = 4 , R (4) = 8 , R (5) = 14 , R (6) = 28 и 34 ≤ R (7) ≤ 47 . ^{[46] [47]}

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

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

Связь с аксиомой выбора

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

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

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

Примечания

1. Некоторые авторы ограничивают значения больше единицы, например (Brualdi 2010) и (Harary 1972), избегая таким образом обсуждения раскраски ребер графа без ребер, в то время как другие перефразируют утверждение теоремы, требуя в простом графе либо r -клику , либо s -независимое множество , см. (Gross 2008) или (Erdős & Szekeres 1935). В этой форме рассмотрение графов с одной вершиной более естественно.
2. До автоморфизмов графа.

1. ^Радзишовский, Станислав (2011). "Малые числа Рамсея". Динамические обзоры. Электронный журнал комбинаторики . 1000. doi : 10.37236/21 .
2. До, Норман (2006). «Проблемы партий и теория Рамсея» (PDF) . Austr. Math. Soc. Gazette . 33 (5): 306–312.
3. «Знакомства по вечеринке».
4. «Графики Рэмси».
5. Джоэл Х. Спенсер (1994), Десять лекций по вероятностному методу, SIAM , стр. 4, ISBN 978-0-89871-325-1
6. 2.6 Теория Рамсея из книги «Математика с иллюстрациями»
7. Монтанаро, Эшли (2016). «Квантовые алгоритмы: обзор». npj Quantum Information . 2 : 15023. arXiv : 1511.04206 . Bibcode : 2016npjQI...215023M. doi : 10.1038/npjqi.2015.23. S2CID  2992738 – через Nature.
8. Ван, Хефенг (2016). «Определение чисел Рамсея на квантовом компьютере». Physical Review A. 93 ( 3): 032301. arXiv : 1510.01884 . Bibcode : 2016PhRvA..93c2301W. doi : 10.1103/PhysRevA.93.032301. S2CID  118724989.
9. Маккей, Брендан Д.; Радзишовский, Станислав П. (май 1995 г.). «R(4,5) = 25» (PDF) . Журнал теории графов . 19 (3): 309–322. дои : 10.1002/jgt.3190190304.
10. Exoo, Geoffrey (март 1989). "Нижняя граница для R (5, 5) ". Журнал теории графов . 13 (1): 97–98. doi :10.1002/jgt.3190130113.
11. Виглейк Ангельтвейт; Брендан Маккей (сентябрь 2024 г.). " ". arXiv : 2409.15709 [math.CO]. ${\displaystyle R(5,5)\leq 46}$
12. Брендан Д. Маккей, Станислав П. Радзишовский (1997). "Подсчет подграфов тождеств и чисел Рамсея" (PDF) . Журнал комбинаторной теории . Серия B. 69 (2): 193–209. doi : 10.1006/jctb.1996.1741 .
13. Станислав Радзишовский. «ДС1» . Проверено 17 августа 2023 г.
14. Ангельтвейт, Виглейк (31 декабря 2023 г.). " ". arXiv : 2401.00392 [math.CO]. ${\displaystyle R(3,10)\leq 41}$
15. Exoo, Geoffrey; Tattooevic, Milos (2015). "Новые нижние границы для 28 классических чисел Рамсея". Electronic Journal of Combinatorics . 22 (3): 3. arXiv : 1504.02403 . Bibcode : 2015arXiv150402403E. doi : 10.37236/5254 .
16. Exoo, Geoffrey (26 октября 2023 г.). «Нижняя граница для R(5,6)». arXiv : 2310.17099 [math.CO].
17. Кампос, Марсело; Гриффитс, Саймон; Моррис, Роберт; Сахасрабудхе, Джулиан (2023). «Экспоненциальное улучшение для диагонального Рэмси». arXiv : 2303.09521 [math.CO].
18. Сломан, Лейла (2 мая 2023 г.). «Очень большой маленький скачок вперед в теории графов». Журнал Quanta .
19. Айтай, Миклош; Комлос, Янош; Семереди, Эндре (1 ноября 1980 г.). «Заметка о числах Рамсея». Журнал комбинаторной теории, серия А. 29 (3): 354–360. дои : 10.1016/0097-3165(80)90030-8 . ISSN  0097-3165.
20. Ким, Чжон Хан (1995), «Число Рамсея R (3, t ) имеет порядок величины t ² /log t », Случайные структуры и алгоритмы , 7 (3): 173–207, CiteSeerX 10.1.1.46.5058 , doi :10.1002/rsa.3240070302 
21. "Процесс без треугольников и число Рамсея R(3,k)". bookstore.ams.org . Получено 2023-06-27 .
22. Бохман, Том; Киваш, Питер (17.11.2020). «Динамическая концентрация процесса без треугольников». Случайные структуры и алгоритмы . 58 (2): 221–293. arXiv : 1302.5963 . doi : 10.1002/rsa.20973.
23. Боман, Том; Киваш, Питер (2010-08-01). «Ранняя эволюция процесса без H». Inventiones Mathematicae . 181 (2): 291–336. arXiv : 0908.0429 . Bibcode : 2010InMat.181..291B. doi : 10.1007/s00222-010-0247-x. ISSN  1432-1297.
24. Маттеус, Сэм; Верстрате, Жак (5 марта 2024 г.). «Асимптотика r(4,t)». Annals of Mathematics . 199 (2). arXiv : 2306.04007 . doi : 10.4007/annals.2024.199.2.8.
25. Цепелевич, Джордана (22 июня 2023 г.). «Математики открывают новый способ предсказывать структуру в графах». Журнал Quanta .
26. Эрдёш, Пауль (1990), Нешетржил, Ярослав; Рёдль, Войтех (ред.), «Проблемы и результаты по графам и гиперграфам: сходства и различия», Математика теории Рамсея , алгоритмы и комбинаторика, т. 5, Берлин, Гейдельберг: Springer, стр. 12–28, doi :10.1007/978-3-642-72905-8_2, ISBN 978-3-642-72905-8, получено 2023-06-27
27. "Проблемы Эрдёша" . www.erdosproblems.com . Проверено 12 июля 2023 г.
28. Эрдеш, П .; Хайнал, А.; Поса, Л. (1975). «Сильное вложение графов в цветные графы». Бесконечные и конечные множества, Vol. 1 . Colloquia Mathematica Societatis Янош Бойай. Том. 10. Северная Голландия, Амстердам/Лондон. стр. 585–595.
29. Дойбер, В. (1975). «Обобщение теоремы Рамсея». Бесконечные и конечные множества, Vol. 1 . Colloquia Mathematica Societatis Янош Бойай. Том. 10. Северная Голландия, Амстердам/Лондон. стр. 323–332.
30. Rödl, V. (1973). Размерность графа и обобщенные теоремы Рамсея (магистрская диссертация). Карлов университет.
31. Эрдёш, П. (1975). «Проблемы и результаты по конечным и бесконечным графам». Последние достижения в теории графов (Труды Второго Чехословацкого симпозиума, Прага, 1974) . Academia, Прага. С. 183–192.
32. Эрдёш, Пол (1984). «О некоторых проблемах теории графов, комбинаторного анализа и комбинаторной теории чисел» (PDF) . Теория графов и комбинаторика : 1–17.
33. Кохаякава, Ю.; Премель, Х.Ю.; Рёдль, В. (1998). «Индуцированные числа Рамсея» (PDF) . Комбинаторика . 18 (3): 373–404. дои : 10.1007/PL00009828 .
34. Fox, Jacob ; Sudakov, Benny (2008). «Индуцированные теоремы типа Рамсея». Advances in Mathematics . 219 (6): 1771–1800. arXiv : 0706.4112 . doi : 10.1016/j.aim.2008.07.009 .
35. Конлон, Дэвид ; Фокс, Джейкоб ; Судаков, Бенни (2012). «О двух проблемах в теории графов Рамсея». Combinatorica . 32 (5): 513–535. arXiv : 1002.0045 . doi : 10.1007/s00493-012-2710-3 .
36. Бек, Йожеф (1990). «О размере Рамсеевского числа путей, деревьев и цепей. II». В Nešetřil, J.; Rödl, V. (ред.). Математика теории Рамсея . Алгоритмы и комбинаторика. Том 5. Springer, Берлин, Гейдельберг. стр. 34–45. doi : 10.1007/978-3-642-72905-8_4 . ISBN 978-3-642-72907-2.
37. Лучак, Томаш; Редль, Войтех (март 1996 г.). «Об индуцированных числах Рамсея для графов с ограниченной максимальной степенью». Журнал комбинаторной теории . Серия B. 66 (2): 324–333. doi : 10.1006/jctb.1996.0025 .
38. Конлон, Дэвид ; Фокс, Джейкоб ; Чжао, Юфэй (май 2014 г.). «Экстремальные результаты в разреженных псевдослучайных графах». Advances in Mathematics . 256 : 206–29. arXiv : 1204.6645 . doi : 10.1016/j.aim.2013.12.004 .
39. Фокс, Якоб ; Судаков, Бенни (2009). «Теоремы плотности для двудольных графов и связанные с ними результаты типа Рамсея». Combinatorica . 29 (2): 153–196. arXiv : 0707.4159v2 . doi : 10.1007/s00493-009-2475-5 .
40. Конлон, Дэвид ; Делламоника-младший, Домингос; Ла Флер, Стивен; Рёдль, Войтех ; Шахт, Матиас (2017). «Заметка о индуцированных числах Рамсея». В Лебле, Мартин; Нешетржил, Ярослав ; Томас, Робин (ред.). Путешествие по дискретной математике . Спрингер, Чам. стр. 357–366. arXiv : 1601.01493 . дои : 10.1007/978-3-319-44479-6_13 . ISBN 978-3-319-44478-9.
41. Гулд, Мартин. "Теория Рамсея" (PDF) . Математический институт Оксфордского университета . Архивировано из оригинала (PDF) 2022-01-30.
42. Душник, Бен; Миллер, Э. У. (1941). «Частично упорядоченные множества». American Journal of Mathematics . 63 (3): 600–610. doi : 10.2307/2371374. hdl : 10338.dmlcz/100377 . JSTOR  2371374. MR  0004862., См. в частности теоремы 5.22 и 5.23.
43. Дистель, Рейнхард (2010). «Глава 8, Бесконечные графы». Теория графов (4-е изд.). Гейдельберг: Springer-Verlag. С. 209–2010. ISBN 978-3-662-53621-6.
44. Маккей, Брендан Д.; Радзишовский, Станислав П. (1991). «Вычислено первое классическое число Рамсея для гиперграфов». Труды второго ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA'91 : 304–308.
45. Dybizbański, Janusz (2018-12-31). "Нижняя граница числа Рамсея гиперграфа R(4,5;3)". Вклад в дискретную математику . 13 (2). doi : 10.11575/cdm.v13i2.62416 . ISSN  1715-0868.
46. Смит, Уоррен Д.; Эксу, Джефф, Частичный ответ на головоломку № 27: величина, подобная Рамсею , получено 2020-06-02
47. Нейман, Дэвид; Макки, Джон; Хейл, Марийн (01.11.2020). «Более строгие границы направленного числа Рамсея R(7)». arXiv : 2011.00683 [math.CO].
48. Хиршфельдт, Денис Р. (2014). Slicing the Truth . Серия конспектов лекций Института математических наук Национального университета Сингапура. Том 28. World Scientific.
49. Бласс, Андреас (сентябрь 1977 г.). «Теорема Рамсея в иерархии принципов выбора». Журнал символической логики . 42 (3): 387–390. doi :10.2307/2272866. ISSN  1943-5886. JSTOR  2272866.
50. Forster, TE; Truss, JK (январь 2007). «Теорема Рамсея и лемма Кёнига». Архив для Mathematical Logic . 46 (1): 37–42. doi :10.1007/s00153-006-0025-z. ISSN  1432-0665.

Ссылки

• Айтаи, Миклош ; Комлос, Янош ; Семереди, Эндре (1980), «Заметки о числах Рамсея», Дж. Комбин. Теория Сер. А , 29 (3): 354–360, doi : 10.1016/0097-3165(80)90030-8.
• Бохман, Том; Киваш, Питер (2010), «Ранняя эволюция процесса без H», Invent. Math. , 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. Amer. Math. Soc. , 53 (4): 292–294, doi : 10.1090/S0002-9904-1947-08785-1.
• Эрдеш, П .; Мозер, Л. (1964), «О представлении ориентированных графов как объединений порядков» (PDF) , A Magyar Tudományos Akadémia, Matematikai Kutató Intézetének Közleményei , 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)», Журнал теории графов , 13 : 97–98, doi :10.1002/jgt.3190130113.
• Грэм, Р.; Ротшильд, Б.; Спенсер, Дж. Х. (1990), Теория Рамсея , Нью-Йорк: John Wiley and Sons.
• Гросс, Джонатан Л. (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), «Теорема Рамсея – новая нижняя граница», J. Combin. Theory Ser. A , 18 : 108–115, doi : 10.1016/0097-3165(75)90071-0.
• Бянь, Чжэнбин; Чудак, Фабиан; Макреди, Уильям Г.; Кларк, Лейн; Гайтан, Фрэнк (2013), «Экспериментальное определение чисел Рамсея», Physical Review Letters , 111 (13): 130505, arXiv : 1201.1842 , Bibcode : 2013PhRvL.111m0505B, doi : 10.1103/PhysRevLett.111.130505, PMID  24116761, S2CID  1303361.

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

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