В комбинаторной математике , теорема Рэмси , в одном из своих графовых форм, утверждает , что каждый найдет монохроматический клик в любом края маркировок (с цветами) достаточно большого полного графа . Чтобы продемонстрировать теорему для двух цветов (скажем, синего и красного), пусть r и s - любые два положительных целых числа . [1] Теорема Рамсея утверждает, что существует наименьшее натуральное число R ( r , s ), для которого любая сине-красная окраска ребер полного графа наR ( r , s ) вершин содержит синюю клику на r вершинах или красную клику на s вершинах. (Здесь R ( r , s ) означает целое число, которое зависит как от r, так и от s .)
Теорема Рамсея является основополагающим результатом комбинаторики. Первую версию этого результата доказал Ф. П. Рэмси . Это положило начало комбинаторной теории, которая теперь называется теорией Рамсея , которая ищет регулярность среди беспорядка: общие условия существования подструктур с регулярными свойствами. В этом приложении речь идет о существовании монохроматических подмножеств , то есть подмножеств связанных ребер только одного цвета.
Расширение этой теоремы применимо к любому конечному числу цветов, а не только к двум. Точнее, теорема утверждает, что для любого заданного числа цветов c и любых заданных целых чисел n 1 , ..., n c существует число R ( n 1 , ..., n c ) такое, что если ребра полного графа порядка R ( n 1 , ..., n c ) раскрашены c разных цветов, то для некоторого i от 1 до c он должен содержать полный подграф порядка n i , ребра которого все цвета i . В приведенном выше частном случае c = 2 (и n 1 = r и n 2 = s ).
Примеры
R (3, 3) = 6
Предположим, что ребра полного графа на 6 вершинах окрашены в красный и синий цвета. Выберите вершину, v . К v инцидентно 5 ребер, поэтому (по принципу «голубятни» ) как минимум 3 из них должны быть одного цвета. Без ограничения общности мы можем считать, что по крайней мере 3 из этих ребер, соединяющих вершину v с вершинами r , s и t , синие. (Если нет, поменяйте местами красный и синий в дальнейшем.) Если какое-либо из ребер ( r , s ), ( r , t ), ( s , t ) также синее, то мы имеем полностью синий треугольник. Если нет, то все три ребра красные, и у нас есть полностью красный треугольник. Поскольку это рассуждение работает для любой раскраски, любое K 6 содержит одноцветное K 3 , и поэтому 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 6 одноцветные.
И наоборот, можно 2-раскрасить K 5 без создания монохроматического K 3 , показывая, что R (3, 3)> 5. Уникальная раскраска [2] показана справа. Таким образом, R (3, 3) = 6.
Задача доказательства того, что R (3, 3) ≤ 6, была одной из задач математического конкурса Уильяма Лоуэлла Патнэма в 1953 году, а также на венгерской математической олимпиаде в 1947 году.
Разноцветный пример: R (3, 3, 3) = 17
Многоцветное число Рамси - это число Рамси, состоящее из 3 или более цветов. Есть (с точностью до симметрии) только два нетривиальных многоцветных числа Рамсея, для которых известно точное значение, а именно R (3, 3, 3) = 17 и R (3, 3, 4) = 30. [3]
Предположим, что у нас есть раскраска ребер полного графа в 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 16 таких раскрасок ровно две , так называемые раскрутки и раскраски скрученные. Обе раскраски показаны на рисунках справа, причем раскрученная раскраска вверху, а закрученная - внизу.
Если мы выберем любой цвет из раскрученной или скрученной раскраски на K 16 и рассмотрим граф, ребра которого являются в точности теми ребрами, которые имеют указанный цвет, мы получим граф Клебша .
Известно, что существует ровно две раскраски краев в 3 цвета на K 15, которые избегают монохроматических треугольников, которые могут быть построены путем удаления любой вершины из раскрученных и скрученных раскрасок на K 16 соответственно.
Также известно, что существует ровно 115 раскрасок краев с 3 цветами на K 14, которые избегают монохроматических треугольников, при условии, что мы рассматриваем раскраски краев, которые различаются перестановкой цветов, как одинаковые.
Доказательство
2-х цветный корпус
Теорема для двухцветного случая доказывается индукцией по r + s . [4] Как видно из определения , что для всех п , R ( п , 2) = R (2, п ) = п . Это запускает индукцию. Докажем существование R ( r , s ) , найдя для него явную оценку. По предположению индукции существуют R ( r - 1, s ) и R ( r , s - 1) .
- Лемма 1. R ( r , s ) ≤ R ( r - 1, s ) + R ( r , s - 1) :
Доказательство. Рассмотрим полный граф на R ( r - 1, s ) + R ( r , s - 1) вершинах, ребра которого раскрашены в два цвета. Выберите вершину v из графа и разделите оставшиеся вершины на два множества M и N так , чтобы для каждой вершины w , w находилось в M, если ( v , w ) синее, и w было в N, если ( v , w ) красный. Поскольку в графе R ( r - 1, s ) + R ( r , s - 1) = | M | + | N | + 1 вершина, то либо | M | ≥ R ( r - 1, s ) или | N | ≥ R ( r , s - 1) . В первом случае, если M имеет красный K s, то также и исходный граф, и мы закончили. В противном случае М имеет голубую K г -1 и так M ∪ { v } имеет голубую K г по определению М . Последний случай аналогичен. Таким образом, утверждение верно, и мы завершили доказательство для двух цветов.
В этом двухцветном случае, если R ( r - 1, s ) и R ( r , s - 1) четные, неравенство индукции может быть усилено до: [5]
- R ( r , s ) ≤ R ( r - 1, s ) + R ( r , s - 1) - 1 .
Доказательство . Предположим, что p = R ( r - 1, s ) и q = R ( r , s - 1) четные. Пусть t = p + q - 1 и рассмотрим двухцветный граф из t вершин. Если степень -я вершина в графе, а затем, в соответствии с Handshaking леммы ,даже. Учитывая, что t нечетное, должно быть четное. Предполагатьчетно, M и N - вершины, инцидентные вершине 1 в синем и красном подграфе соответственно. Тогда оба а также четные. Согласно принципу голубятни , либо, или же . С четно, в то время как нечетно, первое неравенство можно усилить, поэтому либо или же . Предполагать. Тогда либо подграф M имеет красный и доказательство завершено, или на нем есть синий который вместе с вершиной 1 образует синий . Дело обрабатывается аналогично.
Случай большего количества цветов
Лемма 2. Если c> 2, то R ( n 1 , ..., n c ) ≤ R ( n 1 , ..., n c −2 , R ( n c −1 , n c )).
Доказательство. Рассмотрим полный граф из R ( n 1 , ..., n c −2 , R ( n c −1 , n c )) вершин и раскрасим его ребра в c цветов. Теперь «дальтоник» и представьте, что c - 1 и c одного цвета. Таким образом, график теперь ( c - 1) -окрашен. Согласно определению R ( n 1 , ..., n c −2 , R ( n c −1 , n c )), такой граф содержит либо 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 . В любом случае доказательство завершено.
Из леммы 1 следует, что любое R (r, s) конечно. Правая часть неравенства в лемме 2 выражает число Рамсея для c цветов через числа Рамсея для меньшего количества цветов. Следовательно, любое R ( n 1 , ..., n c ) конечно для любого количества цветов. Это доказывает теорему.
Числа Рамсея
Числа R ( r , s ) в теореме Рамсея (и их расширения до более чем двух цветов) известны как числа Рамсея. Число Рамсея, R ( m , n ) , дает решение проблемы вечеринки, которая требует минимального количества гостей, R ( m , n ) , которые должны быть приглашены, чтобы по крайней мере m знали друг друга или, по крайней мере, п не будут знать друг друга. На языке теории графов число Рамсея - это минимальное количество вершин 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 . Такой контрпример называется графом Рамсея . Брендан Маккей ведет список известных графиков Рэмси. [6] Верхние границы зачастую установить значительно труднее: нужно либо проверить все возможные раскраски, чтобы подтвердить отсутствие контрпримера, либо представить математический аргумент в пользу его отсутствия.
Вычислительная сложность
Эрдеш просит нас представить инопланетную силу, намного более мощную, чем мы, приземляющуюся на Земле и требующую значения R (5, 5), иначе они уничтожат нашу планету. В этом случае, утверждает он, мы должны собрать все наши компьютеры и всех наших математиков и попытаться найти ценность. Но предположим, что вместо этого они просят R (6, 6) . В этом случае, считает он, мы должны попытаться уничтожить инопланетян.
Сложной компьютерной программе не нужно рассматривать все раскраски по отдельности, чтобы исключить их все; тем не менее, это очень сложная вычислительная задача, с которой существующее программное обеспечение может справиться только при небольших размерах. Каждый полный граф K n имеет1/2n ( n - 1) ребер, так что всего будет cп ( п - 1)/2графики для поиска (для цветов c ) при использовании грубой силы. [8] Следовательно, сложность поиска всех возможных графов (с помощью грубой силы ) составляет O ( c n 2 ) для c раскрасок и не более чем n узлов.
С появлением квантовых компьютеров ситуация вряд ли улучшится . Самый известный алгоритм [ необходима цитата ] демонстрирует только квадратичное ускорение (см . Алгоритм Гровера ) по сравнению с классическими компьютерами, так что время вычислений по-прежнему экспоненциально зависит от количества узлов. [9]
Известные ценности
Как описано выше, R (3, 3) = 6 . Легко доказать, что R (4, 2) = 4 и, в более общем смысле, что R ( s , 2) = s для всех s : граф на s - 1 узлах со всеми краями, окрашенными в красный цвет, служит контрпримером и доказывает, что R ( s , 2) ≥ s ; среди раскрасок графа на з узлах, окраска со всеми краями цветных красными содержит с -node красный подграфа, а все остальные красители содержат 2 -node синего подграфа (то есть, пара узлов , соединенные с синим краем.)
Используя неравенства индукции, можно заключить, что 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 22 различных 2- раскрасок 16- узловых графов. , и только один (4, 4, 17) граф ( граф Пэли 17-го порядка ) среди 2,46 × 10 26 раскрасок. [6] (Это было доказано Эвансом, Пулхэмом и Шиханом в 1979 г.) Отсюда следует, что R (4, 4) = 18 .
Тот факт, что R (4, 5) = 25 был впервые установлен Бренданом МакКеем и Станиславом Радзишовским в 1995 г. [10]
Точное значение R (5, 5) неизвестно, хотя известно, что оно находится между 43 (Джеффри Эксу (1989) [11] ) и 48 (Ангельтвейт и Маккей (2017) [12] ) (включительно).
В 1997 году Маккей, Радзишовски и Экзоо использовали методы компьютерной генерации графов, чтобы предположить, что R (5, 5) = 43 . Они смогли построить ровно 656 (5, 5, 42) графов, получая один и тот же набор графов разными путями. Ни один из 656 графиков не может быть расширен до графа (5, 5, 43) . [13]
Для R ( r , s ) с r , s > 5 доступны только слабые оценки. Нижние оценки для R (6, 6) и R (8, 8) не улучшались с 1965 и 1972 годов соответственно. [3]
R ( r , s ) при r , s ≤ 10 показаны в таблице ниже. Если точное значение неизвестно, в таблице перечислены наиболее известные границы. R ( r , s ) с r , s <3 задаются формулами R (1, s ) = 1 и R (2, s ) = s для всех значений s .
Стандартное обследование на развитии числа исследований Рэмси является Dynamic Survey 1 из электронного журнала комбинаторики , по Станису Радзисзоуский , который периодически обновляется. [3] Если не указано иное, записи в таблице ниже взяты из издания за март 2017 года. (Обратите внимание на тривиальную симметрию по диагонали, поскольку R ( r , s ) = R ( s , r ) .)
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 |
Асимптотика
Неравенство R ( r , s ) ≤ R ( r - 1, s ) + R ( r , s - 1) может применяться индуктивно, чтобы доказать, что
В частности, этот результат, в связи с Эрдешем и Szekeres , следует , что при г = s ,
Экспоненциальная нижняя граница,
был дан Эрдёшем в 1947 году и сыграл важную роль в введении им вероятностного метода. Очевидно, существует огромный разрыв между этими двумя границами: например, для s = 10 это дает 101 ≤ R (10, 10) ≤ 48620 . Тем не менее, коэффициенты экспоненциального роста для каждой границы не были улучшены на сегодняшний день и все еще составляют 4 и √ 2 соответственно. Не существует известной явной конструкции, дающей экспоненциальную нижнюю границу. Наиболее известные нижняя и верхняя границы диагональных чисел Рамсея в настоящее время равны
из-за Спенсера и Конлона соответственно.
Для недиагональных чисел Рамсея R (3, t ) известно, что они имеют порядок; эквивалентно это можно сформулировать так: наименьшее возможное число независимости в n- вершинном графе без треугольников равно
Верхняя граница для R (3, т ) задается Ajtai , Комлоша и Семереди , нижняя граница была получена первоначально Ким , и была улучшена за счет Griffiths, Моррис , Fiz Pontiveros и Бохман и Keevash , путем анализа triangle- бесплатный процесс. В целом, для внедиагональная Рэмси чисел, R ( ы , т ) , с с фиксированной и т растет, лучшие известные оценки являются
благодаря Бохману и Кеевашу и Айтаи , Комлосу и Семереди соответственно.
Расширения теоремы
Бесконечные графы
Еще один результат, также обычно называемый теоремой Рамсея , применим к бесконечным графам. В контексте, где также обсуждаются конечные графы, ее часто называют «бесконечной теоремой Рамсея». Поскольку интуиция, обеспечиваемая графическим представлением графа, уменьшается при переходе от конечных графов к бесконечным, теоремы в этой области обычно формулируются в теоретико-множественной терминологии. [15]
- Теорема. Пусть X - некоторое бесконечное множество, и раскрасим элементы X ( n ) (подмножества X размера n ) в c разных цветов. Тогда существует некоторое бесконечное подмножество M в X такое, что все подмножества M размера n имеют один и тот же цвет.
Доказательство . Доказательство проводится индукцией по n - размеру подмножеств. Для n = 1 это утверждение эквивалентно утверждению, что если вы разделите бесконечное множество на конечное число наборов, то одно из них будет бесконечным. Это очевидно. Предполагая, что теорема верна для n ≤ r , мы докажем ее для n = r + 1. Для c- раскраски ( r + 1) -элементных подмножеств X , пусть a 0 является элементом X и Y = Х \ { а 0 }. Затем мы индуцируют гр -colouring из г элементных подмножеств Y , просто добавив в 0 для каждого г -элементного подмножества (чтобы получить ( г + 1) -элементное подмножество X ). По предположению индукции существует бесконечное подмножество Y 1 в Y такое, что каждое r -элементное подмножество Y 1 окрашено в один и тот же цвет в индуцированной раскраске. Таким образом, существует элемент a 0 и бесконечное подмножество Y 1 такие, что все ( r + 1) -элементные подмножества X, состоящие из a 0 и r элементов Y 1, имеют одинаковый цвет. По тому же аргументу существует элемент a 1 в Y 1 и бесконечное подмножество Y 2 в Y 1 с одинаковыми свойствами. Индуктивно мы получаем последовательность { a 0 , a 1 , a 2 , ...} такую, что цвет каждого ( 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 ) , чтобы получить желаемый монохроматический набор.
Более сильная, но несбалансированная бесконечная форма теоремы Рамсея для графов, теорема Эрдеша – Душника – Миллера , утверждает, что каждый бесконечный граф содержит либо счетно бесконечное независимое множество, либо бесконечную клику той же мощности, что и исходный граф. [16]
Бесконечная версия подразумевает конечное
Можно вывести конечную теорему Рамсея из бесконечной версии путем доказательства от противного . Предположим, что конечная теорема Рамсея неверна. Тогда существуют такие целые числа c , n , T , что для любого целого k существует c- раскраскабез монохроматического набора размера Т . Пусть С к Обозначим гр -colourings избез монохроматического набора размера Т .
Для любого k ограничение раскраски в C k +1 на(игнорируя цвет всех наборов, содержащих k + 1) является раскраской в C k . Определятьбыть раскрасками в C k, которые являются ограничениями раскрасок в C k +1 . Поскольку C k +1 не пусто, то и.
Аналогично ограничение любой раскраски в в , позволяющий определить как набор всех таких ограничений непустой набор. Продолжая так, определимдля всех целых m , k .
Теперь, для любого целого числа к ,, и каждый набор не пуст. Кроме того, C k конечно, поскольку. Отсюда следует, что пересечение всех этих множеств непусто, и пусть. Тогда каждая раскраска в D k является ограничением раскраски в D k +1 . Следовательно, неограничивая раскраску в D k до раскраски в D k +1 и продолжая это делать, можно построить раскраскубез какого - либо монохроматического набора размера Т . Это противоречит бесконечной теореме Рамсея.
Если принять подходящую топологическую точку зрения, этот аргумент становится стандартным аргументом компактности, показывающим, что бесконечная версия теоремы влечет конечную версию. [17]
Гиперграфы
Теорема распространяется и на гиперграфы . М -hypergraph представляет собой график , чьи «ребро» представляют собой наборы т вершин - в нормальном графике ребро представляет собой набор из 2 -х вершин. Полная формулировка теоремы Рамсея для гиперграфов состоит в том, что для любых целых чисел m и c и любых целых чисел n 1 , ..., n c существует целое число R ( n 1 , ..., n c ; c , m ) такая, что если гиперребра полного m -гиперграфа порядка R ( n 1 , ..., n c ; c , m ) раскрашены c разных цветов, то для некоторого i между 1 и c гиперграф должен содержать a полный суб- m -гиперграф порядка n i , все гиперребра которого цвета i . Эта теорема обычно доказывается индукцией по m , «гипер-сущности» графа. Базовый случай доказательства - m = 2, что в точности соответствует приведенной выше теореме.
Направленные графы
Также возможно определить числа Рамсея для ориентированных графов; они были введены П. Эрдёшем и Л. Мозером ( 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. , и 32 ≤ R (7) ≤ 54. [18]
Отношение к аксиоме выбора
В обратной математике существует значительная разница в силе доказательства между версией теоремы Рамсея для бесконечных графов (случай n = 2) и для бесконечных мультиграфов (случай n ≥ 3). Версия мультиграфа теоремы эквивалентна прочность к арифметическому пониманию аксиоме , что делает его часть подсистемы ACA 0 из арифметики второго порядка , одной из больших пяти подсистем в обратной математике. Напротив, согласно теореме Дэвида Ситапуна , графическая версия теоремы слабее, чем ACA 0 , и (объединяя результат Ситапуна с другими) она не попадает в одну из больших пяти подсистем. [19] Однако над ZF графическая версия эквивалентна классической лемме Кёнига . [20]
Смотрите также
- Кардинал Рэмси
- Теорема Пэрис – Харрингтона
- Сим (игра с карандашом)
- Бесконечная теория Рамсея
- Число Ван дер Вардена
- Рэмси игра
- Теорема Эрдеша – Радо
Заметки
- ^ Некоторые авторы ограничивают значения больше единицы, например ( Brualdi 2010 ) и ( Harary 1972 ), таким образом избегая обсуждения окраски ребер графа без ребер, в то время как другие перефразируют формулировку теоремы так, чтобы она требовалась, в простой граф , либо г -clique или с - независимое множество , см ( брутто 2008 ) или ( Erdős & Шекереса +1935 ). В таком виде более естественно рассматривать графы с одной вершиной.
- ^ с точностью до автоморфизмов графа
- ^ a b c Радзишовский, Станислав (2011). «Малые числа Рэмси» . Динамические опросы. Электронный журнал комбинаторики . DOI : 10.37236 / 21 .
- ^ Делай, Норман (2006). «Партийные проблемы и теория Рамсея» (PDF) . Austr. Математика. Soc. Вестник . 33 (5): 306–312.
- ^ «Партийные знакомства» .
- ^ а б «Графики Рэмси» .
- ^ Джоэл Х. Спенсер (1994), Десять лекций по вероятностному методу , SIAM , стр. 4 , ISBN 978-0-89871-325-1
- ^ 2.6 Теория Рамсея из освещенной математики
- ^ Ван, Хэфэн (2016). «Определение чисел Рамсея на квантовом компьютере». Physical Review . 93 (3): 032301. arXiv : 1510.01884 . Bibcode : 2016PhRvA..93c2301W . DOI : 10.1103 / PhysRevA.93.032301 .
- ^ а б Брендан Д. Маккей, Станислав П. Радзишовский (май 1995 г.). « R (4,5) = 25» (PDF) . Журнал теории графов . 19 (3): 309–322. DOI : 10.1002 / jgt.3190190304 .
- ^ Экзу, Джеффри (март 1989). «Нижняя оценка R (5, 5) ». Журнал теории графов . 13 (1): 97–98. DOI : 10.1002 / jgt.3190130113 .
- ^ Виглейк Ангельтвейт; Брендан Маккей (2017). "". arXiv : 1703.08768v2 [ math.CO ].
- ^ Брендан Д. Маккей, Станислав П. Радзишовский (1997). «Подграф подсчета тождеств и чисел Рамсея» (PDF) . Журнал комбинаторной теории . 69 (2): 193–209. DOI : 10.1006 / jctb.1996.1741 .
- ^ а б в г Эксу, Джеффри; Татаревич, Милош (2015). «Новые нижние границы для 28 классических чисел Рамсея» . Электронный журнал комбинаторики . 22 (3): 3. arXiv : 1504.02403 . Bibcode : 2015arXiv150402403E . DOI : 10.37236 / 5254 .
- ^ Мартин Гулд. "Теория Рэмси" (PDF) .
- ^ Душник, Бен; Миллер, EW (1941). «Частично заказанные наборы». Американский журнал математики . 63 (3): 600–610. DOI : 10.2307 / 2371374 . hdl : 10338.dmlcz / 100377 . JSTOR 2371374 . Руководство по ремонту 0004862 .. См., В частности, теоремы 5.22 и 5.23.
- ^ Дистель, Рейнхард (2010). «Глава 8, Бесконечные графы». Теория графов (4-е изд.). Гейдельберг: Springer-Verlag. С. 209–2010. ISBN 978-3-662-53621-6.
- ^ Смит, Уоррен Д .; Экзу, Джефф, Частичный ответ на загадку № 27: количество , похожее на Рамси , получено 2 июня 2020 г.
- ^ Хиршфельдт, Денис Р. (2014). Нарезка истины . Серия конспектов лекций Института математических наук Национального университета Сингапура. 28 . World Scientific.
- ^ Лолли, Габриэле (октябрь 1977 г.). «О теореме Рамсея и аксиоме выбора» . Журнал формальной логики Нотр-Дам . 18 (4): 599–601. DOI : 10.1305 / ndjfl / 1093888126 . ISSN 0029-4527 .
Рекомендации
- Айтай, Миклош ; Комлос, Янош ; Семереди, Эндре (1980), "Заметка о числах Рамсея", J. Combin. Теория Сер. , 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
- Бруальди, Ричард А. (2010), Введение в комбинаторику (5-е изд.), Прентис-Холл, стр. 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.
- Эрдеш, Пол (1947), "Некоторые замечания по теории графов", Bull. Амер. Математика. Soc. , 53 (4): 292–294, DOI : 10.1090 / S0002-9904-1947-08785-1.
- Erdős, P .; Мозер, Л. (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.
- Exoo, G. (1989), «Нижняя оценка R (5,5)», Journal of Graph Theory , 13 : 97–98, DOI : 10.1002 / jgt.3190130113.
- Graham, R .; Ротшильд, В .; Спенсер, Дж. Х. (1990), Теория Рэмси , Нью-Йорк: Джон Вили и сыновья.
- Гросс, Джонатан Л. (2008), Комбинаторные методы с компьютерными приложениями , CRC Press, стр. 458, ISBN 978-1-58488-743-0
- Харари, Франк (1972), теория графов , Addison-Wesley, стр. 16–17, ISBN 0-201-02787-9
- Рэмси, FP (1930), "Об одной задаче формальной логики", Труды Лондонского математического общества , 30 : 264-286, DOI : 10.1112 / ПНИЛ / s2-30.1.264.
- Спенсер, Дж. (1975), "Теорема Рамсея - новая нижняя оценка", J. Combin. Теория Сер. , 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.
Внешние ссылки
- "Теорема Рамсея" , Математическая энциклопедия , EMS Press , 2001 [1994]
- Ramsey @ Home - это проект распределенных вычислений, предназначенный для поиска новых нижних границ для различных чисел Рамси с использованием множества различных методов.
- Электронный журнал комбинаторика динамического обследования малых чисел Рамсея (по Станису Радзисзоуский)
- Число Рамсея - из MathWorld (содержит нижнюю и верхнюю границы до R (19, 19))
- Число Рэмси - Джеффри Экзу (содержит R (5, 5)> 42 контрдоказательства)