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

[Vladimir Pliassov]

Цитата:

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

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

Здесь речь идет о раскраске именно ребер, а не вершин, поэтому, как я понимаю, если нет ребер, то нет и раскраски.

А как же тогда понять следующее:

Цитата:

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

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

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

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

Я имею в виду случай, когда имеется только одна вершина, в этом случае нет ни одного ребра (и раскрашивать нечего), а тогда, по-моему, нет и графа, во всяком случае, по следующему определению:

Цитата:

Граф — математическая абстракция реальной системы любой природы, объекты которой обладают парными связями. Граф как математический объект есть совокупность двух множеств — множества самих объектов, называемого множеством вершин, и множества их парных связей, называемого множеством рёбер. Элемент множества рёбер есть пара элементов множества вершин. Википедия, "Граф".

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

То есть, как я понимаю, графа без ребер не бывает (опять же не в смысле изолированных вершин).

(А ребер нет только в одном случае: когда имеется всего одна вершина.)

Цитата:

Кликой неориентированного графа называется подмножество его вершин, любые две из которых соединены ребром. Википедия, "Клика".

Исходя из этого, одновершинная клика не определена (так как, если имеется только одна вершина, то не имеется двух вершин).

Цитата:

Связный граф — граф, содержащий ровно одну компоненту связности. Это означает, что между любой парой вершин этого графа существует как минимум один путь. Википедия, "Связный граф".

Исходя из этого, одновершинный связный граф не определен (так как не имеет пары вершин).

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

[Утундрий]

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

[mihaild]

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

Здесь речь идет о раскраске именно ребер, а не вершин, поэтому, как я понимаю, если нет ребер, то нет и раскраски

Более того, тут говорится о полном графе.

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

Возможен ли, вообще, 1-вершинный граф?

Может, конечно, и даже нуль-вершинный.

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

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

Да, в графе с одной вершиной нет ребер. Но никто не запрещает множеству связей быть пустым.

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

Исходя из этого, одновершинная клика не определена (так как, если имеется только одна вершина, то не имеется двух вершин)

Почему же не определена?
Я утверждаю, что любые две вершины соединены ребром. Если Вы считаете, что это не так - предъявите пару вершин, которые не соединены.
Точно так же как любое четное простое число, большее двух, делится на 17, а все крокодилы в моей комнате синего цвета.

Вообще, Вас, видимо, смущает квантор всеобщности по пустому множеству. Это распространенная проблема, надо просто привыкнуть, на самом деле ничего загадочного в этой ситуации нет, всё следует из определений.

[Vladimir Pliassov]

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

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

Спасибо, я попробую, когда разберусь.

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

Я утверждаю, что любые две вершины соединены ребром. Если Вы считаете, что это не так - предъявите пару вершин, которые не соединены.
Точно так же как ... все крокодилы в моей комнате синего цвета.

В видео "Дискретный анализ 1. Теорема Рамсея." на YouTube, $8' 30''$, лектор говорит: "Одна вершина образует клику по определению. Там нет ни одного ребра, но это же не мешает быть справедливым тому факту, что все ребра, какие было возможно, мы провели." Но мне кажется, что утверждать, будто мы провели какие-то ребра, в то время, как мы этого не сделали, это значит говорить неправду. Я думаю, было бы лучше сказать: "Там нет ни одной пары вершин, не соединенных ребрами," -- это была бы правда.

Как бы там ни было, в одновершинном графе ни одного ребра нет:

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

Да, в графе с одной вершиной нет ребер.

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

Но никто не запрещает множеству связей быть пустым.

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

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

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

Хотя мне самому не нравится, что мы говорим: "Это полный граф и все, не спрашивайте." Может быть, усмотреть что-то в том, что вершина естественно связна сама с собой -- то есть связна сама с собой не потому, что нет таких ребер, которые мы могли бы провести, но не провели, -- а просто потому, что она, как и любой объект, связна сама с собой? Может быть, связность для всех графов, имеющих больше одной вершины, определить как наличие ребер между вершинами, а связность для одновершинного графа определить как естественную связность объекта с самим собой?

Но, во всяком случае, понятно, что в одновершинном графе найдется либо $n$-вершинная (при любом $n\in \mathbb N$), либо $1$-вершинная клика, то есть что $R(n,\;1)=R(1,\;n)=1$.

Лемма, которую надо сначала доказать, формулируется как $R(r,\;s)\leqslant R(r-1,\;s)+R(r,\;s-1).$ Значит, базой индукции будет $R(1,\;1)\leqslant R(n,\;1)+R(1,\;n)=2$, правильно? Или база индукции это и есть $R(n,\;1)=R(1,\;n)=1$? Тут я не понимаю.

[svv]

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

Точно так же как любое четное простое число, большее двух, делится на 17, а все крокодилы в моей комнате синего цвета.

Интересно, что в то же время все эти крокодилы и розового цвета, а любое четное простое, большее двух, не делится на $17$.

[mihaild]

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

Но мне кажется, что утверждать, будто мы провели какие-то ребра, в то время, как мы этого не сделали, это значит говорить неправду

А мы не говорим, что мы провели какие-то ребра. Мы говорим, что провели все ребра, какие возможно.
Вполне корректно сказать "мы сделали всё что возможно" если сделать невозможно ничего, и мы ничего не сделали:)

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

То есть бывает граф без единого ребра (в единственном случае: когда граф имеет всего одну вершину)

Почему? Легко может быть граф с 42 вершинами и без ребер.

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

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

Нужно чтобы были раскрашены все ребра. Покажите хоть одно нераскрашенное.

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

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

Нет, не лучше. Тут никакие особые случаи вводить не надо, всё что нужно однозначно получается из общих определений.
Ещё раз: совершенно корректны утверждения вида "все элементы пустого множества обладают свойством $X$". Более того, такие утверждения истинны независимо от того, что такое $X$.

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

однако не потому, что все его вершины соединены ребрами (это не так, поскольку ребер нет)

Это именно что так. Нас не спрашивают, есть ли ребра. Нас спрашивают, есть ли вершины, ребрами не соединенные. И вершин таких нет.

Перечитайте внимательно это и предыдущее моё сообщения. Понимание фраз вида "все ребра такие-то" в случае, когда ребер нет - гораздо более фундаментальная штука, чем теория Рамсея, и с этим для изучения математики критически важно разобраться.

[Евгений Машеров]

(Оффтоп)

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

Вполне корректно сказать "мы сделали всё что возможно" если сделать невозможно ничего, и мы ничего не сделали:)

- Товарищ генерал, все ваши приказания выполнены!
- Так я ж ничего не приказывал!
- А я ничего и не делал!

[Vladimir Pliassov]

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

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

То есть бывает граф без единого ребра (в единственном случае: когда граф имеет всего одну вершину)

Почему? Легко может быть граф с 42 вершинами и без ребер.

Я имел в виду, что когда между некоторыми двумя вершинами есть ребро, то это ребро можно окрасить, скажем, в черный цвет, а когда между некоторыми двумя вершинами нет ребра, то можно считать, что оно есть и что оно белого цвета.

В этом смысле не бывает графа без ребер и не бывает неполных графов.

Именно это имеется в виду в приведенной в первом сообщении формулировке теоремы на языке теории графов? Там ведь нет ни одной пары вершин, не соединенных ребрами?

[zykov]

По определению универсального квантифаера $\forall x\in S : P(x)$ он всегда имеет значение "ИСТИНА", если множество $S$ пустое. Независимо от предиката $P$.
(Например тут.)

Логика тут такая, что при конечном множестве $S$ эта запись эквивалентна $P(x_1) \land P(x_2) \land ... \land P(x_n)$.
Если убираем из множества один элемент, то этот список сокращается на один элемент $P(x_1) \land P(x_2) \land ... \land P(x_{n-1})$.
Если убрать один элемент из $P(x_1)$, что останется?
Если бы было $FALSE \land P(x_1) \land P(x_2) \land ... \land P(x_n)$, то это значение всегда "ЛОЖЬ", что не подходит.
Если $TRUE \land P(x_1) \land P(x_2) \land ... \land P(x_n)$, то всё работает как надо.
При удалении одного элемента из $TRUE \land P(x_1)$ остаётся $TRUE$.

Так и тут. Нет рёбер, значит множество рёбер пустое. Значит универсальный квантифаер по всем рёбрам имеет значение "ИСТИНА" независимо от предиката (хоть даже предикат - это константа FALSE).

[mihaild]

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

а когда между некоторыми двумя вершинами нет ребра, то можно считать, что оно есть и что оно белого цвета

Лучше так считать не надо, это только запутает.
Есть естественная биекция между графами, раскрашенными в $n$ цветов, и полными графами, раскрашенными в $n + 1$ цвет с некоторым выделенным цветом. Особенно уместно она выглядит для $n = 1$.
Но не всегда наличие биекции - повод отождетсвлять объекты, и в данном случае как раз такое отождествление не нужно. Это не какой-то глубокий математический факт, а просто результат наблюдений (возможно даже зависящий от способа изложения теории).

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

В этом смысле не бывает графа без ребер

Графы без рёбер бывают даже в этом смысле.

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

Именно это имеется в виду в приведенной в первом сообщении формулировке теоремы на языке теории графов?

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

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

квантифаер

В математической традиции - квантор (а в программировании да, квантифаер).

[zykov]

mihaild

(Оффтоп)

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

В математической традиции - квантор (а в программировании да, квантифаер).

Это калька с английского "universal quantifier".

[mihaild]

(zykov)

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

Это калька с английского "universal quantifier"

Это понятно. Просто в математике quantifier переводят как квантор.

[Vladimir Pliassov]

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

Так и тут. Нет рёбер, значит множество рёбер пустое. Значит универсальный квантифаер по всем рёбрам имеет значение "ИСТИНА" независимо от предиката (хоть даже предикат - это константа FALSE).

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

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

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

а когда между некоторыми двумя вершинами нет ребра, то можно считать, что оно есть и что оно белого цвета

Лучше так считать не надо, это только запутает.

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

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

Есть естественная биекция между графами, раскрашенными в $n$ цветов, и полными графами, раскрашенными в $n + 1$ цвет с некоторым выделенным цветом.

Вы имеете в виду, что в графе, в котором ребра раскрашены в $n$ цветов, есть пары вершин, между которыми нет ребер? И в полном графе (с тем же числом вершин), раскрашенном в $n + 1$ цвет выделяется цвет тех ребер, которых не было в первом графе?

А, вообще, может ли у раскрашенного графа недоставать ребер?

Или раскрашиваться может только полный граф?

[Под раскрашенными графами я здесь, вообще, имею в виду графы с раскрашенными ребрами (а не вершинами)]

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

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

В этом смысле не бывает графа без ребер

Графы без рёбер бывают даже в этом смысле.

Да, это я забыл: одновершинный граф.

[mihaild]

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

Вы имеете в виду, что в графе, в котором ребра раскрашены в $n$ цветов, есть пары вершин, между которыми нет ребер? И в полном графе (с тем же числом вершин), раскрашенном в $n + 1$ цвет выделяется цвет тех ребер, которых не было в первом графе?

Да, именно так.

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

А, вообще, может ли у раскрашенного графа недоставать ребер?

Может, конечно. Граф - это пара (множество вершин, множество ребер). Раскрашенный граф - это пара (граф, функция из множества ребер в цвета).

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

Да, это я забыл: одновершинный граф.

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

[zykov]

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

Или раскрашиваться может только полный граф?

С чего вдруг?
Чтобы не путаться, рассуждайте на языке множеств.
Граф - пара множеств (множество вершин и множество рёбер, т.е. множество подмножеств размера 2 множества врешин).
Раскраска - функция из множества рёбер в множество цветов.
Соответствие - множество упорядоченных пар из первого множества и из второго. Функция - соответствие, в котором может быть не более 1 пары для любого элемента первого множества.

Если множество рёбер пустое, то это не мешает существованию функции. Просто множество пар этой функции тоже пустое множество.