Тройки знакомых или незнакомых из шести
Начну с одной популярной школьной задачи. В течение долгого времени я был убежден, что этот факт был известен чуть ли не древним грекам, тогда как на самом деле задача возникла лишь в 1947 году на математической олимпиаде Венгрии. В англоязычной Википедии она гордо именуется «Теоремой о знакомых (друзьях) и незнакомых» (Theorem on Friends and Strangers) а по-русски это просто задача о знакомствах среди шести человек:
Среди шести человек всегда найдется либо трое попарно знакомых, либо трое попарно незнакомых.
Для тех, кто незнаком (прошу извинить за тавтологию) с доказательством:
Пусть А - один из вышеупомянутых шести. Остальные 5 человек разбиваются на две группы: группа знакомых с А и группа незнакомых с А. Согласно принципу Дирихле (он же «принцип ящиков» или «принцип голубиных ячеек») найдется группа, состоящая из не менее 3х человек. (Действительно, если в каждой группе не более двух человек, общее количество человек — не более четырех, тогда как на самом деле их пятеро.) Другими словами, у А либо не менее 3х знакомых, либо не менее 3х незнакомых.
Допустим у А не менее 3-x знакомых. Выберем трех из них и обозначим через B, C и D. Если среди этих трех найдутся двое знакомых друг с другом, например B и C, то A, B, C — тройка попарно знакомых. В противном случае B, C, D — тройка попарно незнакомых.
Случай, когда у А не менее 3х незнакомых симметричен: «знакомство» заменяется «незнакомством» и наоборот.
Этот факт можно перевести на язык графов. Берем граф состоящий из 6 вершин по количеству людей (прекрасный случай, дающий каждому возможность достигнуть заветной вершины!) и соединяем каждую пару вершин ребром зеленого или красного цвета, в зависимости от того знакомы или незнакомы соответствующие этим вершинам люди.
Такой граф является полным (любая пара вершин соединена некоторым ребром) и двухцветным, так что утверждение приобретает следующую формулировку:
Любой полный двухцветный граф из 6 вершин содержит треугольник, ребра которого окрашены одинаковым цветом. Треугольник с ребрами одинакового цвета будем для краткости называть монохроматическим.
Граф, изображенный на рисунке, содержит треугольник ACЕ с ребрами зеленого цвета и треугольник BCD с ребрами красного цвета. Если ребро BD окрасить зеленым цветом, получим еще один зеленореберный треугольник BDF, а краснореберных треугольников не останется.
На самом деле в двухцветном графе из 6 вершин всегда найдется не менее двух монохроматических треугольников (см. например доказательство путем двойного подсчета (double counting)), однако это «о другом».
И еще одно замечание не по теме. В нижеприведенном графе монохроматические треугольники отсутствуют. Заметили, чем это вызвано?
Разумеется, дело в отсутствии ребра AD. Если добавить ребро AD зеленого цвета получим два зеленореберных треугольника ACD и AED, тогда как ребро AD красного цвета дает два краснореберных треугольника ABD и AFD. Это показывает существенность требования полноты графа.
Минимальность 6-вершинного графа
Понятно, что если полный двухцветный граф содержит более 6 вершин, выделяем в нем полный подграф, в котором, как мы уже знаем обязательно найдется монохроматической треугольник, который также является треугольником исходного графа.
А если в графе только 5 вершин, всегда ли в нем найдется треугольник с ребрами одного цвета? Оказывается нет. В качестве примера достаточно рассмотреть пятиугольник, в котором стороны окрашены одним цветом, а диагонали — другим.
Поскольку никакие три стороны, а также никакие три диагонали не образуют треугольник, в таком графе отсутствует монохроматический треугольник.
Числа Рамсея
Поставим вопрос в общем виде. Для этого заметим, что на языке графов треугольник — это полный граф из 3х вершин. Таким образом в общем виде задача выглядит следующим образом:
Для заданных натуральных чисел m и n, определить наименьшее число вершин полного двухцветного (напр. зелено-красного) графа, при котором всегда существует либо полный подграф из m вершин, все ребра которого окрашены первым (зеленым) цветом, либо полный подграф из n вершин, все ребра которого окрашены вторым (красным) цветом.
Или на «языке знакомств»:
Для заданных натуральных чисел m и n, определить наименьшее количество людей, среди которых всегда найдутся либо m попарно знакомых, либо n попарно незнакомых.
Такое число обозначается через R(m, n) и называется числом Рамсея по имени британского философа, математика и экономиста, преподавателя Кембриджского университета, Фрэнка Рамсея (Frank P. Ramsey, 22.02.1903 – 19.01.1930).
Из вышесказанного следует, что R(3,3) = 6. В этом случае, m=n=3, хотя значения m и n могут быть различными.
Например, R(4,3)=9. то есть в зелено-красном графе из 9 ребер всегда найдется либо полный 4-вершинный зеленореберный граф, либо полный 3-вершинный краснореберный граф. На «языке знакомств» это означает следующее: «В любой группе из 9 человек найдется либо 4 попарно знакомых, либо 3 попарно незнакомых.» При этом 9 — наименьшее число, обладающее таким свойством.
Доказательство того, что девяти вершин достаточно приводится ниже, зато для доказательства минимальности достаточно привести контрпример, называемый графом Рамсея. Вот он:
Граф содержит 8 вершин. При этом в некоторых треугольниках (напр. ACF, ADF, ADG, BDG, BEG, BEH) все три ребра зеленого цвета, тогда как во всяком подмножестве из четырех вершин обязательно найдутся две вершины, соединенные красным ребром. В то же время граф не содержит ни одного краснореберного треугольника.
Свойства чисел Рамсея
Начнем с вполне очевидных свойств
1. Порядок аргументов не имеет значения: R(m, n) = R(n, m)
Ввиду того, что граф можно перекрасить: назвать первый цвет вторым, а второй — первым.
2. R(1, n) = R(n, 1) = 1 для любого натурального n.
Поскольку граф из одной вершины не содержит ребер, его можно считать полным подграфом любого цвета. (Не зря ведь философы утверждают, что из лжи следует всё что угодно.) Поэтому в 1-вершинном графе, всегда найдется 1-вершинный подграф (это весь граф целиком) первого цвета, так что до второго цвета дело никогда не доходит. Впрочем, некоторые источники настаивают на том, что аргументы числа Рамсея должны быть не меньше 2.
3. R(2, n) = R(n, 2) = n для любого натурального n.
При n=1 это следует из свойства 1. Поэтому будем рассматривать n⩾2. Возьмем произвольный зелено-красный граф из n вершин. Если в нем есть зеленое ребро — получили полный зеленоберный граф из двух вершин. Если все ребра красные — весь граф является полным m-вершинным графом с ребрами красного цвета. Таким образом R(2, m)⩽m. С другой стороны, если количество вершин графа меньше m и все его ребра — красные, то при всем старании мы никак не получим ни двухвершинный зеленореберный граф, ни m-вершинный краснореберный граф, чем доказывается минимальность m, т.е. R(2, m)⩾m.
Перейдем к менее очевидным свойствам чисел Рамсея.
4. Теорема Рамсея: Если m⩾2 и n⩾2, тo
R(m, n) ⩽ R(m−1, n) + R(m, n−1).
Это утверждение называют теоремой (иногда леммой) Рамсея ввиду того, что статья F.P.Ramsey. "On a Problem of Formal Logic", написанная в 1928 году и опубликованная в "Proceedings of the London Mathematical Society" уже после смерти автора в 1930 году, содержит утверждение, равносильное вышеприведенному неравенству.
На самом деле в статье Рамсея не упоминаются ни графы, ни раскраски, да и само неравенство в «привычном виде» не появляется. Современную интерпретацию теоремы Рамсея дал венгерский математик Пауль (Пал) Эрдёш (Paul/Pál Erdős, 26.03.1913 – 20.09.1996), который доказал ряд основополагающих свойств чисел Рамсея и высказал гипотезы, некоторые из которых были впоследствии доказаны.
Нижеследующее доказательство тeоремы Рамсея использует тот же подход, что и в доказательстве для 6 человек (6 вершин графа).
Доказательство теоремы Рамсея.
Если m=2 или n=2, неравенство (которое в этом случае становится равенством) следует непосредственно из свойств 2 и 3. Поэтому будем считать, что m>2 и n>2.
Рассмотрим группу из R(m−1,n)+R(m,n−1) человек, и покажем, что в ней есть либо m попарно знакомых, либо n попарно незнакомых.
Пусть А — один из членов группы. Обозначим через r и s количество людей, знакомых и незнакомых с A соответственно. Тогда сумма r+s равна количеству человек группы, кроме A:
r + s = R(m−1,n) + R(m,n−1)−1
Согласно всё тому же принципу Дирихле (хотя и в слегка измененной формулировке), одно из нижеследующих неравенств должно иметь место:
r ⩾ R(m−1,n)
s ⩾ R(m,n−1)
(В противном случае имеют место оба неравенства: r⩽R(m−1,n) −1 и s⩽R(m−1,n)−1, суммируя которые получаем r+s⩽R(m−1,n)+R(m,n−1)−2, что противоречит предыдущему равенству.)
Пусть имеет место первое неравенство: r⩾R(m−1,n) и
P — множество людей знакомых с A. В в этом множестве не менее R(m−1,n) человек, следовательно, согласно определению числа Рамсея, возможно одно из двух:
— в P существует m−1 попарно знакомых, которые вместе с A образуют m попарно знакомых, что удовлетворяет определению R(m,n);
— в P существует n попарно незнакомых, что также удовлетворяет определению R(m,n)
Случай, когда имеет место второе неравенство симметричен.
Как видим, теорема Рамсея дает верхнюю границу, а не точное значение числа. Если удастся найти контрпример, то есть граф Рамсея для числа, на единицу меньшего вычисленной оценки, то всё в порядке. А если нет?.. К счастью, для решения задач наподобие «задачи о шести» верхней оценки вполне достаточно, а выяснение того, является ли это оценка точной — вопрос чистого любопытства. Беда математиков лишь в том, что большинство из них не лишено любопытства.
Известны случаи, когда теорема Рамсея дает завышенную оценку. Например, если слагаемые R(m-1, n) и R(m, n-1) оба четны, неравенство можно усилить, уменьшив верхнюю оценку на единицу.
5. Если m⩾2, n⩾2, причем R(m−1, n) и R(m, n−1) оба четны, тo R(m, n) ⩽ R(m−1, n) + R(m, n−1) − 1.
Доказательство.
И здесь можно считать, что m>2 и n>2, так как если m=1, то R(m−1, n) = R(1, n) = 1 нечетно, а если n=1, то R(m, n−1) = 1 нечетно.
В этот раз уменьшим размер группы на единицу, т.е. будем рассматривать группу из p = R(m−1, n)+R(m, n−1)−1 человек. Заметим, что поскольку R(m−1, n) и R(m, n−1) оба четны, размер группы число p нечетно. Если в предыдущем случае представитель A выбирался произвольно, то теперь это будем делать боллее тщательно.
Пронумеруем всех членов группы числами от 1 до p и пусть cᵢ — количество знакомых i-го участника группы. Поскольку каждое знакомство учитывается с двух сторон, сумма всеx cᵢ, т.е. S=c₁+c₂+...+c_p в два раза больше общего количества знакомств (т.е. количества ребер графа первого цвета). Поскольку сумма S четна, а количество слагаемых p нечетно, в сумме обязано присутствовать четное слагаемое c_k.
Пусть А — участник группы с номером k. А имеет r=c_k знакомых, и это число четно. Количество незнакомых A составляет s=p-r-1, что также четно, поскольку p нечетно, а r четно. Снова применяем принцип Дирихле и находим, что одно из нижеследующих неравенств должно иметь место:
r ⩾ R(m−1,n)−1
s ⩾ R(m,n−1)
Но r четно, тогда как R(m−1,n)−1 нечетно. Это означает, что первое неравенство не может обращаться в равенство, так что его можно усилить:
r ⩾ R(m−1,n)
s ⩾ R(m,n−1)
Итак, несмотря на то, что размер группы уменьшился, получили точно такие же неравенства, как и в предыдущем доказательстве. Поэтому мы можем завершить доказательство ранее продемонстрированным методом, подтвердив усиленное неравенство.
Из теоремы Рамсея вытекает следующее неравенство:
6. R(m, n) ⩽ C(m+n−2, m−1).
Здесь C(p, q) — количество сочетаний из p элементов по q, известное также под названием биномиальный коэффициент: C(p, q) = n×(n−1)×...×(n-k+1)/(1×2×...×k).
Заметим, что из известного свойства биномиальных коэффициентов
C(p, q)=C(p, p-q) следует C(m+n−2, m−1) = C(m+n−2, n−1), так что на самом деле неравенство симметрично относительно m и n.
Доказательство неравенства.
Докажем индукцией по сумме m+n. Если m+n=2, это возможно только при m=n=1. В таком случае C(m+n−2, m−1)= C(0, 0) = 1 = R(1,1). Для тех, кто решительно против использования единицы в качестве аргумента чисел Pамсея, заметим, что при m=n=2, C(m+n−2, m−1) = C(2, 1)=2=R(2, 2). Как видим, в обоих тривиальных случаях неравенство обращается в равенство, однако в общем случае это не всегда верно.
Пусть доказываемое неравенство имеет место при m+n=k. Покажем, что оно останется верным при m+n=k+1. Возьмем произвольную пару натуральных m и n, для которых m+n=k+1. Согласно теореме Рамсея,
R(m, n) ⩽ R(m−1, n) + R(m, n−1)
В каждом из слагаемых правой части сумма аргументов равна k, поэтому к ним применимо индукционное предположение. Получаем:
R(m, n) ⩽ C(m+n−3, m−2) + C(m+n−3, m−1)
Осталось применить к правой части хорошо известное тождество Паскаля C(p, q) = C(p−1, q) + C(p−1, q−1) (см. напр, Тождество (правило) Паскаля в Википедии) для получения того, что требуется для завершения доказательства.
Получены также нижние оценки чисел Рамсея, среди которых неравенство Эрдеша (1947 год) для чисел Рамсея с равными аргументами:
7. R (n, n) > (n/e√2) × 2^(n/2).
Существование чисел Рамсея. Игра Рамсея
Важным следствием теоремы Рамсея является существование чисел Рамсея.
Для любой пары натуральных чисел m и n число Рамсея R(m, n) существует и конечно.
На этом построена игра Рамсея, предложенная в 1973 году (Erdős P. Selfridge J. L. "On a combinatorial game" Journal of Combinatorial Theory. Series A. 14 (3): 298–301, 1973), называемая также Clique game, поскольку слово «клика» (англ. clique) среди прочего применяется также к полному подграфу.
Суть игры состоит в следующем:
Берется граф из n вершин, в котором каждый игрок по очереди выбирает еще не выбранное ребро (или окрашивает его в свой цвет). Тот кто сможет первым получить полный подграф из «своих» ребер (ребер своего цвета) содержащий заранее заданное количество вершин k, выигрывает. Игра заканчивается вничью, когда все ребра выбраны.
Альтернативные варианты: Maker-Breaker: если все ребра выбраны, выигрывает второй игрок; Avoider-Enforcer: игрок, получивший полный подграф проигрывает; если все ребра выбраны, выигрывает второй игрок.
В исходном варианте, предложенном авторами статьи об игре и допускающем ничью (его именуют strong positional variant), ничья невозможна, если n⩾R(k, k). Это было бы прекрасно, если бы не один нюанс. Своим первым ходом начинающий может выбрать ребро, симметричное себе, а затем «красть стратегию» второго игрока, делая симметричные ходы, обеспечив тем самым либо собственный выигрыш, либо в худшем случае (при n<R(k, k)) ничью. Например, в «классическом» случае n=6, k=3 (см. вышеприведенный рисунок 6-вершинного графа) своим первым ходом начинающий может выбрать ребро, соединяющее протовоположные верчины шестиугольника, например AD, а затем повторять ходы соперника симметрично относительно центра шестиугольника: AE–BD, AF–CD и т. д.
По этой причине предпочтение отдается альтернативным вариантам, где, однако, второй игрок зачастую получает преимуществo. Как указано в Википедии, в варианте Maker-Breaker у начинающего есть выигрышная стратегия при k⩽log₂(n)/2, тогда как второй игрок выигрывает при k⩾log₂(n). Что касается варианта Avoider-Enforcer, то здесь второй находится во всяком случае не в худшем положении по сравнению с Maker-Breaker.
Вариант Avoider-Enforcer с n=6 и k=3 называется игрой Сим и был предложен американским криптографом Г. Симмонсом еще в 1969 году (Simmons, Gustavus J. "The game of SIM," Journal of Recreational Mathematics, 2(2), 1969, стр. 66.), Хотя log₂ 6 меньше log₂ 8 = 3 (то есть k), как показали компьютерные исследования, в игре Сим второму игроку тем не менее выигрыш гарантирован, если, конечно следовать определенной стратегии.
Известные и неизвестные значения чисел Рамсея
Если верить все той же Википедии (как ни надоело ее цитировать, хотим мы это признавать или нет, Википедия — главный источник знаний интеллигенции XXI века!), Пауль Эрдеш говорил о том, что если Землю посетят воинствующие инопланетяне и, под угрозой уничтожения планеты, потребуют указать значение R(5 ,5), следует мобилизовать все имеющиеся компьютеры для нахождения этого значения; если же инопланетяне потребуют значение R(6, 6), землянам придется уничтожить незваных пришельцев.
К сожалению, в настоящее время человечество гораздо ближе к самоуничтожению, чем к уничтожению инопланетянами, но это (уже к счастью) снова «о другом». Что же касается чисел Рамсея, то неужели пессимизм Эрдеша столь оправдан? Чего стоит компьютеру перебрать всевозможные двухцветные раскраски заданного графа и либо найти контрпример, либо, не найдя его, тем самым убедить всех в том, что количество вершин графа и есть то, что так настойчиво желали узнать грозные инопланетяне? Постараемся в этом разобраться.
Каждый полный граф из n вершин содержит C(n, 2) = n(n–1)/2 ребер. Каждой зелено-красной раскраске графа можно поставить во взаимно-однозначное соответствие множество зеленых ребер. Выходит, что количество всевозможных раскрасок — это количество подмножеств множества ребер, то есть 2^[n(n-1)/2]. Заметим, что значение R(5,5) даже по самым аккуратным оценкам не меньше 43. Количество ребер 43-вершинного графа равно (43×42)/2=903, так что количество всевозможных раскрасок равно 2⁹⁰³, что является 272-значным числом в десятичной записи, вообразить которое способен разве что Wolfram Alpha, но уж никак не гости оттуда, какими бы продвинутыми они ни были. Перебирая такое количество раскрасок, даже современный многоядерный процессор способен расплавиться от столь напряженной работы, не дожив до весьма почтенного даже для процессора возраста, необходимого для завершения просмотра.
Правда все раскраски проверять нет смысла, поскольку в силу симметрии, достаточно ограничиться теми, в которых количество зеленых ребер меньше количества красных, а кроме того если некоторый граф содержит полный зеленый подграф из 5 вершин, наращивать «зеленку» за счет перекрашивания красных ребер также необязательно. Кроме того, не следует забывать о человеческой сплоченности и изобретательности, над чем безжалостное время не властно.
И хотя точное значение R(5,5) (не говоря уж об R(6,6)) до сих пор не найдено (известно лишь что 43⩽R(5,5)⩽48 и 102⩽R(6,6)⩽161), то что нам известно дает повод для оптимизма. Поговорим же об известных значениях чисел Рамсея.
Мы уже знаем, что R(n,2)=n для любого натурального n, а также R(3,3)=6. Кроме того, ранее был показан граф Рамсея из 8 вершин, показывающий, что R(4, 3) (а заодно и R(3,4)) не может быть меньше 9: R(4,3)⩾9. Докажем, что R(4,3) в точности равно 9. Согласно теореме Рамсея (свойство 4):
R(4,3) ⩽ R(3,3) + R(4,2) = 6 + 4 = 10
Увы, хотели 9, а получили 10. Но погодите! Ведь R(3,3)=6 и R(4,2)=4 — четные числа, значит теорему Рамсея можно усилить, уменьшив верхнюю оценку на единицу (свойство 5). Таким образом R(4,3)⩽9, что учитывая ранее приведенный контрпример, дает R(4,3)=R(3,4)=9.
А как насчет R(4,4)? Это ведь совсем близко к R(5,5)! Все-таки попробуем, ведь терять нечего. Снова применяем теорему Рамсея:
R(4,4) ⩽ R(4,3) + R(3,4) = 9 + 9 = 18
Теперь слагаемые — нечетные числа, так что усилить неравенство не получится. Придется искать граф Рамсея из 17 вершин. К счастью, однако, в этом нет необходимости, так как такой граф уже найден (авторы: Noga Alon & Michael Krivelevich, опубликовано в The Princeton Companion to Mathematics, 2008, стр.265, см. Cut the knot. Ramsey's number R(4,4)) . Для большей наглядности показываю как граф целиком, так и отдельно зеленые и красные подграфы.
Итак, R(4, 4) = 18.
Пойдем дальше и постараемся найти R(5,3), что уж буквально в 2х шагах от R(5.5). Снова применяем многократно испытанное неравенство:
R(5,3) ⩽ R(5,2) + R(4,3) = 5 + 9 = 14
Осталось найти контрпример с 13 вершинами. И он также есть! (Cut the knot. Ramsey's number R(5, 3)).
Таким образом, точное значение R(5, 3) также известно: R(5,3) = 14.
В отношении R(5,4) теорема Рамсея дает R(5,4) ⩽ R(4,4) + R(5,3) = 18+14=32, где верхнюю границу можно уменьшить на единицу и получить R(5,4) ⩽ 31. Однако еще в 1965 году, было обнаружено что такая оценка является завышенной и 25⩽R(5,4)⩽ 30 (J. G. Kalbfleisch, Construction of special edge-chromatic graphs, Canadian Math. Bulletin, 8 (1965) , стр. 575–584). В дальнейшем промежуток значений R(5,4) неоднократно сужался, и окончательная точка была поставлена в 1995 году, когда было доказано, что R(5,4) = 25 (Brendan D. McKay, Stanisław P. Radziszowski (1997). "Subgraph Counting Identities and Ramsey Numbers" Journal of Combinatorial Theory. Series B. 69 (2), стр. 193–209).
Итак, лишь один шаг остался от раскрытия тайны R(5, 5). И хотя этот шаг затянулся уже на 28 лет, будем надеяться, эта тайна скоро будет раскрыта.
Увеличение цветовой палитры
Двухцветная раскраска сродни черно-белому изображению, тогда как современная жизнь красочна и многообразна. В таком случае почему бы не употребить дополнительные цвета?! При этом количество аргументов числа Рамсея увеличивается, придавая ему следующий вид: R(n₁, n₂, ... nₓ), где x – количество цветов раскраски. (На самом деле вместо x следовало использовать c, но технические трудности это не позволили сделать.) Таким образом
R(n₁, n₂, ... nₓ) — наименьшее количество вершин x-цветного графа, при котором всегда найдется некоторый цвет i, для которого существует полный подграф из nᵢ вершин, все ребра которого окрашены в цвет i.
Но как же быть со знакомствами, которые позволяют только «да» или «нет»? Придется заменить знакомства обсуждением некоторых тем, которые можно выбрать в таком количестве, какое потребуется, благо в современном обществе новые темы для обсуждения возникают чуть ли не каждый день. В такой формулировке определение числа Рамсея выглядит следующим образом:
R(n₁, n₂, ... nₓ) — наименьшее количество людей в группе, где каждые двое обсуждают одну и только одну из x тем, при котором всегда найдется некоторая тема i, для которой существует подгруппа из nᵢ человек, все участники которой попарно обсуждают эту тему.
Отметим некоторые свойства многоцветных раскрасок, аналогичные двухцветным,
1m. Порядок аргументов не имеет значения
Так как и в этом случае граф можно перекрасить как угодно
2m. R(1, n₂, ..., nₓ) = 1 для любых натуральных значений n₂, ... nₓ.
Поскольку и в этом случае ничего не мешает приписать 1-вершинному графу любой цвет.
3m. R(2, n₂, ..., nₓ) = R(n₂, ..., nₓ) для любых натуральных значений n₂, ... nₓ.
Если одно из n₂, ... nₓ, равно 1, то из свойств 1m и 2m следует, что R(2, n₂, ..., nₓ) = R(n₂, ..., nₓ) = 1. Пусть каждое из чисел n₂, ... nₓ не меньше 2. Если в графе есть ребро 1-го цвета, получили полный граф 1-го цвета из двух вершин. Если ребра 1-го цветa отсутствуют, число Рамсея этого графа есть число Рамсея для оставшихся x−1 цветов, то есть R(n₂, ..., nₓ).
В частности, R(2,3,3) = R(3,3) = 6, R(2,3,4) = R(3,4) = 9 и т.д., а кроме того, применяя последовательно свойство 3m, находим что R(2, 2, ..., 2, n) = n.
4m. R(n₁, n₂, ..., nₓ) ⩽ R(n₁, n₂, ..., nₓ₋₂, R(nₓ₋₁, nₓ))
Доказательство.
Рассмотрим граф из R(n₁, n₂, ..., nₓ₋₂, R(nₓ₋₁, nₓ)) вершин и покажем, что в нем обязательно найдется полный подграф с ребрами некоторого цвета i из nᵢ вершин.
Для этого объединим последние два цвета, x−1 и x в один цвет. При этом граф станет (x−1)-цветным, и согласно определению числа Рассела R(n₁, n₂, ..., nₓ₋₂, R(nₓ₋₁, nₓ)), в нем обнаружится либо полный nᵢ-вершинный подграф с ребрами цвета i, меньшего x−1, либо полный подграф из R(nₓ₋₁, nₓ) вершин с ребрами объединенного цвета.
В случае i < x−1 полученный подграф удовлетворяет определению R(n₁, n₂, ..., nₓ). В случае объединенного цвета, в полученном полном подграфе вернем каждому ребру исходный цвет. Согласно определению R(nₓ₋₁, nₓ), в подграфе существует либо полный подграф из nₓ₋₁ вершин с ребрами цвета x−1, либо полный подграф из nₓ вершин с ребрами цвета x. Найденный таким путем подграф является также подграфом исходного графа и удовлетворяет определению R(n₁, n₂, ..., nₓ).
Свойство 4m часто называют теоремой Рамсея для 3x и более цветов, хотя единственное, в чем свойства 4 и 4m сходны — это наличие неравенства вместо равенства.
Есть однако еще одна аналогия между теоремами Рамсея для двух и более цветов. Вспомним, что из «двухцветной» теоремы Рамсея следует сущест-вование и конечность числа Рамсея для любой пары натуральных чисел. На основании этого, применяя последовательно свойство 4m, можно доказать существование и конечность числа Рамсея для любого количества цветов.
Числа Рамсея для раскраски, содержащей более двух цветов
Наименьшее число Рамсея для более чем двухцветной раскраски, значение которого нельзя определить, используя свойства 2m и 3m — это конечно R(3, 3, 3). Дoкажем, что R(3,3,3) = 17.
Вначале покажем, что 17 вершин достаточно, то есть R(3,3,3) ⩽ 17
Рассмотрим группу из 17 человек, где каждые двое обсуждают одну из трех тем. Обозначим через А произвольного участника этой группы. С каждым из остальных 16 участников он обсуждает одну из 3х тем. Согласно принципу ... угадайте какому, существует тема, которую А обсуждает с не менее чем 6 участниками. Назовем ее темой 1 и обозначим 6 участников, обсуждающих тему 1 с А, через B, C, D, E, F, G. Если среди эти шести найдутся двое, например B и C, обсуждающие тему 1 друг с другом, тройка A, B, C образует требуемую подгруппу. Если никакие двое из B, C, D, E, F, G не обсуждают тему 1 попарно, мы нашли подгруппу из 6 человек, обсуждающих только две темы. Назвав одну из них знакомствами, а другую — незнакомствами. приходим к классической «задаче из шести», где, как мы убедились, существует либо тройка попарно знакомых (т.е обсуждающих тему 2), либо тройка попарно незнакомых (т.е. увлеченных темой 3).
Для завершения доказательства осталось нарисовать трехцветный граф из 16 вершин, не содержащий монохроматических треугольников, тем самым доказывающий, что R(3,3,3) ⩾ 17. Здесь я нарисовать поленился, а просто приведу рисунок из ... угадайте откуда (автор Maproom):
Как видите, каждая вершина графа соединена с другими 15 вершинами ровно пятью ребрами каждого цвета.
В статье Stanisław Radziszowski. "Small Ramsey Numbers". Dynamic Surveys. Electronic Journal of Combinatorics, 2021, стр. 42, 43 упоминается значение R(3, 3, 4) = 30, полученное в 2016 году не без участия компьютера. В этой же публикации даются оценки сверху для большего количества цветов, напр. 51 ⩽ R(3, 3, 3, 3) ⩽ 62, 97⩽ R(3, 3, 3, 4) ⩽ 149, 162 ⩽ R(3, 3, 3, 3, 3) ⩽ 307. Пишу об этом потому что информация о значениях чисел Рамсея для более трех раскрасок в Википедии в настоящее время отсутствует, однако исследования в этой области, как видите, проводятся.
Осторожно на бесконечности!
Граф из бесконечного количества вершин? Кажется немыслимым, но нет ничего невозможного в математике! Попробуем так, как это сделано здесь, доказать следующее утверждение, именуемое автором «теоремой Рамсея для бесконечного графа» ("Infinite Ramsey Theorem"):
При любой двухцветной (на самом деле рассуждения автора применимы к любому конечному количеству цветов) раскраске ребер бесконечного графа, всегда найдется бесконечное количество точек, соединенных одинаковым цветом.
Или в переводе на более привычный язык:
Любой полный граф с бесконечным количеством вершин и ребрами окрашенными в конечное количество цветов содержит полный монохроматический подграф из бесконечного количества вершин.
Вот какое доказательство предлагает автор упомянутой статьи:
Выберем произвольную вершину V₁. Поскольку она соединена ребрами со всеми остальными вершинами, исходящих из нее ребер — бесконечное количество. Ввиду конечности количества цветов найдется цвет c₁, которым окрашено бесконечное количество исходящих ребер. (Соответствующее свойство иногда именуется «принципом Дирихле на бесконечности», англ. "Infinite pigeonhole principle".) Окрасим саму вершину V₁ в цвет c₁ и удалим все исходящие ребра других цветов вместе с вершинами, к которым они приходят. Ввиду бесконечного количества ребер цвета c₁ количество оставшихся (неудаленных) вершин также бесконечно, причем теперь из вершины V₁ исходят только ребра цвета c₁.
Из оставшихся вершин выберем вершину V₂, отличную от V₁. Так как она соединена со всеми другими оставшимися вершинами, исходящих из нее ребер снова бесконечное количество. Поэтому снова найдется цвет c₂ (возможно отличный от c₁), которым окрашено бесконечное количество исходящих из V₂ ребер. Окрасим вершину V₂ в цвет c₂ и снова удалим «нерелевантные» ребра заодно с соответствующими вершинами.
Снова остается бесконечное количество вершин, причем из вершин V₁ и V₂ исходят только ребра своего цвета. Выбираем вершину V₃, отличную от V₁ и V₂ и продолжаем процесс.
По завершении процесса (чего на самом деле никогда не произойдет, ввиду его бесконечности, но будем мыслить сюрреалистически) останется бесконечное количество вершин, окрашенных в конечное количество цветов. Поэтому существует цвет c₀, которым окрашено бесконечное количество вершин. Оставим только вершины этого цвета, а все остальные вершины удалим.
Итак, остались только вершины цвета c₀. Их бесконечное количество, причем из них исходят только ребра цвета c₀. Это означает, что ребер другого цвета не осталось, так что полученный граф является монохроматическим и содержит бесконечное количество вершин.
Есть вопросы к доказательству? У меня есть. Bo-первых, доказательство предполагает, что вершины графа можно пронумеровать, то есть поставить во взаимно-однозначное соответствие с рядом натуральных чисел, что однако не дано. Правда такой промах легко «залатать». В случае когда количество вершин графа несчетно, то есть не сопоставимо с натуральным рядом, достаточно выделить подграф, содержащий по-прежнему бесконечное, но счетное количество вершин и, применив к нему вышеприведенные рассуждения, получить требуемый монохроматический подграф, который будет также подграфом исходного графа.
Однако есть другая проблема, выхода из которой не видно: где гарантия, что в результате бесконечного повторения процесса «чистки» графа в нем останется бесконечное количество вершин? Для автора это очевидно, но так ли это? В качестве примера возьмем натуральный ряд чисел и будем из него поочередно удалять наименьшее оставшееся число, сначала 1, потом 2 и т. д. При каждом таком удалении количество оставшихся чисел бесконечно, но по завершении процесса (если снова мыслить сюрреалистически) от ряда ничего не останется! Это показывает, как бережно следует обращаться с бесконечностью.
К счастью, более надежные источники, такие как Википедия и ProofWiki не допускают подобных промахов. Кроме того, упомянутые источники формулируют утверждение в более общем виде примерно так:
Для заданного n окрасим каждое n-элементное подмножество бесконечного множества S конечным количеством цветов. Тогда в S существует бесконечное подмножество M, все n-элементные подмножества которого окрашены одинаковым цветом.
Первая мысль, которая меня посетила по прочтению подобного: «А какое это имеет отношение к теме?» Постараюсь объяснить, насколько я это понимаю. Поскольку ребро графа соединяет две вершины, его можно рассматривать, как 2-элементное подмножество множества вершин графа. В таком случае цвет 2-элементного подмножества — это цвет ребра. При этом множество 2-элементных подмножеств некоторого подмножества M есть множество ребер полного подграфа с вершинами из М. А то, что все 2-элементные подмножества из M окрашены одинаковым цветом означает, что полный подграф с вершинами из M является монохроматическим. Итак, то, что столь усердно пытался доказать автор вышеупомянутой статьи, есть всего лишь частный случай последнего утверждения, соответствующий n=2.
Иногда однако оказывается, что общий случай доказать не сложнее, чем частный. Покажем, как это сделать.
Доказательство.
Применим метод математической индукции. При n=1 имеем одноэлементные подмножества, окрашенные конечным количеством цветов. Поскольку таких подмножеств бесконечное количество, обязан существовать цвет c₀, которым окрашено бесконечное количество подмножеств. Так как одноэлементные подмножества попарно не пересекаются, объединение подмножеств цвета c₀ даст необходимое бесконечное подмножество M.
Пусть утверждение имеет место при n=k. Возьмем произвольную раскраску (k+1) - элементных подмножеств множества S и покажем, что в S найдется бесконечное подмножество, все (k+1) - элементные подмножества которого окрашены одинаковым цветом.
Для этого выберем в S произвольный элемент а₁, и рассмотрим бесконечное множество Т₁, полученное удалением из S элемента а₁: Т₁ = S∖{а₁}. Подмножества из Т₁ пока не окрашены, так окрасим все k-элементные подмножества множества Т₁ следующим методом: добавляя к а₁ некоторому k-элементному подмножеству множества Т₁ получаем (k+1)-элементное подмножество множества S, которое имеет цвет, и применим этот цвет к выбранному подмножеству из Т₁.
Согласно индукционному предположению, в Т₁ существует бесконечное подмножество U₁, все k-элементные подмножества которого окрашены одинаковым цветом c₁. Добавляя а₁ к каждому такому подмножеству, получим (k+1)-элементные подмножества из S, каждый из которых окрашен цветом c₁.
Однако это не конец доказательства. Ведь одинаковый цвет есть только у подмножеств, содержащих а₁, тогда как требуется, чтобы все подмножества выбранного множества имели необходимый цвет. Так что двигаемся дальше.
Выберем в U₁ произвольный элемент а₂, удалим а₂ из U₁ и получим T₂=U₁∖{а₂}. Окрасим каждое k-элементное подмножество из Т₂ тем же цветом, что и (k+1)-элементное подмножество из S, полученное добавлением а₂. Снова применяем индукционное предположение и убеждаемся в существовании подмножества U₂ ⊂ Т₂, все k-элементные подмножества которого окрашены в цвет c₂, так что добавляя а₂ к каждому из таковых, получаем (k+1)–элементное подмножество из S цвета c₂.
Повторяя процесс, приходим к бесконечной последовательности различных элементов а₁, а₂, а₃, ..., принадлежащих соответственно множествам Т₁, Т₂, Т₃, ... . При этом, поскольку S⊃Т₁⊃Т₂⊃Т₃⊃... каждый из аᵢ принадлежит не только Тᵢ но и всем T с индексами меньшими i.
Пусть N — множество всех аᵢ: N = {а₁, а₂, а₃, ...}.
Очевидно N — подмножество S. Кроме того, из процесса нахождения аᵢ следует, что каждое (k+1) – элементное подмножество из N, содержащее а₁, имеет цвет c₁; каждое (k+1) - элементное подмножество из N, содержащее а₂, но не а₁ окрашено в цвет c₂; каждое (k+1) – элементное подмножество из N, содержащее а₃, но не а₁ или а₂, окрашено в в цвет c₃; и.т.д.
Поскольку количество цветов конечно, тогда как количество аᵢ бесконечно и все они различны, существует цвет c₀, относящийся к бесконечному количеству элементов из Nᵢ. Оставим во множестве N только элементы, соответствующие этому цвету. Полученное бесконечное множество M является подмножеством S, причем все (k+1) - элементные подмножества из M окрашены в цвет c₀. Это завершает индукционный переход и доказательство утверждения.
Как видим доказательство по сути основано на той же идее, что и предыдущее, с той лишь разницей, что здесь придраться не к чему.
Наконец-то ...
Не, не всё!
Тех, кому это понравилось, приглашаю прочитать мою публикацию «Разложим по полочкам!» o разных интерпретациях Признака Дирихле, и его различных приложениях. Упоминаются также числа Рассела. Статья дополнена общирным количеством задач, простых и не очень, однако ко всем даются решения.
Добро пожаловать:
https://mdgmath.blogspot.com/2018/01/blog-post_27.html
Вот теперь