27<R(3,8)<29 35 <R(3,9) = 36
Рис.3. Числа Рамсея определяются как наименьшее значение n, для которого в любой группе из n точек либо некоторая группа из j точек образует полную сеть красных рёбер, либо некоторая группа из к точек образует полную сеть синих рёбер. Рисунки показывают, как велико должно быть конкретное число Рамсея. На первой диаграмме изображены пять точек, соединённые красными и синими рёбрами таким способом, что никакие три точки не образуют ни красной, ни синей полной сети. Следовательно, из первой диаграммы можно вывести, что число Рамсея для трёх красных и трёх синих больше пяти. Аналогично можно утверждать, что из второй диаграммы следует, что число Рамсея для трёх красных и четырёх синих больше восьми. Другими более сложными методами можно показать, что число Рамсея для трёх красных и трёх синих равно шести, а число Рамсея для трёх красных и четырёх синих равно девяти. Все точно известные числа Рамсея приведены выше, кроме числа Рамсея для четырёх красных и четырёх синих, диаграмма для которого изображена на рис.1. (На некоторых диаграммах синие рёбра для простоты не показаны.) Относительно числа Рамсея для трёх красных и восьми синих было доказано, что оно больше 27 и меньше или равно 29. Недавно было показано (но пока не подтверждено), что оно равно 28.
Числа Рамсея чрезвычайно трудно вычислять. Усилиями поколений математиков и компьютеров удалось найти лишь семь чисел Рамсея, которые приведены на рис.3. Чтобы наглядно продемонстрировать трудность вычисления чисел Рамсея, Эрдёш часто рассказывает следующий анекдот. Инопланетяне вторглись на Землю и угрожают уничтожить её через год, если человечество не сможет найти число Рамсея для пяти красных и пяти синих. Мы могли бы мобилизовать лучшие умы и самые быстродействующие компьютеры, и тогда в течение года мы, возможно, сумели бы найти искомое значение. Однако если бы инопланетяне потребовали от нас найти число Рамсея для шести красных и шести синих, то у нас не осталось бы иного выбора, как нанести упреждающий удар.
Эрдёш всё же нашёл способ получить некоторое представление о том, насколько большим должно быть число Рамсея. Что если он сможет найти красно-синюю раскраску большой полной сети, не содержащую ни красной, ни синей сети из трёх точек? Такая раскраска полной сети из пяти точек показана на рис.3. Отсюда следует, что число Рамсея для трёх красных и трёх синих должно быть больше пяти. Пять есть нижняя граница для этого числа Рамсея.
В 1947году Эрдёш предложил необычный метод отыскания нижней границы любого числа Рамсея: бросание монеты. Он предпринял мысленный эксперимент, в котором каждое ребро полной сети из, скажем, миллиона точек окрашивалось в соответствии с результатом бросания "настоящей" монеты (т.е. монеты, для которой вероятность выпадения орла или решки строго одинакова и равна 1/2. - Перев.). Ребро окрашивается в красный цвет, если выпадает решка, и в синий, если выпадает орёл. Затем он попытался доказать, что число Рамсея, скажем, для 34 красных и 34 синих больше миллиона. Эксперимент считается успешным, если в результате такой случайной раскраски не образуется ни красной, ни синей сети из 34 точек.
Как бы он мог гарантировать успех? Любые 34 точки соединяются 561 ребром. Если первое бросание предписывает синий цвет для первого ребра, то для получения синей сети необходимо, чтобы следующие 560 бросаний тоже предписывали синий цвет. Вероятность того, что это произойдёт, равна . Вероятность появления красной сети точно такая же, так что общая вероятность возникновения одноцветной сети вдвое больше, или примерно .
Теперь вспомним, что число наборов из 34 точек, выбранных из миллиона точек, равно
Тем самым можно ожидать, что из всех возможных полных сетей из 34 точек одноцветными будут , или приблизительно 0,001. Итак, в 99,9% случаев мысленный эксперимент будет успешным, одноцветные наборы из 34 точек не возникнут.
Затем Эрдёш применил тонкое доказательство от противного. Он предположил, что никакая схема раскраски не является успешной. Тогда мысленный эксперимент будет иметь нулевую вероятность успеха, что, как ему уже известно, не соответствует действительности. Значит, это предположение должно быть ошибочным, т.е. должна существовать успешная схема раскраски (не с вероятностью 99,9%, а с абсолютной достоверностью). Существование такой расскраски означает, что один миллион является нижней границей для 34 красных 34 синих.
Такое рассуждение, известное как вероятностный метод, даёт наилучшие нижние оценки для чисел Рамсея. Однако этот метод не содержит никаких указаний на то, как в действительности следует производить желаемую раскраску. В попытках получить такие раскраски исследователи используют богатый арсенал приёмов из теории чисел, теории множеств и других разделов математики. Хотя полученные при этом результаты интересны, они пока не достигают оценок, которые даёт метод бросания монеты.