1 2
   Рамсей доказал свою теорему в качестве первого шага, пытаясь продемонстрировать справедливость тезиса Рассела в специальном случае. Как оказалось, он мог бы выполнить эту задачу другими средствами. Ранее Рамсей доказал теорему, не имеющую отношения к тезису, который он обосновал и который он никогда бы не смог доказать в общем случае.
   Так обстояли дела до 1933 года, когда два венгерских математика, Пауль Эрдёш и Джордж Шекереш, заново открыли теорию Рамсея. В основном благодаря их усилиям эта теория стала популярной в среде математиков. В то время Эрдёш был девятнадцатилетним студентом Будапештского университета, а Шекереш незадолго до этого получил диплом инженера-химика в Будапештском политехническом институте. Вместе с группой друзей-студентов они почти каждое воскресенье встречались в загородном парке, в основном для разговоров о математике.
   Зимой 1933года одна из студенток, Эстер Клейн, предложила друзьям решить любопытную задачу; доказать, что если пять точек на плоскости расположены таким образом, что никакие три точки не лежат на одной прямой, то обязательно найдутся четыре из них, образующие выпуклый четырёхугольник. (К выпуклым фигурам относится, скажем, правильный шестиугольник, но не относится пятиконечная звезда. Более строго, многоугольник называется выпуклым, если всякий отрезок, соединяющий его вершины, лежит внутри этого многоугольника.)
   Позволив друзьям вдоволь поразмышлять над этой задачей, Клейн представила доказательство (см. рис.2).







Рис.2. Теория Рамсея была заново открыта в 1933году, когда молодая студентка Эстер Клейн предложила следующую геометрическую задачу: доказать, что если пять точек расположены на плоскости и никакие три из них не лежат на одной прямой, то какие-нибудь четыре из них всегда образуют выпуклый четырёхугольник. Любая конфигурация, удовлетворяющая условиям задачи, относится к одному из трёх случаев, показанных на рисунке. Простейший случай - тот, когда выпуклая оболочка (т.е. выпуклый многоугольник, охватывающий все точки) есть четырёхугольник. Если выпуклая оболочка является пятиугольником, то любые четыре точки можно соединить так, что они образуют четырёхугольник. Треугольная выпуклая оболочка всегда содержит внутри две точки; здесь - D и Е. Линия DE делит треугольник на две части так, что две точки, А и В, лежат по одну сторону от неё. Четыре точки ABCD должны образовывать выпуклый четырёхугольник.
     Эрдёш и Клейн быстро нашли обобщение исходной задачи. Они поняли, что пять из девяти точек на плоскости всегда образуют выпуклый пятиугольник. Тогда они предложили новую задачу: если число точек на плоскости равно 1+2к-2, где к=3,4, 5 ... и т.д., то можно ли всегда выбрать к точек, образующих выпуклый многоугольник?
    В своих воспоминаниях Шекереш так описывает последующие события: "Мы вскоре осознали, что простые рассуждения не подходят, и появилось волнующее чувство, что в нашем кружке впервые возник новый тип геометрических задач". Шекереш показал, что существует такое число n, что если n точек лежат на плоскости так, что никакие три из них не находятся на одной прямой, то среди них всегда можно найти к точек, образующих выпуклый k-угольник. Другими словами, если точек достаточно много, всегда можно найти их подмножество, образующее многоугольник с заданным числом сторон. Доказав это, Шекереш заново открыл теорему Рамсея, хотя никто из их группы в то время не знал о ней.
     В 1934году Эрдёш и Шекереш опубликовали свои результаты, хотя ни они, ни кто-либо другой до сих пор не смогли доказать гипотезу Эрдёша о том, что числа точек n=l+2k-2 достаточно. Эрдёш часто называет эту совместную публикацию "статьёй со счастливым концом", поскольку вскоре после её опубликования Шекереш и Клейн поженились. Эрдёш же стал самым продуктивным математиком нашего столетия.
    Эрдёш заинтересовался идеей Рамсея о том, что всякая достаточно большая структура должна содержать регулярную подструктуру заданного размера. Но ему хотелось узнать, какого именно размера должна быть эта структура, чтобы существование определённой подструктуры было гарантировано. Так Эрдёш начал работать над вариантом головоломки о вечеринке.
   В этом варианте шесть человек представлены шестью точками. Для удобства точки располагаются на плоскости так, чтобы никакие три из них не лежали на одной прямой.Точки соединяются ребром, которое окрашивается, чтобы представить отношения между соответствующими двумя людьми. Красное ребро означает, что эти люди между собой знакомы, а синее ребро - что они друг друга не знают.
   Следовательно, если три человека знакомы друг с другом, то рёбра между соответствующими точками образуют красный треугольник, а если эти трое незнакомы, то образуется синий треугольник. Головоломку о вечеринке тогда можно сформулировать так: верно ли, что если каждое ребро, соединяющее любые две из шести точек, окрасить в синий или красный цвет произвольным образом, то всегда возникает либо синий, либо красный треугольник?
   Задача, которую изучал Эрдёш, представляет собой обобщение этой задачи. Он определил полную сеть как набор точек, каждая из которых соединена рёбрами со всеми остальными. Затем он задался вопросом: какова наименьшая полная сеть, которая будучи произвольным образом раскрашена в красный и синий цвет, обязательно содержит полную сеть красного или синего цвета? Ответ следующий: полная сеть - из шести точек. Эту задачу и её решение удобнее выразить так: число Рамсея (R) для трёх красных и трёх синих равно шести.
    А как насчет числа Рамсея для пяти красных и трёх синих? Другими словами, какова наименьшая полная сеть, которая будучи произвольным образом раскрашена в красный и синий цвет, обязательно содержала бы либо красную сеть из пяти точек, либо синюю сеть из трёх точек? Число Рамсея для пяти красных и трёх синих равно 14, что доказали только в 1955году Роберт Гринвуд из Университета шт.Техас в Остине и Эндрю Глисон из Гарвардского университета.
1 2
Закрыть