Jump to content

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

(Перенаправлено из теоремы Рамсея )

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

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

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

Примеры [ править ]

Р (3, 3) = 6 [ править ]

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

Предположим, что ребра полного графа на 6 вершинах окрашены в красный и синий цвета. Выберите вершину, v . Есть 5 ребер, инцидентных v , поэтому (по принципу ячейки ) по крайней мере 3 из них должны быть одного цвета. Без ограничения общности мы можем предположить, что по крайней мере три из этих ребер, соединяющих вершину v с вершинами r , s и t , синие. (Если нет, поменяйте местами красный и синий в дальнейшем.) Если какие-либо из ребер ( rs ) , ( rt ) , ( st ) также синие, то у нас есть полностью синий треугольник. Если нет, то все эти три края красные, и мы имеем полностью красный треугольник. Поскольку этот аргумент работает для любой раскраски, любой 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 треугольников в К 6 одноцветные.

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

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

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

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

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

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

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

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

Доказательство [ править ]

2-цветный футляр [ править ]

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

Лемма 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 . Последний случай аналогичен. Таким образом, утверждение верно, и мы завершили доказательство для двух цветов.

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

Доказательство . Предположим, что p = R ( r − 1, s ) и q = R ( r , s − 1) четные. Пусть t = p + q − 1 и рассмотрим двухцветный граф из t вершин. Если d i — степень i -й вершины в синем подграфе, то согласно лемме о рукопожатии , четный. Учитывая, что t нечетное, должно быть четное d i . Предположим, что d 1 четно, M и N — вершины, инцидентные вершине 1 в синем и красном подграфах соответственно. Тогда оба и четные. Согласно принципу Pigeonhole , либо или Поскольку | М | четно, а p – 1 нечетно, первое неравенство можно усилить, так что либо или Предполагать Тогда либо подграф M имеет красный K s и доказательство завершено, либо у него есть синий K r – 1 , который вместе с вершиной 1 образует синий K r . Дело лечится аналогично.

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

Лемма 2. Если c > 2 , то

Доказательство. Рассмотрим полный граф вершины и раскрасьте их края c цветами. Теперь «станьте дальтониками» и представьте, что c − 1 и c — один и тот же цвет. Таким образом, граф теперь ( c − 1) -цветный. В связи с определением граф содержит либо 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 1 , …, конечен для 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 . Такой контрпример называется графом Рамсея . Брендан Маккей ведет список известных графов Рэмси. [5] Верхние оценки зачастую установить значительно сложнее: нужно либо проверить все возможные раскраски, чтобы подтвердить отсутствие контрпримера, либо привести математическое обоснование его отсутствия.

Вычислительная сложность [ править ]

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

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

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

Известные значения [ править ]

Как описано выше, 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 22 разные 2-раскраски 16-узловых графов и только один (4, 4, 17) граф ( граф Пэли порядка 17) среди 2,46 × 10 26 красители. [5] (Это было доказано Эвансом, Пулемом и Шиханом в 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 годов соответственно. [2]

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

Стандартным обзором развития исследований чисел Рамсея является Динамический обзор 1 Электронного журнала комбинаторики Станислава Радзишовского , который периодически обновляется. [2] [14] Если не указано иное, записи в таблице ниже взяты из издания за январь 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 [15]
4 18 25 [10] 36–40 49–58 59 [16] –79 73–106 92–136
5 43–48 59 [17] –85 80–133 101–194 133–282 149 [16] –381
6 102–161 115 [16] –273 134 [16] –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 = s ,

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

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

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

с и где считается, что эти параметры могут быть оптимизированы, в частности .

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

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

Для границы становятся , но препринт 2023 года [25] [26] улучшил нижнюю границу до что решает вопрос об Эрдеше, который предложил 250 долларов за доказательство того, что нижний предел имеет форму . [27] [28]

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

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

Заявление [ править ]

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

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

История и границы [ править ]

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

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

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

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

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

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

Особые случаи [ править ]

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

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

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

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

Обобщения [ править ]

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

Больше цветов [ править ]

Мы также можем обобщить индуцированную теорему Рамсея на многоцветный случай. Для графов H 1 , H 2 , …, H r определите r ind ( H 1 , H 2 , …, 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 . [40]

Гиперграфики [ править ]

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

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

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

Бесконечные графики [ править ]

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

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

Доказательство : Доказательство проводится индукцией по n , размеру подмножеств. Для n = 1 это утверждение эквивалентно утверждению, что если вы разделите бесконечное множество на конечное число множеств, то одно из них будет бесконечным. Это очевидно. Предполагая, что теорема верна для n r , докажем ее для n = r + 1 . Учитывая c -раскраску подмножеств ( r + 1) -элементов X , пусть a 0 будет элементом X и пусть Y = X \ { a 0 }. Затем мы вызываем c -раскраску r -элементов Y , просто добавляя 0 подмножеств к каждому подмножеству r -элемента (чтобы получить ( r + 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 ) , чтобы получить желаемый одноцветный набор.

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

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

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

Для любого k ограничение раскраски Ck в +1 на [ k ] ( н ) (игнорируя цвет всех множеств, содержащих + 1 ) является раскраской в ​​Ck . k Определять быть раскрасками в Ck , которые являются ограничениями раскрасок в Ck 1 + . Поскольку C k +1 не пуст, то и .

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

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

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

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

каждая раскраска в Dk Тогда является ограничением раскраски в Dk 1 + . Следовательно, ограничивая раскраску в D k раскраской в ​​D k +1 и продолжая делать это, можно построить раскраску без какого-либо монохроматического набора размера T . Это противоречит бесконечной теореме Рамсея.

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

Гиперграфики [ править ]

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

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

Ориентированные графы [ править ]

Также возможно определить числа Рамсея для ориентированных графов; они были введены П. Эрдешем и Л. Мозером ( 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 . [47] [48]

Неисчисляемые кардиналы [ править ]

С точки зрения исчисления разделов теорему Рамсея можно сформулировать как для всех конечных n и k . Вацлав Серпинский показал, что теорема Рамсея не распространяется на графы размера показав это . В частности, гипотеза континуума предполагает, что . Стево Тодорчевич что на самом деле в ZFC показал , , гораздо более сильное утверждение, чем . Джастин Т. Мур еще больше укрепил этот результат. С положительной стороны, кардинал Рэмси , , — большой кардинал, аксиоматически определенный для удовлетворения соответствующей формулы: . Существование кардиналов Рэмси не может быть доказано в ZFC.

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

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

См. также [ править ]

Примечания [ править ]

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

Ссылки [ править ]

Внешние ссылки [ править ]

Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: c214e36afbef7c8abab419d9e77bdf2e__1718746620
URL1:https://arc.ask3.ru/arc/aa/c2/2e/c214e36afbef7c8abab419d9e77bdf2e.html
Заголовок, (Title) документа по адресу, URL1:
Ramsey's theorem - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)