Conference Board of the Mathematical Sciences
Regional Conference Series in Mathematics
supported by the
National Science Foundation
Number 45
RUDIMENTS OF RAMSEY THEORY
by
RONALD L. GRAHAM
Published for the
Conference Board of the Mathematical Sciences
by the
American Mathematical Society
Providence, Rhode Island
1981
P. ГРЭХЕМ
НАЧАЛА ТЕОРИИ
РАМСЕЯ
Перевод с английского
Б. С. СТЕЧКИНА
под редакцией
С. М. ВОРОНИНА
Москва «Мир:
1984

ББК 22.U4
Г 98
УДК 511 +519.1
Грэхем Р.
Г98 Начала теории Рамсея: Пер. с англ.—М.: Мир 1984
96 с. ил.
Книга написана крупным американским математиком и отражает современ-
современные достижения а теории Рамсея, имеющей важные приложения в различных
областях математики (теория множеств, логика, теория групп, вычислительная
математика и др.). Изложение ведется в строгой и доступной форме, каждая
глава сопровождается упражнениями, задачами, приведены открытые проблемы.
Для специалистов по комбинаторике, аспирантов и студентов университетов.
ББК 22.174
517.8
041@1)—84
Редакция литературы по математическим наукам
Рональд Л. Грэхем
НАЧАЛА ТЕОРИИ РАМСЕЯ
Научный редактор И. А. Маховая
Младший научный редактор И. В. Герасимова
Художник В. Е. Карпов
Художественный редактор В. И. Шаповалов
Технический редактор Л. П. Ермакова
Корректор М. А. Смирнов
ИБ № 3785
Сдано в набор 04.07.83. Подписано к печати 24.02.84. Формат 60x90'/i6. Бумага типограф.
:кая JV» 2. Гарнитура литературная. Печать высокая. Объем 3,00 бум. л. Уел печ л
i,00. Усл. кр.-отт. 6,50. Уч.-изд. л. 5,57. Изд. № 1/2922. Тираж 4000 экя. ч-., -тс
екая
6,00.
Цена 85 коп.
Тираж 4000 экз. Зак. 706.'
ИЗДАТЕЛЬСТВО сМИР» ,
129820, Москва, И-110, ГСП, 1-й Рижский пер., 2
Ленинградская типография JVj 2 головное предприятие ордена Трудового Красного Зна-
Знамени Ленинградского объединения «Техническая книга» им. Евгении Соколовой Союзпо-
лиграфпрома при Государственном комитете СССР по делам издательств, полиграфии
и книжной торговли. 198052, г. Ленинград, Л-52, Измайловский проспект, 29.
© American Mathematical Society, 1981
©Перевод на русский язык с дополнениями, «Мир», 1984
О теории Рамсея
В сущности, во многих разделах математики используются
комбинаторные соображения, однако они не всегда излагаются
одинаково четко. Нас не оставляет робкая надежда, что систе-
систематический анализ комбинаторных соображений приведет к по-
повышению их полезности, по крайней мере к усовершенствова-
усовершенствованию доказательств. В этом отношении примечательна судьба
принципа Дирихле.
Принцип Дирихле излагают обычно в терминах размещений
и оттого именуют иногда принципом ящиков:
При любом размещении (п -\- 1) объектов по п ящикам най~
дется ящик с двумя объектами.
Если существенно наличие k предметов в одном ящике, то
принцип формулируется так: ,
При любом размещении (rk — г-\- 1) объектов по г ящикам
найдется k объектов в одном ящике.
Принцип Дирихле тривиален, но полезен: многие теоремы,
его использующие, фундаментальны, например теорема Эйле-
Эйлера— Ферма, теорема самого Дирихле, теорема Матиясевича,
наконец, теорема Рамсея.
Теорема Рамсея — это нетривиальное обобщение принципа
Дирихле; рамки ее полезности расширяются, охватывая и чисто
практические ситуации. Это приводит к самостоятельной тео-
теории. Суть ее — проследить взаимосвязь единого и разделенного.
Если большая структура разбивается на непересекающиеся
части, то наличие какой подструктуры можно гарантировать в
одной из частей? Обратно — сколь богатой должна быть боль-
большая структура, чтобы любое ее разбиение содержало часть
предписанной природы?
Книга Рональда Грэхема, видного специалиста не только в
этой области, но и во многих разделах прикладной математики
и механики, знакомит с началами и насущными вопросами этой
теории. Мы стремились сохранить живой и образный язык ав-
автора. С его любезного согласия настоящее издание снабжено
двумя дополнениями.
С. Воронин
Б. Стечкин

Предисловие
Не будет преувеличением сказать, что последние 10 лет от-
отмечены ярким всплеском активности в области общей комбина-
комбинаторики. Внутри этой области один конкретный объект подвергся
особенно интенсивному развитию. Объект этот есть теория Рам-
сея — предмет настоящих заметок, которые написаны на основе
лекций, прочитанных автором на региональной конференции
Колледжа св. Улава в июне 1979 г. Цель этих лекций состояла
в том, чтобы развить навыки, необходимые для понимания не-
недавних достижений в теории Рамсея. В соответствии со стилем
самих лекций заметки неформальны, однако большинство пред-
представленных результатов сопровождается полными доказатель-
доказательствами. Кроме того, много полезных фактов можно найти в уп-
упражнениях и задачах.
Мне хочется поблагодарить всех участников конференции
за создание стимулирующей атмосферы, столь ценной на собра-
собраниях такого рода. В частности, с особенной благодарностью я
обращаюсь к Ф. Абрамсону, Л. Бейнеке, Т. Брауну, С. Бурру,
Ф. Чжан, Л. Лесняку, Дж. Миллсу, М. Натансону, Дж. Полу,
Дж. Селфриджу за их яркие дополнительные лекции по отдель-
отдельным аспектам теории Рамсея. Критические замечания Т. Брау-
Брауна, С. Бурра и М. Хаймана по некоторым фрагментам текста
оказались весьма полезными. Наконец, эта конференция состоя-
состоялась лишь благодаря прекрасной организации и радушному
гостеприимству Р. Аллена и К. Корцатта (и поддержке Нацио-
Национального научного фонда).
Добавлено в корректуре. С момента выхода этой моногра-
монографии в 1981 г. теория Рамсея развивалась еще более быстрыми
темпами. Ряд направлений обогатился серьезными результа-
результатами: это бесконечные двойственные формы многих классиче-
классических теорем, полученные Карлсоном и Симпсоном; результаты
Бека, Атья, Комлоша, Семерди и др. по рамсеевской теории гра-
графов; Дыобера, Промеля и Войта по каноническим разбиениям
и новые независимые результаты Кетонена, Солозея и Фрид-
Фридмана. Краткий обзор этих и более поздних работ можно найти
в моей статье «Recent Development in Ramsey Theory», Proc.
Inter. Congress of Math^ Warsaw, North-Holland,
Введение
Грубо говоря, теория Рамсея — это ветвь комбинаторики,
имеющая дело со структурами, которые сохраняются под дей-
действием разбиений. Типичен для нее следующий вопрос: если
конкретная структура (например, алгебраическая, комбинатор-
комбинаторная или геометрическая) произвольным образом разбивается на
конечное количество классов, то наличие какого рода подструк-
подструктур всегда можно гарантировать по крайней мере в одном из
этих классов? Вот три конкретных примера.
1. При любом разбиении множества всех целых чисел на
конечное количество классов некоторый класс всегда содержит
сколь угодно длинную арифметическую прогрессию (теорема
ван дер Вардена).
2. Для каждого разбиения множества всех ^-элементных
подмножеств бесконечного множества 5 на конечное количество
классов найдется некоторое бесконечное подмножество этого S
со всеми своими ^-элементными подмножествами, лежащими
в одном классе (теорема Рамсея).
3. При любом разбиении точек плоскости на конечное число
классов некоторый класс содержит прямоугольный треугольник
площади 1.
В течение лишь нескольких последних лет в области рам-
рамсеевской теории получен ряд эффектных результатов, таких, как
работа Семереди и Фюрстенберга, разрешившая примечатель-
примечательную гипотезу Эрдёша и Турана (о том, что множество целых ¦
без fe-членной арифметической прогрессии имеет плотность 0),
теоремы Нешетриля — Рёдля, результаты Пэриса и Харрингтона
о «больших» рамсеевских числах и неразрешимости арифме-
арифметики Пеано первого рода, решение Дьюбером старой гипотезы
Радо, неожиданное обобщение Хиндманом теоремы Шура и по-
положительное разрешение Грэхемом, Либом и Росчайлдом гипо-
гипотезы Рота об аналоге теоремы Рамсея для векторных про-
пространств. Итак, становится бесспорным, что идеи и техника тео-
теории Рамсея связываются со все более широким кругом матема-
математических областей, пересекаясь в весьма существенных местах
с элементами теории множеств, теории графов, комбинаторной
теории чисел, теории вероятностей, анализа и даже вычисли-
вычислительной и машинной математики.

Глава 1
ТРИ ВЗГЛЯДА НА ТЕОРИЮ
РАМСЕЯ
Существует несколько точек зрения, от которых можно от-
отталкиваться при изучении различных классов рамсеевских тео-
теорем; отметим некоторые из них.
Пусть (S, <() — частично упорядоченное множество (конеч-
(конечное) с единственным минимальным элементом 0. Будем гово-
говорить, что 5 градуированное, если для каждого j(eS все мак-
максимальные цепи от х к 0 имеют одну и ту же длину; в этом
случае такую длину называем рангом х и обозначаем через
р(х). Множество всех элементов ранга k из S обозначаем че-
Рез [ft
Примеры, (a) S = 2М— совокупность всех подмножеств
множества [л] = {1,2, ..., л}, упорядоченных по включению;
р(jc) == |jc| = мощность xeS.
(b) S — множество всех подпространств данного «-мерного
векторного пространства V над фиксированным конечным по-
полем GF(q), упорядоченное по включению; р(х) = размерность
(c) S — совокупность всех разбиений множества [л], упо-
упорядоченных по склейке блоков; для разбиения вида х = В\ []
U В2 U ... U Bk = [л] имеем р (х) = л — k.
Пусть (Sn, Ю = У, п^а, — последовательность градуиро-
градуированных частично упорядоченных множеств. Говорят, что & об-
обладает рамсеевским свойством, если для любых1) k, l, геи
существует л, такое, что если элементы Sn ранга k произвольно
разбиваются на г классов, то всегда найдется элемент у е Sn
ранга /, такой, что все элементы ранга k вида xeSn и х^у
принадлежат одному из этих г классов. Более формально:
V*, /,/¦«=© Эл: VA: [ А"]->И Зг/е [ f], Ш[г\,
') Обычно случаи k = 0, / = 0 и г = 0 мы опускаем как очевидно вы-
выполняющиеся.

10
Глава I
Читателю предлагается просмотреть это утверждение для
различных семейств 9*, например состоящих из множеств
Sn = S, где S — множества из примеров (а), (Ь), (с). Доказа-
Доказательства рамсеевости этих частных случаев будем рассматри-
рассматривать в последующих разделах.
Для изложения иной точки зрения рассмотрим двудольный
граф G с множествами вершин А и В и множеством ребер
Е ? А X В. Говорят, что G является r-рамсеевским, если для
всех отображений X: В-*~[г] найдется вершина лгеЛ, такая,
что для некоторого is[r] справедливо включение {у^В:
(х, у) е Е) s %~l (i). Многое из рамсеевской теории можно свести
к вопросу о том, является ли конкретный граф г-рамсеевским.
Однако, будучи концептуально простой, эта формулировка не
многое привносит в решение конкретных задач теории Рамсея.
Быть может, причина кроется в ее общности, из-за которой
структуры конкретных изучаемых проблем ускользают из на-
нашего поля зрения. Для иллюстрации рассмотрим двудольный
граф G на рис. 1.1.
Понятно, что он 2-рамсеев, но прямая проверка этого потре-
потребует перебора всех 220 отображений X: В->[2]. В действитель-
действительности G — это граф, полученный (подходящим) отождествле-
отождествлением А и В с множествами соответственно всех 3- и всех 2-эле-
ментных подмножеств множества [6], в котором наличие ребра
между jtG/5 и г/еВ эквивалентно тому, что усх. В этой
интерпретации факт 2-рамсеевости графа G становится совер-
совершенно прозрачным.
Упражнение 1.1. (а) Проверьте 2-рамсеевость графа G.
(Ь) Сохранится ли 2-рамсеевость G, если из множества А уда-
удалить одну вершину (две вершины)?
Последняя из рассматриваемых нами точек зрения связана
с гиперграфами. Под гиперграфом Ж = Ж (V, Е) мы понимаем
множество V вместе с семейством Е из по крайней мере 2-эле-
ментных подмножеств этого множества V. Хроматическое число
гиперграфа Ж обозначается через %(Ж) и определяется как
наименьшее целое t, при котором существует отображение
Три взгляда на теорию Рамсея
11
X: V~>[t], такое, что нет ребра ее? и ie[/] со свойством
esX-'(/). Термин «хроматическое» возник из следующей ин-
интерпретации. Мы представляем отображение X как приписыва-
приписывание цвета вершинам гиперграфа Ш. Если все точки некоторого
ребра сё? получают один и тот же цвет, то говорим, что е
монохроматично1) и записываем: е — mono%. Таким образом,
%(Ж)= t, если t—наименьшее целое, для которого существует
^-раскрашивание множества V без монохроматических ребер
ее?.
Нетрудно увидеть связь между ^-хроматичностью гипергра-
гиперграфа 5^ и (t—1)-рамсеевостью соответствующим образом по-
построенного двудольного графа G =О(Ж).
Существенным инструментом, который довольно часто исполь-
используется в теории Рамсея, является один из вариантов теоремы
компактности де Бройна и Эрдёша [ВгЕ]. Ее формулировку
предварим еще одним определением. Гиперграф $ = $(V', Е')
называется подгиперграфом гиперграфа Ж(У, Е), если V ^ V
и ?' = ?.
Теорема компактности. Если %(Ж)> i и все ребра гипергра-
гиперграфа Ж конечны, то существует конечный подгиперграф 'S гипер-
гиперграфа Ж с xi$)>t.
Доказательство (счетный случай). Не ограничивая общности,
положим V = со. Определим Жп как подгиперграф с множе-
множеством вершин Vn = [n] и множеством ребер ?„ = {ее?:
egjrtj}. Предположим, что %{Mn)^t при всех пев. Таким
образом, существует раскраска Хп: [п]-*-[?], не дающая моно-
монохроматических ребер. Рассмотрим образы Ъп{\), п = 1, 2, 3
Согласно принципу ящиков Дирихле, некоторое значение, ска-
скажем tjeftf], присутствует бесконечно много раз. Положим
¦ Я,*A)=м, и пусть П\ < п2 < . •. — те индексы, для которых
Хп (i) = jj. Рассмотрим образы XntB), /^2. Как и раньше, не-
некоторая величина, скажем i2^[t], будет встречаться бесконечно
часто. Положим Х*B) = i2, и пусть п\ < п'2 < ... есть подпосле-
подпоследовательность из т, такая, что Xn'B) = ir Рассмотрим образы
Я ' C), /^3. И вновь некоторое число, скажем t3e|7], встре-
встречается бесконечно часто. Положим X* C) = t3 и определим
п'!<п"< ... как подпоследовательность из п\, для которой
Яп»C) = г3- Продолжая этот процесс (согласно лемме Кёнига2)),
') Общеупотребителен (особенно среди специалистов по теории мно-
множеств) синоним гомогенный.
2) Утверждающей, что бесконечное дерево, все вершины которого имеют
конечные степени, содержит конечный путь.

12
Глава 2
получаем отображение Я*: со->-[7] с тем свойством, что в Ж нет
^'-монохроматического ребра, т. е. e$J,'-'(i) для всех ее?,
i^[t]. Это сразу следует из построения X*, поскольку для каж-
каждого п найдется такое п' (а в действительности их бесконечно
много), что Л*(/) = Xn'(i), ie[n]. Однако это противоречит
предположению о том, что %(Ж)> t, и, значит (для счетного
случая), доказательство закончено. Для доказательства общего
случая требуется использование аксиомы выбора либо ее ана-
аналога, такого, как теорема Тихонова, и оно приводиться здесь
не будет. Конечно, этот результат также следует из теоремы
компактности для пропозиционных счислений. П
В заключение заметим, что многие концепции теории Рамсея
можно представить в терминах теории категорий, и именно на
этом пути недавно был получен целый ряд сильных результа-
результатов [L; NR1.3]. Однако, преследуя конкретные цели и для
того, чтобы (без особой на то необходимости) не сужать круг
наших читателей, мы здесь не будем развивать этот подход.
Глава 2
ТЕОРЕМА РАМСЕЯ
Прототипом «рамсеевской теоремы» послужила оригиналь-
оригинальная теорема самого Рамсея. Первоначально доказанная в связи
с некоторыми вопросами разрешимости в логике [R], она ока-
оказалась тем плодотворным зерном, из которого выросла боль-
большая часть рамсеевской теории.
Прежде всего рассмотрим (как и Рамсей) бесконечный слу-
случай.
Теорема Рамсея (бесконечный случай). Для всех k, r е со и
произвольного г-раскрашивания %: ["]-»• И множества всех
k-элементных подмножеств множества со всегда найдется бес-
бесконечное подмножество S s to со всеми своими k-элементными
подмножествами, имеющими один и тот же цвет.
Замечание. Подобные утверждения очень часто формулируют
посредством так называемой стрелочной записи Эрдёша и Радо.
Так, утверждение теоремы в этой форме принимает вид
[/Г -*"[ft]r (или ВИД (,®)k->¦ (<*),, если уславливаются исполь-
использовать (со)* вместо ["}). Эпизодически и мы будем прибегать
к такой записи там, где не возникает двоякого толкования.
Теорема Рамсея
13
Доказательство. Прежде всего разберем случай k = 2 как
наиболее обозримый. Случай k = 1 это не что иное, как беско-
бесконечный аналог принципа Дирихле: если бесконечное число
предметов распределено по конечному числу ящиков, то неко-
некоторый ящик содержит бесконечное число предметов.
При k = 2 можно отождествить пары ["] с ребрами пол-
полного графа /См с со вершинами. Пусть %: [" ]-*•[''] есть произ-
произвольное r-раскрашивание ребер этого Ка.
A) Рассмотрим ребра вида {0, х}, т. е. ребра, инцидентные
нулю. Некоторый цвет, скажем си должен закрашивать беско-
бесконечное количество таких ребер. Пусть X = {хс i е со} — множе-
множество таких х > 0, что' % ({0, х}) = с\.
B) Рассмотрим ребра вида {х0, х,}, где х,- <= X. Некоторый
цвет, скажем с2, должен закрашивать бесконечное количество
таких ребер. Пусть У = {yr. teco}—множество таких г/г > х0,
{ })
C) Рассмотрим ребра {уо, yi). Некоторый цвет, скажем с3,
должен закрашивать бесконечное количество таких ребер. Пусть
Z = {zr. I е со}— множество таких г,- > у0 в У, что %({уо, 2;}) =
= с3, и т. д.
Очевидно, этот процесс продолжаем до бесконечности. По-
Положим Т — {0, х0, г/о, zo, .. •} •
Основное положение. Цвет каждой пары {/, /'} е[?] зави-
зависит только от значения min{t,t'}. Таким образом, каждому це-
целому (еГ можно поставить в соответствие новый цвет %*(t)^
е[г] по правилу
n) Для f>t в Т.
Согласно принципу Дирихле, некоторое бесконечное подмно-
подмножество 5s7 должно быть одноцветным относительно %*, т. е.
все %*(s) одинаковы для всех s^S. Но, согласно определению
X*, это в точности означает, что все {s, s'} имеют один цвет от-
относительно Х"РаскРашивания- Теорема Рамсея доказана для
k = 2. .
Подытожим сказанное выше.
A) По данному раскрашиванию %: [™]->И определяется
новое, «индуцированное» раскрашивание %*: ["]—»¦ И («наве-
(«наведенное»), обладающее достаточно регулярной структурой Hai
(большом) подмножестве множества со.
B) Применяем (по индукции) соответствующую теорему
Рамсея для ["] по отношению к х*-рзскрашиванию.
Такое логическое образование постоянно встречается в тео1-
рии Рамсея. Вероятно, это наиболее продуктивный подход при!

14
Глава 2
доказательстве рамсеевских теорем существования для мно-
многих классов структур. На страницах нашей книги читатель
неоднократно повстречается с различными обличиями этой
техники.
Пример тому — продолжение доказательства теоремы Рам-
сея, случай k = 3. По исходному /--раскрашиванию %: [з]~*И
индуцируем r-раскрашивание xi пар из Х = а — {0} по правилу
Xi ({х, х'}) = зс({0, х, х'}). По теореме Рамсея для k = 2 множе-
множество X содержит некоторое бесконечное mono %i множество
Х' — {х\: /есо} (т. е. все значения %^{х\, х'.}~) одинаковы), ска-
скажем цвета С\. Далее индуцируем r-раскрашивание %2 на[^],
где Y = X' — {x'Q] по правилу %2({у, у'}) = %({х'о, у, у'}). Как и
ранее, по теореме Рамсея для k = 2 множество Y содержит бес-
бесконечное mono Х2 множество Y' = \у\: i e со} с F, имеющее,
скажем, цвет Сг. Затем, конечно, индуцируем %з Hafg]. где Z =
= У — {Уо} по правилу х3 ({г, г'}) = х ({у'о, г, z'} ) и т. д.
Тем самым, в конце концов, как и ранее, образуем множе-
множество Т — \0, х'о, у'о, ...}, которое по построению обладает тем
свойством, что цвет любой тройки {t, t', t") зависит лишь от
min{/, t', t"). Из Т можно тогда выделить желаемое множество
S, все тройки которого имеют один цвет.
Доказательство для произвольного k проводится в точности
ло той же схеме. Теорема Рамсея доказана. О
Общепринятая форма конечного случая теоремы Рамсея
имеет следующую формулировку:
Теорема Рамсея (конечный случай). Для всех k, l, гею
найдется n(k,l,r)<=a>, такое, что если п~^ n(k, I, r) и
X: [I]->И есть произвольное r-раскрашивание всех k-nod-
множеств из [п], то некоторое l-подмножество из [п] имеет все
k-nodмножества одного и того же цвета.
(Более кратко: для всех k, I, re© существует n(k,l,r), та-
такое, что неравенство n~^n(k, I,г) влечет [?]->Гlk] Л
По теореме компактности этот конечный вариант теоремы
Рамсея сразу следует из бесконечного случая. К сожалению,
такой способ доказательства не дает оценки для наименьших
возможных значений чисел n(k, I, r). Эти числа, известные как
числа Рамсея (классические), обозначаются через R(k, l,r); они
интенсивно изучаются на протяжении последних 50 лет. Однако,
несмотря на предпринятые усилия, о них известно относительно
мало. Все известные нетривиальные значения приведены в сле-
следующей таблице:
Теорема Рамсея
15
R(k, 1, г)
2
2
2
2
3
4
3
5
2
2
3
2
6
18
17
42-55
Конечно, R[\,l,r) = {l—\)r+l, R(k,k,r) = k.
Наилучшие известные общие оценки для R (k, I, r) получены
с использованием вероятностного метода Эрдёша. Не удиви-
удивительно, что к нему же восходят и наиболее ранние (но по-преж-
по-прежнему хорошие) оценки.
Проиллюстрируем простой вариант этого метода оценивания
на следующем результате. Обозначим RB,k, 2) через R(k).
Теорема (Эрдёш [Е1]). Для некоторой фиксированной кон-
константы с > 0 имеет место оценка
R(k)>ck2k'2. B.1)
Доказательство. Рассмотрим полный граф Кп на множестве
вершин [п]. Будем называть 2-раскрашивание ребер графа Кп
«хорошим», если оно содержит одноцветную копию графа Kk-
Если X — множество из k вершин графа Кп, то имеется
C)(k)
(полное число 2-раскрашиваний графа Кп), т. е. если
2 . 2^2' ^2' способов для такой 2-раскраски ребер Кп, при ко-
которой все ребра на вершинах X имеют один и тот же цвет. По-
Поскольку имеется в точности (?) способов выбора X, состоя-
щего из k точек, то существует не более чем A^) %
«хороших» раскрашиваний. Таким образом, если
*)+1 < 2(г)
B.2)
то существует «нехорошее» 2-раскрашивание графа Кп- Но это
означает, что R(k) должно превосходить такое значение п, по-
поскольку по определению любое 2-раскрашивание графа /Сад»
должно быть хорошим. А так как неравенство B.2) выпол-
выполняется при п > ck2k/2, то B.1) доказано. О
Наиболее точные границы, известные для рамсеевских чи-
чисел, имеются для r(k, 3)—наименьшего пг, при котором любое
2-раскрашивание графа Km содержит либо Kk цвета 1, либо /Сз

Глава 2
цвета 2. В этом случае для некоторых положительных констант
сие' выполняется
ck2/(logkJ < г(k,3)< c'A2/logk.
Верхняя оценка — это недавний результат Атья, Комлоша
и Семереди, который во время написания книги опубликован
еще не был. Наилучшая конструктивная нижняя оценка для
R{k) имеет вид
R (k) > ехр (с (log kL/3 (log log k) '/3)
и принадлежит Франклю [Fr] и Чжан [Ch]. Эрдёш предла-
предлагает 250 долларов за конструктивное доказательство того, что
R{k)>(\ + е)* для фиксированного е > 0.
Завершим эту главу типичным приложением теории Рамсея.
Предложение. Каждая конечная полугруппа S содержит
идемпотент, т. е. элемент х, такой, что х2 = х.
Доказательство. Рассмотрим произвольную последователь-
последовательность х = (х0, Х\, х2, .... xt), где xi <= 5 и s = 151. Введем s-pac-
крашивание Kt на вершинах [t] по правилу % ({/, /}) = xi+i X
Хл:,+2- ... -Xj^S, i < /. Возьмем t=^R(s), тогда Kt содер-
содержит одноцветный треугольник, скажем %({i, /}) = x({'> k}) =
= X ({/•*})= х е ^> i < / < ?¦ Но это означает, что
П *а=
а= П ^3= П *у = f П
П
Упражнение 2.1. Определим внедиагональное число Рамсея
R{k,l) как наименьшее целое /л, при котором в любой 2-рас-
краске графа Km (скажем, в красный и голубой цвета) най-
найдется либо красный Kk, либо голубой Ki-
(a) Покажите, что R(k, I) s? R(k — 1, l) + R{k, I — 1).
(b) Из этого неравенства выведите верхние оценки для
kl) nR(k).
Упражнение 2.2. (а) Докажите, что для каждого п суще-
существует f(n), такое, что в любом множестве из f(n) точек пло-
плоскости (в общем положении) всегда найдется п точек, которые
образуют вершины выпуклого п-угольника. Оцените / сверху
и снизу. (Указание: используйте теорему Рамсея.)
(Ь) Что изменится, если потребовать, чтобы выпуклый
n-угольник не содержал внутренних точек?
Упражнение 2.3. Под турниром понимается полный граф, в
котором каждое реброЪриентировано. Турнир транзитивен, если
a-i-b и Ь->*с влечет за собой а->~сч Покажите, что для каж-
7 еорема ван оер вириени
дого п существует g(n), такое, что каждый турнир на g(n) точ-
точках содержит транзитивный подтурнир на п точках.
Упражнение 2.4. Пусть Л={а1<а2< ...} состоит из чи-
чисел вида {4' + 4': 0 ^ i < /}. Покажите, что
A) каждое песо имеет не более трех представлений вида
п = щ + a/, i < /;
B) для каждого разбиения А на конечное количество клас-
классов, скажем А—А\\} ... [} А,, для некоторого А1 = (а'1<.
<U2<..-} бесконечно много чисел песо можно представить
в виде п = а^ + а^, i < /, по крайней мере тремя способами.
(Указание: см. теорему Рамсея.)
Упражнение 2.5. Пусть &п обозначает градуированное мно-
множество разбиений множества [п], частично упорядоченное по
склейке блоков. Напомним, что ранг разбиения [n]=BiU •••
... [}Bk определяется как n — k. Покажите, что семейство
{&>п: гаем} обладает рамсеевским свойством. (Указание: рас-
рассмотрите подрешетку t?n, порожденную разбиением, наибольший
элемент которого имеет размер 2.)
Глава 3
ТЕОРЕМА ВАН ДЕР ВАРДЕНА
В 1927 г. ван дер Варден [VI] опубликовал доказательство
следующей неожиданной теоремы:
Если множество всех натуральных чисел разбить на два не-
непересекающихся класса, то по крайней мере один из этих клас-
классов должен содержать произвольно длинную арифметическую
прогрессию.
Постановка этой задачи часто приписывается голландскому
математику П. Баудету, вероятно, потому, что его имя фигури-
фигурирует в названии той работы ван дер Вардена, в которой было
дано первое доказательство. Однако представляется более обос-
обоснованным, что в действительности именно И. Шур впервые
сформулировал эту гипотезу в связи со своей работой о рас-
распределении квадратичных вычетов по модулю р. (По поводу
исторических подробностей см. предисловие А. Брауэра к из-
избранным трудам Шура [Sc2]').)
') См. также дополнение I настоящей книги. — Прим. перев.
2 Зак. 706

Глава 3
Эта теорема породила ряд очень интересных направлений в
комбинаторике и теории чисел; некоторые из них будут осве-
освещены в последующих главах. В настоящей главе рассмотрим
несколько доказательств этой классической теоремы ван дер
Вардена.
Основные соображения. Имеются два на первый взгляд не-
незначительных видоизменения формулировки теоремы ван дер
Вардена, каждое из которых тем не менее существенно влияет
на доказательство. Во-первых, для каждого k будем рассматри-
рассматривать лишь конечный начальный кусок (зависящий от k) множе-
множества Z+ (множества положительных целых), чтобы при его
разбиении по крайней мере один класс всегда содержал й-член-
ную арифметическую прогрессию (А. П.). Эта модификация
принадлежит О. Шрейеру (см. [V2]) и, согласно бесконечному
варианту леммы Кёнига, эквивалентна исходной формулировке.
Во-вторых, допускаем разбиения на г классов, как раньше на 2.
Эта идея была предложена Э. Артином и существенна для всех
известных доказательств теоремы ван дер Вардена. С учетом
этих модификаций «новая» формулировка теоремы ван дер Вар-
Вардена принимает вид:
Для k, reel существует целое W(k,r), такое, что если
\[W{k, r)] разбивается на г классов, то по крайней мере один
класс содержит k-членную А. П.
Или более «цветисто»:
Для всех ^,гёш существует W(k, r)ей, такое, что любое
r-раскрашивание множества [W(k, r)] всегда имеет одноцвет-
одноцветную k-членную А. П.
Обратимся сначала к отдельным частным случаям. Для
k = 2 и произвольного г ответ тривиален: U?B, r)= r-\- 1. Рас-
Рассмотрим случай k = 3, г = 2. Утверждаем, что можно взять
WC, 2) = 325. Чтобы убедиться в этом, предположим, что %:
[325]->[2] есть произвольное 2-раскрашивание. Представим
множество [325] состоящим из 65 последовательных блоков
длины 5, т. е. [325] = [1,5]U[6,10]U ... U[321,325], которое
символически записываем как
в,
в,
в,
65
Каждый блок В,- имеет 5 точек, и, следовательно, его можно
раскрасить одним из 2* = 32 способов. Таким образом, ср^ди
Теорема ван дер Вардена
первых 33 блоков некоторая пара блоков раскрашена одинаково
(по принципу Дирихле); пусть для определенности это блоки
Вц и В2в- Рассмотрим 2-раскрашивание блока Вц = {51, 52, 53,
54,55}. Среди первых трех элементов в Вп по крайней мере
два должны иметь один и тот же цвет, скажем %E1) = ^E3) =
= 1. Если хE5)= 1, то прогрессия найдена, поэтому %E5) = 2.
Рассмотрим сложившуюся ситуацию с этой точки зрения:
51 52 53 54 55 126 127 128 129 1.30 201 202 203 204 205
1x1x2
В
и
A
В
'41
Мы утверждаем, что все сделано. Действительно, если хB05) =
= 2, то 55, 130, 205 —это 3-членная А. П. цвета 2, а если
ХBО5)= 1, то 51, 128, 205 —это 3-членная А. П. цвета 1.
В действительности мы просто сфокусировали две 2-член-
ные А. П., имеющие разные цвета на целом 205, так что вне
зависимости от своего цвета 205 оказывается третьим членом
некоторой mono% А. П.
Используем те же соображения и для доказательства су-
существования ЩЗ, 3). Здесь мы, однако, начнем с 3-раскраши-
вания первых 7B • З7 + l)B • 37B'3'+1) + l) целых.
Прежде всего разобьем эти целые на 2 • 37<2'3'+1> + 1 после-
последовательных блоков В,-, каждый длины 7B-37+ 1). Теперь, по-
поскольку имеется в точности з7B'3'+1) способов для 3-раскраски
блока В;, то среди первых з7B'3'+1)-)- 1 из них по крайней мере
два, скажем -В,-, и В;1+<*„ должны быть 3-раскрашены в точ-
точности одинаково. (Используется именно 2 • 37<2'3'+1)+1 блоков
для того, чтобы блок Bil+2d, был определен; скоро он понадо-
понадобится.)
Далее, для каждого i разобьем целые в В,- на 2-37+ 1 под-
подблоков Bi, j из 7 целых каждый. Поскольку имеется в точности
З7 способов для 3-раскраски каждого В,-, /, то среди первых
З7 + 1 блоков В,,, / по крайней мере 2, скажем В;,, г2 и Blu ;2+ d,
имеют в точности одинаковую 3-раскраску.
Наконец, в первых четырех элементах блока Biu i2 некото-
некоторый цвет должен присутствовать по крайней мере дважды, ска-
скажем хAз) = %(h + d3)= 1, где h, k + d3 e В/„ h. Поскольку
i3 + 2d3 также принадлежит В,-,, tl (поэтому мы и выбрали
длину 7), то можно предположить, не ограничивая общности,
что %(гз + 24) = 2 (если %(t3 + 2d3)=l, то искомая А. П.
имеется). Сложившаяся ситуация показана на рис. 3.1.
Рассмотрим подблок Вгь i2+2dv Вследствие определенного вы-
выбора i2 и d<i он является подблоком блока В*,. Далее, посколь-

20
Глава 3
ку Biu,-, и Biu i2+a2 имеют одинаковую 3-раскраску, то целые
/з + 7d2 и k + d3 -j- 7d2 должны иметь цвет 1, а целое *'з + 2d3 +
+ 7с?2 — цвет 2. Стало быть, соответствующий элемент / -\-2d3-\-
4- 14с?2 s fi,-,, i,+2d, должен иметь цвет 3 из-за монохроматич-
монохроматичности арифметических прогрессий i3 + 2d3, k + 2d3 -j- 7d?,
is ia*A
+2d3
3Xi
1 1 2
Рис. 3.1.
k-\-2dz-\-Hd2
скольку Bit и
+ 7B • З7 +
и i3,
Х(/3 + 2dz + 7B ¦ З7
h + dz + 7d2, i3 + 2d3+l4d2. Конечно, по-
поd, раскрашены одинаково, то хеВ,-, и jc +
Bi,+dt всегда имеет тот же цвет. В частности,
7C7
37+l)di)=2,
- 3.
Теперь рассмотрим целое /и = »з + 2d3 + 14йг+ 14 (З7 + l)di.
Мы утверждаем, что имеется три разноцветных 2-членных
monojc А. П., сфокусированных на т, так что вне зависимости
от цвета %(т) это т станет третьим членом 3-членной mono/
А. П. Дабы убедиться в этом, извлечем просто подходящую
часть рис. 3.1:
7C7
13 V М3 + 7J2 + 7C7_ + l)i/ '••...,
(э + 2d3 + Ш2 • • • /3 + М3 + 14rf2 + 7C7 + 1)</, ¦ ¦ • Л, + а/,
Таким образом, показано, что можно взять
14C'
WC, 3) = 7B-37+l)B-37B3'+I>+ l).
Теорема ван дер Вардена
21
Общее доказательство проводится двойной индукцией по
длине k искомой прогрессии и числу г цветов раскраски, при-
причем предполагается не только существование W(k,r—1), но и
существование W{k—\,r') для всех г'. Нам нужны очень боль-
большие значения г', поскольку в общем случае мы будем всегда
разбивать исходное множество целых на блоки б, равной дли-
длины, состоящие из последовательных :) целых, и применять пред-
предположения индукции к блокам, которые для наших целей долж-
должны вести себя как целые (индуцированное раскрашивание бло-
блоков). Если целые раскрашиваются в г цветов, то блоки —в
Ив'1. По этой причине величины, которые мы получаем для
W{k, r), огромны. В действительности не известны хотя бы при-
примитивно рекурсивные верхние оценки. С другой стороны, даже
при г = 2 наилучшая известная нижняя оценка имеет вид
ck2k [Be]. Столь сильное расхождение границ для W(k, r) де-
демонстрирует размеры наших знаний в этой области.
Завершению доказательства теоремы ван дер Вардена наме-
намеченным путем препятствует еще одно обстоятельство — выбор
приемлемых обозначений.
Упражнение 3.1. Завершите доказательство теоремы ван дер
Вардена (не жульничать!).
Упражнение 3.2. Обозначение W(k, r) обычно используется
для наименьшего целого, для которого выполняется теорема
ван дер Вардена. В этих обозначениях
(a) Известно, что №B,2) = 3, №C,2) = 9, 117D,2) =35,
WE,2)=178,, WC,3) = 27, №C,4) = 76. Докажите 1, 2 и 5-е
из этих равенств2).
(b) Каковы верхние оценки для WA0,10)?
Короткое доказательство. Вероятно, нет ничего удивитель-
удивительного в том, что некоторое усиление утверждения теоремы ван
дер Вардена приводит к несколько более сильному результату,
который тем не менее чуть легче доказывать [GR2]. Приведем
такой результат. Следует отметить, что его доказательство по
своей структуре совпадает с первоначальным доказательством
ван дер Вардена.
Два вектора (xv...,xm), (xv ..., *m)e [0, l\m назовем
/-эквивалентными, если они совпадают вплоть до последнего
появления I. (Таким образом, любые два Z-вектора, не содер-
4) На самом деле эти блоки не должны быть пересекающимися — они
Точно пригнаны друг к другу.
2) Миллс на основании этих данных сделал заключение, что
W(k, 2)-»• C/2)А!.

22
Глава 3
рассмот-
жащие /, являются /-эквивалентными.) Для /, т ^
рим следующее утверждение:
Для любого г существует N(l,m,r), та-
такое, что для любого г-раскрашивания %:
[NA, т, г)]-»-[/¦] существуют a, d\, ...
..., dm е Р, такие, что %(а + 27-1 xi^i)
постоянно на каждом классе /-эквива-
/-эквивалентности множества [0, /]т.
Теорема. Утверждение S{l,m) имеет место для всех /,-
m^s 1.
Доказательство. A) Покажем, что из справедливости S(l,tn)
для некоторого m^l следует справедливость S(/, m+1).
Пусть M = N(l,tn,r), M' = N(l,l,rM) для фиксированного г
и раскраска %: [ЛШ'1-»-[>] задана. Определим индуцированную
раскраску %': [М']-*-[гм] таким правилом: %'(k)=%'(k') тогда
и только тогда, когда / (kM — /) = % (k'M — /) для 0 ^ / < М.
По предположению индукции существуют а' и d', такие, что
%'(а' + xd') постоянно для х^[0,1—1]. Поскольку S(l,m)
можно применить к интервалу I = [(а'—\)М-\-\, а'М], то в
силу выбора М существуют такие a, d\ dm, для которых
все суммы а + 2<li xi^h xi e [0» ^]> лежат в /, что раскраска
%(а + Zf-i xtdi) постоянна на классах /-эквивалентности. По-
Положим d'. = di для /е[/п] и dfm+l=d'M. Тогда 5(/, m + 1) вы-
выполняется.
B) Покажем, что из справедливости 5(/, т) для всех т ^ 1
следует справедливость 5(/+1,1). Пусть г фиксировано и у;.
[2N{I, r, r)]-»-[r] задана. Тогда существуют такие a, d\, ..., dr,
что для Xi е [0, /] величина а + ?'=1 х$г ограничена сверху чис-
числом N(l,r,r) и раскраска %(а + X,=i xtdi) постоянна на клас-
классах /-эквивалентности. В силу принципа Дирихле существуют
и, !)е[0,г],Кв, такие, что х(a+ Z"=i/dO = x(a + ^"-i по-
последовательно, %((a + HUi^iidi)-\-x(j^tMsU+ldiJ) постоянна для
х<=[0, /]. Это доказывает 5(/+1,1).
Поскольку 5A, 1) очевидно справедливо, то теорема следует
из принципа математической индукции. О
Заметим, что теорема ван дер Вардена для (/+ 1)-членных
А. П. есть в точности утверждение S(l, 1).
Упражнение 3.3. Пусть А = (а\ < а2 < ...)—бесконечная
последовательность целых с равномерно ограниченными ая+1 —
— ап.
Теорема Халеса — Джеветта
(a) Покажите, что А содержит произвольно длинную А. П.
(b) Покажите, что А не обязано содержать бесконечную
А. П.
(c) Оцените (в терминах W{k, r)) число членов последова-
последовательности А, необходимых для гарантированного наличия
А-членной А. П. (если сдадитесь, см. гл. 11).
Глава 4
ТЕОРЕМА ХАЛЕСА—ДЖЕВЕТТА
Теорему ван дер Вардена, в сущности, можно рассматривать
не как результат о целых, а как теорему о конечных последо-
последовательностях, образуемых из конечных множеств. Это обстоя-
обстоятельство впервые было отмечено в работе Халеса и Джеветта
[HJ]. Их результат изучается в настоящей главе.
5<
) (
/
1 1
/
/
V
12 3 4 5
Рис. 4.1. Прямые в А2.
Наше изложение будет в основном опираться на следующие
понятия. Для фиксированного конечного множества А = {а\, ...
.,., at} было бы желательно образовать некую структуру из
n-множеств Л", аналогичную n-мерным векторным простран-
пространствам над конечным полем. Не предполагается, понятно, что А
снабжено какой-то специальной алгебраической структурой, так
что весьма ограничен потенциальный список тех линейных урав-
уравнений в координатах, которые могли бы задавать определенные
аналоги векторных подпространств. В действительности такой
список исчерпывается двумя равенствами:
A) Xi = xr,
B) Xi — a (константа).
Как определять «прямую» такими уравнениями? Вполне
естественно такое
Определение. Для непустого множества координат / s [n]
множество L = {(xu ¦.., хп): xt = x/ Vt, /e/, Xj = bj<=A,
j ф. 1} называется (комбинаторной) прямой в Ап.

I ЛИИГ7
Заметим, что поскольку /=^0, то \L\ = t (как и ожида-
ожидалось).
В качестве примера на рис. 4.1 показаны прямые множества
Л2, где Л =[5].
Упражнение 4.1. Сколько прямых имеет множество Л"?
В такой терминологии очень удобную форму приобретает
Теорема Халеса — Джеветта. Для всех конечных множеств
А и целых re со существует N (А, г), такое, что для n^N(A,r)
в любой r-раскраске А" всегда найдется одноцветная прямая.
Набросок доказательства. Доказательство (как обычно) про-
проведем двойной индукцией по \А\ иге одновременным исполь-
использованием г различных раскрашиваний. При |Л|=] результат
очевиден. Предположим, что для некоторого t ^ 2 он выпол-
выполняется для всех значений \A\<t. Идея состоит в следующем:
задаем начальное /--раскрашивание %: Ап-*-[г]. Во-первых, вы-
выберем большое целое N\, определяемое позже1), так что п —
— /V, <С N\. Понимая Ап как An~Nl X.ANl, образуем индуциро-
индуцированное раскрашивание хA) множества AN] по правилу:
X"'((#,, •••. yN)) = tu({y\> •••» y'Nl)) тогда и только тогда,
когда для всех (*,, ..., xn_N)eAn~ '
Х((* * ))ЩУ*,))-
((, „_*,. Ух Ун,))Щх1 хп-н,> У\
Другими словами, раскрашиваем у = (у{,.-., 1/л)е/'
согласуясь с функцией %(х, у), x^An~Nl. Так что это есть в
действительности некоторое rtn~Ni -раскрашивание AN\ Пусть
В = {а\ at-i}. Тогда /О это также и раскрашивание BN\
так что, согласно предположению индукции, найдется прямая
L — mono%A) (при условии достаточной величины Ni), кото-
которую можно записать как
Л"-»* х
:... с....,...),
*(•"*...«,...),
(...*...«,_
t-i
Сокращенно запишем ее как Ап N'XXl(ii), 1<л, г^/— 1,
где Xi(ii) обозначает последние N\ координат из /—1 точек L\
при /ь пробегающем по [t— 1].
*) В конце доказательства.
Теорема Халеса — Джеветта
25
Далее сосредоточимся на «начале» A" Ni, которое можем
понимать как д^-п, __^n-N,-N,y^ ^n, для некотОрОГО дг2-
n — N\ — N2<^N2. В то же время образуем раскрашивание %{2)
множества ANl по правилу: xB)(#j, ..., yN,) = y}2)(y[, ..., y'N)
тогда и только тогда, когда для всех (*,, ..., xn_Ni_N})^ дп-Ni-n,
Иными словами, мы хB)-РаскРашиваем у s ANs посредством
функции %((х, у)~ХХгA)), х е Л' ~Nl~N\ Заметим, что поскольку
L\ одноцветна, то можно использовать Хх B) или Х\ (i) для лю-
любого ie[l—1]. Как и прежде, можно ограничиться рассмотре-
рассмотрением хB> на BN' и, используя предположение индукции, найти
прямую Z.2 — mono%B>, которую можем записать как An-N<-N*y^
~XX2(i2)X,Xi(l), I ^ B ^ t—1 (вновь N2 предполагается до-
достаточно большим). Заметим, что по построению %-цвет любых
(*—IJ точек (*, *n-Wl-w,)X^2(/2)X^i('i), K'[, '2<
^/—1, зависит лишь от выбора (х{, ..., xn_Nl_Nl), з не от
конкретных значений ii и i2. Кроме того, если X2(t) обозна-
обозначает точку, получаемую замещением переменной компоненты
(т. е. не константы) конкретным значением at, то %"Ц.вет
(*,, ¦••. *„_#,-*,) Х*2(/)Х *,(/,) не зависит от выбора /, е
е[<-1].
Продолжая этот процесс, за г шагов приходим к множеству
из Р точек из Л", которое запишем как
*г Иг) ¦' • ^«+1 (/u+i) Хи Ни) • • • *i (А). 1 < /i. • • •, /V < t\
оно обладает тем свойством, что х-цвет Xr(jr) •¦• Xu+1 (ju+i)Xu(iu) ••-
¦ •• Xi(ii), 1 ^ ju+u ..., jr ^ t, не зависит от выбора ik: 1 ^ iu ...
..., t*<f—1.
Теперь доказательство почти закончено. Для его полного за-
завершения рассмотрим г -\- 1 точек
Yu = Xr{t) • • ¦ Xu+x{t)Xu{\) • • ¦ Х{{\), 0<ы<г.
Некоторая пара из них должна иметь один и тот же цвет; пусть
это будут Yh и Yg, где h > А'. Наконец, рассмотрим / точек
Y (i) = Хг @ • • • Xk+l (t) Xh (i) • ¦ ¦ Xh.+l (i) Xh'(l) • • • X, A).
Для 1 ^/^/—1 цвет Y(i) тот же, что и у Yh (по предыду-
предыдущему замечанию). При i = t цвет Y(t) тот же, что и у Yh', ко-
который, по определению А', совпадает с цветом Yh- Таким обра-
образом, множество {Y(i): i^[t]} образует одноцветную прямую
в Л", что и дает утверждение теоремы. О

26
Глава 4
Нетрудно довести все эти замечания до уровня реального
доказательства. Для этого прежде всего требуется четко опре-
определить yV(|/4|, г), Nu Л'2 и т. д. Вот один из допустимых ва-
вариантов. Для t— 1 полагаем Лф,г) = 1. Для t~^2 рекурсивно
определяем N(t, г):
и N(t,r) = cr'-\-cr-i-{¦ ... +cj.
Является ли столь сильный рост1) N отражением реальной
ситуации, или же это всего лишь недостаток техники нашего
доказательства? Это одна из наиболее интересных открытых
проблем в данной области.
Как и обещано, выведем теорему ван дер Вардена из тео-
теоремы Халеса — Джеветта. Действительно, любое л-раскрашива-
ние х множества [?*<*•г)] должно содержать ^-членную mono^
А. П. Каждое целое х е [kN(k'r)] можно записать в системе
счисления по основанию k в виде х = XfJo*' r)~l xtkl, где xt s
e {0, ..., k—l}. Таким образом, каждому х ставим в соот-
соответствие последовательность (л:0, ..., xN(k r)_,). По определе-
определению N(k,r) и согласно теореме Халеса — Джеветта, должна
существовать одноцветная прямая, скажем
(...«. -о, ь,...о,...),
(...а, 1 Ъ, ... 1,-...),
(...a, 2 Ь,...2,...),
(...«,...*-!,'...*,...2,...)
Ясно, что k целых, представляемые этими точками L, принадле-
принадлежат арифметической прогрессии.
Обобщения. Естественно поинтересоваться, выполняется ли
теорема Халеса — Джеветта для комбинаторных «плоскостей»
(или подпространств более высокой размерности). Конечно,под
¦*) В оригинале— Дскегтапп-like. — Я/?«ж. перед,
Теорема Халеса — Джеветта
27
плоскостью Р понимается множество из t2 точек из Ап, порож-
порожденное разбиением [п] == /0 U h U h при 1\, 12ф0 по правилу
Оказывается, что аналоги теоремы Халеса — Джеветта для
более высокой размерности сразу следуют из одномерного слу-
случая. Например, для плоскости нужно просто заменить исходное
А новым множеством А2. Тогда прямая V в этом новом мно-
множестве примет вид
Поскольку имеется по крайней мере одна переменная коорди-
координата, то эти t2 тбчек естественным образом соответствуют не-
некоторой плоскости в А2п.
Более утонченное обобщение теоремы -.- подмена раскраски
точек множества А'1 раскраской подпространств из Ап более вы-
высокой размерности. Например, можно г-раскрашивать прямые
из Ап и задаваться вопросом о наличии плоскости, все прямые
которой были бы покрашены в один цвет. Все такие обобщения
также истинны и осмысленны, но доказательства их более
сложны. Можно немного расширить и понятие прямой (или под-
подпространства). Для фиксированной группы перестановок G:
/4->-Л ={а.ь ..., щ} прямой L будет называться множество
из t точек множества А" вида
Л" а\ Ъ <,...),
ЬЛ
[(*. • ¦"", *>• ¦•<>•••)
где а, т, ... аО.
Иначе говоря, на каждую переменную координату действует
некоторый элемент из О. Вообще такай структура известна как
n-параметрическое множество. Как впервые было показано

28
Глава 5
в [GR1], и для них выполняются соответствующие рамсеевские
теоремы (с рангом, равным «размерности»), такие же, как"сама
теорема Рамсея, теорема ван дер Вардена, Халеса — Джеветта
и многие другие. Здесь также содержатся зародыши идей, необ-
необходимых для доказательства того, что совокупность конечно-
конечномерных векторных пространств над фиксированным конечным
полем обладает рамсеевским свойством — гипотеза, выдвинутая
Рота и доказанная Грэхемом, Либом и Росчайлдом [GLR]. Сов-
Совсем недавно очень прозрачное доказательство было дано Спен-
Спенсером [S] (подробнее см. [GRS]).
Упражнение 4.2. Докажите 2-мерный вариант теоремы ван
дер Вардена, т. е. при всяком конечном раскрашивании Z2 не-
некоторый цвет содержит произвольно большую квадратную под-
таблицу. (Указание: используйте теорему Халеса — Джеветта.)
Упражнение 4.3. Докажите, что для любой конечной полу-
полугруппы 5 существуют п <= со, x^S, такие, что множество
nS + х = {s'+ s+^- + s + x: s eS}
n
одноэлементно. (Указание: используйте теорему Халеса — Дже-
Джеветта с раскраской %: (xi xn)->Xi + ••• -f xn.)
Упражнение 4.4. Пусть G(kn) обозначает n-мерное обобще-
обобщение игры в крестики-нолики на n-мерную таблицу размера
&Х&Х ¦•• Х& {п раз). Как обычно, игроки попеременно ри-
рисуют X или 0 в свободных клетках (таблицы), и тот, кто пер-
первым полностью заполнит прямую k одинаковыми символами,
будет победителем. Доказать, что для любого k при достаточно
большом п первый игрок всегда может выиграть. (Именно эта
постановка навела Халеса и Джеветта на мысль о теореме.)
Глава 5
ТЕОРЕМА СЕМЕРЕДИ
Теорема ван дер Вардена, гарантирующая существование
одноцветного класса, содержащего сколь угодно длинную ариф-
арифметическую прогрессию, не указывает, какой именно класс об-
обладает этим свойством. Более чем 45 лет назад Эрдёш и Туран
[ЕТ] выдвинули следующее предположение: если множество
натуральных чисел А имеет положительную верхнюю плотность,
Теорема Семереди
т. е. выполняется
Umsup(\A()[\,N]\/N)>0,
N
(*)
то это А содержит произвольно длинные арифметические про-
прогрессии (А. П.).
Таким образом, из этой гипотезы следовало бы, что длинные
А. П. всегда присутствуют в «наиболее часто встречающемся»
цвете. В 1953 г. К. Ф. Рот [Ro] доказал, что из соотношения (*)
следует, что А всегда содержит трехчленную А. П. В 1969 г.
Е. Семереди [Szl] показал, что из (*) следует существование
четырехчленной А. П., принадлежащей А. Наконец, в 1975 г.
Семереди тонкими комбинаторными рассуждениями установил
справедливость этой гипотезы в общем случае [Sz2]. Полное
доказательство выходит за рамки настоящей работы. Здесь мы
изложим очень упрощенный вариант этого доказательства для
трехчленных А. П., который содержит многие из существенных
моментов общего случая.
Теорема (Рот). Пусть с > 0. Если А^[п], причем \А\~^ сп
и п достаточно велико, то А содержит трехчленную А. П.
Доказательство (Семереди). Теорема будет следовать из
ряда лемм и утверждений. Прежде всего потребуется следую-
следующий результат.
Лемма. Пусть а = 2 + V3- Для k^O определим числа
Zfc=an1-1'2\ Пусть А = {ai < •¦• < ai) s [n] и I ^ lk. Тогда
существуют а и Xq, .... xk ~> 0, такие, что
M (a; x0, ..., xk) = \ a + ? e^, ег = 0, 1 eA
Доказательство. Используем индукцию по k. Во-первых, за-
заметим, что для всех k ^ 1
>(a- lJn2-Wk/2 = an2-V2k-* =nlk_u E.1)
поскольку (a — !)z/2 = аип>1.
При k = 0 имеем /0 = an ^ а > 3, и, следовательно, утвер-
утверждение леммы очевидно. Предположим, что для некоторого
k ^ 1 утверждение леммы справедливо для всех значений,
меньших k,и предположим также, что А = [ 1, п] и \А\= l^lh.
Среди Пк\ разностей щ — uj, i > /, по крайней мере /A_i

30
Глава S
должны быть равны между собой, так как, согласно E.1), вы-
выполняется неравенство —('^^Ik-u и ПРИ этом все разности
It \ 2 /
принадлежат \п]. Таким образом, имеем а. —а. =а. —а. =...
'i h B h
¦¦• =а. —a. = d>0 для некоторого m^lk-\. Приме-
т 'т
няя предположение индукции к А' = [а,, ..., а. ), получаем,
I '1 'mi
ля некоторого а и хо> • • •,
{а +
а,, )
I '1 'mi
что для некоторого а и хо> • • •, хк~\ выполняется включение
{ UliZo eixi: e< = 0> l}Si4'. Положим xk = d. Тогда для а и
утверждение леммы, поскольку
хк-\, xk выполняется
=>a' + d<=A. ?
Следствие. Предположим, что A s[n], причем \А\^сп для
некоторой фиксированной константы с > 0. Тогда для доста-
достаточно большого п некоторые М(а; х0, ..., **) — А и k^
^loglogn +0A).
Доказательство. Если ^ < (log log n — log(logr<x — log с))/
/log 2, то 2* (log a — logc)< logn, т. e. en > шг1-1'2^. Утвержде-
Утверждение сразу следует из леммы, о
Заметим, что следствие также выполняется, если А е[т+ 1,
m -\- п] при \А\^сп и произвольном т. Предположим теперь,
что теорема неверна, т. е. для фиксированного с > 0, для бес-
бесконечно многих п существует А (п) s [n], \А(п)\^ сп, такое, что
это А (п) не содержит трехчленной А. П. Для каждого / через
f(l) обозначим число элементов наибольшего подмножества [/],
не содержащего трехчленной А. П. Предположим без ограниче-
ограничения общности, что | А (п) | = / (п), и положим с0 = lim sup (/ (/)//).
Утверждение 1. lim (/(/)//) = с0.
Доказательство. Достаточно показать, что lim inf (f(l)/l) j>c0.
Предположим противное, т. е. что lim inf (/(/)//) = с' < с0. Та-
ким образом, для некоторого е>0 существуют /[, !'2 ..., та-
такие, что f{lk)/h<. Со — е. По определению с0 существуют
l[,l'v..., такие, что \А (Q\ = f(Q > (с0 — fe/2)/? при всех k.
Выберем большое m (определяемое позже) и для произвольного
фиксированного k положим l'm = Nlk + г, где 0 г=: г < lk. Ра-
Разобьем множество [/^] на Л^ непересекающихся подынтерва-
подынтервалов длины h, скажем Л, ..., IN (рис. 5.1). Согласно выбору lk,
каждое /,- может иметв не более /(/*)< (со — гIк элементов из
A (l'm)- Таким образом, полное число элементов изЛ(/^) в [1, 1'Л
Теорема Семереди
31
не превосходит N(c0 — е)/* + г. Значит,
0 - е/2) (Nlk) < Nlk (со - в
Nlke < 2/ъ
и N < 2/е. Однако последнее неравенство не выполняется для
достаточно большого N. ?
Выберем теперь малое фиксированное е > 0, определяемое
позже. Для достаточно большого 10, согласно утверждению 1,
Y
I'm
Рис. 5.1.
при всех />loglogZ0 выполняются неравенства с0 — е<
< f (/)//< Со + е. Выберем некоторое / >/0 и положим А =
= АA). Разобьем множество [/] на /1/2 + ОA)=/' непересе-
непересекающихся подынтервалов длины /1/2~1-0A) и обозначим их /j,
/2 Jl\.
Утверждение 2. Существует j, такое, что
(\)\1,ПА\>со1т/2;
B)\j-n2\^2dll2/c0.
Доказательство. Согласно выбору I и определению /,-, для
всех i выполняется неравенство |/(П^| ^(со + е)/1/2. Таким об-
образом, если | // Г] А1 ^ со/1/2/2 для всех /, удовлетворяющих
п. B), то
/ Bе + с0 - 4е —^-
оA) <1(с0- г)
для достаточно большого /, что противоречит тому, что |Л| =
() ?
Обозначим через / интервал // (с индексом j) из утвержде-
утверждения 2. Согласно следствию, можно найти некоторые М(а;х0, ...
..., xk)^J с k :ss log log/1/2 + 0A), что обеспечивается доста-
достаточно большим / (как функции со и е). Можно положить k =
= log log/ + 0A). Заметим, что х,^ /1/2 + 0A) при всех i.
Положим /; = {хе[/]: x</}, f = {хе[/]: х>]}. Пусть
Mi обозначает множество М(а\х0, ..., х«) для —1 ^ i ^ k, где

32
Глава 5
М-\={а). Определим Л/, для —1 ^ t^ k по правилу: Ni =
= {/" е /": {/', mi, j") есть трехчленная А. П. для некоторых
Утверждение 3. |#ж | = |tf, [}(Nt + 2*,+,) |+ О(/'/2), -1 <
Доказательство. Множества Ni+i и Ni\J(Ni + 2xi+l) разнятся
лишь теми трехчленными А. П., в которых либо х очень мало,
т. е. j;e /, либо х очень велико, т. е. х > /. В первом случае
ошибка не превосходит О(/1/2), так как \J\-=ll/2, а во втором
ошибка не превосходит О (Iх'2) в силу п. B) утверждения 2. О
Заметим, что поскольку Ni+i = М, то
(/1/2/2 + 2е/1/2/с0 + 1) + О (П =
>(со-еI- (с0 + е)
= /(с0/2-7е/2) + О(/1/2).
Кроме того, поскольку \Nd\<l, k = log log/ + 0A) и
растают, то для некоторого i должно выполняться
E.2)
- воз-
возE.3)
Рассмотрим некоторый произвольный класс вычетов по мо-
модулю 2xi+i в /", скажем С,={^е/": х = /mod 2xi+l}. Назовем
подмножество В = {Ь\ < ¦•• < bt) ? С/ блоком множества М,
если
A) bs+i = bs + 2xt+i для 1 ^ s < /;
B) bs <= М для 1 < s ^ t\
C) bi — 2xi+l ф Ni, bt + 2xi+i ф. Ni.
За исключением краевых случаев, каждый блок множества
Ni порождает по крайней мере один новый элемент при пере-
переходе от Ni к Ni+[. Таким образом, из E.3) видим, что Ni имеет
не более //(loglog/) + 0(/1/2) блоков, когда у пробегает по
всем классам вычетов по модулю 2х,+1 (мажорирование xi+l и
|/| обеспечивает включение концевых эффектов в остаточный
член 0{11'2)).
Поскольку по предположению А не содержит трехчленной
А. П., то
А П N,- = 0. E.4)
Для каждого /, 0 ^ / < 2xi+u рассмотрим элементы из /" — Nit
которые сравнимы с / по модулю 2xt+\. Это элементы, которые
не принадлежат блокам из Ni. Назовем множества элементов,
сравнимых с / по модулю 2Xi+u которые попадают между двумя
Теорема Семереди
последовательными блоками множества Ni, дырами множества
Ni. Таким образом, имеется не более //(log log/)+ 0(/1/2) дыр
в Ni, когда / пробегают все классы вычетов по модулю 2xi+\.
Дыру G множества Ni назовем маленькой, если |G|^
^ log log log/; в противном случае G называется большой.
Если дыра G маленькая, то она содержит не более |G|^
^ log log log/ точек из А. Таким образом, полное число точек
из А, принадлежащих маленьким дырам в Ni, не превосходит
(// (log log /) + О (Z1/2)) log log log / = о (I).
Если G — большая дыра в Ni, то, по определению /о, она со-
содержит не более |G|(co + e) точек из А. Конечно, все, кроме
0(/1/2) точек из /" — Ni, принадлежат либо малым, либо боль-
большим дырам. Стало быть,
<[/A/2 + 2е/с0) -1(со/2 - 7е/2)](с0 + е) + о(/)<
<(//2)(со-6е) + о(/),
что обеспечивается выбором е при 6^^/25. Однако это влечет
за собой, что
|Л
> / (с0 - е) - A/2) (с0 - бе) + о (I) = A/2) (с0 + 2е) + о (/).
А это в свою очередь противоречит тому, что |/'| = //2 +
+ 0(/1/2). Тем самым теорема доказана. ?
Две волнующие гипотезы. Было бы весьма интересно выяс-
выяснить справедливость следующей гипотезы1). Она так же соот-
соотносится с теоремой Семереди, как результат Халеса — Джеветта
с теоремой ван дер Вардена.
Гипотеза. Для любого конечного множества А и положитель-
положительного е существует М = М(А, е), такая, что если п^М и
R^An: |JR| > е|Л|п, то R содержит (комбинаторную) пря-
прямую 2).
Другими словами, верно ли, что если R^An имеет «плот-
«плотность» по крайней мере е для некоторого е>Ои л достаточно
велико, то это R содержит прямую? (Из этой гипотезы также
следует теорема Семереди.)'
') Это усиленный вариант гипотезы Л. Мозера [Ml (см. [Chvl]).
4) Определение см. в предыдущей главе.
8 Зак. 706

Глава 5
Для |Л| = 2 гипотезу можно доказать с использованием
классического результата Шпернера: если F— семейство под-
подмножеств множества [я], такое, что X, Y^F=$~X<?Yq?X, то
Доказательство гипотезы для \А\ = 2. Пусть Л ={0,1}, и
предположим, что R ^ Ап не содержит прямой. Заметим, что
прямая в А" есть в точности пара я-ок х = (х{, ..., хЛ, х'=
= {х\ х'п) с хг -*7е{0> 1}> xi ^x'i> причем для по крайней
мере одного индекса j справедливо х,- = 0, х'.= \. Если интер-
интерпретировать х и х! как характеристические функции подмно-
подмножеств S(x) и S(x') из [п] в обычном смысле, т. е. iGS(i)-<^
<=3-xi = 1, то условие, что х и х' образуют прямую, эквивалентно
тому, что S(x)— собственное подмножество S(x'). Таким обра-
образом, по теореме Шпернера может быть не более чем ([„«])<
< c2"/Vn подмножеств S(x) для некоторого с > 0и, следова-
следовательно, | R | < c2"/V«> что влечет за собой гипотезу. ?
Пока даже для случая |Л| = 3 нет хороших предположений
о структуре максимальных подмножеств /?*еЛ" без комбина-
комбинаторной прямой. Один естественный подход состоит в том, чтобы
взять за Л множество {0, 1,2} и положить Rw={(xu ..., х„)Ап:
?"_i xt e W\ для подходящего множества IFs {0, 1, ...
..., Зя}. (В случае Л = {0, 1} экстремальные конструкции имеют
вид R* = RW, где W = {[n/2]} или № = {я — [я/2]}.) В ча-
частности, если W не содержит трехчленной А. П., то Rw не со-
содержит прямой. (Это выполняется для |Л| = я.) Однако тео-
теорема Рота (или теорема Семереди в общем случае) показывает,
что W = o(n), а это в свою очередь дает \RW\ = (о\А\п) — со-
совсем не то, что нам нужно!
По традиции, введенной Эрдёшем, автор предлагает 100 аме-
американских долларов1) за доказательство или опровержение этой
гипотезы для случая | Л | = 3.
Мы заканчиваем этот раздел замечательной гипотезой Эр-
дёша C000 $), из которой также следует теорема Семереди.
Гипотеза Эрдёша. Если А — множество натуральных чисел,
такое, что 2аа л(^/а)=ш °°> то ^ содержит сколь угодно длин-
длинную арифметическую прогрессию.
Нужно заметить, что совсем недавно Фюрстенберг дал дока-
доказательство теоремы Семереди, используя новые методы из эрго-
дической теории. Некоторые из них будут отмечены в гл. 11.
') Как говорит Эрдёш, возможны замены на западногерманские марки,
золото, бриллианты или нефть — кто что предпочитает.
Рамсеевская теория графов
35
Глава 6
РАМСЕЕВСНАЯ ТЕОРИЯ ГРАФОВ
Рамсеевская теория графов — это область, которая за по-
последние 10 лет проделала путь от своего зарождения до превра-
превращения в один из наиболее активных разделов общей теории
Рамсея. В настоящей главе обсуждаются лишь отдельные ре-
результаты из всего имеющегося обилия — те, которые наиболее
полно отражают многообразие рассматриваемых вопросов и
техники, используемой в этой области.
Первые работы в области рамсеевской теории графов были
написаны в надежде на то, что эти исследования в конце кон-
концов приведут к методам вычисления больших значений класси-
классических чисел Рамсея R(m,n). Однако, как это часто случается
в математике, надежда осталась нереализованной, а из исследо-
исследований выросла отдельная самостоятельная дисциплина. Ве-
Вероятно, можно даже утверждать, что результаты рамсеевской
теории графов сами -по себе более ценны и интересны, нежели
знание точного значения RE, 5) (или даже R(m,n)).
Основная задача, с которой имеет дело рамсеевская теория
графов, формулируется следующим образом: для произвольного
(фиксированного) графа G определить то наименьшее целое
R = R(G), при котором во всякой 2-раскраске ребер графа Kr
найдется одноцветный подграф, изоморфный исходному графу
G. В случае классических чисел Рамсея в качестве G берется
полный граф. Когда вместо двух используется k цветов, вместо
R(G) будем употреблять обозначение R(G; k).
Точно так же,, как и в классическом случае, допустимо рас-
рассматривать и более общую «внедиагональную» ситуацию. Имен-
Именно, для графов G\, ..., Gk символом R(G\, ..., Gk) будем
обозначать наименьшее целое R, такое, что вне зависимости от
/г-раскраски ребер графа Kr для некоторого i в i-м цвете нали-
наличествует копия графа G,-. Существование чисел R{Gi, ..., Gk),
разумеется, гарантируется теоремой Рамсея.
Начнем с одного из простейших и наиболее общих резуль-
результатов рамсеевской теории графов. Пусть для графа G (в кото-
котором всегда предполагается отсутствие изолированных вершин)
%{G) обозначает его хроматическое число1), a c(G)—мощность
его наибольшей компоненты связности.
*) То есть наименьшее число цветов, необходимых для такой раскраски
вершин G, при которой нет пары одноцветных вершин, соединенной ребром.

Глава 6
Теорема 6.1 (Хватал —Харари [ChvH2]).
)+. F.1)
Доказательство. Положим m = (%(G)—\)(с(Н)—1) и рас-
рассмотрим граф Km как i{G)—\ копий графа Кс(Н)-\ вместе со
всеми ребрами, соединяющими все пары вершин разных копий
графа Кс{н)-\. Покрасим все ребра копий графа Кс(Н)-\ в цвет 2,
а все добавочные ребра (между копиями) в цвет 1. Конечно,
при такой раскраске нет копии графа G цвета 1, поскольку если
бы она была, то мы могли бы покрасить вершины этой копии
в %(G)—1 цветов — по номеру той копии графа КС{н)-\, в кото-
которой они лежат, а это противоречит определению %(Ь). С дру-
другой стороны, нет и копии графа Н цвета 2, поскольку наиболь-
наибольшая связная компонента графа Km цвета 2 имеет с(Н)— 1 вер-
вершин. О
Теорема 6.1 используется в одном весьма элегантном ре-
результате рамсеевской теории графов, принадлежащем Хваталу.
Теорема 6.2 [Chv2]. Для любого m-вершинного дерева Тт
выполняется равенство
R(Tm,Kn) = (m-l)(n-l)+l. F.2)
Доказательство. Нижняя оценка следует из F.1), так что
нужно лишь показать, что
R(Tm, Кп) ^ (ш — 1) (п — 1)+ 1.
F.3)
При m = 2 или п = 2 это очевидно. Предположим, что F.3)
выполняется при всех значениях пг' и п', таких, что пг' -+-«'<
< т + п. Рассмотрим 2-раскраску графа /С(т_1)(„_1)+1 в красный
и синий цвета. Пусть Т — дерево, образованное из Т удалением
некоторой концевой вершины х (х смежна вершине у в Тт).
По предположению индукции наш граф /Qm-ixn-o+i содержит
либо синий Кп (и тогда все закончено), либо красное Т. Та-
Таким образом, предполагаем наличие красного дерева Т в графе
/C(m-i)(n-i)+i. Удаляя m — 1 точек этого красного V, получаем
2-раскрашенный граф К(т-\)(п-2)+\. И вновь, по предположению
индукции, этот граф содержит либо красное дерево Т, либо си-
синий граф Кп-й очевидно, можем предположить наличие именно
последнего подграфа.
Следовательно, в исходном /Qm-ixn-n+i имеется красное де-
дерево V и синий граф Кп-и не пересекающиеся между собой.
Обратимся, наконец, к ребрам, соединяющим у с синим Кп-\-
Если какое-то из них красное, то имеем красное дерево Тт, если
же все они синие, то Это дает синий граф Кп- Это завершает
индукционный переход, а значит, и доказательство теоремы. ?
Рамсеевская теория графов
37
Известно сравнительно немного точных нетривиальных зна-
значений R(G,H); одно из самых интересных представляет
Теорема 6.3 [Bui]. Пусть Тт —дерево с т вершинами и
(т — 1) делит (п — 1). Тогда
R(Tm,Ki,n)=m + n—\. F.4)
Доказательство. Во-первых, покажем, что
R(Tm,Ki,n)>m + n—\. F.5)
Пусть k = {n—l)/(m—1). Образуем 2-раскрашивание Кт+п-2,
взяв k + 1 копий графа Кт-\ (все полностью красные)
и соединив их всеми синими ребрами. Такая раскраска не со-
содержит красного дерева Тт как имеющего т вершин. Но она
же и не содержит синего К\,п, поскольку наибольшая синяя
степень в Кт+п-2 равна k(m— 1) = п— 1. Это доказывает F.5).
Далее покажем, что
Ki,n)^m + n—\. F.6)
При т = 2 это очевидно так. Как и в доказательстве преды-
предыдущей теоремы, образуем дерево Т удалением висячей вер-
вершины х из Тт (х связана с у в Тт). В 2-раскрашенном графе
Кт+п-и согласно предположению индукции, найдется либо си-
синий К\,п (и тогда все закончено), либо красное дерево Т', так
что можем предполагать наличие именно последнего. Поскольку
имеется пг-\-п—1—(т—\) = п вершин vi графа Кт+п-и ко-
которые не являются вершинами красного Т', и Km+n-i не содер-
содержит синего К\, п, то некоторое ребро из у в некоторую вершину
vt должно быть красным. Но это дает красное дерево Т в Kn+m-\-
Таким образом, 'согласно предположению индукции, неравен-
неравенство F.6) выполнено, а тем самым и вся теорема доказана. ?
Случай, когда (пг — Г) не делит (п—1), много более сло-
сложен и полностью не изучен. Однако и здесь выполняются нера-
неравенство F.6) и для почти всех деревьев Тт для достаточно
больших п равенство R(Tm, К\, п) = п + т — 2.
В рамсеевской теории графов особого внимания заслужи-
заслуживает класс графов, состоящих из непересекающихся копий кон-
конкретного графа. Прекрасным примером тому служит результат,
принадлежащий Буру, Эрдёшу и Спенсеру [BuES], о графе
пКз, состоящем из п непересекающихся треугольников.
Теорема 6.4.
R (пКз) — 5л, п ^ 2.
F.7)
Доказательство. Напомним, что для п = 1 мы уже знаем,
что /?(/Сз) = 6. Дабы убедиться в том, что /? (п/С3) ^ 5п,

38
Глава 6
рассмотрим 2-раскраску графа /CSn_,, как на рис. 6.1. Легко
проверяется, что эта 2-раскраска K5»-i не содержит одноцвет-
НОГО ЯДз-
Далее индукцией по п покажем, что
Я(пКз)^5п, п^2. F.8)
Сначала рассмотрим случай п = 2. Зафиксируем некоторую
2-раскраску графа Kw (на вершинах {1,2, .... 10}) и предпо-
предположим, что она не содержит одноцветного 2/Cj. Таким образом,
Синий
Красный
Рис. 6.1.
должны существовать непересекающиеся красный и синий тре-
треугольники Кг, пусть для определенности это будут: красный —
{1,2,3} и синий—{4,5,6}. Рассмотрим ребра между {1,2} и
{4, 5, 6}. Непосредственной проверкой удостоверяемся в наличии
Красный
j Синий
3.
Рис. 6.2. Бантик.
«бантика» (рис. 6.2) на этих вершинах, т. е. пары треугольни-
треугольников разных цветов, соединяющихся в одной вершине. Без огра-
ограничения общности можно предполагать, что бантик именно та-
таков, как на рис. 6.2.
Далее рассмотрим шесть вершин {1,6,7,8,9,10}. В силу
равенства Я(К3)—€) эти шесть вершин содержат одноцветный
граф Кз- Если он не нересекается с нашим бантиком, то полу-
получаем требуемый 2/С3, и все сделано. Поэтому предполагаем од-
одноцветность треугольника {1, 6, 7}: пусть он красный. На том же
Рамсеевская теория графов
основании пять вершин {6, 7, 8, 9, 10} должны давать 2-раскра-
шенный граф Къ, не содержащий одноцветного Кз- Легко ви-
видеть, что это возможно только, если ребра графа Къ образуют
два непересекающихся одноцветных 5-цикла. Таким образом,
без ограничения общности можем предположить, что ребра
{6, 7}, ..., {10, 6} красные, а ребра {6, 8}, ..., {9,6} синие.
Аналогично дополнение бантика {1,4,5,6,7} должно быть так-
также свободно от одноцветных Кз- Поэтому, как и ранее, можем
предполагать, что ребра {2,3}, ..., {10,2} красные, а ребра
{2,8} ... {9,2} синие (рис. 6.3).
Теперь, если или {2, 6}, или {3,7} синий, то либо {2,6,9},
либо {3,7,9} дают синий граф Кз, не пересекающийся с {1,4,5}.
С другой стороны, если {2,6} и {3,7} красные, то {2,6,8} и
{3,7,10} суть два непересекающихся красных треугольника. Это
показывает, что ЯBКз)^ 10.
Наконец, для п ^ 3 можно, как и раньше, вывести суще-
существование бантика на некоторых пяти вершинах 2-раскрашен-
ного графа Кы- Удалим эти пять вершин; тогда, согласно пред-
предположению индукции, найдется одноцветный (п—1)/(з в остав-
оставшемся Кьп-ь- Это вместе с одноцветным Къ из бантика и даст
одноцветный граф пКъ- п
Приведем теперь несколько результатов для случая, когда
число цветов k может превышать 2. Лучший общий результат
для деревьев составляют следующие оценки Эрдёша и Грэхема
[EG].
Теорема 6.5. Для дерева Тт с m ребрами имеют место
оценки
(m—\)[{k+l)/2]<R(Tm;k)^2mk+l. F.9)
Доказательство. Для доказательства нижней оценки в F.9)
положим t = [{k-\- l)/2] и рассмотрим Кцт-\) как /копий гра-
графа Кт-и занумерованных числами от 1 до /: K{^_v ¦¦-, K[mLv
Раскрасим в цвет i все ребра между Ю^_{ и К{?_1 для 1 ^ /<
< j ^ ( и в цвет t— 1 + i все ребра в К'^_у Это дает Bt— 1)-
раскрашивание графа Кцт-\) без одноцветного дерева Тт. Так
как 2t— I ^ k, левая часть F.9) доказана.
Для доказательства правой части F.9) воспользуемся тем
фактом, что для всех d любой граф G с d вершинами и md реб-
ребрами содержит в качестве подграфа любое m-реберное де-
дерево Тт-
Упражнение 6.1. Докажите этот факт.
Во всяком А-раскрашивании графа Kikm+x по крайней мере
ребер должны иметь один и тот же цвет. Поскольку

Глава 6
это есть (одноцветный) граф с 2km -\- 1 вершинами и по край-
крайней мере m{2km-\- 1) ребрами, то, согласно приведенному за-
замечанию, он содержит одноцветную копию графа Тт, и тем са-
самым правая часть F.9) доказана. ?
Верхнюю оценку в F.9) для достаточно большого k можно
усилить до
R(Tm;k)<(m—l)k + 4, F.9')
если справедлива
Гипотеза Эрдёша и Шош [Е2]. Любой d-вершинный граф
с [(т—l)d/2]-\-\ ребрами содержит в себе в качестве под-
подграфа любое m-реберное дерево Тт.
Вполне возможно, что именно F.9') дает правильную асимп-
асимптотику роста для графа R(Tm\k). Основанием такому предполо-
предположению служит, например,
Теорема 6.6 [EG]. Для достаточно большого k и ш-ребер-
ного дерева Тт справедливо неравенство
R(Tm;k)>(m—l)k — m2.
Доказательство. Для целого k через k0 обозначаем наиболь-
наибольшее целое, не превосходящее k и сравнимое с 1 по модулю т.
Согласно глубокому результату Рай-Чаудхури и Вильсона
[RW], всегда существует разрешимая уравновешенная непол-
неполная блок-схема Dko,n, имеющая (т—1)k0 + 1 точек и ko(kom —
— ko-\-\)/m блоков объема т, существование которой обеспе-
обеспечивается лишь тем, что k0 достаточно велико. Отождествим
точки схемы Dk_n с вершинами полного графа К^т-ц^+и При-
Припишем цвет / всем тем ребрам графа K(m-i)ka+u которые соот-
соответствуют парам точек, принадлежащим i-му параллельному
классу схемы Z)*0,n. Это дает &0-раскрашивание графа /C(m-D*0+i»
которое не содержит одноцветного связного подграфа с т + 1
вершинами. А так как k0 > k — т, то это даст А-раскрашива-
ние графа K(m-\)k-m> без одноцветного Тт. ?
Известен ряд точных результатов о деревьях специального
вида. Например, для Я3-пути с тремя ребрами Ирвингом [I]
была доказана
Теорема 6.7.
Г 2? + 2, Л si (mod 3),
R(P3; k) = < 2k+l, ?^2(mod3), F.10)
1 2k или 2k + 1, & = 0(mod3).
Доказательство F.10) также основывается на результатах
работы [RW]. В действительности вычисление многих точных
Рамсеевская теория графов
41
значений рамсеевских чисел для графов зависит от существова-
существования (или отсутствия) некоторых специальных комбинаторных
схем или алгебраических структур. Это, например, проявилось
при вычислении классических чисел Рамсея R C,3,3) и /? D, 4),
которое провели Гринвуд и Глисон [GrG].
Поучительно сравнить рамсеевские числа для Р3 и для С4 —
цикла на 4-х вершинах. Оказывается, что рамсеевские числа
для С4 растут много более быстро, чем для Р3.
Теорема 6.8 (Чжан и Грэхем [ChG]).
k)^k2 + k + 2 для всех k.
Если k — 1 есть степень простого, то
F.11)
F.12)
Доказательство. Прежде всего нам понадобится оценка для
наибольшего числа е ребер п-вершинного графа G без С4. Пусть
А = (aij) обозначает матрицу смежности такого графа. Так как
G ф С4, то для 1 ^ i < i' <: п
F.13)
Если Cj обозначает ]
и i', получаем
п
/=1
i,/, то, суммируя F.13) по всем i
F.14)
Применяя неравенство Шварца к F.14), получаем неравенство
п
2е = ? с, <п/2 + п л/я - 3/4, F.15)
которое представляет собой широко известную оценку для»
\G\:GJ>CA. ¦
Предположим теперь, что, ребра графа Kk!+k+2 раскрашены
в k цветов. Тогда в один из цветов окрашено по крайней мере
A/6) (*1+*+2 ) ребер. Если возьмем п= k2 + k + 2, e>(l/jfe) X
X(fe!+2fc+2)> T0 видим, что соотношение F.15) явно не выполня-
выполняется. Это доказывает F.11).
Для доказательства F.12) воспользуемся хорошо известным
фактом [Ry] о том, что если k—. 1 есть степень простого, то
существует простое разностное множество D = {di, .... dk\ no.

42
Глава 6
модулю (k2— k-\-\). Для каждого t, I ^ t ^ k, образуем цик-
циклическую (симметричную) матрицу Bt = (bt(i, /)) по правилу:
!1, если i + j + dt = ds (mod k2 — k + 1)
для некоторого ds e D,
О в противном случае.
Поскольку D — разностное множество, это влечет за собой,
что для любых /, /eZis_ft+i существует /, такое,что bt(i,f)= 1.
Кроме того, для каждого t нет двух строк матрицы Bt, имею-
имеющих общую пару единиц.
Образуем теперь ^-раскрашивание графа Kv-k+\ следую-
следующим образом. Вершинами графа Kk'-k+i будут элементы про-
пространства Zk'-k+u Для /, /eZt'-i+i красим ребро {;',/} в цвет
t, где t — наименьшее целое, такое, что bt(i,j)= 1. Из преды-
предыдущих замечаний явствует, что это есть ^-раскрашивание графа
Kw-k+i без одноцветных С4; тем самым соотношение F.12)
доказано, п
И вновь в доказательстве нижней оценки проявляются ком-
комбинаторные структуры (на сей раз разностные множества). Из
достаточной плотности распределения степеней простых, а
также из F.11) и F.12) следует, что R(Ci,k)~k2 при &->-оо.
Естественно предполагать, что поскольку С3 меньше, чем С4,
то С3 в некотором смысле много чаще появляется при й-раскра-
шивании полного графа, и, значит, R(C3;k) должно быть су-
существенно меньше, чем R(C4;k). В действительности, однако,
имеет место в точности обратная ситуация, как это показывает
Рамсеевская теория графов
Теорема 6.9 [EG].
2k<R(C3;
F.16)
Упражнение 6.2. (а) Докажите неравенства F.16). (Указа-
(Указание: индукция здесь весьма своеобразна.)
(Ь) Усильте F.16).
Причина столь разительного отличия в поведении #(С4;&)
и R(C3,k) кроется в том факте, что для С4 имеет место много
более «плотная» теорема, чем для С3. Действительно, из нера-
неравенств F.15) видно, что если G имеет m вершин и (т3/2/2)-\-
+ (т/4) ребер, то G должен всегда содержать С4, в то время
как теорема Турана (см. [Во]) гласит, что G может иметь
т2/4 ребер и не содержать С3.
Конечно, разница между четными и нечетными циклами
проявляется в теории трафов довольно часто. Поэтому нет ни-
ничего удивительного в том, что она проявляется и здесь.
Для больших четных циклов известна (см. [EG])
Теорема 6.10. R(C2m; k) > {k — 1) (m— 1) Vk, m. Если
k ^ 10m/201m, to R{C2m; k)^ 201 km. Кроме того, существуют
а > 0 и положительная функция g, такие, что при всяком е > 0
выполняются неравенства
R (C
2m;
g (m, e)
Этот результат говорит о том, что /?(С2т;&) как функция от k
растет линейно по k, пока k не превосходит довольно большой
величины, после чего R растет как степень k (превосходящая 1).
Для нечетных циклов имеет место следующий аналог тео-
теоремы 6.9 [EG].
Теорема 8.11. 2hm<R(C2m+u k)<2(k + 2)\m для любых
k и т.
Вопрос Эрдёша: верно ли, что для некоторого А выполняется
неравенство R (C3; k) < Л*?
Неизвестно, выполняется ли R(C5; k) > R(C3; k) или даже
R{C2m+uk)> R(CZ; k) для фиксированного т и достаточно
большого k. Сам Эрдёш придерживается того мнения, что в
действительности легче показать, что /?(C2m+i; k) < Ak для не-
некоторого т > 1 (особенно, если это верно!).
При желании изучать более медленно растущие рамсеев-
ские числа нужно, естественно, перейти к рассмотрению
R(F;k), где F есть лес (т. е. ациклический граф) некоторого
специального вида. Здесь имеется полезная информация [EG],
хотя известные результаты и далеки от исчерпывающе полных.
Теорема 6.12. Если Fm — лес с т ребрами, то k{-^Jm — l)/2<
<R(Fm; k) < 4km,.Кроме того, если k ^ m2, toR(Fm; k) > aл/km
для подходящей положительной константы а.
Мы опускаем доказательство (с которым можно ознако-
ознакомиться в [EG]). Таким образом, для каждого леса F величина
R(F\k) как функция от k растет по существу линейно для
больших k (подобно поведению R(T;k) для деревьев Т). Од-
Однако при малых k вторая оценка показывает, что для R(F;k)
остается возможность расти как -\/k. Следующий результат по-
показывает, что это действительно может иметь место.
Теорема 6.13. Если k ^ m, то существует такая константа а,
что R (mKu m;k)<a -у'km2. Если же k ^ Зт2, то R (mK\, m\ k) sg
<3&т.
Естественно поинтересоваться скоростью роста R{G) как
функции от числа вершин G. Здесь имеются достаточно точные
результаты.

Глава 6
Теорема 6.14 [ВиЕ]. Если G — связный граф с т верши-
вершинами, то R(G)^s[Dm— 1)/3]. При этом для каждого m ^ 3
существует граф G, реализующий указанную оценку.
Эта граница достигается на графах, состоящих из звезды
порядка 2/л/З, связанной с.путем длины 3.
Если допустить несвязность графа G (пусть даже без изо-
изолированных вершин), то R(G) может быть еще меньше, как это
показывает
Теорема 6.15 [ВиЕ]. Если G имеет m вершин, то R(G)^
^ m + (Iogm/log2) — a log log m, где а>0 — некоторая кон-
константа. Кроме того, существует граф G и константа В, такие, что
R (G) < m + Р л/т.
Имеется предположение, что нижняя оценка точна.
Мы завершаем эту главу рядом результатов, гипотез и за-
замечаний, которые указывают на различные направления иссле-
исследований в этой области. Большинство из них относится к слу-
случаю 2-раскраски; к аналогичным утверждениям для ^-раскраски
читатель может обратиться сам.
Множество графов $ = {Gb G2, ...} будем называть L-мно-
L-множеством, если существует константа a = a(^), такая, что
R(Gi)s^av(Gi) для всех i (v(Gi) обозначает число вершин
графа Gi). Определим (локальную) реберную плотность p(G)
графа G как р(G) = max (е(Я)/и (Я)), где е{Н) обозначает число
н s о
ребер в Я. Эрдёшу принадлежит следующая сильная
Гипотеза. Если реберная плотность p(G)ограничена для всех
G e ?F, то *3 является L-множеством.
И хотя вся гипотеза в целом далека от разрешения, тем не
менее имеется ряд подтверждающих ее результатов. Так, на-
например, множество деревьев образует L-множество, и для лю-
любого m множество {С?} из пг-х степеней циклов также образует
L-множество. Относительно одного достаточно интересного мно-
множества графов (хотя и не обладающих ограниченной реберной
плотностью) неизвестно, является ли оно L-множеством; это
множество кубов {Q;} (т. е. Q, — это 1-скелет /-мерного куба).
Следующий весьма общий результат полезен, в частности,
для относительно плотных графов.
Теорема 6.16 (Хватал, Харари [ChvHl]). Пусть G — граф
с р вершинами и q ребрами, и пусть s — порядок группы авто-
морфизмоа графа G. Тогда
)'/'. F.17)
Рамсеевская теория графов
45
Доказательство. Доказательство проведем простым исполь-
использованием «вероятностного метода» [ES].
Пусть вершины графа G произвольным образом помечены
буквами v\ vp, порождая тем самым «помеченный» граф
О. Легко видеть, что полный граф Кп содержит в точности
(п)р = п(п—1)---(п — р+1) различных копий G. Из опреде-
определения s как числа симметрии G заключаем, что Кп содержит
t = (n)p/s копий G, скажем Gb G2, ..., Gt. Будем говорить, что
fe-раскрашивание Кп является Gj-плохим, если все ребра под-
(
графа Gi из Кп одинаково окрашены. Поскольку имеется kS2
й-раскрашиваний, то 0,-«плохих» раскрашиваний существует в
точности k^2' . Следовательно, имеется не более tft^2 '
раскрашиваний, которые Сг-«плохи» для некоторого /. Поэтому,
(} (Л
если tkS2 J "' < fe^2/\ то некоторое й-раскрашивание не дает
одноцветной копии G в Кп. Это условие, очевидно, выполнено,
если k"~l >(nP/s)^((n)p/s)= t, т. е. п <(ski-l)^p. Таким об-
образом, R(G; k) ГЗ1 (skq-x)xlP, и тем самым теорема доказана. ?
Недавно возникла еще одна модификация чисел Рамсея, на-
нашедшая отражение в литературе. Пусть Re(G) обозначает для
данного графа G наименьшее число ребер, при котором суще-
существует граф Я с таким числом ребер, любая 2-раскраска ребер
которого всегда содержит одноцветную копию графа G. Оче-
Очевидно, что
/ D (ГЛ \
F.18)
Если G — полный граф, то F.18) обращается в равенство
[EFRS]. Равенство в F.18) может также иметь место и для
неполных графов, например для С4 [Ви2]. С другой стороны, не-
нетрудно показать [EFRS], что
2т- 1
2т
для четного пг,
для нечетного
т.
Таким образом, при т->-оо
Re(KU,
¦0.
F.19)
Имеется один любопытный вопрос, связанный с вычислением
Re: будет ли справедлива формула F.19), если К\, m заменить
на путь Рт? Пока в качестве возможных вариантов мы даже
не можем отвергнуть ни Re{Pm)<. cm, ни Re(Pm)> cm2.

46
Глава 6
Наконец, можно рассмотреть класс 'S'(G) графов Н, таких,
что Н—>-(G, G)[), но Н'-f*(G,G) для любого собственного под-
подграфа Н'аН. В работе [BuFS] такие графы названы рам-
сеевски минимальными для графа G. Бурр [Ви2] высказал
предположение о том, что класс 9?(G) всегда бесконечен, за
исключением того случая, когда G имеет форму S\JM, где S —
нечетная звезда, а М — паросочетание. Однако недавно было
показано, что эта гипотеза неверна. Известно [Bu2; NR0], что
класс Ч?{G) бесконечен в любом из следующих случаев:
(a) G трехсвязен;
(b) G имеет хроматическое число по крайней мере 3;
(c) G — лес, который не является объединением звезд.
Особенно поучительно доказательство п. (с), поскольку в
нем представлен ряд идей, постоянно встречающихся в рамсеев-
ской теории графов.
Теорема 6.17 (Нешетриль, Рёдль [NR0]). Пусть G — лес, не
являющийся объединением звезд. Тогда класс ^(G)— беско-
бесконечен.
Доказательство. Покажем, что для каждого данного целого
t найдется граф flef(G), имеющий более t вершин. Пусть
п. — число вершин графа G.
Начнем с упоминания классического результата Эрдёша
[ЕН], согласно которому существует граф К с хроматическим
числом %(К), превосходящим п2, и обхватом, превосходящим /.
При любом 2-раскрашивании ребер графа К ребра хотя бы од-
одного из цветов образуют граф К' с %{К')> п (вообще, если
E(K) = E(Ki)\jE(k2), то x(KXx(Ki)x(*2J, поскольку произ-
произведение двух вершинных раскрасок в соответственно %{К\) и
%{К2) цветов дает правильнуюx(&i)x№)-раскраску вершин К).
Последовательным удалением ребер из К' можно образовать
наименьший подграф К" Е К' с тем свойством, что %(/(") =
= /г+ 1. В частности, все вершины подграфа К" должны иметь
степень по крайней мере п. Действительно, если v — вершина
К" степени, меньшей п, то в силу минимальности граф К" — {v}
может быть n-раскрашен, а так как вершина v смежна не более
п—\ вершинам графа К"— {о}, то это я-раскрашивание можно
продолжить до правильной n-раскраски вершин всего К" (что
неосуществимо). Помимо того, легко видеть, что К" содержит
в качестве подграфа каждый лес Fen вершинами (можно на-
начать вкладывать F в любом месте К"\ поскольку все вершины
в К" по крайней мере степени п, мы никогда не попадем в ту-
тупик).
') Напоминаем, что запись #->-(G, G) означает, что любое 2-раскраши-
чание ребер Н содержит одноцветный подграф, изоморфный G.
Рамсеевская теория графов
47
Таким образом, показано, что /(->G. Стало быть, К содер-
содержит (минимальный) подграф A^*e<g'(G). Заметим, что сам К*
может и не быть лесом, поскольку ребра каждого леса всегда
можно 2-раскрасить так, чтобы не получилось одноцветного
пути Р3 из трех ребер (а по предположению, так как G не яв-
является объединением звезд, он содержит Р3 как подграф). Та-
Таким образом, обхват подграфа К* конечен; разумеется, он
больше t — обхвата графа К. Но это влечет за собой, что К*
имеет больше t вершин, и тем самым доказательство завер-
завершено. О
Выдвигается весьма тонкая гипотеза относительно
если класс ^(G) конечен и граф G' получается из G добавле-
добавлением непересекающихся ребер, то класс 'ff(G') конечен.
В заключение этой главы сформулируем одну очень сильную
гипотезу Эрдёша.
Гипотеза, х(Gm) = m =$¦ R (Gm) ^ R(Km).
Упражнение 6.З. Выберите (случайным образом) граф G
с пятью ребрами и определите R(G).
Замечания. Здесь было бы уместно указать новые направле-
направления рамсеевской теории графов. Опишем в общих чертах лишь
два наиболее существенных.
I. Гальвин-рамсеевские теоремы. Поскольку любое 2-рас-
крашивание ребер графа Кв дает Кз — monox (или проще:
/F_)_(/Ci Кз)), то для любого G, содержащего в себе в качестве
подграфа Къ, очевидно, что G—»-(/Сз» Кз)- В 1967 г. Эрдёш и
Хайнал задались вопросом: существует ли граф G, не содержа-
щий /С6. но для которого также G -^-(/Сз, /Сз)? Такие графы были
последовательно обнаружены рядом авторов, включая Поша,
ван Линта и автора.
Упражнение 6.4. Пусть К&— Сь есть граф К» без 5-цикла С5
(значит, этот граф имеет 23 ребра). Покажите, что (а) /С6 ?
^К8 — С5, (Ъ) Кв — С5^{Кз,Кз), (с) ни для какого собствен-
собственного подграфа графа Кв—С5 п. (Ь) не выполняется.
Граф в конструкции, предложенной Поша, не обладал /С5
в качестве подграфа. Однако наибольшего успеха здесь достиг
Фолкман [F2], предложивший весьма примечательный граф G,
для которого A) G^(K3,K3), B) /D? G.
К сожалению, число вершин v(G) в графе Фолкмана очень
велико. Побуждаемый естественным стремлением понизить эту
границу, автор предлагает следующую гипотезу.

48
Глава 7
Гипотеза. Эрдёш платит [1000/у18] долларов за граф G,
удовлетворяющий п. A) и B) и имеющий v вершин1).
Гальвин сформулировал более общий вопрос. Предположим,
что G — это ^-свободный граф, т. е. G не содержит подграфа,
изоморфного графу X. Существует ли ^-свободный граф Н,
такой, что H^(G, G)?
Результат Фолкмана представляет собой случай G = Кз,
X = Ка-
Пока имеющиеся на этот вопрос ответы далеки от полных,
хотя весьма впечатляющие результаты были получены Дьюбе-
ром, Нешетрилем и Рёдлем [D2; NR2, 3]; они показали, напри-
например, что ответ утвердителен, когда X — любой полный граф, а
G — любой Х-свободный граф. С другой стороны, для X = {С*
с диагональю} ответ отрицателен. Вопрос в случае X = С4 пока
открыт.
II. Индуцированные рамсеевские теоремы для графов. Мно-
Много более сильное условие состоит в требовании наличия такой
одноцветной копии графа G при любом 2-раскрашивании графа
Н, чтобы она оказывалась индуцированным2) подграфом графа
Н. Ряд результатов такого типа уже имеется, сильнейшие со-
содержатся в работе [NR3]. Основной здесь является следующая
Теорема. Для любых G « rsio существует граф Н, такой,
что если его ребра r-раскрашены, то в Н найдется индуциро-
индуцированный одноцветный подграф G.
Некоторые из таких результатов будут также отмечены в по-
последней главе.
Глава 7
ЕВКЛИДОВА ТЕОРИЯ РАМСЕЯ
В настоящей главе описывается класс результатов рамсеев-
ского типа, некоторым образом зависящих от структуры л-мер-
ного евклидова пространства Е". Для этого класса типичен сле-
следующий вопрос. Пусть задана группа G преобразований
Е"->Е"; для каких множеств СеЕ"и чисел геш выполняется
утверждение:
при любом r-раскрашивании Е" най-
найдется geG, такой, что g(C) одно-
одноцветно?
') Известно, что гипотеза-верна по крайней мере для одного значения о.
3) То есть если v, v' — вершины графов G и Н и {v, v'} — ребро Н, то
оно также и ребро G.
Евклидова теория Рамсея
49
Нам уже приходилось иметь дело с подобными утвержде-
утверждениями, например с теоремой ван дер Вардена') (n= I, G =
= {x^-ax-\-b Va=7^0}, С—конечное подмножество) и ее п-мер-
ными обобщениями. В этой главе ограничимся рассмотрением
группы G движений пространства Е", т. е. комбинаций парал-
параллельных переносов и поворотов.
Определение. Будем говорить, что имеет место R(C,n,r)b
если при любом r-раскрашивании Е" всегда имеется одноцвет-
одноцветная копия С, т. е. (одноцветный) образ С при некотором дви-
движении.
Упражнение 7.1. Пусть С —три вершины равностороннего
треугольника единичной площади.
а) Покажите, что R(C,4,2) выполняется. (Указание: рас-
рассмотрите единичный симплекс в Е4-)
(b) Покажите, что R (С, 2л, г) выполняется.
(c) Покажите, что R (С, 2, 2) не выполняется.
(d) А как обстоит дело с R(C, 3, 2)?
Упражнение 7.2. Пусть С состоит из двух точек, отстоящих
друг от друга на расстояние 1. • .
(a) Покажите, что R (С, 2,3) выполняется.
(b) Покажите, что R(С, 2,7) не выполняется.
(c) Выполняется ли R(C', 2, 4)?
В качестве чуть менее тривиального примера рассмотрим
Q — четыре вершины единичного квадрата.
Утверждение. R(Q, 6,2) выполняется.
Доказательство. Рассмотрим множество 5 = Е6: S={(xu ...
..., х6): xt=l/<yf2 для двух /, дс,- = 0 для остальных /}. Каж-
Каждое 2-раскрашивание % пространства Е6 порождает и 2-раскра-
шивание 5. С каждой точкой s^S можно связать ребро e(s)
полного графа на множестве [6], именно если xi = X/ > 0 для
s, то e(s)= {/,/}. Таким образом, х индуцирует 2-раскрашива-
2-раскрашивание ребер графа Кв- Однако легко показать, что в любом 2-рас-
2-раскрашивании ребер Кб образуется некоторый одноцветный 4-цикл
С4, скажем (м, k, k, ц). По построению графа /С6 четыре точки
S// = @ 1/V2, .... О, ..., 1/V2, .... 0),
(«, /) = (h, k)> ('2. is), (h> U), (U, i\),
имеют одинаковый цвет. Но расстояние между последователь-
последовательными точками si/ равно 1, в то время как расстояние между не-
непоследовательными stj равно -у/2. Это означает, что sy обра-
образуют одноцветную копию графа Q. D
') Строго гоиоря, это относится к Z но расширение до Е> несложно.

50
Глава 7
Ряд результатов в этом направлении был опубликован сов-
совсем недавно (например, [EGMRSS1, 2, 3]). Вот один из них: из-
известно, что R(C, 2, 2) выполняется, когда С — множество вер-
вершин любого прямоугольного треугольника.
Однако следующая гипотеза остается неразрешенной.
Гипотеза. При всяком 2-раскрашивании пространства Е2
каждое трехточечное множество наличествует монохромати-
монохроматически, за исключением, быть может, вершин лишь одного рав-
равностороннего треугольника.
Задача. Покажите, что R(C, 2,3) никогда не выполняется,
если |С| = 3.
Упражнение 7.3. Покажите, что если Е2 покрыть двумя зам-
замкнутыми множествами цветов, то любое трехточечное множество
наличествует монохроматически.
Теперь дадим определение, ключевое для этой главы.
Определение. Конфигурация С называется рамсеевской1),
если для каждого г существует п, такое, что R(C,n,r) выпол-
выполняется.
Другими словами, конфигурация С является рамсеевской,
если наличие ее одноцветной копии в г-раскрашенном Е" зави-
зависит только от величины п.
Упражнение 7.4. Покажите, что если конфигурация С рам-
сеевская, то С должно быть конечно.
. Пример. Множество С из вершин равностороннего треуголь-
треугольника является рамсеевским, поскольку, как отмечалось (упр. 7.1),
R(C,2r,r) выполняется.
Должно отметить, что если множество С рамсеевское, то по
теореме компактности существует конечное множество X, кото-
которое всегда содержит одноцветную копию С, каково бы ни было
его г-раскрашивание.
Рамсеевость всех известных доныне рамсеевских конфигура-
конфигураций основывается на следующем результате.
Теорема 7.1. Если множества С\ и С2 рамсеевские, то и
С\ X С2 рамсеевское2).
Доказательство. Зафиксируем С\ = Ет, С2 Е Е", и пусть
геи. Выберем и таким, что R(Cuu,r) выполняется. Согласно
Евклидова теория Рамсея
51
теореме компактности, найдется конечное множество Т д[", та-
такое, что любое r-раскрашивание Т влечет за собой одноцвет-
одноцветность С\<=Т. Пусть t — \T\ и Т = {хи ..., xt). Выберем v так,
чтобы R(C2, v, г') выполнялось.
Утверждение. R (С\ X С2, и -\- v, r) выполняется.
Доказательство утверждения. Пусть раскраска %: Е"+о-*-[/]
задана. Определим индуцированное раскрашивание %': Е"->-|/']
по правилу %'(y) = (%(xiXy), %{х2Х У), ¦ ¦ ¦, %{xt X у)). Со-
Согласно выбору v, в Е" найдется копия С2 — mono%', скажем С2.
Определим, наконец, индуцированное r-раскрашивание %"
множества Т, полагая %"(х{) = %(х, Ху) для некоторого у е С2.
(Это определение корректно, поскольку С2 — mono%'.) Теперь
остается проверить, что Т (вследствие выбора и) содержит од-
одноцветную копию С\ X С2- а
Поскольку любое двухточечное множество рамсеевское, то
и любое (декартово) произведение таких множеств также будет
рамсеевским. Они суть в точности множества вершин прямо-
прямоугольных параллелепипедов; их мы также будем называть кир-
кирпичами. Все известные в настоящее время рамсеевские множества
являются подмножествами кирпичей. В этой связи возникает
интересный вопрос: какие симплексы1) S являются подмноже-
подмножествами кирпичей?
Конечно, необходимо, чтобы для любых трех вершин S тре-
треугольник, ими образуемый, не был тупоугольным. Для п = 2, 3
это условие оказывается и достаточным. Общего хорошего опи-
описания таких «прямоугольных» симплексов пока нет. Неожидан-
Неожиданности начинаются с размерности 4: в Ё4 существует симплекс со
всеми реберными углами, меньшими чем 89°, не являющийся
подмножеством никакого кирпича. Кстати, он примечателен еще
и тем, что является' для нас первым примером нерамсеевского
конечного множества. Но этой уникальности его лишает следую-
следующий результат.
Будем называть множество сферическим, если оно лежит на
сфере в некотором Е".
Теорема 7.2 [EGMRSS1]. Если множество С рамсеевское, то
оно сферическое.
Для доказательства теоремы потребуется несколько предва-
предварительных лемм.
Лемма 1. Существует 2п-раскрашивание % прямой R, такое,
что уравнение ?"_,(*/< — y'i)== 1 не имеет решений с
') А как же иначе?
*) С\ X С? обозначает обычное декартово произведение.
') То есть вершины симплекса.

52
Глава 7
Доказательство. Определим х, полагая х(#) = / при условии
ye[2m + j/n, 2m + (j+ I)/")- meZ. Тогда равенство х (*/,) =
Е=Х(^Э влечет за собой yt — y'i — 2mi+Qi для некоторого 6,-:
|0,|< 1/л. Тогда
где 0 = ?г_1Э,-. Но это равенство не может иметь места, так
какО<|0|<1. ?
Лемма 2. Пусть си ..., сп, Ъ ф 0 сг/гь действительные числа.
Тогда существует Bп) "-раскрашивание %* прямой R, такое, что
уравнение
Z
G.1)
не имеет решений с х*(*() = X*{х\), 1 < / < п.
Доказательство. Заметим, что G.1) выполняется тогда и
только тогда, когда
!/;(*,•-*;)=!. -G.ioi
где c\ = clb~x. Определим х* на R по правилу
X (а) = X* (Р) <=>¦ X «а) = х (с'р) V/ е= [л],
где х —это 2п-раскрашивание, определенное в лемме 1. Таким
образом, х* — эт0 некоторое Bп)"-раскрашивание. Предполо-
Предположим теперь, что равенство G.1') выполняется при х* (*',) = %*(*;),.
1</</г. Но тогда %{c*jxi) = %(ctjx'.), 1<г, /<п, и, в частно-
частности, Х(с"х^ = х(с*х1), 1^/<л. Стало быть,
п п
i_i '^ ' '' 1-Л ' 1 ' *' .
= S Bт,. + в, - 2т; - 0;) = 2М + ? (в, - бД Ф I,
поскольку 0 ^ ?"_, 10( — 0; | < 1. ?
Далее понадобится геометрическая
Лемма 3. Множество К = {уо, •. •, п\) не является сфери-
сферическим тогда и только тогда, когда существуют с,-, не все рав-
равные 0, такие, что
Евклидова теория Рамсея
53
(I) У с (v п ) = 0
еде для х = (х\ хп) запись х2 обозначает х • х = х\ -\- • • • -f
Доказательство. Пусть /(^сферическое множество, лежащее
на сфере радиуса г с центром в да, и пусть /(удовлетворяет п. A).
По теореме косинусов имеем /-2==@,- — wJ = {5q — шJ + (^
— voJ — 2(vi — vo){w — vo), т. е. (Vi — voJ = 2(vi^
— по), поскольку (г>о — wJ = г2. Поэтому
'- что противоречит п. B).
1 С другой стороны, пусть К не является сферическим. Без
¦¦' потери общности предположим, что К—минимальное несфери-
\ ческое множество, т. е. любое собственное подмножество мно-
\ жества К является сферическим множеством. Точки ?>,-, 0 < i <
¦'¦ ^ k, не могут образовывать симплекс, поскольку симплекс есть
; сферическое множество. Поэтому векторы у,- — v0 должны быть
i линейно зависимыми, т. е. должны существовать числа а,
: 1 ^ i ^ k, не все равные нулю, такие, что
Z ct (v{ - б0) = О,
G.2)
например ck ф 0. По предположению минимальности множества
К векторы по, .. •, У*-1 лежат на некоторой сфере радиуса г
с центром в до. -
Так как v\ — v\ = (у,- — доJ — (р0 — доJ + 2 (vl — v0) до, то
Z с, {у] - v\) =tct ((в, - ДОJ - (в, - доJ) +
k
+ 2 ? с, (в, - е>„) ш = cft ((в* - доJ - г2) ^= о,
поскольку имеет место равенство G.2) и вектор у* не лежит
на сфере радиуса г с центром в до. Следовательно, п. B) вы-
выполняется, и тем самым лемма доказана. П
Изложим теперь
Доказательство теоремы 7.2. Предположим, что С = {% . ....
..., vn) не является сферическим множеством. В силу леммы 3

54
Глава 7
существуют с,- и b ф О, такие, что
G-3)
Окрасим каждую точку «еЕ* в цвет i по правилу х(м) =
= Х*("Х«), где х* есть Bп) "-раскрашивание из формулировки
леммы 2. Таким образом, если х окрашивает в один и тот же
цвет все vi, то %* окрашивает в один и тот же цвет v\, что не-
невозможно, поскольку, согласно лемме 2, уравнения G.3) не
могут иметь одноцветных решений. Следовательно, при этом
Bп) "-раскрашивании х пространства Е" множество С не может
наличествовать монохроматически. Значит, в силу произволь-
произвольности N множество С нерамсеевское. ?
Простейший пример нерамсеевской конфигурации представ-
представляет собой множество L, состоящее из трех коллинеарных то-
точек. Согласно доказанной теореме, пространство Ew может быть
16-раскрашено без наличия одноцветного L. Неизвестно, можно
ли здесь константу 16 уменьшить.
Схематически ситуация такова:
Кирпичи ? Рамсеевость е Сферичность.
Сегодняшнее «экспертное» мнение тяготеет к тому, что ле-
левая часть истинна, хотя для этого нет никаких реальных осно-
оснований. Простой путь поколебать это мнение мог бы состоять,
например, в демонстрации того, что множество вершин некото-
некоторого тупоугольного треугольника рамсеевское. Было бы очень
интересно увидеть, как эта ситуация в конце концов разрешится.
Упражнение 7.5. (Очень кстати!) Покажите, что для любых
четырех точек в Е2 некоторое расстояние между двумя из этих
точек не является нечетным целым.
Рассмотрим теперь следующий вопрос. Какие рамсеевские
теоремы могут выполняться, когда фиксированное евклидово
пространство разбивается на произвольное (конечное) число
(цветовых) классов, а группой преобразований является груп-
группа движения Е"? Как уже отмечалось в упр. 7.2, даже семи
цветов достаточно, чтобы избежать появления одноцветной пары
точек с предписанным расстоянием (в Е2). А положительный
результат в этом направлении, гипотетически высказанный
Р. Гуревичем, состоит в следующем:
При любом конечном раскрашивании
Е2 всегда найдутся три точки, имеющие
одинаковый- цвет и образующие тре-
треугольник площади 1.
Евклидова теория Рамсея
55
Обычно мы будем говорить проще: найдется одноцветный
треугольник площади 1. Для доказательства некоторой усилен-
усиленной формы этой гипотезы нам понадобится
Теорема 7.3. Для каждого г е ш существует (наименьшее)
положительное целое Т(г), такое, что при любом г-раскраши-
вании Z2 всегда найдется одноцветный прямоугольный тре-
треугольник с площадью, в точности равной Т(г).
Доказательство. Для фиксированного геи предположим,
что решетка точек Z2, будучи г-раскрашенной, не обладает од-
одноцветным прямоугольным треугольником площади Т=Т(г),
где Т(г) определяется по такому правилу:
Пусть Si=l, Si+]=(Si+l)\WB(Si+\)l + l, i+\), »<
^ i < г, и W(k, г)— функция ван дер Вардена ') (из гл. 3).
Положим Т = T(r) = S1S2 ••• Sr.
Шаг 0. Пусть X, обозначает целое Sr-\Sr-2 ¦ ¦ ¦ S2S1. Рас-
Рассмотрим последовательность из Wr = WB(Sr-i + 1)! + 1,г) це-
целых точек (iXr,0), I ^ t^ Wr, на оси х. Так как по предполо-
предположению эти точки r-раскрашены, то по определению W они со-
содержат одноцветную арифметическую прогрессию из 2(Sr-\-\-
+ 1)! + 1 членов, скажем {ar + igrXr,0), 0 ^ i < 2(S,_i + 1)!,
где gr — величина шага этой прогрессии. Конечно, gr ^ Wr. Без
ограничения общности можно предполагать, что точки этой про-
прогрессии имеют цвет г. Так как мы предположили отсутствие
одноцветных прямоугольных треугольников площади Т, то оп-
определенные точки Z2 не могут иметь цвет г. В частности, точки
вида
рц = [ar + igrXr, JXJ^T
не могут иметь цвет г. Если бы это было не так, то, привлекая
еще две точки цвета г, именно р, = (ar -\- igrX, 0) и р, = (аг +
+ igrXr + grXr (Sr-i -f- 1)!//, 0), получили бы прямоугольный
треугольник цвета г и площади Т (рис. 7.1).
Заметим, что пространство между соседними строками в
этой таблице имеет величину
/g, G.4)
Шаг 1. Прежде всего слегка преобразуем систему коорди-
координат, приняв нижнюю строку таблицы (/?,/) за новую ось х, а са-
самый левый ее столбец — за ось у. В этой системе координаты
') То есть л-раскрашивание [W(k, r)] всегда содержит одноцветную
ft-членную А. Ц,

56
Глава 7
наших точек (с учетом G.4)) принимают вид ЦегХг,
BWA/gr)j), 0<t-<(S,-, + l)!, 0^/^S,-,. Пусть It=
— (Sr-i-\- l)\grSr-2 ... S2Si. Сосредоточим внимание на точках
базовой строки вида (t%-i,0). Так как Xr-i/grXr = Er_, +
+ 1)!/St-i, to все эти точки находятся в нашей свободной от
цвета г подтаблице 0 < / < Sr-u Но, согласно определению,
Sr-,1 ^ WB(Sr-2 + О' + 1. r—\)=Wr-u значит, среди этих
точек должна найтись некоторая одноцветная арифметическая
ZrXr grXr
Рис. 7.1.
прогрессия с 2Eг-2+1)! + 1 членами, скажем ((ar-i'+1
+ igr-i)Xr-u 0), 0 «? i s^ 2 (Sr-2 + 1)!, где gr-i ==S Wr~\\ без огра-
ограничения общности можем предполагать, что эта прогрессия
имеет цвет г—1. Как и ранее эта арифметическая прогрессия
предохраняет от наличия определенных точек цвета г — 1 в на-
нашей таблице; в частности, так же как и ранее, точки вида
i /„ w 2Г/
1)!
не могут иметь цвет г—1. Заметим, что так как строчное про-
пространство в этой подтаблице равно
2T/gr-lXr-! (Sr-2 + 1 ) ! = 2WA Wr-l\/grgr-l,
то эти точки p'tl оказываются подмножествами множества то-
точек pi,-, и, значит, они также не могут иметь и цвет г.
Шаг k. Предположим, что теперь имеется изолированная
подтаблица из точек
'-0
G.5)
-ft».
Евклидова теория Рамсея
57
не содержащая цветов г, г—1, ..., г— k-\-\, где
^=^BE,-1
1, 0. r-
Положим
Xr-K = (Sr-1
1 ) !
(Sr_* + 1 ) \gr ¦ ¦ . gr-k+lSr-Ш ¦ ¦ ¦ 52S! = =
i = Xr-k+1 (Sr-k + 1) \gr-k+\/Sr-k--
"i Так как Xr-k/gr-k+\Xr-k+\ = {Sr-k+ \)\/Sr-k, то точки (iXr_*,0),.
•i 0 ^ i ^ 5r-fe, принадлежат нашей подтаблице {qa). Кроме того,,
' так как S,-* 5» H?B(S,_*_i + 1)! + 1, r — k)saWr-k, то точки;
(iXr-k, 0) содержат одноцветную арифметическую прогрессию'
из 2Eг-*-1 + 1)! + 1 членов, скажем ((ar-k + igr-k)Xr-k,O);,
0 ^ i< 2Er_ft_i + 1)!, где gr-k ^ Wr-k, и без ограничения:
общности можно предполагать, что эта прогрессия имеет цвет
г — k. Расположение этих точек влечет за собой, что ни одна
из точек подтаблицы (дц) вида
igr~k)
1I) •
не может иметь цвет г — k. Видим также, что пространств»
между соседними строками в (q'it\ равно
2Г
W
r_k\
Простой заменой координат приходим теперь к таблице вида
G.3) с г — k + 1 вместо г — &.
По завершении (г — 2)-го 'пага, наконец, образуется пря-
моугольная таблица из точек р* (все цвета 1), которая может
быть записана (в подходящей системе координат) как
где ^2
... (S2 +
'(Ply) есть
+ l)! + l, 2) и Х2 = (Sr_, + 1)! ...
. Вертикальное строчечное пространство
IT _ 2Wr\Wr-l
Однако три точки p^, р2о> Poi образуют прямоугольный тре
угольник цвета 1 с площадью
(l/2)Bg2X2)BT/2g2X2)=T,

58 Глава 7
поскольку 5i = 1. Полученное противоречие завершает доказа-
доказательство теоремы. О
Легко видеть, что использованные здесь рассуждения при-
применимы и к непрямоугольным таблицам. Таким образом, как
непосредственное следствие теоремы 7.3 в подходящем мас-
масштабе получаем следующий результат, являющийся усилением
гипотезы Гуревича.
Следствие. Для каждого а > 0 и любой пары непараллель-
непараллельных прямых L\ и Li при любом разбиении плоскости на конеч-
конечное количество классов некоторый класс содержит вершины
треугольника, который имеет площадь а и две стороны, парал-
параллельные прямым L\ и L2.
Сравнительно просто распространить эти идеи на доказа-
доказательства соответствующих результатов в Е", используя п-мер-
ное обобщение теоремы ван дер Вардена для Е". Читатель не
должен столкнуться с трудностями при детальном доказатель-
доказательстве следующего обобщения:
Теорема 7.4. Для каждого а>0 и любого множества из п
прямых L\, .... Ln, которые порождают пространство Е" (т. е.
линейная оболочка которых и есть Е"), п ^ 2, при любом раз-
разбиении \Еп на конечное количество классов некоторый класс со-
содержит вершины п-мерного симплекса, имеющего (п-мерный)
объем а и параллельные прямым L; ребра, исходящие из одной
вершины.
Упражнение 7.6. (а) Каково значение ТB) в теореме 7.3?
(b) Что можно сказать о 7C)?
(c) Покажите, что Т (г) ^ и.о. к. B, 3, ..., г)/2 для каж-
каждого г.
Упражнение 7.7 (Штраус). Покажите, что в теореме 7.3
«площадь 1» нельзя заменить на «периметр 1».
Замечания. Неизвестно, могут ли эти результаты распростра-
распространяться на конфигурации более общие, нежели симплексы. На-
Например, применима ли теорема 7.2 к параллелограммам (т. е.
к четырем вершинам параллелограмма), ромбам, прямоуголь-
прямоугольникам? Разумеется, легко видеть, что она не выполняется для
квадратов.
Имеется плотностный аналог теоремы 7.3, который можно
доказать, исходя из теоремы Семереди вместо теоремы ван дер
Вардена. Этот плотностный аналог утверждает, что для любого
е>0 существует целое Т(г), такое, что если п^п(г) и R е
— {('. /): 1 *^ г> / ^г я}.~|#| > en2, то граф R содержит вершины
треугольника площади Г(е). Непрерывным аналогом служит
Общая теорема рамсеевского умножения
59
одна старая теорема Эрдёша, которая утверждает, что если
X— неограниченное множество положительной меры на пло-
плоскости, то X содержит вершины треугольников всех площадей.
Наконец, было бы интересно получить несколько улучшен-
улучшенные оценки для функции Т(г) из теоремы 7.3. Обладает ли эта
функция в действительности гиперэкспоненциальным ростом
аккермановского типа, как и верхние оценки для W(k, r), или
же на самом деле ее поведение более скромно?
Глава 8
ОБЩАЯ ТЕОРЕМА
РАМСЕЕВСКОГО УМНОЖЕНИЯ
В этой короткой главе доказывается весьма общая теорема
«умножения», которая приводит к нескольким интересным
приложениям в теории Рамсея. Сначала введем некую терми-
терминологию.
Семейство ЯГ из конечных подмножеств множества U назы-
называем рамсеевским, если для всех г sew и всех г-раскрашиваний
%: U-*~[r] существует одноцветное F e ST. Для данного произ-
произвольного отображения Р: ?/Х U -> U семейство &~ именуем
Р-идеалом множества U, если Fey =>P(F, и)^ЗГ, Р(и, F)^
^.ЯГ, для всех ие(/, где Р продолжается на 2иХ2у обычным
образом, т. е. Р(Х, У) = {Р{х, у): х<^Х, уеУ) для X, Y<=U.
Следующий, отчасти неожиданный результат показывает,
что рамсеевское свойство выполняется одновременно для произ-
произвольных совокупностей рамсеевских семейств при весьма общих
условиях.
Теорема умножения. Пусть {^"Jjej—произвольная сово-
совокупность из рамсеевских Р-идеалов множества U, где отобра-
отображение Р: UX U-*¦ U произвольно. Тогда для любого геи и,
любого г-раскрашивания %: ?/-»-[г] найдутся fe[r] и Fa^&~a,
а е А, такие; что Fa E X" @ для всех а ее Л.
Иными словами, имеется один цвет i, в который одноцветные
элементы Fa^&~a окрашены одновременно для всех аеА. Ис-
Кодя из этого, техника доказательства должна быть достаточно
простой (и использующей, разумеется, индуцированные рас-
раскраски), в связи с чем мы приводим (для полноты) компактный,
вариант доказательства [GS].

60
Глава 8
Доказательство. Сначала покажем, что для любого целого
m и любой конечной подсовокупности УО|, ..., &~at из
{^"a}ae/i найдется конечное подмножество F = \!Fa.i, .-., &*"'*]„
из U, такое, что для всякого раскрашивания %: F-+[m] суще-
существуют ie[m] и Fi^SFa, для которых F/Sx~40> 1 ^ / ^?
Для i = 1 это сразу следует из теоремы компактности. Пусть
t > 1 фиксировано, и предположим, что утверждение выполнено
для всех t<t. Оно очевидно выполняется при т= 1, поэтому
пусть in > 1 фиксировано, и предположим, что утверждение
также выполняется для t = t и всех m <.m. Пусть ?Га1, •.., #"а?
— произвольная фиксированная подсовокупность {&~а)а^А- Со-
Согласно предположению индукции, множества X = f&~ai> •••
...,?"„- 1 , У = \3~аЛ ,где т( = йИ, и Z ==/>(*, У) суще-
ствуют и конечны. _
Пусть %: U->-[fn] — произвольное фиксированное т-раскра-
шивание U. Определим индуцированное раскрашивание х* мно-
множества У так, что %*(у) — х*(«/'). </> У'е ^> тогда и только тогда,
когда х(Р(х,у)) = х(Р{х,у')) для всех хе= X.
Поскольку |Р(АГ, г/) |^|^| для всех i/еУ, то х* является
некоторым т*-раскрашиванием множества У. Согласно опреде-
определению У, существует F. е ^"а-> такое, что F. s х* @ Для не-
некоторого i e [m*]. Пусть / е F..
Теперь введем иное раскрашивание %': Х-*-[т], полагая
%'(х) = %{Р(х, /)), ^е! Заметим, что значения %' в действи-
действительности не зависят от выбора /.
Согласно определению X, существуют k e [т] и Ft e ^"О/)
такие, что Fj^%'-l(k), l^j^t— 1. Стало быть, P(F/, /)s
EX (A), 1 </<*—!, и, значит, P(F,,F{)^x-l(k), 1</^
<г—1, поскольку х(^(*./)_) = Х(^(*.П). ^1 и /, feff.
Но Р (F,-, /) <= 5Г«/. 1 < / < ? — 1, поскольку #-ау — это Р-
идеал, и по той же причине Р(х, Fje^o- А так как все t
из этих множеств лежат в %~l(h), то P(X,Y) можно использо-
использовать какГ^"а, ••• &~а 1 • Это завершает индукционный переход,
L t-irh
и тем самым первое утверждение доказано.
Предположим теперь, что теорема неверна. То есть при не-
некотором г существуют раскрашивание %: U-*-[r] и семейства
д ,
такие, что
для всех F,
?, 1 </<г.
(8.1)
Согласно доказанному утверждению, (конечное) множество
]r^t/ существует, Таким образом, для некото-
Теоремы Шура, Фолкмана и Хиндмана
61
рого k^[r] и F\ = ^"Р/ имеем /^s X" (*), 1 < j < г. В частно-
частности, FkS%~l(k) и F'k^@~pk а это противоречит соотношению
(8.1); тем самым теорема доказана. ?
Упражнение 8.1. Докажите, что при любом конечном раскра-
раскрашивании Е2 некоторый цвет содержит треугольники каждой
площади. (Указание: воспользуйтесь теоремой умножения.)
Глава 9
ТЕОРЕМЫ ШУРА, ФОЛНМАНА
И ХИНДМАНА
В 1916 г. Шур [Scl] доказал теорему, являющуюся, по-види-
по-видимому, наиболее ранним результатом ясно выраженного рам-
сеевского типа ').
Теорема 9.1. Для каждого конечного раскрашивания мно-
множества Z* существует одноцветное решение уравнения
х + у = г. (9.1)
Доказательство. Здесь поможет простое применение теоре-
теоремы Рамсея. В качестве ./V возьмем число Рамсея #B,3, г) из
гл. 2, и пусть %: [N]->-[r]. Это порождает некоторое г-раскра-
шивание х* ребер графа Kn по правилу
По определению JV граф Kn должен содержать одноцветный
треугольник цвета х*> скажем {i, /, k) с i < / < k. Таким обра-
образом, %(j — i)=%(k — j) = %(k — i). Поэтому равенство (/ — /)+,
-\-[k — /) = k — i является одноцветным решением уравне-
уравнения (9.1). п
Здесь, быть может, интересно отметить, что теорема 9.1
была нужна Шуру в связи с хорошо известным предположе-
предположением Ферма:
Уравнение хт + ут = zm не имеет решений в положитель-
положительных целых для т ^ 3.
Шур показал, что для каждого т сравнение хт + ут s
==zm(modp) всегда имеет решение для всех достаточно боль-
больших простых р. Чтобы убедиться в этом, обозначим через Zp
') За исключением, возможно, работы Гильберта [Н] 1892 г.

Глава 9
поле вычетов по модулю р, а через g первообразный корень по
модулю р (т. е. g порождает Z*p). Также положим п =
= н. о. д. (т, р—1). Тогда т-е степени в Zp суть в точности
{gmt: (eZ} = {f(: (eZ), поскольку g?-1 = 1 (modp). Таким
образом, можем предполагать, что т\{р—1), поскольку
п\ (р— 1). Стало быть, каждый ненулевой x^Zp можно запи-
записать в виде х = gi+m>, где 0 ^ I < m (так что такое i единствен-
единственно). Определим m-раскрашивание %: Zp — {0}->[т] по правилу
^(g<+m/)_j j^aK видно из доказательства теоремы Шура, при
достаточно большом р (например, p>RB,3;m)) найдутся х,
у, zeZp — {0}, удовлетворяющие равенству х + у = z и имею-
имеющие один и тот же цвет, скажем I. Поэтому x^g i+mlxt y==gl+m'y'
у g
z = gi+m'z. А поскольку x + у = z, имеем g
i+mlx
i + tniu —
+ gi+m'y =
= gl+miz{moA p), и, умножая на g~l, получаем gmlx + gmly==
= gm'z(mod p), что и дает требуемое решение. ?
В конце шестидесятых годов по крайней мере три автора
[Sa; GR1; F1] независимо обнаружили следующее обобщение
теоремы Шура. Этот результат обычно именуется теоремой
Фолкмана в честь Джона Фолкмана, последнего в этом списке,
а в действительности он первым представил доказательство1).
Сначала введем
Определение. Для А = Z+ через FS(/4) обозначим множе-
множество конечных сумм, образованных из элементов множества А,
т. е.
FS (А) = { X i: 0 Ф I czA, I конечно).
Теорема Фолкмана. Для каждого конечного раскрашивания
множества Z+ существует сколь угодно большое подмножество
A a Z+ с одноцветным множеством FS(A).
Приводимое здесь доказательство следует оригинальному
доказательству Фолкмана (которое никогда не публиковалось).
Прежде всего нам понадобится
Лемма. Для любых k, tge Z+ существует п = n(k, г), такое,
что при всяком г-раскрашивании %: [п]-^[г] всегда найдется
А = {аи ..., ak) с FS(i4)s[n], так что x(Z; s/ i) = x(niax(/))
для всех (непустых) / = Л.
Доказательство. Проведем индукцию по k. Для k = 2 лемма
тривиальна. Предположим, что требуемое имеет место при не-
некотором фиксированном значении k~^2. Утверждается, что
') Как оказалось, этот результат также прямо следует из работы Радо
тридцатых годов. Мы обсудим это в следующей главе.
Теоремы Шура, Фолкмана и Хиндмана
63
можно взятьв качестве п (k + 1, г) величину 2W* = 2W(n(k, г) +
+ 1, г), где W — функция ван дер Вардена.
Чтобы убедиться в этом, положим %: [2W*]^*-[r] и обратим-
обратимся ко второй части интервала, т. е. [Й^*+ 1,2№*]. По опреде-
определению W* она содержит mono^ А. П. из n(k,r)-\- 1 членов, ска-
скажем ak+\, ak+\ + d, ..., ak+i + n(k, r)d — все красные.
Между тем, обращаясь к первой половине отрезка, рассмот-
рассмотрим множество d[n(k, r)] = {d, 2d, ..., dn(k,r)}. По предпо-
предположению индукции (наличие множителя d здесь ничего не ме-
меняет) найдутся da\, ..., dak^d[n(k, r)] (с тем свойством, что
(dai + ••• — dak) ^ dn(k, r) ^ W*), такие, что цвет любой ча-
частичной суммы зависит только от цвета наибольшего dai. Эта
ситуация проиллюстрирована на рис. 9.1.
-W*-
¦W*-
aktl+2d.
Рис. 9.1.
Искомое множество есть в точности A'= {da,\, ..., dak,
} Е /Л' A) ((I)) ?1
dak+\}. Если /еЛ', то
( ((I)
{
п) = %(max(I)) при ак+х<?1 и ра-
равен %(ak+i = %(max(I)) при a*+i е/. Это завершает индук-
индукционный переход, и тем самым лемма доказана. ?
Для завершения доказательства теоремы Фолкмана предпо-
предположим, что г, k e Z+ и х- Z+-+[r] заданы. Выделим (исполь-
(используя лемму) множество А = {а\, .-., ar(k-i)+i}, такое, что
XB(e/i) для /еЛ зависит только от тахG). Таким образом,
каждый индекс /е[г(/г—1)+1] обозначает цвет (это и есть
индуцированное раскрашивание), именно цвет, задаваемый зна-
значением xB/e/t), где тах(/)=а/. Согласно принципу ящиков,
k различных индексов из [r(k— 1)+1], скажем /ь j2, ..., /*,
должны иметь один и тот же цвет. Тогда множество А* = Ja;. ,
а. а X обладает требуемым свойством, т. е. FS(/1*)
'2 Ik)
одноцветно.
D
Было бы интересно выяснить, можно ли теорему Фолкмана
вывести непосредственно из теоремы Рамсея (подобно доказа-
доказательству теоремы Шура).
Недавно А. Тейлор [Та] предложил иное доказательство
теоремы Фолкмана. Его доказательство, в котором не исполь-
используется теорема ван дер Вардена, проще имевшихся и в деиетви-

64
Глава 9
тельности дает верхние оценки (для конечного аналога), кото-
которые можно выразить в элементарных функциях. Именно, Тей-
Тейлор показал, что если S(k,r) обозначает наименьшее целое,
такое, что при любом r-раскрашивании [S(k,r)] найдется
^-множество A^[S(k, г)] с одноцветным FS(/1), то
к, г > 2..
S(k, r) < V
Упражнение 9.1. Покажите, что если А = {а\ < а2 < •••} и
разность ап+\ — ап ограничена, то для любого к найдутся
B = {bu ..., Ьи) и /.такие, что t FSBA
Упражнение 9.2. Покажите, что теорема Фолкмана эквива-
эквивалентна следующему утверждению: для любого конечного рас-
раскрашивания конечных подмножеств со всегда можно найти k
непересекающихся непустых подмножеств S], ..., Sk, таких,
что все (непустые) объединения этих S,- имеют один и тот же
цвет. (Указание: рассмотрите разложения ieZ+ по основа-
основанию 2 и используйте усиление теоремы Рамсея, которое гаран-
гарантирует, что в любом конечном раскрешивании конечных под-
подмножеств со найдется /-множество L, такое, что для всех /gt,
j/|^fe, цвет / зависит только от |/|. Конечно, как «подупраж-
нение» это тоже нужно доказать.)
Упражнение 9.3. Постройте 2-раскрашивание конечных под-
подмножеств со, такое, что для каждого бесконечного X s со най-
найдутся A, BczX, имеющие различные цвета и |Л| = |В|.
Упражнение 9.4. Докажите аналог (конечный вариант) тео-
теоремы Фолкмана для групп. Иными словами, докажите, что для
всех k, r^'Z+ существует n'(k,r), такое, что если %: G->-[/¦]
есть произвольное г-раскрашивание группы G с \G\ ^ n'(k, r),
то должна существовать подгруппа XgGc \X\ = k, такая, что
все непустые (групповые) произведения, образуемые из элемен-
элементов подгруппы X, имеют один и тот же цвет. (Указание: исполь-
используйте тот факт, что большие группы содержат большие абелевы
подгруппы1).)
После того как теорема Фолкмана стала известна, возник
естественный вопрос: верен ли ее бесконечный аналог? Он был
поставлен в конце шестидесятых годов независимо в работах
[Sa] и [GR1]. Должно отметить, что ответ на него непосред-
непосредственно не следует из соображений компактности, и сам вопрос
оставался открытым до. 1974 г., когда Хиндман [Hil] предло-
Желаю удачи.
Теорема Радо
65
жил в высшей степени изобретательное доказательство для
бесконечного аналога. Впоследствии его упростил Баумгартнер
[В] и сильно сократил Глазер (с использованием ультрафиль-
ультрафильтров) [G1]. За последние несколько лет проявился фундамен-
фундаментальный характер теоремы Хиндмана в дальнейших исследова-
исследованиях этой ветви теории Рамсея. Точности ради, приведем ее
здесь во всей полноте.
Теорема Хиндмана. Для каждого конечного раскрашивания
множества Z+ всегда найдется бесконечное подмножество
А е Z + с одноцветным FS(^).
Упражнение 9.5 (Натансон). Покажите, что имеет место бес-
бесконечный аналог упр. 9.1.
Глава 10
ТЕОРЕМА РАДО
Р. Радо начиная с 1933 г. опубликовал целый ряд ярких ре-
результатов в серии работ [Ral,2, 3] (на основе своей диссерта-
диссертации, выполненной, кстати, под руководством И. Шура), пол-
полностью осветивших следующий вопрос:
Какие системы 2 = 3?{х\, ..., хп)
однородных линейных уравнений над Z
обладают тем свойством, что при любом
конечном раскрашивании Z+ система 3?
обладает одноцветным решением?
Ответ на этот вопрос Радо дал в виде весьма компактного
необходимого и достаточного условия, называемого условием
столбцов. Как оказалось, он унифицировал доказательства тео-
теорем Шура, ван дер Вардена и Фолкмана. Тем самым была до-
достигнута высокая ясность их понимания как определенных
свойств разбиений рациональных решений линейных уравнений.
В этой главе докажем частный случай теоремы Радо, в ко-
котором содержится большинство существенных моментов. Это
случай, в котором 9? состоит из единственного уравнения
L'- ?(=i ctXi = 0, CjeZ — {0}. Будем называть L регулярным,
если каждое конечное раскрашивание множества Z.+ содержит
одноцветное решение уравнения L.

ее
Глава 10
Теорема Радо (одно уравнение). Уравнение L регулярно
тогда и только тогда, когда некоторая непустая сумма его коэф-
коэффициентов равна нулю.
Например, уравнения х-\-у— 2 = 0, х-\-у— 22 = 0 регу-
регулярны, а х + У — Зг = 0 нет.
Упражнение 10.1. Найдите конечное раскрашивание мно-
множества Z+, при котором уравнение х-\-у — 3z = 0 не имеет
одноцветного решения.
Для доказательства теоремы Радо прежде всего понадобит-
понадобится следующее усиление теоремы ван дер Вардена.
Теорема ван дер Вардена (сильная форма). Для любых
k, г, s e Z+ существует N = N(k, r, s), такое, что если [N] яв-
является r-раскрашенным, то всегда найдутся a, (feZ+, такие,
что а-\- d, a-\-2d, ..., а-\- kd и sd имеют один и тот же цвет.
Иными словами, не только есть й-членная А. П. {а -\- jd:
/е[й]}—monox, но и sd также имеет тот же самый цвет.
Доказательство. Используем индукцию по г. Для г = 1
можно взять d=l и N = тах{& + 1, s). Для фиксированного
г ^2 предположим, что N(k,r—\,s) существует для всех k и
s. Пусть N = sW(kN(k,r—l,s),r), где, как обычно, W — функ-
функция ван дер Вардена, и пусть раскрашивание %: \N]-+[r] про-
произвольно. Таким образом, можем найти a, (I'gZ+, такие что
[W(kN(k, r—\, s)r)]^{a + id': \^i^kN(k, r—\,s)} —
monox, скажем красные. Имеются две возможности:
(a) sd'j красное для некоторого /^[N(k,r— 1, s)]. Возьмем
d = jd'; тогда а + d, a-\-2d, .... a-\-kd = a-\- kjd' и sd = sd'j
все красные и, значит, N(k, г, s) существует;
(b) sd'j не красное для всех j<=[N(k,r— 1, s)]. Стало быть,
точки sd'[N(k,r—l,s)j имеют (г—1) цветов, и это очевидно
индуцирует некоторое (г—1)-раскрашивание [N(k,r—l,s)].
По определению N(k,r—l,s) существуют А -\- D, A -\- 2D, ...
.... А + kD и sD, имеющие один и тот же цвет, скажем голу-
голубой. Таким образом, в исходном раскрашивании sd'(A-\-D),
sd'(A + 2D), ..., sd'(A + kD) и sd'{sD) все голубые, т. е.
sd'A + sd'D, sd'A + 2sd'D, ..., sd'A + ksd'D и s(sd'D) тоже го-
голубые.
Значит, и в этом случае N(k,r,s) тоже существует. Это за-
завершает индукционный переход, и тем самым результат до-
доказан. п
Следствие. Для любых i,se Z+ и произвольного конечного
раскрашивания множества Z+ найдутся a, dGZ+, такие, что
{а-\-Ы: \k\^k}\J{ds}—money.
Теорема Радо
Доказательство теоремы Радо. A) Предположим, что сумма
некоторых коэффициентов равна нулю. Переобозначим их так,
что С\ + c<i + ••¦ + Ck = 0. Пусть х — некоторое г-раскрашива-
ние множества Z+. Если k = п, положим х\ = ••• =хп=1.
Это, очевидно, одноцветное решение уравнения L. Таким обра-
образом, далее считаем, что k < п. Положим А = н. о. д. (сь ..., ck),
B = ck+1+ — +сп, s = A/h.o.a.{A,B).
Если В = 0, то С\ + ••• + с„ = 0, и вновь х\ = ••• = хп = 1
есть одноцветное решение уравнения L. Следовательно, можем
считать, что ВфО. Значит, найдется /gZ, такое, что At-\-
+ Bs = 0. Кроме того, можно найти Я,ь ..., Я*еЕХ, такие, что
С1Я1 + ••• + Ckhk = At. Утверждаем теперь, что L для всякого
deZ+ и любого а имеет параметрическое решение вида
_ (а + М. i e [k],
Xi~\sd, i>k.
Действительно,
л ft k
dsB = 0.
sd
= a • 0
Наконец, выберем k0 > max | Xi |, a s, как и раньше. Согласно
следствию, найдутся a, deZ+, такие, что {а-\-Ы: \%\^ko}\]
\]{sd)—monox- Однако по определению k0 это множество со-
содержит решение уравнения L, и, значит, A) доказано.
B) Для доказательства в обратную сторону предположим,
что не существует непустой суммы коэффициентов с,-, равной
нулю. Выберем большое простое р и определим раскрашивание
Хр множества Z+ следующим образом: ieZ+ представляем
в виде х = pa(pt + k), \ ^.k^p—l, и полагаем iP(x) — k.
Таким образом, хР есть (р— 1)-раскрашивание Z+.
Предположим, что уравнение ?Г=1С;л:; = 0 имеет одноцвет-
одноцветное решение при раскраске Хр. скажем цвета k. Пусть X{=pai X
X (ptt + Щ ¦— такое решение. Предполагаем без ограничения
общности, что oci = ¦•• = as < as+i ^ as+2 ^ ••• ^ an, s^l
(допускается s = n). Тогда 2"=ic<^ = 2"-ic'Pa'(p^ + ^) = 0,
и, следовательно,
0 (mod p),
0 (mod p),
т.е.
*== 0 (mod p).

68
Глава 10
д(=(СиС2), ..., ? ce(C
Однако если р выбрано достаточно большим, например
р> ?"-i|cJ, то с необходимостью Xf=iC; = 0. Это противоре-
противоречит предположенному в B), и тем самым теорема Радо (для
одного уравнения) доказана. ?
Для того чтобы сформулировать необходимые и достаточ-
достаточные условия Радо (условия столбцов) для регулярности си-
системы линейных однородных уравнений 2, представим 2 в мат-
матричной форме: Ах = 0, где A=(aij)— это &Х «-матрица с це-
целыми коэффицеинтами и х = (хи ..., хп)т Будем говорить, что
А удовлетворяет «условиям столбцов», если можно разбить
столбцы матрицы А в непустые непересекающиеся подмноже-
подмножества (столбцов) С] U • • • U Cs = А так, что
(CC)
где с обозначает вектор-столбец матрицы А, а {X, Y, ,..> — век-
векторное пространство над Q, порожденное множествами векто-
векторов X, Y
В качестве примера читателю предлагается показать, что
следующая система удовлетворяет (СС):
Аи — 3v — 5х + у + 2г = 0,
2и + v + Зх + Чу — Зг = 0,
Зи — 2v + х + Чу — z = 0.
(Указание: не забывайте, что можно брать рациональные ли-
линейные комбинации.)
Теперь можно сформулировать общий случай.
Теорема Радо (общий случай). Система однородных линей-
линейных уравнений над Z регулярна тогда и только тогда, когда
она удовлетворяет «условию столбцов».
(Заметьте, что здесь есть и теорема об одном уравнении.)
Имеется иная формулировка теоремы Радо:
, Система регулярна, если она имеет топо%р-решение для
каждого раскрашивания %р и простого р.
Другими словами, если при каком-то раскрашивании одно-
одноцветного решения нет, то его нет и при некотором %р (упр. 10.1).
Детали доказательства (в действительности они не слишком
трудны) см. в [GRS; Ra2].
Упражнение 10.2. Покажите, что из теоремы Радо следует
теорема ван дер Вардена.
Современные вопросы теории
69
Упражнение 10.3. Покажите, что из теоремы Радо следует
теорема Фолкмана.
Упражнение 10.4. Найдите необходимое и достаточное усло-
условие для того, чтобы уравнение ?"=1СгХ; = 0 было разрешимо с
йеЛ, где А — произвольное подмножество из Z+ положитель-
положительной верхней плотности (т. е. limsup|Л [\[п] \/п > 0).
Глава 11
СОВРЕМЕННЫЕ ВОПРОСЫ
ТЕОРИИ
В этой заключительной главе остановимся на некоторых на-
направлениях теории Рамсея. Из-за недостатка места мы позна-
познакомимся с этими областями вкратце, но хочется надеяться, что
у читателя когда-нибудь появится желание более подробно
разобраться в некоторых из этих вопросов.
Начнем с того, что Фюрстенберг благодаря своим исследо-
исследованиям по эргодической теории дал совершенно иное доказа-
доказательство теоремы Семереди. Более того, используя такой под-
подход, Фюрстенберг и Кацнельсон [FuK] доказали и-мерный ана-
аналог теоремы Семереди, который не поддавался другим методам.
Вообще говоря, элементарные соображения эргодической тео-
теории и теории динамических систем уже использовались в топо-
топологических доказательствах теорем ван дер Вардена и Хинд-
мана.
' Приведем несколько результатов такого типа.
Теорема (Фюрстенберг, Вейс [FuW]). Пусть Т: Х-^-Х —не-
—некоторый гомеоморфизм компактного метрического пространства
(X,d) в себя. Тогда для любых г > 0, &<=Z+ существуют
х<=Х, neZ+ такие, что d(x,TnX)<e. (Это влечет теорему
ван дер Вардена.)
Теорема (Фюрстенберг [Ful]). Пусть Т: Х^-Х — некоторое
сохраняющее меру преобразование конечного метрического про-
пространства (X, |х) в себя. Тогда для любого Ле! положитель-
положительной меры существует neZ+, такое, что р(А[\ТпА[\ ...
... П ТкпА) > 0. (Это влечет теорему Семереди.)
Подробно эти результаты обсуждаются в работе [Fu2].
Возможно, такой контакт эргодической теории с комбина-

Глава И
торикой породит'плодотворный союз этих дисциплин.
Напомним, что система линейных однородных уравнений на-
называется регулярной, если она обладает одноцветными реше-
решениями при любом конечном раскрашивании множества Z+.
Будем называть подмножество XsZ+ регулярным, если каж-
каждая регулярная система S разрешима в X.
Упражнение 11.1 (Радо). Покажите, что если Z+ = С\ (J ...
... U Сг, то некоторое С* регулярно. (Указание: используйте тео-
теорему умножения.)
В 1973 г. Дьюбер [D1] разрешил гипотезу Радо сорокалет-
сорокалетней давности.
Теорема. Если IsZ+ регулярно и X = Cj (J ... [}СГ, то не-
некоторое С« регулярно.
Доказательство Дьюбера, использующее понятие так назы-
называемого (п, р, с) -множества, обеспечило весьма существенное
продвижение в этой области рамсеевской теории.
Параллельно с этим в последние несколько лет принци-
принципиально новое направление начало разрабатываться Пари и
Харрингтоном [РН]. Лишь слегка (!) модифицировав утверж-
утверждение (конечного аналога) теоремы Рамсея, они получили пер-
первый пример «естественной» теоремы, недоказуемой в арифме-
арифметике Пеано первого порядка. Одна из простейших форм такого
утверждения имеет следующий вид. Множество A s Z+ назы-
называем большим, если |Л | ;> тш(Л).
Теорема (Пэрис, Харрингтон [РН]). Для любых k, reZ+
найдется целое яг = РН(&, г), такое, что для каждого г-рас-
краишвания всех k-подмножеств множества [пг] найдется боль-
большое множество Xs[m], \Х\ > k, такое, что все k-nodмножества
X имеют один и тот же цвет. Однако этот результат не может
быть доказан в арифметике Пеано первого порядка.
Существование PH(k,r) сразу следует из бесконечного ва-
варианта теоремы Рамсея (поскольку каждое бесконечное мно-
множество содержит большое подмножество). Вместе с тем Пари
и Харрингтон показали, что это не выводимо в рамках арифме-
арифметики Пеано первого порядка. Одно из объяснений, почему так
происходит, состоит в том, что нижние оценки для PH(k,r)
растут так быстро, что в арифметике Пеано первого порядка
нельзя доказать даже их корректность. Последнее, в частности,
навело Соловея [So] и ряд других специалистов на мысль о
том, что известные оценки аккермановского типа для функций
ван дер Вардена и Халеса — Джеветта все-таки отражают ре-
реальную ситуацию. Интуиция автора подсказывает ему, что это,
по-видимому, не Так.
Современные вопросы теории
71
В этой связи отметим два следующих результата.
1. Пусть n(k) обладает тем свойством, что любое 2-раскра-
шивание множества {[а* + Р]: х = 1, 2, . .., n(k)} содержит
ft-членную А. П. Такие множества обладают рядом общих
свойств с А. П. (хотя их и больше). Какую величину можно
взять в качестве «(А)? Оказывается1), достаточно величины
порядка ck2.
2. Предположим, что последовательность А= {ai<a2<--}
имеет ограниченные дыры, скажем ап+\ — ап^ В. Какое число
w(k,B) членов последовательности А необходимо взять, чтобы
среди них нашлась /г-членная А. П.? Можно было бы ожидать,
что условие регулярности, наложенное на А, позволит получить
оценку сверху для w(k,B), например, в терминах примитивно
рекурсивных функций. Однако, как заметил Натансон2), функ-
функция w(k,B), по существу, ведет себя так же, как и W(k,B) —
обычная функция ван дер Вардена. С одной стороны, можно
В-раскрасить множества Z+, приписывая х цвет i, если ап + i =
= х <; ап+\ для некоторого ie{0,1 В — 1}. Значит, вся-
всякая одноцветная fe-членная А. П. цвета i должна быть сдвигом
(на i) некоторой fe-членной А. П. цвета 0, т. е. из А, и, следо-
следовательно, w(k, В) ^ W{k, В). С другой стороны, рассмотрим х^
Z+-*~[B]. Определим последовательность А(%)= {аи а2, ...},
полагая ak — (k—\)B-\-%(k), ?eZ+. Таким образом, ап+\ —
— ап<2В. Однако если с -j- d, c-\-2d, ..., c + kBd есть kB-
членная А. П. в А(%), то В-е члены ее, скажем с + Bd, с +
+ 2Bd, ..., с + kBd, имеют один и тот же /-цвет. Стало быть,
B{kB2B)
(k,B)^w{kB,2B).
В недавней (неопубликованной) работе Миллс показал, что
определенные функции, связанные с помеченными деревьями,
неожиданно (для меня) дают сверхвзрывной рост (и могут ис-
использоваться для двустороннего оценивания функции Пари —
Харрингтона). Только время покажет3), что же на самом деле
верно для функции ван дер Вардена.
Ранее уже упоминались некоторые из примечательных ре-
результатов, достигнутых не так давно Нешетрилем и Рёдлем.
Они преуспели в доказательствах большого числа утвержде-
утверждений, которые можно было бы назвать рамсеевскими результа-
результатами с «ограничениями». Так, например, если G — это Кп-сво-
бодный граф, то существует /(„-свободный граф Н: H-*-(G,G).
Или же: для любых k, re Z+ найдется множество /lgZ+, не
содержащее (k -f 1)-членной А. П., такой, что каждое г-раскра-
шивание А должно всегда содержать одноцветную fe-членную
А. П. Обзор этих результатов представлен в [NR1.3].
') Неопубликованная работа Абрамсона, Бурра и Эрдёша,
2) В ходе настоящей конференции.
- 3) Д мы, быть может, этого и не увидим.

72
Глава 11
Недавно ряд исследователей, включая, в частности, Хинд-
мана, Баумгартнера, Глейзера, Тейлора и Гальвина, предпри-
предприняли попытку изучения бесконечных аналогов рамсеевских тео-
теорем с помощью ультрафильтров. В частности, Глейзер полу-
получил на этом пути короткое доказательство теоремы Хиндмана.
Удобочитаемое изложение этих исследований можно найти в
[Hi2]. В этой связи Хиндман исследовал вопрос о возможности
усилений своей теоремы для бесконечных множеств со всеми
одноцветными конечными суммами. Ограничиваясь рассмотре-
рассмотрением степеней двойки, легко видеть, что каждое конечное рас-
раскрашивание множества Z+ содержит бесконечное множество
со всеми своими конечными произведениями, имеющими один
и тот же цвет. Хиндман показал, что нельзя гарантировать на-
наличие одноцветности всех произведений и всех сумм одновре-
одновременно. В частности, в [Hi3] он привел 7-раскрашивание
X: Z+-*-[7], при котором не существует бесконечного множе-
множества А: Лех~'@. {а + а': а ф а'<= A) s х~'@> {а-а': аф
Ф а' <= А) е х (О ДЛЯ некоторого /. Возможно, такое А и су-
существует, если опустить условие Л?х~'@-
Здесь вопрос открыт и для конечного случая.
Вопрос. Верно ли, что при любом конечном раскрашивании
множества Z+ найдется сколь угодно большое (конечное) мно-
множество А, все суммы и произведения из которого имеют один
и тот же цвет?
Вероятно, наибольшее число публикаций в последнее время
пришлось на рамсеевскую теорию графов; в ней было введено
много новых понятий, ознакомиться с которыми можно по ра-
работам [Вис; LeR; EFRS; ChuL] и обзорам [Bui, 2; BCL-F; Ра].
Большой и важной областью теории Рамсея, не затронутой
нами, является так называемое исчисление разбиений Эрдёша
и Радо. Это в основном рамсеевская теория бесконечных кар-
кардиналов и ординалов. Типичный результат этого направления
представляет
Теорема. (сди)-^(сои, ЗJ.
(Впоследствии снабженная весьма элегантным доказательством
Ларсона [La].)
То есть если пары из множества порядкового типа им 2-рас-
крашены, то найдется либо множество порядкового типа со* со
всеми парами, имеющими цвет 1, либо 3-элементное множество
со всеми парами, имеющими цвет 2.
Подводя последний итог знакомства с этой теорией, адре-
адресуем читателя к ожидающейся (?) книге Эрдёша, Хайнала.Мате
и Радо [EHMR] (которая, к сожалению, существует лишь
$ виде препринта). Многое из этого можно также найти в [W|.
Литература1)
[В] J. Baumgartner, A short proof of Hindman's theorem, J. Combinatorial Theory
Ser. A 17 A974), 384-386.
[BCUF] M. Behzad, G. Chartrand and L. Lesniak-Foster, Graphs and digraphs, Prin<
die, Weber & Schmidt, Boston, Mass., 1979.
[Be] E. R. Berlekamp, A construction for partitions which avoid long arithmetic pro-
progressions, Canad. Math. Bull. 11 A968), 400-414.
[Bo] B. Bollobis, Extremal graph theory, Academic Press, London, 1978.
[BrE] N. G. de Bruijn and P. Erdos, A colour problem for infinite graphs and a prob-
problem in the theory of relations, Nederl. Akad. Wetensch. Proc. Ser. A 54 A951), 371-373.
[Buc] F. Buckley, Graph functions which are Ramsey functions, Ann. New York
Acad. Sci. 328 A979), 52-57.
[Bui] S. A. Burr, Generalized Ramsey theory for graphs-A survey, Graphs and Com-
Combinatorics, Springer-Verlag, Berlin, 1974, pp. 52-75.
[Bu2] , A survey of noncomplete Ramsey theory for graphs, Ann. New York
Acad. Sci. 328 A979), 58-75.
[BuE] S. A. Burr and P. Erdos, Extremal Ramsey theory for graphs, Utilitas Math.
9 A976), 247-258.
[BuES] S. A. Burr, P. ErdSs and J. H. Spencer, Ramsey theorems for multiple copies:
of graphs, Trans. Amer. Math. Soc. 209 A975), 87-99.
[BuFS] S. A. Burr, R. J. Faudree and R. H. Schelp, On Ramsey-minimal graphs, Proc.
Eighth Southeastern Conf. on Comb., Graph Theory and Computing, Utilitas Math. Pub.,
Winnipeg, 1977, pp. 115-124.
¦ [Cha] С. С. Chang, A-partition theorem for the complete graph on to", J. Combina-
Combinatorial Theory Ser. A 12 A972), 396-452.
[Ch] F. R. K. Chung, A note on constructive methods for Ramsey numbers, J. Graph
Theory (to appear).
[ChG] F: R. K. Chung and R. L. Graham, On multicolor Ramsey numbers for com-
complete bipartite graphs, J. Combinatorial Theory Ser. A 18 A975), 164-169.
[ChuL] K. M. Chung and С L. Iiu, A generalization of Ramsey theory for graphs.
Discrete Math. 21 A978), 117.-127.
[Chvl ] V. Chvatal, Remarks on a problem ofMoser, Canad. Math. Bull. IS A972),
19-21.
[Chv2] .Tree-complete graph R amsey numbers, J. Graph Theory 1 <1977), 93.
JChvHl] V. Chvital and F. Harary, Generalized theory for graphs, Bull. Amer. Math.
&С.Л8 A972), 423-426.
') Работы, помеченные знаком *, имеются на русском языке (см. спи-
список на с. 76).

Литература
Литература
75
[ChvH2]
-, Generalized Ramsey theory for graphs. HI. Small off-diagonal num-
numbers, Pacific J. Math. 41 A972), 335-^345.
[Dl] W. Deuber, Partitionen und Lineare Gleichungssysteme, Math. Z. 133 A973),
109-123.
[D2] , Partitionstheoreme fur Graphen, Math. Helv. SO A9.75), 311-320.
[El] P. Erdos, Some remarks on the theory of graphs, Bull. Amer. Math. Soc.
S3 A947), 292-294.
*[E2] , Extremal problems in graph theory, Theory of graphs and its applica-
applications, Proc. Sympos. Smolenice, Publ.'Czechoslovak Acad., Prague, 1964, pp. 29-36.
[EFRS] P. Erdos, R. J. Faudree, С. С. Rousseau and R.. H. Schelp, The size Ramsey
number, Period. Math. Hungar. 9 A978), 145-161.
[EG] P. Erdos and R. L. Graham, On partition theorems for finite graphs, Colloq.
Math. Soc. Ja'nps Bolyai, vol. 10, Infinite and Finite Sets, Keszthely, Hungary, 1973,
pp. 515-527.
[EGMRSS1] P. Erdos, R. L. Graham, P. Montgomery, B. L. Rothschild, j. Spencer
and E. G. Straus, Euclidean Ramsey Theorems. I, J. Combinatorial Theory Ser. A 14 A973),
341-363.
[EGMRSS2] , Euclidean Ramsey Theorems. IF, Colloq. Math. Soc. Janos Bolyai, ,
vol. 10, Infinite and Finite Sets, Keszthely, Hungary and North-Holland, Amsterdam, 1973,
520-557
[EGMRSS3] , Euclidean Ramsey Theorems. Ill, Colloq. Math. Soc. Ja'nos Bol-
Bolyai, vol. 10, Infinite and Finite Sets, Keszthely, Hungary and North-Holland, Amsterdam,
1973, pp. 559-583.
[EH] P. Erdos and A. Hajnal, On chromatic number of.graphs and set-systems, Acta.
Math. Acad: Sci. Hungar. 17 A966), 61—99.
[EHMR] P. Erdos, A. Hajnal, A. Mate and R. Rado, Combinatorial set theory: Parti-
Partition relations for cardinals (to appear).
# [ES] P. Erdos and J. Spencer, Probabilistic methods in combinatorics, Academic Press,
New York, 1974.
[ET] P. Erdos and P. Turan, On some sequences of integers, 3. London Math. Soc.
11 A936), 261-264.
[Fl] J. Folkman, personal communication.
[F2] , Graphs with monochromatic complete subgraphs in every edge coloring,
SIAM J. Appl. Math. 18 A970), 19-24.
[Fr] P. Frankl, A constructive lower bound for some Ramsey numbers, Ars Combina-
toria 3 A977), 297-302.
[Ful] H. Furstenberg, Ergodic behavior of diagonal measures and a theorem of
Szemeridi on arithmetical progressions, J. Analyse Math. 31 A977), 204-256.
[Fu2] H. Furstenberg', Recurrence in ergodic theory and combinatorial number
theory, Princeton Univ. Press (to appear).
[FuK] H. Furstenberg and Y. Katznelson, An ergodic Szemeridi theorem for com-,
•muting transformations, 3. Analyse Math. 34 A978), 275-291.
[FuWJ H. Furstenberg and B. Weiss, Topologicat dynamics and combinatorial num-
number theory, J. Analyse Math. 34 A978), 61-85.
[Gl] S. Glazer, Ultrafilters and semigroup combinatorics, J. Combinatorial Theory
Ser. A' (to appear).
V:
I
ti"
[GLR] R. L. Graham, K. Leeb and B. L. Rothschild.'Senuey'j theorem for a class
of categories, Advances in Math. 8 A972), 417-433; Errata, 10 A973), 326-327.
[GR1] R. L. Graham and B. L. Rothschild, Ramsey's theorem for n-parameter
sets, Trans. Amer. Math. Soc. 1S9 A971), 257-292.
[GR2] - , A short proof of van der Waerden's theorem on arithmetic pro-
progressions, Proc. Amer. Math. Soc. 42 A974), 385-386.
[GRS] R. L. Graham, B. L Rothschild and J. H. Spencer, Ramsey theory, Wiley,
New York, 1980.
[GS] R. L. Graham and J. H. Spencer, A general Ramsey product theorem, Proc.
Amer. Math. Soc/ 73 A979), 137-139.
[GrG] R. E. Greenwood and A. M; Gleason,. Combinatorial relations and chromatic
graphs, Canad. J. Math. 7 A955), 1-7.
[HI] A. W. Hales and R. I. Jewett, Regularity and positional games, Trans. Amer.
Math. Soc. 106 A963), 222-229.
[H] D. Hubert, Uber die Irreduzibilitat ganzer rationaler Functionen mil ganzzah-
legen Koefflzienten, 3. Reine Angew. Math. 110 A892), 104-129.
[Hil] N. Hindman, Finite sums from sequences within cells of a partition of N,
J. Combinatorial Theory Ser. A 17 A974), 1-11.
[Ш2] , Ultrafilters and combinatorial number theory. Lecture Notes in Math.,
vol. 751 (M. B. Nathanson, ed.), Springer-Verlag, Berlin, 1977, pp. 119-184.
[ШЗ] , Partitions and sums and products-two counterexamples, 3. Combina-.
torial Theory Ser. A 29 A980), 113-120:
[I] R, W. Irving, Generalized Ramsey numbers for small graphs, Discrete Math.
9 A974), 251-264.
[La] J. A. Larson, A short proof of a partition theorem for со", Ann. Math. Logic
6 A973), 129-145.
[L] K. Leeb, Voriesungen uber Pascaltheorie, Erlangen Univ., 1973.
[LeR] L. Lesniak and J. A. Roberts, On Ramsey theory and graphical parameters,
Pacific 3. Math. 68 A977), 105-114.
[M] L. Moser, Prob. 170, Canad. Math. Bull. 13 A970), 268.
[NR0] J. Nesetfil and V. Rodl, The structure of critical Ramsey graphs, Colloq.
iiternationaux С N. R. S. 260 A978), 307-308.
[NR1] J. Nesetfil. and. V. Rodl, Partition (Ramsey) theory-a survey, Colloq. Math,
Soc. Jinos Bolyai, vol. 18, North-Holland, Amsterdam, 1978, pp. 754-792-
[NR2] ,A simple proof of the Galvin-Ramsey property of the class of all finite.
graphs and a dimension of a graph, Discrete Math. 23 A978), 49-55.
[NR3J , Partition theory and its applications, Surveys in Combinatorics, Lon-
London Math. Soc. Lecture Note Series, no. 38, Cambridge Univ. Press, London, 1979, pp. 96—
¦149.
[PH] 3. Paris and L. Harrington, A mathematical incompleteness in Peano Arithmetic,
Handbook of Mathematical Logic (J. Barwise, ed.), North-Holland, Amsterdam, 1977,
pp. 1133-1142.
[Pa] T. Parsons, Ramsey graph theory, Selected Topics in Graph Theory .(L. W.
Beineke and R. J. Wilson, eds.), Academic Press, London, 1978, pp. 361-384.
[Ral] R. Rado, Verallgemeinerung eines Satzes von van der Waerden mil Anwendun-
gen aufein Problem der Zahlentheorie, Sonderausgabe aus den Sitzungsberichten der Preuss.
Ak»d. d« Wiss. Phys.-Math. Klasse 17 A933), 1-J.0,

-Ч-
76
Литература
[Ra2] , Studien zur Kombinatorik, Math. Z. 36 A933), 424-480.
[Ra3] , Some recent result} in combinatorial analysis, Congres International
des Mathematiciens, Oslo, 1936.
IRJ F. P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. B)
30 A930), 264-285.
[RW] D. K. Ray-Chaiidhu'ri and R. M. Wilson, The existence of resolvable block de-
designs, A Survey of Combinatorial Theory (J. N. Srivastava, ed.), North-Holland, Amsterdam,
1973,361-376.
[Ro] K. F. Roth,0/i certain sets of integers, J. London Math. Soc. 28 A953), 104-
109.
* [Ry] H. J. Ryser, Combinatorial mathematics, Cams Math. Mono., no. 14,.Math.
Assoc. Amer./New York,.1963.
[Sa] J. Sanders, A generalization ofSchur's Theorem, Dissertation, Yale University,
1969.
[Scl] I. Schur, Uber die Kongruenz xm + ym congruent zm (mod p), Jbe'r. Deutsche
Math.-Verein. 25 A916), 114-116.
[Sc2] — , Gesammelte Abhandlungen, Springer-Verlag, Berlin, 1973.
[So] R. Solovay, personal communication.
[S] J. H. Spencer, Ramsey's theorem for spaces, Trans. Amer. Math. Soc. 249 A979),
363-371.
[Szl] E. Szemere'di, On sets of integers containing no four elements in arithmetic pror
gression, Ada. Math. Acad. Sci. Hungar. 20 A969), 89-104.
[Sz2] ¦ , On sets of integers containing no к elements in arithmetic progression,
Acta.Arith. 27 A975), 199-245.
[Та] A. Taylor, Bounds for the dijoint unions theorem (to appear).
[VI] B. L. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw Arch. Wuk.
IS A927), 212-216.
* [V2] B. L. van det Waerden, How the proof'ofBaudet's conjecture was found, Studies
In Pure Mathematics (L Minky, ed.), Academic Press, London, 1971, pp. 251-260.
[W] N. H. Williams, Combinatorial let theory. Studies in Logic, vol. 91, North-
Holland, Amsterdam, 1977.
Литература, имеющаяся на русском языке
[ES] Эрдёш П., Спенсер Дж. Вероятностные методы в комбинаторике.—
М.: Мир, 1976.
[Ry] Райзер Г. Комбинаторная математика. — М., Мир, 1966.
[V2] Ван дер Варден Б. Л. Как было найдено доказательство гипотезы
Баудета (см. дополнение I настоящей книги).
Литература, добавленная при переводе
[D] Deuben W. On van der Waerden's theorem on arithmetic progression.
J. Comb. Th., (A), 32, 1982, 115—118.
FFKO] Furstenberg H., Katznelson J., Orstein D. The ergodic theoretical
Л of Szemeredi's theorem. Bull, of the AMS, 7, 1982, N3, 527—552.
[NR4] Nesetril J., Rodl V. Another proof of the Folkman — Rado — San-
Sanders theorem. J. Comb. Th, (A), 34, 1983, 108—109.
[FRS] Faudree R. J., Rousseau С. С, Schelp R. H. All triangle-graph
Ramsey numbers for connected graphs of order six. J. of Graph Th., 4, 1980,
293—300.
[AC1 Abbott H. C, Cin-A. Remarks, on a paper of Hirschfeld concerning
Ramsey numbers, Discrete Math., 39, 1982, N3, 327—328.
[KR] Kettoda S. Y., Roberts J. D. Some results on Ramsey numbers usinp
eumfree sets. Discrete Math., 40, 1982, N1, 123—124.
lit
proo
Дополнение I
КАК БЫЛО НАЙДЕНО
ДОКАЗАТЕЛЬСТВО
ГИПОТЕЗЫ БАУДЕТА1)
Б. Л. ван дер Варден
Психология творчества в математике — это интересный, но
трудный предмет. Здесь классическими книгами считаются:
Адамар Ж. Исследование психологии процесса изобретения в области
математики. Пер. с франц. — М.: Советское радио, 1970.
Пойа Д. Как решать задачу. Пер. с англ. — М.: Учпедгиз, 1961.
Пойа Д. Математика и правдоподобные рассуждения. Пер. с англ.—М.:
Наука, 1975.
В своей небольшой брошюре «Einfall und Ueberlegung»
Bnd ed., Basel, 1968) я предпринял попытку синтеза точек зре-
зрения Адамара и Пойа. Настоящая работа в каком-то смысле
представляет собой переработку 2-й части этой брошюры.
Однажды — это было в 1926 г. — я за ленчем рассказал
Эмилю Артину и Отто Шрееру о гипотезе голландского матема-
математика Баудета:
Если последовательность целых 1,2,3, ... разделена на два
класса, то хотя бы один из классов содержит арифметическую
прогрессию из I членов а, а-\-Ь, ..., а-\-A—\)Ь вне зависи-
зависимости от величины этой заданной длины I.
После ленча мы отправились к Артину (на кафедру мате-
математики Гамбургского университета) и попытались с ходу найти
доказательство. Начертили на доске несколько диаграмм. Со-
Состояние, в котором мы пребывали, немцы называют «Einfalle»:
каждого из нас обуревали внезапно нахлынувшие идеи. Эти
новые идеи по нескольку раз меняли направление дискуссии,
пока наконец одна из них не привела к решению.
Одна из основных трудностей в психологии творчества со-
состоит в том, что большинство математиков, публикуя свои ре-
результаты, сопровождают их сжатыми доказательствами и не
') Van der Waerden В. L. How the Proof of Baudet's' Conjecture was
Found. — В кн. Studies in Pure Mathematics/Ed. L. Mirsky. Academic Press,
1971, p. 251—260. (Настоящая работа в большей части представляет собой
перевод статьи «Wie der Beweis der Vermutung von Baudet gefunden wurde»,
Abh. Math.Sem. Univ. Hamburg, vol. 28. Печатается с разрешения издателей
оригинала.)
Copyright © 1971 By Academic Press Inc. (London) Ltd,

78
Дополнение 1. Б. Л. ван дер Варден
рассказывают, как они пришли к этим результатам. Во многих
случаях они даже не помнят своих исходных идей. Сверх того,
трудно излагать наши расплывчатые идеи и практические при-
прикидки таким образом, чтобы другие могли понять их. Я, напри-
например, привык выражаться краткими намеками, которые один
и могу понимать. Излагая свои мысли другим, нам приходится
делать их более отчетливыми и, таким образом, менять их
природу.
В нашем случае с обсуждением гипотезы Баудета ситуация
оказалась более благоприятной для психологического анализа.
Все формируемые в наших умах соображения тотчас высказы-
высказывались и пояснялись небольшими схемками на доске. Мы пред-
представляли целые 1, 2, 3, ... в двух классах вертикальными чер-
черточками на двух параллельных прямых. Все то, что делаешь
ясным и наглядным, много легче сохранять и воспроизводить,
нежели просто мысль. Поэтому дискуссия между Артином,
Шреером и мной представляет уникальную возможность для
психологического анализа процесса математического мышления.
С самого начала было ясно, что случай 1 = 2 тривиален.
Даже нет нужды рассматривать бесконечную последователь-
последовательность целых; достаточно рассмотреть первые три: 1, 2, 3. Если
они разделены на два класса, то один из них содержит пару
чисел (в арифметической прогрессии).
Следующий случай, рассмотренный нами, был / = 3. Здесь
также нет необходимости рассматривать все целые: достаточно
взять целые от 1 до 9. Числа от 1 до 8 многими разными спосо-
способами можно разбить на два класса так, чтобы ни один из клас-
классов не содержал арифметической прогрессии из 3-х членов, на-
например так:
12 5 6 — в первом классе,
3 4 7 8 — во втором классе.
Однако в каждом из таких случаев число 9 добавить уже
нельзя. Если мы поместим его в первый класс, то получим про-
прогрессию 15 9, а если поместим во второй, получим прогрес-
прогрессию 7 8 9. И точно так же со всеми остальными возможными
случаями. Я уже заметил это днем ране«.
Далее Шреер спросил: «Если гипотеза Баудета верна для
всех целых и определенного значения /, то всегда ли можно
найти целое NA), такое, что эта же гипотеза выполняется уже
для сегмента 1,2,3, ..., NA) в том смысле, что каждая раз-
разбивка этого сегмента на два класса приводит к наличию ариф-
арифметической прогрессии длины / в одном из этих классов?»
Шреер сам и ответил на свой вопрос. Да, если гипотеза Бау-
Баудета выполняется при фиксированном /, то можно найти NA),
такое, что гипотеза выполняется уже для сегмента 1,2,3, ...
Как было найдено доказательство гипотезы Баудета ?9
..., NA). При доказательстве был применен хорошо известный
из теории множеств «диагональный процесс». Само рассужде-
рассуждение проводилось так:
Если такого целого нет, то для каждого N имелась бы раз-
разбивка DN множества чисел от 1 до N на 2 класса, при которой
ни один класс не содержал бы арифметической прогрессии
длины /, что дало бы бесконечную последовательность D\,D2,...
таких разбивок. При каждой из этих разбивок в одном из двух
классов имеется 1. Поэтому происходит так, что 1 бесконечно
много раз входит в какой-то один класс (первый либо второй).
И, значит, существует бесконечная подпоследовательность
D\, D'2, ..., состоящая из всех тех разбивок, при которых 1
наличествует в одном и том же классе, скажем в классе номер
ix (i! = 1 или 2).
При разбивках D2, ZK, ... число 2 принадлежит одному из
двух классов. Поэтому, согласно тому же рассуждению, что и
для 1, существует бесконечная подпоследовательность
/>2> А), • • • в которой 2 всегда наличествует только в классе i2.
И так далее. Для каждого п получается подпоследователь-
подпоследовательность разбивок D]?K /)<,">.!, ..., такая, что во всех этих разбив-
разбивках целые 1, 2, ..., п всегда наличествуют в одних и тех же
классах:
1 в классе i\,
2 в классе [2,
п в классе U.
Далее можно образовать «диагональную разбивку» D D из
всех целых 1, 2, 3, .... при которой 1 лежит в классе ih 2 —
в классе i2 и т. д. При такой разбивке число п лежит в том же
классе, что и при разбивке D{n\ поэтому такая процедура име-
именуется диагональным процессом.
При разбивке D D нет арифметической прогрессии длины /,
все члены которой принадлежали бы одному классу. Если бы
она существовала, то такая же существовала бы и при раз-
разбивке D{n\ т. е. при одной из исходных разбивок. Но мы пред-
предполагали истинность гипотезы Баудета для последовательности
всех целых 1,2,3, ... и этого конкретного значения /. Таким
образом, получили противоречие.
С этого момента мы старались доказать, как мы говорили,
«сильную гипотезу» для конечного сегмента от 1 до NA), т.е.
пытались отыскать число NA), обладающее означенным свой-
свойством. Для / = 2 и / = 3 такие числа были уже найдены:
NB) = 3, jVC) = 9. Итак, мы старались перейти от /—1 к /.
Для такого индуктивного рассуждения замена изначальной ги-
гипотезы более сильной дает определенные преимущества, как

Дополнение I. Б. Л. ван дер Варден
правильно заметил Артин. Если можно предполагать для /—1
существование конечной границы МA—1), то имеется больше
шансов найти доказательство для следующего числа /.
Далее Артин заметил: если сильная гипотеза верна для двух
классов и всех значений, то она также должна быть верна для
произвольного числа классов, скажем для k классов. Для до-
доказательства этого утверждения он, во-первых, предположил,
что k = 4. Четыре класса могут быть сгруппированы в 2 и 2.
Это дает первичную разбивку целых на два больших класса,
в которой каждый большой класс состоит из двух меньших
классов. В одном из таких больших классов существует ариф-
арифметическая прогрессия из NA) членов. Члены этой прогрессии
можно занумеровать от 1 до NA). Эти числа в свою очередь
разделены на два меньших класса, и поэтому в одном из мень-
меньших классов найдется арифметическая прогрессия из / членов.
Таким образом, если сильная гипотеза верна для двух классов,
то она также верна и для четырех классов. Точно таким же
рассуждением устанавливается, что это имеет место для 8 клас-
классов и т. д., а стало быть, и для любого числа классов вида
k = 2". Но если это выполняется для k = 2", то это также вы-
выполняется и для каждого k ^ 2", поскольку всегда можно доба-
добавить несколько пустых классов. Значит, если гипотеза Баудета
верна для двух классов, то она также верна (даже в сильной
форме) и для произвольного числа классов.
Теперь мы старались доказать «сильную гипотезу» уже для
произвольных k и / индуктивным переходом от /—1 к /. Это
значит, что мы пытались найти такую границу N = N(l,k), что
если целые от 1 до N разделены на k классов, то один из клас-
классов содержит арифметическую прогрессию длины /.
Артин рассчитывал — и он оказался прав — на преимущество
доказательства по индукции при обобщении от двух до k клас-
классов. Он обосновывал это тем, что мы теперь можем стараться
доказывать сильную гипотезу для произвольного фиксирован-
фиксированного значения и длины I при том предположении индукции, что
это имеет место для всех k при длине /—1. Это значило, что
с самого начала мы обладали очень сильным предположением
индукции, что дает определенное преимущество.
Следуя этой линии, намеченной Артином, мы теперь уже
старались доказать гипотезу Баудета для двух классов и про-
прогрессий длины /, предполагая выполнимость сильной гипотезы
при всех k для прогрессий длины /— 1.
Далее Артин высказал очень хорошую мысль: если целые
1,2, ... разделены на два класса, то блоки из трех последова-
последовательных целых автоматически разбиваются на 23 = 8 классов.
Каждое из трех чисел "внутри блока может лежать в первом или
втором классе, и это дает 8 возможностей для всего блока.
Как было найдено доказательство гипотезы Баудета
81
Теперь блоки из трех последовательных целых можно занумеро-
занумеровать: блок номер п состоит из целых п, п-\-\, п + 2. Если эти
блоки разбиваются на 8 классов, то их начальные числа п
также разбиваются на 8 классов, и к этому разбиению мы можем
применить предположение индукции. Таким образом, получаем
следующий результат: из достаточно большого количества
последовательных блоков можно выделить арифметическую
прогрессию из /—1 блоков, лежащих в одном классе. Схе-
Схема распределения целых по двум классам в первом блоке будет
точно повторяться и в остальных / — 2 блоках.
То же самое имеет место и для блоков произвольной длины
т, состоящих из последовательных чисел л, п+1, ..., п +
-J- m — 1, Число классов для этих блоков есть 2т. Снова можно
-\ Н
Рис. 1.
Рис. 2.
лолучать арифметические прогрессии из /—1 блоков одного
класса с точным повторением схемы первого блока. Кроме того,
если блоки достаточно длинны, можно также найти арифмети-
арифметические прогрессии из 1—1 целых внутри каждого блока.
В простейшем случае / = 2 гипотеза, разумеется, верна при
:всех k; если целые от 1 до k + 1 разделены на k классов, то
.должны быть два целых в одном из классов. Это и есть «прин-
«принцип ящиков» Дирихле: если / + 1 объектов располагаются по k
ящикам, то один ящик содержит два из них. Очень полезный
лринцип в теории чисел!
Таким образом, отталкиваясь от очевидного случая /= 2,
мы попытались перейти к случаю двух классов и / = 3 (хотя
этот случай и был уже рассмотрен перебором всех возможно-
возможностей). Целые в двух классах мы представляли маленькими вер-
вертикальными черточками на двух параллельных прямых, как на
рис. 1.
Согласно предположению индукции, в данном случае совпа-
совпадающему с принципом ящиков, среди трех последовательных це-
целых всегда найдутся два в одном классе. Теперь рассмотрим
блок из пяти последовательных целых. Среди первых трех
имеются два в одном и том же классе: это дает арифметиче-
арифметическую прогрессию длины 2. Третий член этой прогрессии также
лежит внутри этого блока из 5. Если он в том же классе, в ко-
котором и два первых члена, то в этом классе получаем искомую
прогрессию длины 3, Стало быть, можно предполагать, что тре-

82
Дополнение I. Б. Л. ван дер Варден
тий член лежит в другом классе, и внутри каждого блока из
5 имеем схему, как на рис. 1.
Я рисовал такие блоки на доске и думал: имеется 25 = 32
класса блоков по 5, поэтому среди 33 последовательных блоков
должно быть два блока в одном и том же классе. Схема рас-
расположения черточек в первом из них (как на рис. 1) в точ-
точности повторяется во втором блоке из 5 (рис. 2).
Мы хотели построить прогрессию длины 3. Поэтому я на-
нарисовал еще один блок на том же самом расстоянии от вто-
второго, как второй от первого, и отметил те три места в этом
блоке, на которых расположены черточки в первых двух бло-
блоках (рис. 3).
Третье из этих отмеченных мест представляет целое, кото-
которое может быть в первом либо втором классе. Если оно в пер-
первом, то имеем в этом классе арифметическую прогрессию ааа
-\—ь
-\ Ь
1
Рис. 3.
Рис. 4.
(рис. 3). Если же во втором, то имеем в этом классе прогрес-
прогрессию ЪЪЪ. Следовательно, во всяком случае внутри блока це-
целых от 1 до 5 + 32 + 32 = 69 получаем арифметическую про-
прогрессию из трех членов в одном классе.
Продумав доказательство этого частного случая k = 2 и
/ = 3, я изложил его Артину и Шрееру. Я чувствовал уверен-
уверенность, что именно такое доказательство должно работать и в
общем случае. Они не разделили этой уверенности, и я перешел
к рассмотрению доказательства для следующего случая: k = 3,
7 = 3.
Вместо блоков из 3 + 2 = 5 я теперь рассматривал блоки из
4+ = 7 последовательных целых. Поскольку первые четыре
числа такого блока распределяются по трем классам, то два из
них должны принадлежать одному и тому же классу. Третий
член этой арифметической прогрессии, начинающейся с указан-
указанных двух членов, принадлежит тому же самому блоку из 7.
Если этот третий член в том же классе, то получаем прогрес-
прогрессию длины 3 в этом классе. Поэтому можно предполагать, что
третий член лежит в другом классе. Таким образом, в каждом
блоке из 7 получаем схему, подобную схеме первого малень-
маленького блока на рис. 4.
Блоки по 7 элементов разбиваются на З7 классов. Поэтому
среди З7 + 1 последовательных блоков по 7 найдутся два,
Как было найдено доказательство гипотезы Баудета
83
принадлежащих одному и тому же классу. В первом блоке имеет-
имеется три целых в арифметической прогрессии, два из которых при-
принадлежат одному классу; та же схема повторяется и во вто-
втором блоке. Если второй блок сдвигается на то же самое рас-
расстояние, то получается три блока, образующих арифметическую
прогрессию блоков, как показано на рис. 4.
Рис 5.
В третьем блоке я отметил три места, соответствующие трем
черточкам в первом и втором блоках, и рассмотрел возмож-
возможности для третьего из этих мест. Если это число попадает в
первый или второй класс, получаем арифметическую прогрес-
прогрессию длины 3 в том же классе (тем же рассуждением, что и
раньше), но теперь эта третья черточка может оказаться и в
третьем классе. Таким образом, получим схему, изображенную
на рис. 4.
В каждом большом блоке из З7 + З7 + 7 = h последователь-
последовательных целых имеем такую схему. Теперь большие блоки из h це-
1 1°
ы
1
1
1
1
Т
-е-1
Рис. 6.
лых разделяются на 3h классов. Поэтому среди 3ft + 1 последо-
последовательных больших блоков найдутся два, принадлежащих од-
одному и тому же классу. Изображая маленькие блоки внутри
больших, я получил рис. 5.
Теперь, отодвигая второй большой блок на то же самое рас-
расстояние и рассматривая третье место в третьем маленьком бло-
блоке третьего большого блока, я показал, что черточку на этом
месте никуда нельзя поставить. Если она лежит в первом клас-
классе, то имеется прогрессия а а а в первом классе, если она во
втором классе, то имеется прогрессия b b b в этом классе, а
если в третьем классе, то прогрессия с се в этом классе (рис.6).
После этого все мы согласились, что подобное доказатель-
доказательство может пройти для произвольного k. Но теперь Артину и
Шрееру захотелось просмотреть случай / = 4.

Дополнение I. Б. 71. ван дер Варден
Как и ранее, я сначала рассмотрел случай двух классов.
Для этого случая я уже доказал, что среди достаточно боль-
большого количества, скажем л, последовательных целых найдется
прогрессия из трех членов в одном классе. Можно предпола-
предполагать п нечетным. Расстояние между первым и последним чле-
членами этой прогрессии не превосходит п— 1; следовательно, рас-
расстояние между двумя последовательными ее членами не более
чем (п—1)/2. Теперь рассмотрим четвертый ее член. Все эти
четыре члена лежат внутри блока из g = n-\-(n—1)/2 после-
последовательных целых. Если четвертый член принадлежит тому
же классу, что и три первых, то цель достигнута. Предположим,
что он лежит в другом классе; тогда имеем схему, как на рис. 7.
Рис. 7.
Рис. 8.
В каждом блоке из g последовательных целых должна наличе-
наличествовать такая схема. Теперь эти блоки по g элементов подраз-
подразделяются на 2е классов. Поэтому среди достаточно многих,
скажем NC, 2ё), блоков длины g найдутся три блока в ариф-
арифметической прогрессии, принадлежащих одному классу. Схема
первого блока в точности повторяется во втором и третьем бло-
блоках (рис. 8).
Добавляя четвертый блок к этой прогрессии, я легко полу-
получил прогрессии аааа в первом или bbbb во втором классе.
Теперь каждому из нас стало ясно, что индуктивный пере-
переход от /— 1 к / проходит для произвольного / при любом фик-
фиксированном значении k. Следовательно, если сильная гипотеза
Баудета верна для длины /— 1 при всех k, то она также верна
для / и любого k. А так как она верна при 1 = 2, то это вле-
влечет ее истинность и в общем случае.
При анализе изложенного четко выделяется череда неожи-
неожиданных соображений, придававших каждый раз нашей дискус-
дискуссии новое направление.
1. Первой была шрееровская идея редукции к конечному
сегменту от 1 до N; она явилась основой всего доказательства.
2. Вторая идея: постараться провести индукцию по /. Это
было вполне естественно, поскольку случай 1 = 2 очевиден, а
случай / = 3 получался перечислением всех возможных ва-
вариантов.
3. Артин доказал: если сильная гипотеза верна для двух
. классов, то она также верна и для четырех классов. В его
Как было найдено доказательство гипотезы Ваудета
85
доказательстве прослеживалась и иная идея, а именно: если эта
гипотеза верна для сегмента из всех целых от 1 до N, то она
также верна и для любой арифметической прогрессии длины
N: а, а-\-Ь, ..., a-\-(N—\)b, поскольку члены этой прогрес-
прогрессии могут быть занумерованы целыми от 1 до N. Это тоже одна
из ключевых идей доказательства.
4. Далее Артин сказал: в индукции всегда удобно иметь
с самого начала сильное индуктивное предположение. Поэтому
давайте начнем с того предположения, что эта гипотеза выпол-
выполняется для прогрессий длины /—1 и всех k, и постараемся до-
доказать ее для прогрессий длины / и одного значения k, скажем
k = 2. Тем самым был выработан план доказательства.
5. Следующая мысль, которая также пришла от Артина,
была решающей. Он сказал, что мы можем применять предпо-
предположение индукции не только к отдельным числам, но и к бло-
блокам, ибо они тоже делятся на классы. Таким образом, мы убе-
убедились, что и блоки целиком повторяются по /— 1 раз.
6. После этого было вполне естественно рассматривать про-
прогрессию из / — 1 блоков и ! — 1 целых внутри этих блоков и
стараться продлить эти прогрессии длины / — 1 до прогрессий
длины /. Простейший нетривиальный случай был / — 3, и я
естественно был подведен к рассмотрению схем типа рис. 2.
7. Эта схема не содержит прогрессии длины 3 в одном клас-
классе. Поэтому необходимо было продлить прогрессию длины 2,
наличествующую во втором классе на рис. 2, до прогрессии
длины 3. Я, стало быть, расширил схему рис. 2, пририсовав тре-
третий блок (рис. 3), и рассмотрел третий член прогрессии bbb. Как
только внимание сосредоточилось на этом члене, стало ясно,
что он не может избежать образования арифметической про-
прогрессии длины 3 в первом либо втором классе.
Эта последняя идея сопровождалась чувством полной уве-
уверенности. Я нисколько не сомневался в том, что этот метод до-
доказательства будет работать для произвольных k и /. Я не могу
объяснить это чувство, могу лишь сказать, что математиков
часто посещает такое откровение. Когда основная идея прихо-
приходит в голову, мы ощущаем уже наличие всего искомого дока-
доказательства, остается лишь проработать его в деталях.
Более того, берусь в известной мере объяснить, почему Ар-
Артин и Шреер не чувствовали такой уверенности. Они видели
только результат: присутствие прогрессии а а а в первом классе
или bbb во втором классе. Я же нашел метод для выделения
таких прогрессий и был уверен, что этот метод будет работать
и в остальных случаях так же хорошо.
Это подобно сбору .яблок с дерева. Если срываешь яблоко
с дерева и видишь другое, висящее чуть выше, может статься,

86
Дополнение I. Б. Л. ван дер Варден
что знаешь: чуть больше усилий — и оно тоже твое. Человек,
стоящий рядом, лишь видит, как я сорвал первое, и сомневает-
сомневается, смогу ли сорвать еще; я же не только владею первым, но
чувствую само движение, которым сорву другое.
Ощущение, что метод доказательства может быть перенесен
и на другие случаи, иногда обманчиво. Часто в иных случаях
возникают дополнительные сложности. И все-таки чувство по-
подобного рода весьма полезно в математических исследованиях.
Поиск доказательства гипотезы Баудета — хороший пример
совместной работы. Каждый из нас внес существенный вклад.
После этой дискуссии с Артином и Шреером я проработал де-
детали доказательства и опубликовал его в журнале Nieuw
Archief voor Wiskunde 15, 212A927). (Интересные приложения
и обобщения этой теоремы, доказанной в моей работе, были
даны Ричардом Радо').)
А. Я. Хинчин включил эту теорему в свои «Три жемчужины
теории чисел» A948) и опубликовал доказательство М. А. Лу-
комской, которое по существу такое же, как и у меня, с той
лишь разницей, что в ее доказательстве требуется, чтобы блоки
не перекрывались.
') R. Rado: Studien zur Kombinatorik, Ph. D-Thesis, Berlin, 1931, Math.
Zeitschr., 36, p. 424. Verallgemeinerung eines Satzes von van der Waerden,
Sitzungsber, preuss. Akad., Berlin, 1933, p. 589. Note on Combinatorial Ana-
Analysis, Proc. London Math. Soc, BL8, p. 122.
Дополнение II
ПРИНЦИП ПОЛНОГО
РАЗМЕЩЕНИЯ
Б. С. Стечкин
Вопрос о закономерностях существования подструктуры с
заданными свойствами у произвольной структуры из определен-
определенного класса — это типичный для комбинаторики вопрос о взаи-
взаимодействиях единого и разделенного. Иногда удается вскрывать
такие закономерности для конкретных классов структур; наи-
наиболее общие из них представлены теоремами Рамсея, ван дер
Вардена, Шура и др. Основным первичным фактом такого типа,
равно как и основным инструментом разрешения подобных во-
вопросов, служит принцип Дирихле.
Здесь мы изложим еще один общий принцип — принцип пол-
полного размещения. Этот принцип возник как средство для реше-
решения вполне конкретной инженерно-технической задачи, связан-
связанной с управлением памятью ЭВМ; подробнее о ней будет
сказано ниже. Сначала принцип полного размещения будет изло-
изложен и рассмотрен в модельной ситуации — в терминах разбие-
разбиений чисел; в частности, в этих терминах будут вскрыты и иные
экстремальные факты, пригодные для прямого инженерного ис-
использования. Далее будет указана связь этого нового принципа
с уже имеющимися фактами такого рода — прежде всего с тео-
теоремой Рамсея. Наконец, посредством принципа полного разме-
размещения асимптотически точно будет решен класс экстремальных
задач о локальных свойствах графов. В частности, последний
результат указывает -на наличие прямой связи между техниче-
техническими вопросами управления памятью ЭВМ и вычислением хро-
хроматических чисел графов.
Определения. Разбиение натурального п есть представление
его в виде неупорядоченной суммы натуральных слагаемых
гс = щ + ••• + п,. Эти слагаемые щ называются частями раз-
разбиения (rti ... пг)\-п (числа п), а их число г — рангом этого
разбиения.
Пусть Р — множество всех разбиений всех натуральных чи-
чисел, Рг — множество всех разбиений ранга г, Р(п)—множество
всех разбиений числа п и Рг (п) = Рг Л Р (п). Запись (п ... тг°г)
обозначает разбиение (п] ... п1 ... пг ... пг), а запись [г]—¦
множество {1 г} с
1984

88
Дополнение П. Б. С. Стечкин
Принцип полного размещения
Разбиения чисел позволяют формулировать принципы раз-
размещения в достаточно общей форме.
Принцип Дирихле. Для натуральных k, r пусть n(k, г)—то
наименьшее п, при котором V (щ ... nr) \— n3i е [г]: nt^k.
Тогда n(k,r) = rk — г-\- 1.
Теорема Рамсея (частный случай). Для натуральных k\, ...
..., kr пусть n(k\ ... k,)— то наименьшее п, при котором V («i ...
... nr)Y- n 3i «= [г]: щ 5= ki. Тогда n{ki ... &,-) = ?f=i & — г + 1.
Смысл этих утверждений как логических принципов разме-
размещения совершенно прозрачен: принцип Дирихле обеспечивает
полное размещение объекта объема k в любое разбиение
п~^ n(k, г) на г частей, т. е. в любое разбиение из множества
Рг(п), в то время как теорема Рамсея гарантирует размещение
лишь одной части разбиения (k\ ... kr) в любое разбиение из
Рг{п), если п*^ n(k\ ... kr). В частности, из принципа Дирихле
при k = 2, г = п сразу следует широко известный
Принцип ящиков. Если п + 1 предметов размещаемы по п
ящикам, то найдется ящик с по крайней мере двумя предме-
предметами.
Естественно поинтересоваться принципом, который гаранти-
гарантировал бы полное размещение фиксированного разбиения в лю-
любое разбиение из Рг(п). Для этого прежде всего нужно более
четко определить само понятие размещения.
Будем говорить, что разбиение (k\ ... kt) \~ k вложимо
в разбиение (п\ ... nr)'t~ n (это обозначается (k\ ... kt)cz
cz(«i ...nr)), если существует <р: [*]—••[/], при котором
?/е=ф-' (i)kj^ni V/ е [г], где ф-1 — полный прообраз элемента /;
иными словами, если чисти ki разбиения {k\ ... kt) можно так
сгруппировать в г групп (каждая часть ki входит ровно в одну
группу, причем пустые группы допускаются), что по сложении
всех частей &; каждой из этих групп получится г чисел /?ь ..., рг,
таких, что Pi ^ П{, i = 1, ..., г.
Далее некоторые утверждения приводятся в виде упражне-
упражнений, а открытые вопросы — в виде задач.
Упражнение 1. Проверьте, что бинарное отношение вложи-
мости разбиений является отношением частичного порядка.
Задача 1. Вычислить мёбиус-функцию частично упорядочен-
упорядоченного множества (Р, с).
Понятие вложимости разбиений позволяет сформулировать
Принцип полного размещения. Для натуральных г, k1 ^ ...
^ kt пусть n(k\ ... kr, r) — то наименьшее п, при котором
rti ... nr)hn (ki ... kt)cz(m ... nr). Тогда
n(kx
= max I У k, + (*, - 1) (r - 1I.
A)
Доказательство. Обозначим правую часть A) через f(ki ...
*.. kt\r). Так как из вложимости (k\ ... kt)a(n — (г—1 )(&<•—~
-1), (kt— 1)«г-'>) следует, что n—(r—l)(kt—l)^ki + ...
¦ ¦¦ + ki, то n{k\ ... kt\r)^\(k\ ... kt; r), и, значит, достаточно
доказать обратное неравенство. Отметим, что
f(ki ... k?,r)>ki + f{ka ... kt;r). (*)
Действительно, если i — индекс, максимизирующий функ-
функцию f(k2 ... kt;r), то f(ki ... fc;r)> ?/-i*/ + (*<-OX
X(r-l) = *i+ZJ-2*/ + (*i-0(r-l) = Ai + K*2 ... kt\r).
Проведем индукцию по /. При t = 1 получаем принцип Ди-
Дирихле. Для индуктивного перехода от t— 1 к t достаточно пока-
показать, что если п = f(ki ... kf, r), то полная размещаемость осу-
осуществима. Рассмотрим произвольное разбиение (п\ ... nr) \— n
вида m ~&z ••• 1Э= rtr. В нем всегда п\ ^ k\, так как f(k\ ...
... kt;r)^kl+(r—l)(ki — \), поэтому вложение
(k2 ... kt)d(nx — kx,n2 nr) (**)
влечет вложение (k\ ... kt)a(n\ ... пг). В свою очередь (**)
следует из (*) и предположения индукции
ni — ki + «2 + • • • + nr = п — k\ = /(*i •
t;r) —
.. kt;r).
Если при этом п\ = k\, то надлежит еще воспользоваться моно-
монотонностью f по г. ?
Следствие. Если для натуральных k\~^ ••• ^ kt, n~^k~\
-\{k\ ... kt) через r(k\ ... kt; n) обозначено то наибольшее г,
при котором в каждое разбиение числа п на г частей вложимо
разбиение [k\ ... kt),ro
' п, k{ = l,
i
kt; n) -= •
min
l:kt>\
_ ki-\ _
1, k{>\.
Действительно, искомое г, согласно принципу полного раз-
размещения, есть наибольший целый корень неравенства п ^
?sn(?i ... kt;r).

Дополнение П. Б. С. Стечкин
Опишем теперь исходную инженерную постановку. При ра-
работе вычислительных систем наблюдается явление фрагмента-
фрагментации памяти ЭВМ, т. е. ситуация, при которой вся память раз-
разбита на занятые и свободные куски (фрагменты); в то же время
нужно разместить очередную порцию информации в эти фраг-
фрагменты, причем информация эта может быть разделена на не бо-
более чем определенное количество блоков определенного объема
(например, из-за одноадресности массивов). Естествен вопрос об
определении возможности размещения требуемой информации
в данную систему фрагментов. Явление фрагментации памяти
требует также быстрых алгоритмов размещения системы запро-
запросов информации объемов k\, ..., kt в систему фрагментов сво-
свободной памяти объемов п\, ..., пг. Из принципа полного раз-
размещения явствует, что если J]*=i щ ~^n{k\ ... kt; r), то разме-
разместить запросы можно, причем быстрыми алгоритмами «большее
в большее», «большее в наименьшее возможное» или же «боль-
«большее в любое подходящее».
Принцип полного размещения можно рассматривать и про-
просто как экстремальный результат о разбиениях. Вычисление
иных экстремальных характеристик о разбиениях также оказы-
оказывается полезным.
Упражнение 2. Докажите следующие утверждения.
а) Пусть na{k,t,r)—наибольшее п, при котором никакое
разбиение числа k на t частей не вложимо ни в какое разбие-
разбиение числа п на г частей. Тогда na(k, t, r) = max {А—\,k—1 —
-t + r).
(b) Если tib{k,t,r) — наименьшее п, при котором VpePr(n)
Vq<^Pt{k) pgtq, то nb(k,t,r)=mm{k+\,k+l — t + r}.
(c) Пусть nc(qi ... цп г) — наименьшее п, при котором ни-
никакое разбиение п на г частей не вложимо в разбиение (q{ ...
... Qt), 7i > ••• >Qt- Тогда
min{r, О
ne(q{ ... qt;r)=\ + ? qt.
(d) Если q^Pt(k) и rid(q;r)—наибольшее п, при котором
разбиение q не вложимо ни в какое разбиение числа п на г
частей, то na{q\ г) = maxjfe — 1, k — 1 — t + г}.
(e) Если ne(k,t,r)—наименьшее п,при котором VpePr(n)
Vq<=Pt(k) p=>q, то ne(k, t,r)= max {k, r(k — t)+I}.
(f) Если rif(k, t, r)— наибольшее п, при котором VpePr(n)
V<7 e Pt (k) pczq, то n, (k, t, r) = min {&, J у [ -f r — 1 j.
Задача 2. Для данных ti\, .... nr, t вычислить k{ti\..-. nr; t) —
наибольшее k, при "котором V(ki ... kt)\- k (ni ... n/)r>
=э(Л, ... kt).
Принцип полного размещения
91
Вычислению аналогичной характеристики для «рамсеевской
структуры» посвящено
Упражнение 3. Для данных п\, ..., пг вычислить то наи-
наибольшее k, при котором V (k\ ... k,) \- k 3i e [r] m ^ k;.
Подобно своему частному случаю — принципу Дирихле,
принцип полного размещения допускает реализации в терми-
терминах урновых схем и случайных размещений.
Упражнение 4. Докажите, что при любом размещении п ча-
частиц по г ячейкам найдется t различных групп частиц (по
[(п + г—\)/(t-\-r— 1)] частиц в каждой), целиком лежащих
в ячейках.
Изучение свойств функции полного размещения n(k\... kt\r)
обеспечивает усиление достаточных условий вложимости раз-
разбиений.
Упражнение 5. Докажите следующие равенства и утвержде-
утверждения:
„ ...,lkt\r) = ln(
n((k[ ... k't)\rl-
... kt\r).
(a) Разбиение (k\ ... kt) вложимо в любое разбиение из
Рг{п) тогда и только тогда, когда разбиение {lk\, ..., Ikt) вло-
вложимо в любое разбиение из Pr(nl-\-(r—1)(/—1)).
(b) Разбиение (ki ... kt) вложимо в любое разбиение из
Рг(п) тогда и только тогда, когда разбиение (k{ ... klt) вло-
вложимо в любое разбиение из Pri-i+i(nl).
(c) Если разбиение (k\ ... kt) вложимо в любое разбиение
из Рг(п), то разбиение (k[ ... kt) вложимо в любое разбие-
разбиение из Рг(Ш + (г — 1)(/— 1)).
(d) Если для натуральных г, t, п\ nr, k\~^- ••• ~^-kt
выполняется неравенство
(г - 1) (/ -
max
— 1)(Л4 - 1)}.
)
max
ilk,
<=1 t
то разбиение (ki ... kt) вложимо в разбиение (п\ ... пГ).
Определим теперь аналогичную экстремальную константу
для обычных графов и рассмотрим ее связь с числами Рамсея.
Пусть c(k\ ... kt; r)—наименьшее с, при котором в любом
r-раскрашивании полного с-вершиннйго графа Кс найдется t
реберно непересекающихся графов Kfci, ...,Kkt> каждый из
которых одноцветен.

92
Дополнение II. Б. С. Стечкин
Будем рассматривать 2-раскрашивания полных графов, ис-
используя обозначения c(k{ ... kt) для c{k\ ... kr,2) и R(k) для
R(k,k;2). Взаимосвязь между числами с и R иллюстрирует
Утверждение 1. c(k,3) = R{k), k = 4, 5
Доказательство. Ясно, что если k~^zk', то c(k,k')~^R{k);
кроме того, если k и k' таковы, что R{k) — k-\-l ^R(k'), то
c(k,k') = R(k). Действительно, положим R = R(k) и рассмот-
рассмотрим произвольную 2-раскраску Kr; эта раскраска с необходи-
необходимостью содержит одноцветный Kk, скажем на вершинах мно-
множества [k]. Рассмотрим теперь нашу раскраску на вершинах
множества [k,R]. Так как \[k,R]\ = R — k+l^R(k'), то в
этой раскраске найдется одноцветный Kk' (очевидно, пересе-
пересекающийся с Kk не более чем по одной вершине), так что тре-
требуемая конфигурация получена.
Ясно, что при k' = 3 используемое неравенство принимает
вид R(k)^ k -\- 5, и оно, согласно соотношению B.1) из гл. 2
основного текста, выполняется при k ^ 4. D
Упражнение 6. Докажите следующие утверждения.
(a) Если па — наименьшее п, для которого при любой 2-рас-
краске ребер Кп найдутся два монохроматических треугольника,
быть может, разных цветов, но без общих ребер, то па = 7.
(b) Если пь-—наименьшее п, для которого при любой 2-рас-
краске ребер Кп найдутся два монохроматических треугольника
одного цвета и без общих ребер, то пь = 8. (Указание: исполь-
используйте раскраски, приведенные на рисунке.)
(а)
(Ь).
Опишем теперь один класс экстремальных задач о графах,
решения и ответы которых содержат в себе принцип полного
размещения в явном виде.
Задача. Сколь мало ребер m(n; Hk) может иметь п-вершин-
п-вершинный граф, у которого на любых k вершинах найдется k-вершин-
ный граф, изоморфный наперед заданному k-вершинному
графу ?
Принцип полного размещения
93
Этот класс задач о графах с такими локальными свойствами
является подклассом более широкого класса экстремальных за-
задач, именно задач о монотонных свойствах, или, иначе, о за-
запрещенных подграфах.
Задача о запрещенных подграфах. Сколь много ребер f(n;L)
может иметь п-вершинный граф, не содержащий в себе в ка-
качестве подграфа ни одного «запрещенного» графа из наперед
заданного списка L таких запрещенных графов'?
Включение первого класса задач во второй определяется
очевидным равенством
пг\
Асимптотическое решение задачи о запрещенных подграфах
дает
Теорема Эрдёша — Шимоновича.
f(n; L) = ( 1
Основной характеристикой, определяющей асимптотику
f(n;L), оказывается хроматическое число; в классе локальных
свойств применением принципа полного размещения коэффи-
коэффициент удается значительно упростить:
Теорема. Пусть непустой граф Hk состоит из t компонент
связности по ki вершин в 1-й компоненте связности, причем
h^k2^ — ^zkt^tl, ki+ - +kt = k. Тогда
m (re; Hk) = n
„2
2min
o(re2).
B)
Доказательство. Введем необходимые обозначения и опре-
определения. Gn — это п-вершинный граф, Кп — полный граф на п
вершинах, Кп\.- пг ~ полный r-дольный граф, в котором i-я
доля имеет ге,- вершин; Оп = Кп—Gn, так что если щ-\- •••
¦¦¦ + Пг = п,то KnV..nr = Kn — KnV..nr = Kni + -.-+Knr, т.е.
п-вершинный граф, состоящий из г непересекающихся полных
графов по щ вершин в /-м графе.
Через \i{n; Fk) обозначаем максимум числа ребер в «-вер-
«-вершинном графе, у которого любой ^-вершинный подграф вложим
в ^-вершинный граф Fk- Ясно, что m(n; Hk)-\- ц(п; #*) = (?),
поэтому всюду далее предполагаем, что Fk = Hk. Внешним хро-

94
Дополнение П. Б. С. Стечкин
матическим числом ^-вершинного графа Fk называем число
x(Fk) = jninx(Gk).
Лемма. Если Fk^ Kk и Fk состоит из t компонент связности
по ki вершине i-й компоненте связности,причем k\ ^ ••• ^kt^
¦^\,к\Л \-kt = k,To
— t
1.
Доказательство леммы. Действительно, если Gk<f.Fk и G* с:
<=/(„,...„, где (ш ... rtr) г- Л, то Knx...nr<?Fk\ поэтому равен-
равенство %(Fk) = г эквивалентно тому, что
3 (п, ... nr) \-k Knl...nr<?Fk, V(n.../ir_,)Hft KnX-nr^^Fk.
Значит, если г — это то наибольшее целое, при котором
V (я, ... nr) \- k Knv..nrczFk, то
=г+1- В свою очередь
Кп
¦к
п\ ¦ ¦ •
<Fk или #„,+ ...+/(
пг
а последнее вложение, очевидно, имеет место тогда и только
тогда, когда (пх ... nr)^(k\ ... kt)\~ k, где & — число вершин
графа Hk в его i-й компоненте связности. Значит, искомое г —
это в точности г(k) ... kt\k) из следствия, согласно которому
при учете того,«что Fk^Kk, а значит, k\>\, имеем
'г, ... kt; /г)= min
= mm
k-
_ ft* — 1 _
*/
=min
П
Теперь доказательство теоремы основывается на последова-
последовательном применении определения ц, теоремы Эрдёша — Шимо-
новича, определения внешнего хроматического числа и нашей
леммы:
( 2
Принцип полного размещения
95
Упражнение 7. Докажите следующие следствия из теоремы,
(а) Если граф Нк состоит из / компонент связности по /
вершин в каждой компоненте и (k — It) изолированных вершин,
(/([4f])L
то
(([4f])L
(Ь) Если граф Hk не имеет изолированных вершин, то
m{n;Hk) = n2/2 + O{n).
Задача 3. Провести оценку остаточного члена в уравне-
уравнении B).
Для многих конкретных типов Hk удается получать и точные
решения.
Упражнение 8. Докажите следующие утверждения,
(а) Если граф Fk имеет изолированную вершину, то
\Fk\, Fkj>g-k,
in; Fk) =
max
где 9~k — система из [k/2] независимых ребер на k вершинах,
(b) Если Ск — цикл на k вершинах, то пг(п; Ck) = \n(n —
* + 2)/2[
(c) Если Pk — путь на k вершинах, то m(n,Pk)=]n(n-—
— k+\)/2[,n>k.
(d) Если &~*k — система из ]k/2[ по возможности независи-
независимых ребер на k вершинах, то пг(п;ЗГ'к) = ]п(п — k + 1)/2[.
(e) Если п ^ 2р + q, то
р=1, 4 = 0,
р=\, q=\,
n-l,
тах{р2,«},
= 2, ^=1,^ = 5,7,9,
, q=\, « = 2p
q = \, n
(f) Пусть m(n,p,q)—минимум числа ребер в «-вершинном
графе, у которого среди любых р вершин найдется Kq. Дока-

Дополнение If. В. С. Стечкин
жите, что
tn (n, p, q) = min
p-
Г n — r + i "|
L Tr J
2
>-\)-(q-l)t0, n > (<7/(<7 - 1)) (p - 1),
и в частности, если р ^ 2 (? — 1), то m («, р, <7) = (" ~ \ +') и
« < -Г (Р — 1).
(р-
t-0
Закончим двумя открытыми задачами, первая из которых
асимптотически уже решена, а во второй даже для получения
асимптотического решения приходится обращаться к экстре-
экстремальным характеристикам разбиений.
Задача 4. (а) Сколь мало ребер может иметь п-вершинный
граф, у которого среди любых k вершин найдется / независи-
независимых ребер?
(Ь) Вычислить ц{п; КР,Ч). (Указание: см. задачу 2.)
Текст настоящего дополнения составлен по материалам сле-
следующих публикаций:
[1] Баранов В. И. Комбинаторная модель явления фрагментации па-
памяти.— Программирование, 1978, № 3, с. 46—52.
[2] Баранов В. И. Одна экстремальная задача о разбиениях чисел. —
Матем. заметки, т. 29, 1981, № 2, с. 303—306.
[3] Стечкин Б. С. Экстремальные свойства разбиений чисел. — ДАН
СССР, т. 264, 1982, № 4, с. 833—836.
[4] Стечкин Б. С. Экстремальные свойства разбиений. — В кн.: Эн-
дрюс Г. Теория разбиений. — М.: Наука, 1982, с. 249—253.
[5] Стечкин Б. С, Франкл П. Локально-турановское свойство для
ft-графов. — Матем. заметки, т. 29, 1981, № 1, с. 83—94.
[6] Стечкин Б. С, Франкл П. Локально-турановское свойство для
fe-графов. — Препринт МИАН ВНР, 1977, № 20, Будапешт.
[7] Катона Д., Косточка А., Стечкин Б., О локально-гамильтоновых
графах. — Препринт МИАН ВНР, 1982, Будапешт.
[8] Комбинаторный анализ: задачи и упражнения/Под ред. К. А. Рыб-
Рыбникова.— М., Наука, 1982.
[9] Erdos P., Simonovits .M. A limit theorem in graph theory. Stud. Sci.
Math. Hungar, Vol. 1, 1966, p. 51—57.
[10] Стечкин Б. С. Вложимость разбиений. — Препринт МИАН ВНР,
1983, Будапешт
Оглавление
О теории Рамсея . 5
Предисловие 6
Введение 7
Глава 1. Три взгляда на теорию Рамсея 9
Глава 2. Теорема Рамсея • • ¦ • 12
Глава 3. Теорема ван дер Вардена ..'... у]
Глава 4. Теорема Халеса — Джеветта • ¦ ¦ • 23
Глава 5. Теорема Семереди • . • • 28
Глава 6. Рамсеевская теория графов 35
Глава 7. Евклидова теория Рамсея 48
Глава 8. Общая теорема рамсеевского умножения 59
Глава 9. Теоремы Шура, Фолкмана и Хиндмана 61
Глава 10. Теорема Радо 65
Глава 11. Современные вопросы теории 69
Литература 73
Дополнение I. Как было найдено доказательство гипотезы Баудета.
Б. Л. ван дер Варден 77
Дополнение II. Принцип полного размещения. Б. С. Стечкнн ..... 87