Теорема о друзьях и незнакомцах: Гарантированное наличие трио

Введение

В любой группе из 6 человек, найдётся как минимум 3 человека, которые не знакомы друг с другом, либо как минимум 3 человека, которые знакомы. Теорема о друзьях и незнакомцах Пола Эрдоша, Альфреда Рени и Веры Т. Сос характеризует графы, в которых любые две вершины имеют ровно одного общего соседа. Теорема о друзьях и незнакомцах — математическая теорема в области математики, называемой теорией Рамси.

Заявление

Предположим, что на вечеринке есть шесть человек. Рассмотрим любых двух из них. Они могут встретиться впервые – в этом случае мы будем называть их взаимными незнакомцами; или они могли встречаться раньше – в этом случае мы будем называть их взаимными знакомыми. Теорема утверждает:

На любой вечеринке из шести человек найдется по крайней мере трое, которые являются (попарно) взаимными незнакомцами или взаимными знакомыми.

Переход на графико-теоретическую установку

Доказательство теоремы требует лишь трехступенчатой логики. Удобно сформулировать задачу на языке теории графов. Предположим, граф имеет 6 вершин, и каждая пара (различных) вершин соединена ребром. Такой граф называется полным графом (поскольку больше ребер быть не может). Полный граф на n вершинах обозначается символом K_n. Теперь возьмем K₆. Он содержит всего 15 ребер. Пусть 6 вершин представляют 6 человек в нашей компании. Окрасим ребра в красный или синий цвет в зависимости от того, являются ли два человека, представленные вершинами, соединенными ребром, взаимными незнакомцами или взаимными знакомыми, соответственно. Теперь теорема утверждает:

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

Доказательство

Выберите любую вершину; назовите её P. Из вершины P выходит пять рёбер. Каждое из них окрашено в красный или синий цвет. Принцип Дирихле утверждает, что по крайней мере три из них должны быть одного цвета; ведь если рёбер одного цвета, скажем красного, меньше трёх, то рёбер другого цвета, синего, будет не менее трёх. Пусть A, B, C – другие концы этих трёх рёбер, все окрашены в один и тот же цвет, скажем синий. Если какое-либо из рёбер AB, BC, CA окрашено в синий цвет, то вместе с двумя рёбрами, идущими из P к концам этого ребра, оно образует синий треугольник. Если же ни одно из рёбер AB, BC, CA не окрашено в синий цвет, то все три ребра окрашены в красный цвет, и мы получаем красный треугольник ABC.

Газета Рамзи

Абсолютная простота этого аргумента, который столь убедительно приводит к весьма интересному заключению, и делает эту теорему привлекательной. В 1930 году в статье под названием «О проблеме формальной логики» Фрэнк Рэмси доказал весьма общую теорему (ныне известную как теорема Рэмси), частным случаем которой является данная теорема. Эта теорема Рэмси заложила основу области, известной как теория Рамси в комбинаторике.

Границы теоремы

Вывод теоремы не выполняется, если заменить группу из шести человек группой, состоящей менее чем из шести человек. Чтобы это показать, приведем раскраску K5 в красный и синий цвета, не содержащую одноцветный треугольник. Изобразим K5 в виде пятиугольника, окружающего звезду (пентаграмму). Окрасим ребра пятиугольника в красный цвет, а ребра звезды – в синий. Таким образом, 6 – наименьшее число, для которого справедливо заключение теоремы. В теории Рамзи этот факт записывается как: