Рассмотрим граф из R ( n 1 , … , n c − 2 , R ( n c − 1 , n c ) ) {\displaystyle R(n_{1},\;\ldots ,\;n_{c-2},\;R(n_{c-1},\;n_{c}))} вершин и ...
Условие:
Рассмотрим граф из R ( n 1 , … , n c − 2 , R ( n c − 1 , n c ) ) {\displaystyle R(n_{1},;\ldots ,;n_{c-2},;R(n_{c-1},;n_{c}))} вершин и окрасим его рёбра c {\displaystyle c} цветами. Будем временно считать цвета c − 1 {\displaystyle c-1} и c {\displaystyle c} одним цветом. Тогда граф становится ( c − 1 ) {\displaystyle (c-1)}-цветным. Согласно определению числа R ( n 1 , … , n c − 2 , R ( n c − 1 , n c ) ) {\displaystyle R(n_{1},;\ldots ,;n_{c-2},;R(n_{c-1},;n_{c}))}, такой граф либо содержит K n i {\displaystyle K_{n_{i}}} для некоторого цвета i {\displaystyle i}, такого что 1 ⩽ i ⩽ c − 2 {\displaystyle 1\leqslant i\leqslant c-2} либо K R ( n c − 1 , n c ) {\displaystyle K_{R(n_{c-1},;n_{c})}}, окрашенный общим цветом c − 1 {\displaystyle c-1} и c {\displaystyle c}. В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметим, что, по определению числа Рамсея, полный R ( n c − 1 , n c ) {\displaystyle R(n_{c-1},;n_{c})} — вершинный граф содержит либо K n c − 1 {\displaystyle K_{n_{c-1}}} цвета c − 1 {\displaystyle c-1}, либо K n c {\displaystyle K_{n_{c}}} цвета c {\displaystyle c}, так что утверждение полностью доказано. Из леммы 1 следует конечность чисел Рамсея для c = 2 {\displaystyle c=2}. Отсюда, на основании леммы 2, следует конечность R ( n 1 , … , n c ) {\displaystyle R(n_{1},;\ldots ,;n_{c})} для любого c {\displaystyle c}. Исходя из чего мы можем вывести следующию теоремы матемически выражаемую следующими формулами:
Решение:
Исследования в области чисел Рамсея имеют важное значение в комбинаторике и теории графов. Числа Рамсея, обозначаемые как R(n1, ..., nc), представляют собой минимальное количество вершин в полном графе, в котором либо содержится полный подграф цвета c размером ni, либо не содержится ни одного полного подграфа цвета c размером ni.
В данной статье мы рассмотрим граф из R(n1, ..., nc-2, R(nc-1, nc)) вершин и окрасим его ребра c цветами. Для удобства, временно считаем цвета c-1 и c одним цветом, чтобы получить (c-1)-цветный граф. Согласно определению числа R(n1, ..., nc-2, R(nc-1, nc)), такой граф либо содержит полный подграф цвета i для некоторого i, такого что 1 <= i <= c-2, либо содержит полный подграф R(nc-1, nc), окрашенный общим цветом c-1 и c.
Если граф содержит полный подграф цвета i, то доказательство завершено. В противном случае, возвращаем прежние цвета и замечаем, что полный граф R(nc-1, nc) содержит либо полный подграф цвета c-1 размером nc-1, либо полный подграф цвета c размером nc. Таким образом, утверждение полностью доказано.
Из леммы 1 следует конечность чисел Рамсея для c = 2. Отсюда, на основании леммы 2, следует конечность R(n1, ..., nc) для любого c.
Таким образом, мы можем сделать вывод, что числа Рамсея являются конечными для любого заданного количества цветов c и размеров подграфов ni.
Эта теорема имеет важные практические применения в различных областях, таких как теория кодирования, теория игр и криптография. Исследования в области чисел Рамсея продолжаются и вносят вклад в развитие комбинаторики и теории графов.
