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

[Vladimir Pliassov]

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

И еще один пример есть.

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

zykov в сообщении #1580487 писал(а):

С чего вдруг?
Чтобы не путаться, рассуждайте на языке множеств.

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

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

Кстати, ведь может быть не два, больше дополняющих друг друга графов? То есть несколько графов, имеющих одно и то же число вершин и непересекающихся в своих ребрах, объединение которых является полным графом?

Раскрасим ребра каждого из них в свой цвет и получим полный раскрашенный граф.

[zykov]

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

Кстати, ведь может быть не два, больше дополняющих друг друга графов?

Думаю, так не говорят.
"дополняющие" - это про два
а если несколько, то это какое-то разбиение (попарно не пересекаются, в объединении дают полный)

[Vladimir Pliassov]

Спасибо, понял.

[mihaild]

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

Или есть еще пример?

Да, есть два неизоморфных полных графа без ребер.

[Vladimir Pliassov]

1.

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

Да, есть два неизоморфных полных графа без ребер.

Граф с одной вершиной и граф без вершин (и без ребер)? Граф без вершин это аналог пустого множества?

2.

В видео "Дискретный анализ 1. Теорема Рамсея." на YouTube, $7' 50''-9'50''$, лектор приводит выражения $R(1, t)=1$ и $R(2, t)=t$. Попытаюсь их доказать (частично самостоятельно, частично нет) с двух точек зрения: теории графов и теории множеств. Приведу две формулировки теоремы Рамсея из Википедии.

Цитата:

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

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

Цитата:

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

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

Пусть $p$, $q$ и $r$ — натуральные числа, причём $p,\;q\geqslant r$.

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

множества $S$,

Цитата:

все $r$-элементные подмножества которого содержатся в $\beta$.

Унифицирую обозначения, то есть заменю некоторые обозначения в первой формулировке на соответствующие им обозначения из второй формулировки.

Цитата:

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

Теперь обозначения (в основном) соответствуют также обозначениям у М. Холла в http://mathscinet.ru/files/HallM.pdf стр. 79 - 81.

Сначала $R(2, t)=t$, это, по-моему, проще, чем $R(1, t)=1$, во всяком случае, на графах.

По теории графов. Пусть дан граф $S$ на $t$ вершинах. Либо в нем нет ребер, и тогда он содержит полностью независимый $t$-вершинный подграф (то есть сам себя), либо есть хотя бы одно ребро, и тогда он содержит, по крайней мере, однореберный подграф. Если же взять $(t-1)$-вершинный граф, то, если в нем нет ребер, то он полностью независимый, но не содержит $t$ вершин, таким образом, он недостаточно большой для $R(2, t)$. Значит, утверждение $R(2, t)=t$ верно.

По теории множеств. Имеем $p=2, q=t, r=2$. Пусть дано множество $S$ мощности $t$. Имеем $T^2$ -- множество всех его $2$-элементных подмножеств (то есть множество всех его $r$-элементных подмножеств при $r=2$). Разобьем $T^2$ на два непересекающихся семейства $\alpha$ и $\beta$. Любое $2$-элементное множество имеет единственное $2$-элементное подмножество -- само себя. Поэтому, если $\alpha$ или $\beta$ содержит хотя бы одно $2$-элементное подмножество $A\in T^2$, то $\alpha$ или $\beta$ содержит также и все подмножества $A$

(при $p=2$ каждое $2$-элементное множество $A\in T^2$ является одновременно $p$-элементным подмножеством $A$ множества $S$, потому что здесь, по совпадению, $p=r=2$),

а если $\alpha=\varnothing$ или $\beta=\varnothing$, то, соответственно, либо $\beta$, либо $\alpha$ содержит все $2$-элементные подмножества множества $S$, то есть все подмножества $t$-элементного подмножества множества $S$. Значит, утверждение $R(2, t)=t$ верно.

Теперь $R(1, t)=1$ по теории графов. Здесь $p=1, q=t$, и пусть $t>1$. $p$-ребра будем красить в черный, $q$-ребра в белый цвет.

Возьмем $1$-вершинный граф $S$. Он не имеет ребер, и, значит, не имеет $t$ ребер и потому не может содержать $t$-вершинного полного белого подграфа. Однако, поскольку он не имеет ребер, то все его ребра черные, и поэтому он является полным чёрным графом и, значит, содержит полный чёрный подграф $S$ (то есть сам себя) из $1$ вершины. Таким образом, утверждение $R(1, t)=1$ верно.

$R(1, t)=1$ по теории множеств. Имеем $p=1, q=t$. Пусть и здесь $t>1$.

Пусть дано множество $S=\lbrace a\rbrace$. Поскольку оно одноэлементное, $r\leqslant S\rightarrow r=1$. Имеем $T^1=\big \lbrace \lbrace a\rbrace\big\rbrace$ -- множество всех его $1$-элементных подмножеств. Разобьем $T^1=\big \lbrace \lbrace a\rbrace\big\rbrace\cup \varnothing$ на два непересекающихся множества (это можно сделать единственным образом), то есть на $\alpha=\big \lbrace \lbrace a\rbrace\big\rbrace$ и $\beta=\varnothing$ (пустое множество $2$-элементных подмножеств). Мы видим, что не существует $t$-элементного подмножества множества $S$, все $1$-элементные подмножества которого принадлежали бы одному из множеств $\alpha$, $\beta$ (поскольку вообще не существует $t$-элементного подмножества множества $S$, так как $S$ состоит из единственного элемента, а $t>1$), но существует $1$-элементное ($p$-элементное) подмножество $\lbrace a\rbrace$ множества $S$ (то есть само множество $S$), все $1$-элементные ($r$-элементные) подмножества которого (то есть всего одно подмножество $\lbrace a\rbrace$) содержатся в $\alpha$, значит, утверждение $R(1, t)=1$ верно.

[Vladimir Pliassov]

Цитата:

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

Множества ребер, инцидентных $v$?

Цитата:

в чёрном и белом подграфе соответственно.

Эти черный и белый подграфы не обязательно полные?

Цитата:

Так как в графе $R(r-1,\;s)+R(r,\;s-1)=|M|+|N|+1$ вершин, согласно принципу Дирихле (комбинаторика), либо $|M|\geqslant R(r-1,\;s)$, либо $|N|\geqslant R(r,\;s-1)$.

Пусть $|M|\geqslant R(r-1,\;s)$. Тогда либо в $M$ (и следовательно во всём графе) есть белый $K_s$, что завершает доказательство,

Если $M$ это множество черных ребер, инцидентных $v$, то, во-первых, откуда в нем возьмется белый подграф $K_s$? а во-вторых, в множестве ребер $M$, по-моему, не может быть полного подграфа, так как это множество ребер, инцидентных одной и той же точке.

($K_s$ это ведь полный подграф?)

Цитата:

либо в $M$ есть чёрный $K_{r-1}$,

Если $K_{r-1}$ полный подграф, то его тоже не может быть (так как $M$ это множество ребер, инцидентных одной и той же точке).

Цитата:

который вместе с $v$ образует чёрный $K_{r}$.

Тоже не понятно, потому что $v$ это вершина, инцидентная всем черным ребрам, составляющим множество $M$.

Цитата:

Случай $|N|\geqslant R(r,\;s-1)$ рассматривается аналогично. Википедия, "Теорема Рамсея".

Или я все совсем не так понял?

[Vladimir Pliassov]

Здесь https://en.wikipedia.org/wiki/Ramsey%27s_theorem, кажется, лучше.

[mihaild]

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

Множества ребер, инцидентных $v$?

Множество вершин. Соединенных с $v$ черными и белыми ребрами соответственно.

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

Эти черный и белый подграфы не обязательно полные?

Чёрный подграф тут - подграф из вершин, соединенных с $v$ черным ребром. Он полный.

Дальше должно стать понятно.

[Vladimir Pliassov]

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

... Дальше должно стать понятно.

Да, спасибо, так понятно, и здесь то же говорится.

Утундрий в сообщении #1580390 писал(а):

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

Вот здесь базой берется не $R(n,\;1)=R(1,\;n)=1$, а $R(n, 2) = R(2, n) = n$.

Там написано, что доказательство существования $R(r, s)$ состоит в нахождении для него an explicit bound (явной границы?). Не знаю, что значит an explicit bound. Это какая-то (очевидно, верхняя) граница, но, я думаю, не supremum (не точная верхняя граница), иначе написали бы supremum. А ведь есть еще и нижняя граница $R(r, s)$?

Эта explicit bound, как я понимаю, и есть $R(r-1,s)+R(r,s-1)$, потому что, как доказывается, $R(r,s)\leq R(r-1,s)+R(r,s-1).$

А почему $R(r,s)\leq R(r-1,s)+R(r,s-1)$ это лемма? Потому что полное доказательство теоремы включает в себя еще и доказательство для случаев, когда $R(r-1, s)$ и $R(r, s-1)$ оба четные?

(Тогда $R(r,s)\leq R(r-1,s)+R(r,s-1)-1.$)

[mihaild]

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

Не знаю, что значит an explicit bound. Это какая-то (очевидно, верхняя) граница, но, я думаю, не supremum (не точная верхняя граница), иначе написали бы supremum.

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

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

А почему $R(r,s)\leq R(r-1,s)+R(r,s-1)$ это лемма?

Потому что это для двух цветов. Полная теорема Рамсея для произвольного числа цветов.

[Vladimir Pliassov]

1.

Цитата:

База индукции. $R(n,\;1)=R(1,\;n)=1$, так как 1-вершинный граф можно считать полным графом любого цвета. Википедия, "Теорема Рамсея"

Сомневаюсь в утверждении $R(n,\;1)=R(1,\;n)=1$.

Цитата:

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

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

Пусть $p$, $q$ и $r$ — натуральные числа, причём $p,\;q\geqslant r$.

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

При $r=1$ утверждение $R(n,\;1)=R(1,\;n)=1$ не верно:

имеем $T^1$ -- множество всех $1$-элементных подмножеств $S$. Поскольку $\vert T^1\vert=\vert S\vert$, то $\vert \alpha \vert + \vert \beta \vert=N\geqslant p+q-1$.

(Например, при $p=3, q=7, r=1$ будет $N(p, q, r)=N(3, 7, 1)\to N\geqslant 3+7-1=9$, иначе при $N=8$ и при $\vert \alpha \vert=2, \vert \beta \vert=6$ условие не будет соблюдено.)

Но тогда при $n\ne 1$ (и при $r=1$) утверждение $R(n,\;1)=1$, которое можно выразить как $N(n, 1, 1)=1$, не верно, так как здесь $p=n, q=1$, и поэтому должно быть $R(n, 1)=n+1-1=n$, то есть $N(n, 1, 1)=n$.

Это подтверждается здесь на стр. 80: $n(p, r, r)=p$.

Для того, чтобы утверждение $R(n,\;1)=1$ было верным, надо изменить условие:

Цитата:

... то либо существует $p$-элементное подмножество множества $S$, все $r$-элементные подмножества которого содержатся либо в $\alpha$, либо в $\beta$,

либо существует $q$-элементное подмножество (множества $S$), все $r$-элементные подмножества которого содержатся, соответственно, либо в $\beta$, либо в $\alpha$.

То есть если привязывать $p$ к $\alpha$ и $q$ к $\beta$, то при $r=1$ утверждение $R(n,\;1)=R(1,\;n)=1$ не верно, а если не привязывать, то оно верно.

Но не привязывать -- то есть изменить условие, -- нельзя.

2.

Еще одно доказательство того, что утверждение $R(n,\;1)=R(1,\;n)=1$ не верно: при $N=1$, и поэтому $r=1$.

Выше я написал (привожу с исправлениями):

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

Доказательство $R(1, t)=1$ по теории множеств. Имеем $p=1, q=t$. Пусть и здесь $t>1$.

Пусть дано множество $S=\lbrace a\rbrace$. Оно одноэлементное, и при этом $r\leqslant \vert S\vert$, поэтому $r=1$. Имеем $T^1=\big \lbrace \lbrace a\rbrace\big\rbrace$ -- множество всех $1$-элементных подмножеств $S$. Разобьем $T^1=\big \lbrace \lbrace a\rbrace\big\rbrace\cup \varnothing$ на два непересекающихся подмножества (это можно сделать единственным образом), то есть на $\alpha=\big \lbrace \lbrace a\rbrace\big\rbrace$ и $\beta=\varnothing$ (пустое множество $1$-элементных подмножеств). Мы видим, что не существует $t$-элементного подмножества множества $S$, все $1$-элементные подмножества которого принадлежали бы одному из множеств $\alpha$, $\beta$ (поскольку вообще не существует $t$-элементного подмножества множества $S$, так как $S$ состоит из единственного элемента, а $t>1$), но существует $1$-элементное ($p$-элементное) подмножество $\lbrace a\rbrace$ множества $S$ (то есть само множество $S$), все $1$-элементные ($r$-элементные) подмножества которого (то есть всего одно подмножество $\lbrace a\rbrace$) содержатся в $\alpha$, значит, утверждение $R(1, t)=1$ верно.

Но теперь я думаю: а почему разбить $T^1=\big \lbrace \lbrace a\rbrace\big\rbrace\cup \varnothing$ на два непересекающихся множества можно единственным образом, то есть на $\alpha=\big \lbrace \lbrace a\rbrace\big\rbrace$ и $\beta=\varnothing$? Ведь можно разбить наоборот: $\alpha=\varnothing$ и $\beta=\big \lbrace \lbrace a\rbrace\big\rbrace$. Тогда ни в $\alpha$ не будет всех подмножеств $p=1$-элементного подмножества $S$, ни в $\beta$ не будет всех подмножеств $q=t$-элементного подмножества $S$ -- потому что $t$-элементное подмножество множества $S$ не существует.

То есть снова выходит, что -- при $N=1$, $r=1$ -- утверждение $R(1, t)=1$ не верно.

Если же кто-то скажет, что именно потому, что $t$-элементное подмножество множества $S$ не существует, все его подмножества есть в любом множестве, то я попрошу предъявить эти подмножества в множестве $\beta$.

3.

Во всяком случае, в п. 1, по-моему, показано, что при $r=1$ утверждение $R(1, t)=1$ не верно, а при $r=2$ имеем $p, q\geqslant 2$, так как $p,\;q\geqslant r$, и поэтому $R(1, t)$ превращается в $R(2, t)$ [тогда $R(t, 2) = R(2, t) = t$].

(При этом $\vert S\vert$ не может быть равно $1$, поэтому не приходится говорить об $1$-вершинном графе.)

Так что я не вижу обстоятельств, в которых утверждение $R(n,\;1)=R(1,\;n)=1$ было бы верно (и потому могло бы служить базой индукции).

[mihaild]

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

При $r=1$ утверждение $R(n,\;1)=R(1,\;n)=1$ не верно:

Уже здесь какая-то путаница. В этом утверждении вообще нет $r$.

На всякий случай: формулировка для теории графов - соответствует случаю $r = 2$ для множеств (в этом случае $r$-элементные подмножества интерпретируются как рёбра графов). В обозначениях рувики, $N(p, q, 2) = R(p, q)$ (это как раз пример, почему не надо учить математику по википедии - совмещать $N(p, q, r)$ и $R(r, s)$ с таким именованием переменных в одной статье - идея крайне неудачная).

[Vladimir Pliassov]

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

формулировка для теории графов - соответствует случаю $r = 2$ для множеств

Я это понимаю.

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

(в этом случае $r$-элементные подмножества интерпретируются как рёбра графов)

А при $r>2$ -- как рёбра гиперграфов.

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

В обозначениях рувики, $N(p, q, 2) = R(p, q)$ (это как раз пример, почему не надо учить математику по википедии - совмещать $N(p, q, r)$ и $R(r, s)$ с таким именованием переменных в одной статье - идея крайне неудачная).

По-моему, тоже. Поэтому в одном из предыдущих постов я унифицировал обозначения: взял $N(p, q, r)$ и $R(p, q)$. Но часто приходится переходить от одних обозначений к другим, например, потому что у разных авторов по одной и той же теме разные обозначения.

Я использую не только Википедию, я начал с Верещагина, Шеня (https://www.mccme.ru/free-books/shen/sh ... art1-2.pdf), у них нет доказательства, взял Харари (https://stugum.files.wordpress.com/2014 ... theory.pdf), но и у него нет, он отсылает к Холлу (http://mathscinet.ru/files/HallM.pdf), у Холла доказывается для множеств (при произвольном $r$) в принципе с той же формулировкой, что и в русской Википедии, хотя немного более сложной. Но у него нет доказательства для графов, его я нашел только в Википедии, причем, в русском варианте что-то не так, а в английском все было понятно (правда, я еще не дошел до четных $R(r-1,\;s)$ и $ R(r,\;s-1)$). Так что только в Википедии и нашел. А у кого еще можно найти?

Кстати, многоцветный случай я тоже нашел только в Википедии.

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

Уже здесь какая-то путаница. В этом утверждении вообще нет $r$.

Я имею в виду, что в выражении $R(p, q)$ подразумевается $r$, то есть $N(p, q, r)$ и $R(p, q)$ это одно и то же, но в $R(p, q)$ предполагается, что значение $r$ фиксировано и известно.

Вообще, за основу $R(p, q)$, которое используется для графов, я беру $N(p, q, r)$ (у Холла $n(p, q, r)$) для множеств. При этом, мне кажется, что ограничиваться только случаем $r=2$ (то есть графами) не следует, а в $N(p, q, r)$ переменная $r$ может принимать различные значения. Это, как я понимаю, выражение и для гиперграфов, хотя это не главное, и вообще, по моему, здесь можно было бы обойтись без гиперграфов (граф это частный случай гиперграфа?), одной только теорией множеств, хотя обращение к (гипер-) графам очень помогает в понимании.

А числа Рамсея это только для $r=1$ и $r=2$? Если так, то это странно.

В предыдущем посте я пытался разобраться в случае $r=1$, там, по-моему, все не так просто.

Там я написал, что утверждение $R(1, t)=1$ не верно.

[mihaild]

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

А у кого еще можно найти?

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

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

но в $R(p, q)$ предполагается, что значение $r$ фиксировано и известно

Более того, предполагается что $r = 2$. Это обозначение - $R(p, q)$ - для случая графов.

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

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

Да, граф - это частный случай гиперграфа.
В чём угодно можно обойтись одной теорией множеств (только не говорите категорщикам), в частности теория графов формулируется в терминах теории множеств. Но это часто не очень удобно.

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

А числа Рамсея это только для $r=1$ и $r=2$?

Тут есть разные варианты.

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

Там я написал, что утверждение $R(1, t)=1$ не верно

Если уж говорить об $r$, то давайте использовать какую-то нотацию, где $r$ есть. Например Холла. Можете записать в его нотации, какой случай у Вас вызывает сомнения?

[Vladimir Pliassov]

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

Если уж говорить об $r$, то давайте использовать какую-то нотацию, где $r$ есть. Например Холла. Можете записать в его нотации, какой случай у Вас вызывает сомнения?

$n(p, 1, 1)=1$ -- не верно, $n(p, 1, 1)=p$ -- верно, потому что, вообще, $n(p, r, r)=p$ (Холл стр. 80). Так что при $r=1$ имеем $R(1, t)=t$, то есть $R(1, t)\ne1$.

А при $r=2$ будет $p, q\geqslant 2$, так как по условию $p,\;q\geqslant r$, и поэтому имеем $n(t, 2, 2) = t$,

то есть $R(1, t)$ с подразумеваемым $r=1$ превращается в $R(2, t)$ с подразумеваемым $r=2$.

[тогда $R(t, 2) = R(2, t) = t$].

($R(1, t)$ с подразумеваемым $r=2$ быть не может.)

(При этом $\vert S\vert$ не может быть равно $1$, поэтому не приходится говорить об $1$-вершинном графе.)

Так что я не вижу обстоятельств, в которых утверждение $R(n,\;1)=R(1,\;n)=1$ было бы верно -- ни при $r=1$, ни при $r=2$.

В позапрошлом посте об этом подробнее.