Конструктивная оценка снизу чисел Рамсея
Теорема Рамсея утверждает, что
Дано $s, t\in \mathbb{N}$, есть $n\in \mathbb{N}$ такой, что для каждого графа с $n$ вершин, он содержит $s$-clique или ее дополнение содержит $t$-клика.
Наименьший $n$ удовлетворяющий утверждению, обозначается $R(s, t)$.
В статье «Вероятностный метод в комбинаторике, лекции Ниранджана Балачандрана» я нашел следующее утверждение:
Конструктивная нижняя оценка R (s, s), открытая Надь, такова: $$R(s, s)\ge \binom{s}{3}$$ (Явно его конструкция выглядит следующим образом: возьмем любой набор $S$, и включите сборку всех $3$-элементные подмножества $S$ в граф, соединяя подмножества тогда и только тогда, когда их пересечение нечетное.)
Мне не удалось доказать, что этот граф и его дополнение не содержат $s$-клики. Любая помощь в этом вопросе будет принята с благодарностью.
Ответы
Давайте $S = \{1, 2, \dots, s\}$. На самом деле мы можем показать, что график Надя имеет
- клики размером не более $\max\{7, \frac{s-1}{2}\}$, и
- независимые наборы размера не более $s-1$ или меньше, когда $s \not\equiv 0 \pmod 4$, и самое большее $s$ когда $s \equiv 0 \pmod 4$.
Это не показывает, что $R(s,s) \ge \binom s3$ для всех $s$, но это показывает, что $R(s,s) > \binom s3$, и даже это $R(\frac{s}{2}, s) > \binom s3$, для бесконечного числа значений $s$.
Сначала найдем самую большую клику. Есть два случая:
- Клика содержит $4$ вершины, пересекающиеся в одном элементе $S$: сказать, $\{1,2,3\}$, $\{1,4,5\}$, $\{1,6,7\}$, и $\{1,8,9\}$. Тогда каждая вторая вершина должна содержать$1$: в противном случае он должен был бы иметь элемент из каждого из $\{2,3\}$, $\{4,5\}$, $\{6,7\}$, и $\{8,9\}$, что невозможно. Такая клика может иметь не более$\frac{s-1}{2}$ вершины.
- Клика содержит не более $3$ вершины, пересекающиеся в одном элементе $S$. Сказать$\{1,2,3\}$одна из вершин. Тогда может быть самое большее$2$ другие вершины, содержащие каждую из $1$, $2$, или же $3$, поэтому у клики не более $7$ вершины.
Далее найдем самый большой независимый набор. Здесь обратите внимание, что если две вершины в независимом множестве делят$2$ элементов, а третья вершина в независимом множестве разделяет $2$ элементов с одним из них, он должен разделять хотя бы один элемент (и, следовательно, $2$элементы) с другим. Таким образом, независимый набор должен состоять из кластеров, где любые две вершины в кластере совместно используют$2$ элементы, и любые две вершины за пределами кластера разделяют $0$.
И снова кластеры могут иметь две разные формы:
- Предположим, что в кластере есть $3$ вершины, которые все имеют одинаковые $2$ элементы: скажем, $\{1,2,3\}$, $\{1,2,4\}$,и $\{1,2,5\}$. Другая вершина в кластере, содержащая только одну из$\{1,2\}$ должен содержать каждый из $3$, $4$, и $5$, что невозможно. Итак, кластер состоит из$k$ вершины формы $\{1,2,x\}$, которые "израсходуют" $k+2$ элементы $S$.
- Предположим, что в кластере не более $2$ вершины, разделяющие любые $2$элементы. Тогда если$\{1,2,3\}$ является вершиной в кластере, каждая другая вершина в кластере должна содержать две из $\{1,2,3\}$, но может быть не более одного каждого вида для $4$всего вершин. Они должны использовать как минимум$4$ элементы $S$, например, с $\{1,2,3\}, \{1,2,4\}, \{1,3,4\}, \{2,3,4\}$.
Мы видим, что кластер использует $k$ элементы $S$ может содержать не более $k$ вершин, поэтому в целом кластеры могут содержать не более $S$вершины. Но это возможно только тогда, когда все кластеры относятся ко второму типу и охватывают все элементы$S$, что требует $s \equiv 0 \pmod 4$.