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

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

Формулировки

Теоретико-множественная формулировка

Частный случай N(p, q, r)

Пусть p {displaystyle p} , q {displaystyle q} и r {displaystyle r} — натуральные числа, причём p , q ⩾ r {displaystyle p,;qgeqslant r} .

Тогда существует число N = N ( p , q , r ) {displaystyle N=N(p,;q,;r)} , обладающее следующим свойством: если все r {displaystyle r} -элементные подмножества N {displaystyle N} -элементного множества S {displaystyle S} произвольным образом разбиты на два непересекающихся семейства α {displaystyle alpha } и β {displaystyle eta } , то либо существует p {displaystyle p} -элементное подмножество множества S {displaystyle S} , все r {displaystyle r} -элементные подмножества которого содержатся в α {displaystyle alpha } , либо существует q {displaystyle q} -элементное подмножество, все r {displaystyle r} -элементные подмножества которого содержатся в β {displaystyle eta } .

Общий случай

Пусть множество S {displaystyle S} имеет N {displaystyle N} элементов. Рассмотрим его r {displaystyle r} -подмножества r ⩾ 1 {displaystyle rgeqslant 1} , обозначим совокупность всех этих подмножеств P r ( S ) {displaystyle P_{r}(S)} , упорядоченные t {displaystyle t} -разбиения P r ( S ) = A 1 ∪ A 2 ∪ … ∪ A t {displaystyle P_{r}(S)=A_{1}cup A_{2}cup ldots cup A_{t}} , числа q 1 ,   q 2 ,   … ,   q t {displaystyle q_{1}, q_{2}, ldots , q_{t}} , задающие разбиение 1 ⩽ r ⩽ q 1 , q 2 , … , q t {displaystyle 1leqslant rleqslant q_{1},;q_{2},;ldots ,;q_{t}} .

Тогда для любого упорядоченного t {displaystyle t} -разбиения множества P r ( S ) {displaystyle P_{r}(S)} существует такое минимальное число N ( q 1 , q 2 , … , q t ; r ) {displaystyle N(q_{1},;q_{2},;ldots ,;q_{t};;r)} , что если N ⩾ N ( q 1 , q 2 , … , q t ; r ) {displaystyle Ngeqslant N(q_{1},;q_{2},;ldots ,;q_{t};;r)} , то существует ( q i , A i ) {displaystyle (q_{i},;A_{i})} — подмножество множества S {displaystyle S} , то есть такое q i {displaystyle q_{i}} — подмножество множества S {displaystyle S} , все r {displaystyle r} -подмножества которого содержатся в A i ,   1 ⩽ t ⩽ t {displaystyle A_{i}, 1leqslant tleqslant t} .

Формулировка на языке теории графов

Для любых c {displaystyle c} натуральных чисел n 1 ,   n 2 ,   … ,   n c {displaystyle n_{1}, n_{2}, ldots , n_{c}} в любой c {displaystyle c} -цветной раскраске рёбер достаточно большого полного графа содержится полный подграф с n i {displaystyle n_{i}} вершинами для некоторого цвета i {displaystyle i} . В частности, для любых r {displaystyle r} и s {displaystyle s} , достаточно большой полный граф двухцветной (чёрно-белой) раскраски, содержит либо полный чёрный подграф из r {displaystyle r} вершин, либо полный белый подграф из s {displaystyle s} вершин.

Числа Рамсея

Минимальное число R ( r , s ) {displaystyle R(r,;s)} , при котором это выполнено, называют числом Рамсея.

Например, равенство R ( 3 , 3 ) = 6 {displaystyle R(3,;3)=6} означает, что с одной стороны в любой двухцветной раскраске полного графа K 6 {displaystyle K_{6}} найдётся одноцветный треугольник, а с другой стороны — то, что полный граф K 5 {displaystyle K_{5}} допускает двухцветную раскраску без одноцветных треугольников.

В общем случае для c {displaystyle c} -цветной раскраски используется обозначение R ( n 1 , n 2 , … , n c ) {displaystyle R(n_{1},;n_{2},;ldots ,;n_{c})} для минимального числа вершин, обеспечивающего существование K n i {displaystyle K_{n_{i}}} для некоторого цвета i {displaystyle i} .

Доказательство теоремы Рамсея

Двухцветный случай

Лемма 1. R ( r , s ) ⩽ R ( r − 1 , s ) + R ( r , s − 1 ) . {displaystyle R(r,;s)leqslant R(r-1,;s)+R(r,;s-1).}

Доказательство. Докажем с помощью метода математической индукции по r + s {displaystyle r+s} .

База индукции. R ( n , 1 ) = R ( 1 , n ) = 1 {displaystyle R(n,;1)=R(1,;n)=1} , так как 1-вершинный граф можно считать полным графом любого цвета.

Индукционный переход. Пусть r > 1 {displaystyle r>1} и s > 1 {displaystyle s>1} . Рассмотрим полный чёрно-белый граф из R ( r − 1 , s ) + R ( r , s − 1 ) {displaystyle R(r-1,;s)+R(r,;s-1)} вершин. Возьмём произвольную вершину v {displaystyle v} и обозначим через M {displaystyle M} и N {displaystyle N} множества инцидентные v {displaystyle v} в чёрном и белом подграфе соответственно. Так как в графе R ( r − 1 , s ) + R ( r , s − 1 ) = | M | + | N | + 1 {displaystyle R(r-1,;s)+R(r,;s-1)=|M|+|N|+1} вершин, согласно принципу Дирихле (комбинаторика), либо | M | ⩾ R ( r − 1 , s ) {displaystyle |M|geqslant R(r-1,;s)} , либо | N | ⩾ R ( r , s − 1 ) {displaystyle |N|geqslant R(r,;s-1)} .

Пусть | M | ⩾ R ( r − 1 , s ) {displaystyle |M|geqslant R(r-1,;s)} . Тогда либо в M {displaystyle M} (и следовательно во всём графе) есть белый K s {displaystyle K_{s}} , что завершает доказательство, либо в M {displaystyle M} есть чёрный K r − 1 {displaystyle K_{r-1}} , который вместе с v {displaystyle v} образует чёрный K r {displaystyle K_{r}} . Случай | N | ⩾ R ( r , s − 1 ) {displaystyle |N|geqslant R(r,;s-1)} рассматривается аналогично.

Замечание. Если R ( r − 1 , s ) {displaystyle R(r-1,;s)} и R ( r , s − 1 ) {displaystyle R(r,;s-1)} оба чётны, неравенство можно усилить: R ( r , s ) ⩽ R ( r − 1 , s ) + R ( r , s − 1 ) − 1 {displaystyle R(r,;s)leqslant R(r-1,;s)+R(r,;s-1)-1} .

Доказательство. Предположим, p = R ( r − 1 , s ) {displaystyle p=R(r-1,;s)} и q = R ( r , s − 1 ) {displaystyle q=R(r,;s-1)} оба чётны. Положим t = p + q − 1 {displaystyle t=p+q-1} и рассмотрим чёрно-белый граф из t {displaystyle t} вершин. Если d i {displaystyle d_{i}} степень i {displaystyle i} -й вершины в чёрном подграфе, то, согласно лемме о рукопожатиях, ∑ i = 1 t d i {displaystyle sum _{i=1}^{t}d_{i}} — чётно. Поскольку t {displaystyle t} нечётно, должно существовать чётное d i {displaystyle d_{i}} . Для определённости положим, что d 1 {displaystyle d_{1}} чётно. Обозначим через M {displaystyle M} и N {displaystyle N} вершины инцидентные вершине 1 в чёрном и белом подграфах соответственно. Тогда | M | = d 1 {displaystyle |M|=d_{1}} и | N | = t − 1 − d 1 {displaystyle |N|=t-1-d_{1}} оба чётны. Согласно принципу Дирихле (комбинаторика), либо | M | ⩾ p − 1 {displaystyle |M|geqslant p-1} , либо N ⩾ q {displaystyle Ngeqslant q} . Так как | M | {displaystyle |M|} чётно, а p − 1 {displaystyle p-1} нечётно, первое неравенство можно усилить, так что либо | M | ⩾ p {displaystyle |M|geqslant p} , либо | N | ⩾ q {displaystyle |N|geqslant q} .

Предположим | M | ⩾ p = R ( r − 1 , s ) {displaystyle |M|geqslant p=R(r-1,;s)} . Тогда либо подграф, порождённый множеством M {displaystyle M} , содержит белый K s {displaystyle K_{s}} и доказательство завершено, либо он содержит чёрный K r − 1 {displaystyle K_{r-1}} , который вместе с вершиной 1 образует чёрный K r {displaystyle K_{r}} . Случай | N | ⩾ q = R ( r , s − 1 ) {displaystyle |N|geqslant q=R(r,;s-1)} рассматривается аналогично.

Случай большего количества цветов.

Лемма 2. Если c > 2 {displaystyle c>2} , то R ( n 1 , … , n c ) ⩽ R ( n 1 , … , n c − 2 , R ( n c − 1 , n c ) ) . {displaystyle R(n_{1},;ldots ,;n_{c})leqslant 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 1leqslant ileqslant 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} . Это доказывает теорему Рамсея.

Значения чисел Рамсея

Таблица значений

Для N ( q 1 , q 2 , … , q t ; t ) {displaystyle N(q_{1},;q_{2},;ldots ,;q_{t};;t)} при t > 2 {displaystyle t>2} имеется очень мало данных. Следующая таблица значений чисел Рамсея для N ( q 1 , q 2 ; 2 ) {displaystyle N(q_{1},;q_{2};;2)} взята из таблицы Радзишевского, данные приведены по состоянию на 2020 год.

Асимптотические оценки

Из неравенства R ( r , s ) ⩽ R ( r − 1 , s ) + R ( r , s − 1 ) {displaystyle R(r,;s)leqslant R(r-1,;s)+R(r,;s-1)} вытекает, что

R ( r , s ) ⩽ ( r + s − 2 r − 1 ) . {displaystyle R(r,;s)leqslant {inom {r+s-2}{r-1}}.}

В частности отсюда вытекает верхняя граница (Эрдёш, Секереш)

R ( s , s ) ⩽ ( 1 + o ( 1 ) ) 4 s − 1 π s . {displaystyle R(s,;s)leqslant (1+o(1)){frac {4^{s-1}}{sqrt {pi s}}}.}

Нижняя граница

R ( s , s ) ⩾ ( 1 + o ( 1 ) ) s 2 e 2 s / 2 , {displaystyle R(s,;s)geqslant (1+o(1)){frac {s}{{sqrt {2}}e}}2^{s/2},}

получена Эрдёшем в 1947 году с помощью его вероятностного метода.

Современные оценки получены Спенсером и Конлоном соответственно.

( 1 + o ( 1 ) ) 2 s e 2 s / 2 ⩽ R ( s , s ) ⩽ s − c log ⁡ s / log ⁡ log ⁡ s 4 s . {displaystyle (1+o(1)){frac {{sqrt {2}}s}{e}}2^{s/2}leqslant R(s,;s)leqslant s^{-clog s/log log s}4^{s}.}

Очевидно, что эти оценки незначительно улучшают первые результаты и не близки между собой.

Эрдёш полагал, что в случае крайней необходимости человечество ещё способно найти R ( 5 , 5 ) {displaystyle R(5,;5)} , но не R ( 6 , 6 ) {displaystyle R(6,;6)} .

Известна также найденная Кимом в 1995 году оценка R ( 3 , t ) ⩾ ( 1 162 + o ( 1 ) ) t 2 ln ⁡ t {displaystyle R(3,;t)geqslant left({frac {1}{162}}+o(1) ight){frac {t^{2}}{ln {t}}}} . В сочетании с оценкой R ( 3 , t ) ⩽ ( 1 + o ( 1 ) ) t 2 ln ⁡ t {displaystyle R(3,;t)leqslant (1+o(1)){frac {t^{2}}{ln {t}}}} это неравенство задаёт порядок роста величины R ( 3 , t ) = Θ ( t 2 ln ⁡ t ) {displaystyle R(3,;t)=Theta left({frac {t^{2}}{ln {t}}} ight)} .