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

[Vladimir Pliassov]

Как известно, число Рамсея $R(5,5)$ находится в промежутке $[43, 48]$. То есть пока что не найдено, какому из чисел от $43$ до $48$ оно равно.

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

Но что если попытаться найти всего лишь один двухцветный граф на $43$ вершинах, в котором не будет ни одного полного пятивершинного подграфа? Если это удастся, будет ясно, что число $43$ можно исключить. Затем перейти к числу $44$ и так далее.

Можно ли сделать это на вычислительной машине? Может быть, даже это очень просто?

Я попытался найти такой граф сразу на $48$ вершинах -- без вычислительной машины, -- но не смог.

Не думаю, чтобы мне это удалось и для остальных чисел от $43$ до $47$.

[mihaild]

Vladimir Pliassov в сообщении #1594991 писал(а):

Но что если попытаться найти всего лишь один двухцветный граф на $43$ вершинах, в котором не будет ни одного полного пятивершинного подграфа?

Вопрос в том, как это сделать:)
Для $42$ как раз придуман некоторый хитрый способ раскраски, и дальше на компьютере проверено, что у него нет монохроматических подграфов на 5 вершинах. Но придумать такую раскраску нетривиально.
Для $48$ было сделано что-то аналогичное: некоторым хитрым рассуждением было показано, что если контрпример существует, то он лежит в некотором множестве из примерно двух триллионов графов, и дальше каждый из них был проверен.

Проверить любой конкретный граф на компьютере - просто. Но если брать графы с потолка, то шансы наткнуться на контрпример очень невелики.

[Vladimir Pliassov]

Спасибо! Поищу еще -- для $47$. Это число простое, и мне кажется, что оно может не давать полных пятерок (так же как и $43$).

Для сравнения: $48$ делится на $2, 3, 4, 6, 8, 12, 16, 24$, что, может быть, дает больше возможностей для полных подграфов.

[mihaild]

Для 43 должно быть найти проще, чем для 47 - если есть пример для 47, то любой подграф размера 43 даст пример для 43.
Но насколько я понимаю, большинство специалистов считает что скорее всего $R(5,5)=43$.

[Vladimir Pliassov]

Я пытаюсь идти методом исключения: если удастся исключить 43, то придется потом пытаться исключить 44, 45, 46, и 47. Но если удастся исключить сразу 47 (то есть если удастся доказать, что существует такой двухцветный граф на 47 вершинах, в котором не содержится ни одного полного подграфа одного цвета на 5 вершинах), то ясно, что $R(5,5)=48$.

К тому же 47, так же как и 43, это простое число, и в некотором отношении все равно, работать с 43 или с 47, только чуть больше вычислений.

[mihaild]

А если на самом деле $R(5,5)=46$, то исключить $43$ получится, а $47$ нет.
У вас есть какие-то хорошие причины считать, что $R(5,5)>43$? Я знаю причину предполагать обратное - доказывать нижние границы по идее чуть проще, чем верхние (потому что достаточно привести один пример), но нижняя граница уже 25 лет не улучшалась, а верхняя улучшалась.

[Vladimir Pliassov]

mihaild в сообщении #1595332 писал(а):

У вас есть какие-то хорошие причины считать, что $R(5,5)>43$?

Нет, у меня нет таких причин, просто, раз мне все равно, пытаться доказывать для 43 или для 47, я сразу беру 47.

[Vladimir Pliassov]

mihaild в сообщении #1594993 писал(а):

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

А какой хитрый способ? Можно об этом где-то почитать?

Пока что мне не удалось найти таких двухцветных раскрасок для полных графов на 47 или даже на 43 вершинах, чтобы в них не было монохроматических подграфов на 5 вершинах

(как я понимаю, монохроматический подграф это полный подграф, все ребра которого одного цвета?).

Мое достижение гораздо скромнее (и то если я не ошибаюсь): всего лишь 13 вершин. Но все же я нашел эту раскраску не случайно и не подбором, а по какой-то системе. Теперь хотелось бы найти системы для больших чисел.

Пусть дано множество $V$ точек $v$ мощности $n$. Перенумеруем их от $1$ до $n$, назовем каждую точку ее номером и расположим все точки на окружности, причем номера будут возрастать против часовой стрелки. При этом нумерация будет периодическая с периодом $n$: каждая точка будет иметь бесконечное множество номеров: точка $a$, то есть точка номер $a \;\; 1\leqslant a\leqslant n$, будет иметь также номера $a+kn \;\; k=\overline {1, \infty}$ (вообще, точка $a$ будет иметь номера $a+kn \;\; k=\overline {0, \infty}$).



Например, для номеров точек при $n=13$ (рис. 1) имеем $1=14=27=40=\ldots, \quad 2=15=28=41=\ldots$ и так далее.

Будем смотреть на множество $V$ как на множество вершин графа $G(V,E)$, соответственно, будем соединять его вершины ребрами $e\in E\quad e=\{v_1, v_2\}$:

$$G(V,E)=\left\langle V,E\right\rangle ,\quad V\neq \varnothing ,\quad E\subseteq V\times V,\quad \left\{v,v\right\}\notin E,\quad v\in V.$$

На рис. 1 видно, что любое ребро графа $G$ похоже на хорду окружности: хорда окружности образует пару дуг с одними и теми же крайними точками по разные стороны хорды, также и ребро $\{a, b\}$ графа $G$ (здесь $a=7, b=10$) образует пару дуг с одними и теми же крайними точками по разные стороны ребра: дугу $\buildrel\,\,\frown\over{a,b}$ и дугу $\buildrel\,\,\frown\over{b,a}$.

Договоримся называть длиной дуги $\buildrel\,\,\frown\over{a,b}$ ребра $\{a, b\}$ разность $b-a$ между номерами его вершин и, соответственно, длиной дуги $\buildrel\,\,\frown\over{b, a}$ того же ребра $\{a, b\}$ разность $a-b$ (в дуге от вершины к вершине мы движемся против часовой стрелки), причем
уменьшаемое и вычитаемое могут заменяться на любые равные им номера по правилу $a=a+kn \;\; k=\overline {0, \infty}$ при условии, что уменьшаемое остается или становится больше вычитаемого.

Например, длина дуги $\buildrel\,\,\frown\over{1, 13}$ ребра $\{1, 13\}$ равна $13-1=12$, а длина дуги $\buildrel\,\,\frown\over{13, 1}$ того же ребра $\{1, 13\}$ равна $1-13=14-13=1$ (так как $1=14$). Длину дуги $\buildrel\,\,\frown\over{a,b}$ будем обозначать $l({\buildrel\,\,\frown\over{a,b}})$.

Отметим, что $l({\buildrel\,\,\frown\over{a,b}})=l({\buildrel\,\,\frown\over{a,b}})+kn \quad k=\overline {0, \infty}$ -- так же как точка $a$ имеет номера $a+kn \;\; k=\overline {0, \infty}$, -- то есть в отношении длин дуг, так же как и в отношении нумерации вершин имеет место периодичность с периодом $n$, например, $12=l({\buildrel\,\,\frown\over{1, 13}})=l({\buildrel\,\,\frown\over{1, 39}})=38=12+2\cdot 13.$

Назовем дуги одного и того же ребра сопряженными друг с другом, соответственно, сопряжены друг с другом их длины. Сумма длин сопряженных дуг равна $n$, в рассматриваемом случае -- $13$, то есть числу вершин графа:

$$\begin{matrix} 1+12=13, \\ 2+11=13, \\ 3+10=13, \\ 4+9=13, \\ 5+8=13, \\ 6+7=13. \end{matrix}\eqno (1)$$

Можно определить и длину (размер) ребра. На рис. 1 видно, что, например, ребро $\{2, 11\}$ больше, чем ребро $\{3, 5\}$, и очевидно, что это потому, что отношение $4/9$ длины меньшей дуги ребра $\{2, 11\}$ к длине его большей дуги больше, чем отношение $2/11$ длины меньшей дуги ребра $\{3, 5\}$ к длине его большей дуги (то, что ребро $\{2, 11\}$ и отношение $2/11$ это просто совпадение). Таким образом, наименьшей является длина ребра с отношением длин дуг $1/12$, а наибольшей длина ребра с отношением длин дуг $6/7$, и каждой длине ребер можно поставить во взаимно однозначное соответствие одну из дробей от $1/12$ до $6/7$. При этом каждой из этих дробей можно поставить во взаимно однозначное соответствие ее числитель, так что каждой длине ребер можно поставить во взаимно однозначное соответствие одно из чисел от $1$ до $6$, и этим определяется длина каждого ребра, то есть есть ребра длиной $1$, есть ребра длиной $2$ и так далее до $6$ включительно.

Таким образом, всего имеется $6$ различных размеров (различных длин) ребер полного графа на $13$ вершинах. Впрочем, это можно увидеть непосредственно, если провести от одной вершины всевозможные ребра (соединив ее с каждой из остальных вершин): ребра симметричны по размерам относительно этой вершины, так что их размеров вдвое меньше, чем их общее число.

Построим граф $G$ на $13$ вершинах полным, и раскрасим его в два цвета так, чтобы все ребра одной и той же длины были одного цвета. Поскольку $13$ число простое, то оно взаимно просто с каждым из чисел от $1$ до $6$, так что при этом образуется $6$ одноцветных цепочек по $13$ ребер одинаковой длины (Число ребер в полном графе равно $n(n-1)/2$. ).

(Все $13$ ребер каждой цепочки окрасим одним цветом -- либо красным, либо синим -- так что получим сколько-то полностью красных и сколько-то полностью синих цепочек.)

Каждая цепочка состоит из ребер одного размера (одной длины).

Каждая цепочка будет замкнута (то есть будет циклом): если за отправную точку взять вершину $1$, то каждая цепочка будет выходить из $1$ и приходить в $1$.

В отношении номеров вершин это будет $6$ арифметических прогрессий, с соответствующим шагом каждая (шаг каждой прогрессии будет равен длине ребра соответствующей цепочки). Первым членом прогрессии может служить номер любой вершины, но мы для определенности будем исходить из $1$.

Вообще, если раскрасить полный граф на достаточно большом числе вершин -- числе произвольном, но обязательно простом, -- таким образом, чтобы было $10$ цепочек ребер одного цвета, то образуются цепочки полных пятерок этого цвета (для каждого набора размеров ребер своя цепочка), начиная с пятерок, все $10$ ребер которых разные, заканчивая пятерками, имеющими минимальное число разных по длине ребер, а именно $4$.

(Если все $10$ ребер полной пятерки имеют разные размеры, то ее образуют минимум $10$ цепочек соответствующих шагов, если же не все $10$ ребер полной пятерки имеют разные размеры, то потребуется менее $10$ цепочек, минимум $4$ цепочки.)

Если будет только $3$ цепочки одного цвета, то они не образуют ни одной полной пятерки (ни одной цепочки полных пятерок) одного цвета. Если будет всего $6$ цепочек, то одну половину из них можно окрасить одним цветом, а другую -- другим цветом, так что не будет четырех цепочек одного цвета. (Если будет $7$ цепочек, то при двухцветной окраске не удастся окрасить их так, чтобы не было четырех цепочек одного цвета.)

$6$ разных размеров ребер имеют полные графы на $12$ и на $13$ вершинах. Но граф на $12$ вершинах не имеет цепочек из $n$ ребер ($n$ это число вершин), потому что число его вершин не простое. Возьмем граф на $13$ вершинах и раскрасим его так, чтобы было $3$ синих и $3$ красных цепочки. В этом графе не будет ни одной полной пятерки (ни одной цепочки полных пятерок) одного цвета.

[mihaild]

Vladimir Pliassov в сообщении #1596391 писал(а):

А какой хитрый способ? Можно об этом где-то почитать?

Exoo, Geoffrey, "A lower bound for $R(5, 5)$" - оригинальная статья, там всё понятно.

Vladimir Pliassov в сообщении #1596391 писал(а):

Пока что мне не удалось найти таких двухцветных раскрасок для полных графов на 47 или даже на 43 вершинах, чтобы в них не было монохроматических подграфов на 5 вершинах

Ну было бы очень странно, если бы Вам с наскоку удалось получить результат, над которым десятки лет бьется куча сильных математиков.

-- 04.06.2023, 00:05 --

Vladimir Pliassov в сообщении #1596391 писал(а):

Но все же я нашел эту раскраску не случайно и не подбором, а по какой-то системе

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

[Vladimir Pliassov]

mihaild в сообщении #1596410 писал(а):

Exoo, Geoffrey, "A lower bound for $R(5, 5)$"

Спасибо! Попробую найти.

mihaild в сообщении #1596410 писал(а):

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

Возьмем полный граф на $13$ вершинах и раскрасим его так, чтобы было $3$ синих и $3$ красных цепочки. В этом графе не будет ни одной полной пятерки одного цвета.

Каждая цепочка состоит из $13$ ребер одинакового размера, всего цепочек $6$ (всего ребер $n(n-1)/2$, то есть $13(13-1)/2=13\cdot 6$).

[Aritaborian]

Vladimir Pliassov в сообщении #1596418 писал(а):

Спасибо! Попробую найти.

Тыц.

[Vladimir Pliassov]

Aritaborian в сообщении #1596428 писал(а):

Тыц
.

Большое спасибо! Вижу, что я пошел по тому же пути, что и Geoffrey Exoo (это ведь имя автора статьи?), но не так далеко: я дошел только до $13$, потому что нашел только очень простую конструкцию (может быть, простейшую для циклической раскраски), а он прошел дальше -- до $42$, потому что нашел более сложную конструкцию (в которой я еще не разобрался).

Мы оба начинаем с циклической раскраски, но я так на ней и остаюсь, а он, начиная с циклической раскраски -- для $43$, затем, как утверждается, переходит к нециклической для $42$.

Но тут мне непонятно. У автора читаем:

Цитата:

Циклическая раскраска есть такая, в которой вершины $K_n$ отождествляются с целыми числами от $0$ до $n - 1$, и в котором цвет ребра зависит только от численной разницы между его конечными вершинами. Эти разности часто называют длинами хорд. Циклическую раскраску можно задать, указав длину хорды (от $1$ до $[n/21]$) для каждого цвета.

То есть все ребра одной и той же длины имеют один и тот же цвет.

Автор берет циклическую раскраску для $K_{43}$, и затем пишет:

Цитата:

Следующим шагом в построении является удаление нулевой вершины. В этой (нециклической) раскраске $K_{42}$ ...

Разве оттого, что удаляется одна вершина, ребра одной и той же длины перестают быть окрашенными в один и тот же цвет? По-моему, нет, значит, в соответствии с определением автора, раскраска продолжает оставаться циклической.

Может быть, имеется в виду, что при циклической раскраске цикл должен состоять из $n$ ребер, что возможно только если число вершин $K_n$ и длина ребра взаимно просты? Например, в $K_ {12}$ все ребра длины $2$ (их всего $12$) разбиваются в две замкнутые цепочки (в два цикла) по $6$ ребер. А в $K_ {13}$ имеется всего одна цепочка ребер длины $2$, она состоит из $13$ ребер.

Но тогда определение автора неполное.

[Vladimir Pliassov]

В Тыц читаем:

Цитата:

Последний шаг в конструкции состоит в том, чтобы изменить цвет следующего списка ребер с 1 на 2:

$$\begin {matrix} 4-5\\ 5-6\\ 6-7\\ 7-8 \end {matrix}\quad \quad \begin {matrix} 13-14\\ 14-15\\ 15-16\\ 16-17\\ \end {matrix}\quad \quad \begin {matrix} 23-24\\ 24-25\\ 30-31\\ 33-34 \end {matrix}\quad \quad \begin {matrix} 39-40\\ 40-41\\ 41-42\\ 11-32 \end {matrix} \eqno (2) $$

1. Этот список это список размеров ребер. То есть ребра всех размеров из этого списка надо перекрасить из цвета 1 в цвет 2? Но многие размеры из этого списка это и так размеры ребер цвета 2.

2. То, что в этом списке окрашено цветом 1 перекрасить в цвет 2?

2. "$4-5$" ведь не означает "$4$ минус $5$"? А что это означает?

Что цвет размера $4$ надо перекрасить в цвет размера $5$? Но они одного цвета, и уже цвета 2.

3. "$4-5$" означает, что размер $4$ в $K_{43}$ превращается в размер $5$ в $K_{42}$ или наоборот? Но размер ребер не зависит от числа вершин (если их достаточно).

4. В $K_{43}$ и в $K_{42}$ всего $21$ размер ребер. Откуда в списке взялись числа больше $21$? Здесь я могу предположить, что каждое ребро по длине имеет две идентификации -- длины двух своих дуг, сопряженных друг с другом таким образом (об этом я писал выше). Для $K_{43}$ имеем следующие пары идентификаций:

$$\begin {matrix} 1\sim 42\\ 2\sim 41\\ 3\sim 40\\ 4\sim 39\\ 5\sim 38\\ 6\sim 37\\ 7\sim 36\\ \end {matrix} \quad \quad \begin {matrix} 8\sim 35\\ 9\sim 34\\ 10\sim 33\\ 11\sim 32\\ 12\sim 31\\ 13\sim 30\\ 14\sim 29 \end {matrix} \quad \quad \begin {matrix} 15\sim 28\\ 16\sim 27\\ 17\sim 26\\ 18\sim 25\\ 19\sim 24\\ 20\sim 23\\ 21\sim 22 \end {matrix} \eqno (3) $$

Тогда список (2) можно переписать так:

$$\begin {matrix} 4-5\\ 5-6\\ 6-7\\ 7-8 \end {matrix}\quad \quad \begin {matrix} 13-14\\ 14-15\\ 15-16\\ 16-17\\ \end {matrix}\quad \quad \begin {matrix} 20-19\\ 19-18\\ 13-12\\ 10-9 \end {matrix}\quad \quad \begin {matrix} 4-3\\ 3-2\\ 2-1\\ 11-11 \end {matrix} \eqno (2-a) $$

Но все равно непонятно.

[mihaild]

Vladimir Pliassov в сообщении #1596718 писал(а):

2. "$4-5$" ведь не означает "$4$ минус $5$"? А что это означает?

Это значит ребро из $4$ в $5$.

[Geen]

Откуда взялись размеры рёбер?