#6 Идеи Рамсея

Если красных рёбер не больше \(2\) и синих рёбер не больше \(2\), то всего рёбер не больше \(4\). Но их \(5\). Значит, хотя бы один цвет встречается не менее \(3\) раз.

У треугольника \(3\) ребра и только \(2\) цвета. По принципу Дирихле два ребра имеют один цвет.

Выберем вершину \(v\). Из неё выходят \(3\) ребра двух цветов. По принципу Дирихле два из них одного цвета, скажем \(va\) и \(vb\).

Тогда \(a-v-b\) — путь из двух рёбер одного цвета.

Расположим вершины как правильный пятиугольник. Пять сторон покрасим в красный цвет, пять диагоналей — в синий.

Красный граф является циклом длины \(5\), поэтому красного треугольника нет. Синий граф тоже является циклом длины \(5\), поэтому синего треугольника нет.

Если красных рёбер не больше \(m-1\) и синих не больше \(m-1\), то всего рёбер не больше \(2m-2\). Но рёбер \(2m-1\). Значит, один цвет встречается хотя бы \(m\) раз.

Выберем вершину \(v\). Из неё выходит \(5\) рёбер, поэтому хотя бы \(3\) из них одного цвета. Пусть это красные рёбра к вершинам \(a,b,c\).

Если хотя бы одно из рёбер \(ab,bc,ca\) красное, то вместе с \(v\) оно образует красный треугольник. Если ни одно из этих рёбер не красное, то все они синие, и вершины \(a,b,c\) образуют синий треугольник.

Построим граф на \(6\) вершинах: вершины — люди. Ребро красное, если люди знакомы, и синее, если не знакомы.

По задаче о \(K_6\) в такой раскраске есть одноцветный треугольник. Красный треугольник означает \(3\) попарно знакомых людей, синий — \(3\) попарно незнакомых.

Из задачи о \(K_6\) следует, что при \(6\) вершинах одноцветный треугольник неизбежен, значит, \(R(3,3)\le6\).

С другой стороны, рёбра \(K_5\) можно раскрасить так: стороны пятиугольника красные, диагонали синие. Тогда каждый цвет образует цикл длины \(5\), и одноцветного треугольника нет. Значит, \(R(3,3)>5\).

Итак, \(R(3,3)=6\).

Возьмём вершину \(v\). Если из неё выходят три красных ребра к \(a,b,c\), то среди \(a,b,c\) не может быть красного ребра, иначе возникнет красный треугольник с \(v\). Значит, все рёбра между \(a,b,c\) синие, и получается синий треугольник. Противоречие.

Следовательно, красная степень любой вершины не больше \(2\). Аналогично синяя степень не больше \(2\). Но всего из вершины выходит \(n-1\) рёбер, значит, \(n-1\le4\), откуда \(n\le5\).

Из любой вершины выходит \(2m-1\) рёбер. По усиленному принципу Дирихле среди этих рёбер есть хотя бы \(m\) рёбер одного цвета. Поэтому подходит даже произвольная вершина.

Покажем, что \(t\) вершин достаточно. В красно-синей раскраске \(K_t\), если есть красное ребро, то есть красный \(K_2\). Если красных рёбер нет, то все рёбра синие, и все \(t\) вершин образуют синий \(K_t\).

Меньше \(t\) вершин недостаточно: покрасим все рёбра в синий цвет. Тогда красного \(K_2\) нет, а синего \(K_t\) тоже нет, потому что вершин меньше \(t\). Значит, \(R(2,t)=t\).

Среди выбранных \(6\) человек по факту \(R(3,3)=6\) уже есть либо \(3\) попарно знакомых, либо \(3\) попарно незнакомых. Значит, среди всех \(7\) человек такая тройка тоже есть.

Число \(7\) не является точным порогом, потому что тот же результат гарантирован уже для \(6\) человек.

Пусть \(N=R(s-1,t)+R(s,t-1)\), и рёбра \(K_N\) покрашены в красный и синий цвета. Выберем вершину \(v\). Остальные \(N-1\) вершин делятся на красных соседей \(v\) и синих соседей \(v\).

Если красных соседей не меньше \(R(s-1,t)\), то внутри них есть либо красный \(K_{s-1}\), либо синий \(K_t\). В первом случае вместе с \(v\) получаем красный \(K_s\), во втором уже есть синий \(K_t\).

Если красных соседей меньше \(R(s-1,t)\), то синих соседей не меньше \(R(s,t-1)\). Тогда внутри них есть либо красный \(K_s\), либо синий \(K_{t-1}\), который вместе с \(v\) даёт синий \(K_t\).

Во всех случаях нужная структура существует.

По рекурсии Рамсея имеем

\[R(3,4)\le R(2,4)+R(3,3).\]

Из \(R(2,4)=4\) и \(R(3,3)=6\) получаем \(R(3,4)\le10\). Значит, в любой красно-синей раскраске рёбер \(K_{10}\) есть либо красный \(K_3\), либо синий \(K_4\).

Переведём это на язык людей: красное ребро — знакомство, синее — незнакомство. Получаем либо \(3\) попарно знакомых, либо \(4\) попарно незнакомых.

По рекурсии Рамсея

\[R(4,4)\le R(3,4)+R(4,3).\]

По симметрии \(R(4,3)=R(3,4)\). Так как \(R(3,4)\le10\), получаем

\[R(4,4)\le10+10=20.\]

Покрасим ребро между двумя людьми в красный цвет, если они знакомы, и в синий, если не знакомы. По оценке \(R(4,4)\le20\) в \(K_{20}\) есть либо красный \(K_4\), либо синий \(K_4\).

Красный \(K_4\) означает \(4\) попарно знакомых людей, синий \(K_4\) — \(4\) попарно незнакомых.

Если красный граф связен, всё доказано. Пусть он не связен. Тогда его вершины разбиваются на несколько красных компонент.

Любое ребро между двумя разными красными компонентами не может быть красным, иначе эти компоненты соединились бы. Значит, все такие рёбра синие.

Покажем, что синий граф связен. Если две вершины лежат в разных красных компонентах, между ними есть синее ребро. Если они лежат в одной красной компоненте, возьмём вершину из другой красной компоненты; обе связи с ней синие, поэтому есть синий путь длины \(2\). Следовательно, синий граф связен.

Переведём задачу в раскраску рёбер \(K_9\): красный цвет — знакомство, синий — незнакомство. Предположим, что нет красного треугольника и нет синего \(K_4\). Рассмотрим красный граф \(G\).

Граф \(G\) не содержит треугольников. Кроме того, в нём нет независимого множества из \(4\) вершин, потому что такое множество соответствовало бы синему \(K_4\).

Покажем, что степень любой вершины в \(G\) не больше \(3\). Действительно, если у вершины \(v\) есть \(4\) красных соседа, то между этими соседями не может быть красных рёбер, иначе возникнет красный треугольник с \(v\). Значит, эти \(4\) соседа образуют независимое множество в \(G\), то есть синий \(K_4\). Противоречие.

Если бы степень каждой вершины была ровно \(3\), сумма степеней равнялась бы \(9\cdot3=27\), что невозможно, потому что сумма степеней графа чётна. Значит, есть вершина \(v\) степени не больше \(2\).

Рассмотрим вершины, не смежные с \(v\) в красном графе. Их не меньше \(9-1-2=6\). В индуцированном на них красном графе также нет красного треугольника. По факту \(R(3,3)=6\), среди этих \(6\) вершин найдутся либо красный треугольник, либо независимая тройка. Красного треугольника нет, значит, есть независимая тройка.

Эта независимая тройка вместе с \(v\) образует независимое множество из \(4\) вершин в красном графе, то есть синий \(K_4\). Противоречие. Следовательно, нужная группа людей существует.

Выберем вершину \(v\). Из неё выходит \(16\) рёбер трёх цветов, поэтому по принципу Дирихле хотя бы \(6\) из них имеют один цвет. Пусть это красные рёбра к множеству \(A\) из \(6\) вершин.

Если внутри \(A\) есть красное ребро, то оно вместе с \(v\) образует красный треугольник. Если красных рёбер внутри \(A\) нет, то все рёбра внутри \(A\) покрашены двумя оставшимися цветами.

По факту \(R(3,3)=6\) в двухцветной раскраске рёбер на \(6\) вершинах есть одноцветный треугольник. Он будет одноцветным в одном из двух оставшихся цветов. Значит, в исходной трёхцветной раскраске одноцветный треугольник тоже существует.

Докажем, что красный или синий граф связен. Если красный граф связен, то в нём есть остовное дерево, и оно красное.

Пусть красный граф не связен. Тогда его вершины разбиваются на красные компоненты. Любое ребро между разными красными компонентами синее, иначе эти компоненты были бы одной компонентой. Поэтому синий граф связен: между разными красными компонентами есть синие рёбра, а две вершины внутри одной красной компоненты соединяются синим путём длины \(2\) через вершину из другой компоненты.

Значит, синий граф связен, а в любом связном графе есть остовное дерево. Это дерево будет синим и проходит через все вершины.