Числа Рамcея и монохроматические подграфы в полных графах

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

Пусть мы организуем вечеринку, куда приглашаем знакомых и не знакомых друг с другом людей. Число Рамсея R(m, n) равно минимальному числу гостей, которое следует позвать для того, чтобы либо m человек было знакомо друг с другом, либо n человек не знало друг друга. Теорема Рамсея утверждает, что такой число существует для любых целых m и n.

Пусть теперь мы раскрашиваем ребра полных графов в два цвета: красный и синий. И пусть мы всеми силами стараемся избежать построения полных одноцветных подграфов. Их называют монохроматическими кликами (monochromatic clique).

> Термин «клика» пришел из социологии. Кли?ка (фр. clique — шайка, банда) — группа людей, объединенная корпоративными — политическими, экономическими, социальными интересами, осуществляющая свои корыстные требования через институты и каналы государства. Клика состоит из индивидов, принадлежащих к одной среде и сплочённых общими интересами.

> Клика неориентированного графа — это подмножество его вершин, в котором все вершины соединены ребром между собой.

Теорема Рамсея предсказывает, что для достаточно большого графа мы обязательно создадим монохроматическую клику красного или синего цвета. Минимальное число вершин полного графа, в котором обязательно появится монохроматическая клика — это и есть число Рамсея — R(m, n). В данном случае m — это количество вершин в красной, а n — в синей клике.

Числа Рамсея известны для немногих значений m и n. Дело в том, что даже для малых m и n необходим перебор огромного числа графов, с которым не могут справиться даже современные суперкомпьютеры.

Но давайте посмотрим на известные симметричные числа Рамсея вида R(m, m). Для сокращения записи их обозначают как R(m).

Возьмем простейший граф, состоящий из двух вершин, и окрасим его единственное ребро. В этом случае мы всегда получил либо синюю, либо красную двухвершинную клику. То есть R(2)=2. Это первое число Рамсея.

Теперь отыщем R(3).

Для полного пятивершинного графа мы достаточно легко можем избежать построения монохроматических клик (Рис.). То есть R(3) > 5. А вот если мы увеличим число вершин графа до шести, то в таком графе обязательно возникнет либо синий, либо красный полный подграф, содержащий три вершины (Рис.). Отсюда R(3)=6.

Четвертое и прочие числа Рамсея вычисляются аналогично — перебором. Понятно, что чем больше вершин графа следует перебрать, тем сложнее это сделать.

Четвертое число Рамсея было вычислено в 1955 году: R(4)=18.

А вот прочие точны значения чисел Рамсея вида R(k) для k>4 неизвестны. Трудоемкость расчетов слишком велика. Известны только интервальные оценки.

R(5) ? [43; 48],

причем верхняя граница интервала — 48, была уточнена не так давно, в 2017 году. До этого ее считали равной 49. (Математический справочник Вольфрама до сих пор указывает в качестве верхней границы число 49; https://mathworld.wolfram.com/RamseysTheorem.html)

R(6) ? [102; 165].

R(7) ? [205; 497].

R(8) ? [282; 1532].

R(9) ? [565; 5366].

R(10) ? [798; 17730].

Как вы видите, границы неопределенности растут быстро. Но существуют функциональные оценки границ интервалов со значениями чисел Рамсея.

Пал Эрдёш и Дьёрдем Секереш еще в 1935 году показали, что R(k) не превышает 4^k. Через 12 лет, в 1947 году Эрдёш определили нижнюю границу, как корень k-ой степени из двух: ?2^k.

R(k) ? [?2^k; 4^k].

В 1975 году Джоел Спенсер удвоил нижнюю границу. А верхняя граница оставалась нетронутой вплоть до марта 2023 года, когда коллектив математиков показал, что верхняя оценка симметричных чисел Рамсея представима в виде:

R(k) ? (4-?)^k.

Кроме того, они понизили верхнюю границу на 0,007, то есть

R(k) ? 3,993^k.

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

https://arxiv.org/abs/2303.09521

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

https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1

Вот уж правду говорят, что нет незначительных чисел, есть только заниженная оценка их значимости (с)

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

На этом позвольте откланяться.

Источник: mathworld.wolfram.com

Комментарии: