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

[Vladimir Pliassov]

Geen в сообщении #1596725 писал(а):

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

Я об этом писал здесь.

-- 06.06.2023, 00:06 --

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

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

А, так просто! Значит, список, о котором идет речь, это не список размеров ребер, а список ребер. Спасибо! Буду думать.

[Vladimir Pliassov]

В разбираемой статье Geoffrey Exoo читаем:

Цитата:

С помощью компьютера легко убедиться, что нет монохроматических (полных) подграфов $F_5$ в этой раскраске.

А зачем привлекать компьютер? Я распечатал две копии рис. 2,



из одной вырезал фигуру, ограниченную вершинами $1, 3, 23, 24$ (что-то вроде стрелки компаса), чуть-чуть укоротил ее на концах (чтобы они не закрывали окружность), совместил ее на фанерке с ней же самой на целой копии рисунка, нашел центр окружности (он находится на прямой, проходящей через вершину $11$ и между вершинами $32, 33$), вбил в него иголку (можно гвоздик), стал вращать "стрелку" и убедился, что везде либо с одного, либо с другого конца "стрелки" находится по крайней мере одна пунктирная дуга длиной $1$, либо длинные ребра совмещаются с пунктирным ребром $11-32$.

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

Разве этого не достаточно?

[Vladimir Pliassov]

В разбираемой статье Geoffrey Exoo читаем:

Цитата:

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

Мы строим раскраску в три шага. Начинаем с циклической двухцветной раскраски $K_{43}$, как приведено ниже:

цвет 1: $1\; 2\; 7\; 10\; 12\; 13\; 14\; 16\; 18\; 20\; 21$

цвет 2: $3\; 4\; 5\; 6\; 8\; 9\; 11\; 15\; 17\; 19$

В этой раскраске имеется 43 монохроматических подграфов $K_5$ в цвете 1 и ни одного в цвете 2.

Откуда можно знать, что в цвете 2 нет ни одного монохроматического подграфа $K_5$?

Это проверено на компьютере или есть другое обоснование?