Теория Рамсея (стр. 2 из 4)

В своих воспоминаниях Шекереш так описывает последующие события: «Мы вскоре осознали, что простые рассуждения не подходят, и появилось волнующее чувство, что в нашем кружке впервые возник новый тип геометрических задач». Шекереш показал, что существует такое число n, что если n точек лежат на плоскости так, что никакие три из них не находятся на одной прямой, то среди них всегда можно найти k точек, образующих выпуклый k-угольник. Другими словами, если точек достаточно много, всегда можно найти их подмножество, образующее многоугольник с заданным числом сторон. Доказав это, Шекереш заново открыл теорему Рамсея, хотя никто из их группы в то время не знал о ней.

В 1934году Эрдёш и Шекереш опубликовали свои результаты, хотя ни они, ни кто-либо другой до сих пор не смогли доказать гипотезу Эрдёша о том, что числа точек n=1+2^k–2 достаточно. Эрдёш часто называет эту совместную публикацию «статьёй со счастливым концом», поскольку вскоре после её опубликования Шекереш и Клейн поженились. Эрдёш же стал самым продуктивным математиком нашего столетия.

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

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

Следовательно, если три человека знакомы друг с другом, то рёбра между соответствующими точками образуют красный треугольник, а если эти трое незнакомы, то образуется синий треугольник. Головоломку о вечеринке тогда можно сформулировать так: верно ли, что если каждое ребро, соединяющее любые две из шести точек, окрасить в синий или красный цвет произвольным образом, то всегда возникает либо синий, либо красный треугольник?

Задача, которую изучал Эрдёш, представляет собой обобщение этой задачи. Он определил полную сеть как набор точек, каждая из которых соединена рёбрами со всеми остальными. Затем он задался вопросом: какова наименьшая полная сеть, которая будучи произвольным образом раскрашена в красный и синий цвет, обязательно содержит полную сеть красного или синего цвета? Ответ следующий: полная сеть — из шести точек. Эту задачу и её решение удобнее выразить так: число Рамсея (R) для трёх красных и трёх синих равно шести.

А как насчет числа Рамсея для пяти красных и трёх синих? Другими словами, какова наименьшая полная сеть, которая будучи произвольным образом раскрашена в красный и синий цвет, обязательно содержала бы либо красную сеть из пяти точек, либо синюю сеть из трёх точек? Число Рамсея для пяти красных и трёх синих равно 14, что доказали только в 1955году Роберт Гринвуд из Университета шт.Техас в Остине и Эндрю Глисон из Гарвардского университета.

5 < R(3,3) = 6	8 < R(3,4) = 9	13 < R(3,5) = 14
17 < R(3,6) = 18		22 < R(3,7) = 23
27 < R(3,8) ≤ 29		35 < R(3,9) = 36

Рис.2. Числа Рамсея определяются как наименьшее значение n, для которого в любой группе из n точек либо некоторая группа из j точек образует полную сеть красных рёбер, либо некоторая группа из k точек образует полную сеть синих рёбер. Рисунки показывают, как велико должно быть конкретное число Рамсея. На первой диаграмме изображены пять точек, соединённые красными и синими рёбрами таким способом, что никакие три точки не образуют ни красной, ни синей полной сети. Следовательно, из первой диаграммы можно вывести, что число Рамсея для трёх красных и трёх синих больше пяти. Аналогично можно утверждать, что из второй диаграммы следует, что число Рамсея для трёх красных и четырёх синих больше восьми. Другими более сложными методами можно показать, что число Рамсея для трёх красных и трёх синих равно шести, а число Рамсея для трёх красных и четырёх синих равно девяти. Все точно известные числа Рамсея приведены выше, кроме числа Рамсея для четырёх красных и четырёх синих, диаграмма для которого изображена на рис.1. (На некоторых диаграммах синие рёбра для простоты не показаны.) Относительно числа Рамсея для трёх красных и восьми синих было доказано, что оно больше 27 и меньше или равно 29. Недавно было показано (но пока не подтверждено), что оно равно 28.

Числа Рамсея чрезвычайно трудно вычислять. Усилиями поколений математиков и компьютеров удалось найти лишь семь чисел Рамсея, которые приведены на рис.2. Чтобы наглядно продемонстрировать трудность вычисления чисел Рамсея, Эрдёш часто рассказывает следующий анекдот. Инопланетяне вторглись на Землю и угрожают уничтожить её через год, если человечество не сможет найти число Рамсея для пяти красных и пяти синих. Мы могли бы мобилизовать лучшие умы и самые быстродействующие компьютеры, и тогда в течение года мы, возможно, сумели бы найти искомое значение. Однако если бы инопланетяне потребовали от нас найти число Рамсея для шести красных и шести синих, то у нас не осталось бы иного выбора, как нанести упреждающий удар.

Эрдёш всё же нашёл способ получить некоторое представление о том, насколько большим должно быть число Рамсея. Что если он сможет найти красно-синюю раскраску большой полной сети, не содержащую ни красной, ни синей сети из трёх точек? Такая раскраска полной сети из пяти точек показана на рис.2. Отсюда следует, что число Рамсея для трёх красных и трёх синих должно быть больше пяти. Пять есть нижняя граница для этого числа Рамсея.

В 1947году Эрдёш предложил необычный метод отыскания нижней границы любого числа Рамсея: бросание монеты. Он предпринял мысленный эксперимент, в котором каждое ребро полной сети из, скажем, миллиона точек окрашивалось в соответствии с результатом бросания «настоящей» монеты (т.е. монеты, для которой вероятность выпадения орла или решки строго одинакова и равна 1/2. — Перев.). Ребро окрашивается в красный цвет, если выпадает решка, и в синий, если выпадает орёл. Затем он попытался доказать, что число Рамсея, скажем, для 34 красных и 34 синих больше миллиона. Эксперимент считается успешным, если в результате такой случайной раскраски не образуется ни красной, ни синей сети из 34 точек.

Как бы он мог гарантировать успех? Любые 34 точки соединяются 561 ребром. Если первое бросание предписывает синий цвет для первого ребра, то для получения синей сети необходимо, чтобы следующие 560 бросаний тоже предписывали синий цвет. Вероятность того, что это произойдёт, равна 2^–561. Вероятность появления красной сети точно такая же, так что общая вероятность возникновения одноцветной сети вдвое больше, или примерно 2,6×10^–169.

Теперь вспомним, что число наборов из 34 точек, выбранных из миллиона точек, равно

1000000! 34! · 999966!

≈3,4×10165.

Тем самым можно ожидать, что из всех возможных полных сетей из 34 точек одноцветными будут 3,4×10¹⁶⁵×2,6×10^–169, или приблизительно 0,001. Итак, в 99,9% случаев мысленный эксперимент будет успешным, одноцветные наборы из 34 точек не возникнут.

Затем Эрдёш применил тонкое доказательство от противного. Он предположил, что никакая схема раскраски не является успешной. Тогда мысленный эксперимент будет иметь нулевую вероятность успеха, что, как ему уже известно, не соответствует действительности. Значит, это предположение должно быть ошибочным, т.е. должна существовать успешная схема раскраски (не с вероятностью 99,9%, а с абсолютной достоверностью). Существование такой раскраски означает, что один миллион является нижней границей для 34 красных и 34 синих.

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