Author: Спенсер Дж. Эрдеш П.
Tags: теория вероятностей и математическая статистика математика теория вероятностей
Year: 1976
Text
PROBABILISTIC
METHODS
IN COMBINATORICS
by
Paul Erdos
and
Joel Spencer
AKADEMIAI KIADO BUDAPEST
1974
П. Эрдёш, Дж. Спенсер
Вероятностные
методы
в комбинаторике
Перевод с английского
Б. С. СТЕЧКИНА
С предисловием
Ю. В. ПРОХОРОВА
ИЗДАТЕЛЬСТВО «МИР»
МОСКВА
1976
УДК 519.21
Книга известного венгерского математика Пауля Эрдёша,
написанная совместно с американским ученым Джоэлом
Спенсером, посвящена применению теории вероятностей к
комбинаторике. Это первая в мировой литературе монография
по данному вопросу. Она содержит как несложные
комбинаторные результаты, позволяющие демонстрировать технику
использования вероятностных методов, так и комбинаторные
теоремы, доказать которые можно лишь вероятностным
методом.
Разнообразие представленных проблем и несложность
вероятностных доказательств делают книгу интересной
специалистам по комбинаторике и теории графов и доступной
студентам младших курсов университетов и педвузов.
Редакция литературы по математическим наукам
20203-014 © Akademiai Kiado, Budapest, 1974
041 (01)-76 © Перевод на русский язык, «Мир», 1976
Предисловие к русскому изданию
В последнее время наблюдается тенденция переводить
сложные комбинаторные конструкции на простой язык
теории (конечных) множеств. Теоретико-множественный подход
к граф-комбинаторным задачам, во-первых, способствует
достижению наибольшей общности результатов, а во-вторых,
является весьма удобным для использования вероятностных
концепций.
В книге П. Эрдёша и Дж. Спенсера с большой ясностью
продемонстрированы оба эти преимущества; именно четкий
переход к теоретико-множественной трактовке позволяет
интуитивно вводить вероятностные модели, оперирование с
которыми (посредством чисто вероятностных методов) приводит
к выводам, подчас весьма тонким, о структуре исследуемых
комбинаторных объектов. Вероятностные методы, несмотря
на свою „неконструктивность", могут в ряде случаев
показать, что является правилом, а что исключением, и тем самым
помочь отысканию требуемого объекта (хотя бы с помощью
случайного эксперимента).
Обзорный характер изложения делает книгу полезной не
только студентам, но и специалистам по комбинаторике и
теории графов. Для русского издания книги авторы прислали
ряд исправлений; мы весьма признательны им за это.
Некоторые изменения в текст (согласованные с авторами) внес
переводчик — они отмечены специальным знаком.
В конце книги в качестве дополнения помещена статья
П. Эрдёша и Д. Дж. Клейтмена „Экстремальные задачи
о подмножествах конечного множества".
Ю. В. Прохоров
Предисловие
Область комбинаторной математики в последние
десятилетия переживает период бурного развития. Уже не являясь
более „деловым подвалом" топологии, комбинаторика сегодня
составляет самостоятельную часть стандартной
математической программы. Исследования по этой тематике ведутся во-
всех крупных математических центрах. Связанная со
многими областями, комбинаторика повсеместно используется
математикой, естественными и общественными науками. Уже
построены прочные основы и развит разнообразный
методологический аппарат комбинаторной математики.
Цель настоящей монографии — описать некоторый подход,,
который мы называем вероятностным методом.
(Предварительное его описание дано в первом параграфе.) Этот метод,
с большим успехом применяется к широкому кругу
комбинаторных задач.
Вероятностный метод будет служить мощным орудием
в любых комбинаторных исследованиях. При знании era
основ многие трудные задачи можно решить почти
тривиально. Тем более огорчительно, что многие исследователя
не знакомы с этими основами. Возможно, это объясняется
тем, что предшествующие работы по использованию
вероятностного метода были рассеяны в море литературы. Мы
искренне надеемся, что издание данной монографии
послужит более широкому распространению этого метода.
Несколько слов о задачах. Они сильно разнятся по
трудности, в связи с чем была предпринята попытка выделить
особенно трудные. Задачи, отмеченные знаком (?), не решены
до настоящего времени. Лицам, решившим такие задачи,,
предлагается установить контакт с авторами. Некоторые
нерешенные задачи помечены различными денежными суммами,
например ($ 25), ($ 50) — старший автор (П. Эрдёш)
предлагает эти суммы как приз за первые решения этих задач.
Мы выражаем благодарность издательствам „Академиа
Киадо" и „Академик Пресс" за публикацию этой книги.
Научно-исследовательское управление ВМС США оказала
поддержку младшему автору при подготовке окончательного
варианта рукописи. Мы благодарим миссис Б. Бойд за
превосходное оформление.
Наконец, младший автор хочет поблагодарить свою жену
Марианну за ее помощь, поддержку и понимание. Без нее
работа над книгой не могла бы успешно закончиться.
Пауль Эрдёш Джоэл Спенсер
Будапешт, Венгрия Кембридж, Масс, США
1. ДВА ПРИМЕРА
В этой книге рассматривается некий метод
доказательства теорем, который мы будем называть вероятностным или
неконструктивным. Этот метод используется для
доказательства того, что некоторый член исследуемого класса объектов
обладает определенным свойством, без непосредственного
конструирования такого члена. Мы показываем, что в
некотором вероятностном пространстве вероятность того, что такой
объект существует, положительна. Для большей наглядности
продемонстрируем на примерах этот метод.
Турнир Т транзитивен, если (/, /), {/, k)^T влечет, что
•(/, k) ^ Г, или: Т транзитивен тогда и только тогда, когда
существует перестановка а его игроков, такая, что (/, /') е Т
тогда и только тогда, когда o(i) < о (j). (Определения
используемых здесь понятий даются в следующем параграфе.)
Пусть v (/г) — то наибольшее целое, для которого всякий
турнир на {1, ..., п) содержит транзитивный подтурнир
с v (п) игроками.
Теорема 1.1 (Эрдёш, Мозер [1964]). v (л)< 1 + [2 log2/z].
Иными словами, найдется турнир Теп «игроками», не
обладающий транзитивным подтурниром с v = 2 + [2 log2п]
игроками. (Р. Стирнз при помощи индукции показал, что
v (п) > 1 + [Iog2/z] (доказательство см. Мун [1968]).)
Доказательство. Пусть & = Уп обозначает класс всех
турниров на {1, ..., /г}, а &' — класс тех турниров на {1, ..., /г},
которые содержат транзитивный подтурнир с v игроками.
Тогда
^'=УУ^Л.а, (Ы)
где Ле{1, ..., /г}, \А | = v, а —- перестановка элементов
множества А и УА,а — множество турниров Г, таких, что
турнир Т | А генерирован а. Таким образом,
8
7. Два примера
и, согласно элементарным оценкам,
I^^^^HO^^^bMO.- 2(*)=| 34. (1.3)
А, а
Итак, 3— °f'ф ф\ это означает, что существует турнир
Ге^- 3f', не содержащий транзитивного подтурнира
с v игроками. ■
Концовка доказательства подчеркивает его
неконструктивный характер. Мы доказали, что множество не пусто иу
следовательно, содержит требуемый член 7Y Это
доказательство не дает алгоритма для построения такого Г. После того
как теорема доказана неконструктивными методами, все же
представляет интерес получение доказательства при помощи
конструкций. В данном примере было бы интересно
«сконструировать» турнир Тп, не содержащий транзитивного под'
турнира с 1001og2/z игроками, хотя из приведенного выше
доказательства и вытекает, что «почти все» турниры Тп
обладают этим свойством.
Имеется сходство между неконструктивным методом и
использованием аксиомы выбора. Можно даже понимать
неконструктивный метод как конечный аналог аксиомы выбора.
Однако есть одно принципиальное отличие. Мы всегда можем
найти гарантированный Т трудоемким перебором каждого-
члена (конечного) множества Э', пока не найдем один с
требуемым свойством. Следовательно, в отличие от аксиомы
выбора здесь нет логических трудностей.
Приложение вероятностного метода к «действительному
миру» задач может вызвать дополнительные трудности.
Пусть, например, какому-то вычислителю дано задание
построить на вычислительной машине матрицу турнира со 127
игроками, не содержащего транзитивного подтурнира с 15
игроками. Представим себе, что если матрица содержит такой
подтурнир, то его фирма (или страна) понесет большие
финансовые потери. Из нашей книги он узнает, что такой турнир
существует. Но этого недостаточно — руководство требует от
него конкретную матрицу. Наш вычислитель подсчитывает,
что ее нахождение методом полного перебора может обойтись
в миллионы долларов, а он, подобно многим из нас, имеет
ограниченный бюджет. Как ему поступить? Имея слабый
характер, он скорее всего станет, уповая на судьбу, строить
Т наобум, но на случай спешного отъезда упакует
чемоданы. По опыту нашего общения с вычислителями это и есть
«действительно мировое» решение. Если же его характер
тверд, он, по-видимому, потребует вернуть деньги,
истраченные на книгу. Конечно, мы ему откажем.
/. Два примера
9
«Реальная» ситуация меняется, если потребовать, чтобы
турнир не содержал транзитивного подтурнира с 16
игроками. Тогда
lW]<CS)2~"2'~0,00128.
-«Случайный» турнир будет обладать требуемым свойством
с вероятностью ^0,998. Такая вероятность успеха вполне
достаточна для многих практических ситуаций — наш
вычислитель может рандомизировать и успокоиться.
Мы будем формулировать наши теоремы в следующей
манере: «существует турнир (или граф, или матрица) с
данным свойством»; Во многих случаях они могут быть
сформулированы и так: ««случайный» турнир обладает данным
свойством с вероятностью р», где 1 — р <С 1. Постановки второго
типа могут иметь большую аппликативность.
Можно поинтересоваться, действительно ли
неконструктивное доказательство дает решение данной проблемы? Как
показывает наш пример, это зависит от конкретного вида
задачи.
Передокажем теперь теорему 1.1 другим способом. Пусть
Т = Тп — случайная переменная, чьи значения суть члены
-(п)
множества &, для каждого из которых Р(Т = Г) = 2 ^2'
Т^У. То есть все члены множества & суть
равновероятные значения случайной величины Т. Можно взглянуть на Т
и несколько по-другому. Для каждой пары (/, /) игроков
справедливо равенство Р ((/, /) gT)= 1/2, и эти вероятности,
взятые по каждой игре, взаимно независимы. Перечисленные
-свойства определяют Т. Тогда
Р (Т содержит транзитивный подтурнир с v игроками) ^
<!"X £ Р (Т I А генерируется а) =
А о
= (;)о!2"(*)<1. (1.4)
Таким образом, некоторое значение Т случайной величины Т
не содержит транзитивного подтурнира с v игроками.
По существу мы просто переписали первоначальное
доказательство, которое служит примером «оценочного рассужде-
лия». Второе доказательство — это «вероятностное
рассуждение». При доказательстве большинства теорем этой книги
будем придерживаться одного из этих подходов.
Вероятностные рассуждения представляются нам более ясными и
интуитивными. В более сложных результатах (например, тео-
iO
/. Два примера
ремы 5.3, 8.1) вероятностный подход допускает
непосредственное применение вероятностных теорем. Мы будем
стремиться к использованию случайных переменных. Следует,
однако, отметить, что большинство предшествующих работ
основывалось на оценочных рассуждениях.
Рассмотрим еще один пример. Гамильтонов путь Р в
турнире Тп определяется как такая перестановка Р (1), ..., Р (п)
игроков турнира, для которой (Р (/), Р (/ + I)) ^Т, 1 <л < п..
Следующий результат Селе [1943], возможно, был первым
применением неконструктивных методов.
Теорема 1.2. Существует турнир Т = ТПУ содержащий
неменее п\ 2~п+{ гамильтоновых путей.
Доказательство. Пусть множество 2f = 2/n определено^
как и ранее. Положим
U = {{Tt Р): Ts=3fn, Р — гамильтонов путь в Т}9
тогда
\U\=Z\{P: (T,P)<=U}\ = (1.5).
т
= Z\{T: (T,P)e=U}\. (1.6)-
Р
Зафиксируем произвольный путь Р. Тогда (Г, Р)е[/ в том
и только том случае, когда (я — 1) определенных игр,,
а именно (/г—1) игр, составляющих путь Р, наличествуют
(п \ , _ -.
турниров Г. А так как имеется /г! путей Р, то
If/I^^b*-0. (1.7),
(")
Правая часть (1.5) имеет в точности 2^2' слагаемых.
Следовательно, для некоторого Т
\{Р: (Г, P)<=U)\>n\2-{n-l). ■ (1.8)
Замечание. Селе также показал конструктивными
методами, что наибольшее число гамильтоновых путей
ограничено сверху величиной п\ 2~3п/4.
Сейчас мы перепишем это доказательство как
вероятностное. Пусть снова Т = Тп — случайный член множества 3V
с тем же распределением. Определим fP на 2fn следующим,
образом:
( 1, если Р — гамильтонов путь в Г,
1р\ ) |q в Пр0ТИВН0М случае.
/. Два примера
U
Положим
^ (Т) = 2 fp (Т) = (число гамильтоновых путей в Г).
р
Тогда
Е[ЛКТ)] = Е[ЕЫТ)]= (1.9)
= Ее[ЫЩ= (1.Ю)
Р
= Е2'я+'= (1.11)
р
= n!2"rt+1, (1.12)
где Е обозначает математическое ожидание. Таким образом,
для некоторого Т имеет место требуемое неравенство
N(T)^n\2"n+l.
Решающий переход от (1.9) к (1.10) обусловлен
следующей теоремой.
Теорема 1.3 Если Хь ..., Хп суть случайные величины
х конечными математическими ожиданиями, то
математическое ожидание их суммы существует и равно сумме их мате-
магических ожиданий.
Доказательство можно найти практически в любом
руководстве по теории вероятностей (см., например, Феллер [1964]).
Заметим, что зависимость или независимость X/ не
оговаривается. Неожиданная польза теоремы 1.3 обнаруживается
б упр. 3 и 4.
Такое использование математического ожидания
называется методом первых моментов.
Упражнения
1. Пусть w (п) — наибольшее целое, такое, что для всякого
турнира Т на {1, ..., п) найдутся непересекающиеся
множества Л, Ве{1, ..., п) мощности w(n) = \ А | = | В |, такие,
что ЛХВ^Г. Найти верхнюю оценку w(n).
2. Гамильтоновым циклом в турнире Т называется такая
перестановка Р, для которой (Р (/), Р(/+1))еГ (l^.i<n)
и (Р(п), P(1))gjT. Доказать, что существует турнир Г,
содержащий по крайней мере п\ 2~п гамильтоновых циклов.
3. Гардеробщице ночного клуба было сдано 30 шляп.
Она поссорилась с управляющим и, досаждая ему, выдала
все 30 шляп случайным образом. Каково среднее число людей,
лолучивших обратно свои собственные шляпы?
12
/. Два примера
4. Народ Нортумбрии1) решил выдать ведущим лидерам
своих политических, культурных и деловых кругов
специальные удостоверения с номерами от 1 до 2000 включительно.
В результате широкой дискуссии был составлен список 2000
таких лидеров. Во избежание дальнейших обсуждений было
решено выдавать им удостоверения случайным образом.
Каково среднее число лидеров, номера удостоверений
которых совпадают с годом их рождения?
]) Нортумбрия — англо-саксонское королевство, существовавшее
с конца VI в. по 829 г. на территории современной Великобритании.
История донесла до нас имя одного выдающегося деятеля культуры
этого государства —- Беды Достопочтенного (673—735), основоположника
английской исторической науки. — Прим. перев.
2. ОБОЗНАЧЕНИЯ
В этом параграфе вводятся стандартные для всей книги
обозначения. Этот параграф предназначен главным образом
для справок, однако читателю полезно просмотреть его при
первом чтении. Вероятностные обозначения (подчас необычные)
существенны для дальнейшего изложения.
На протяжении всей книги (кроме § 17А) мы будем
иметь дело исключительно с конечными объектами.
Встречается некоторая путаница в обозначениях
(например, [х]), но мы надеемся, что смысл будет ясен из контекста.
Арифметика
Если х — действительное число, то
[х] — наибольшее целое, не превосходящее х\
{х} — наименьшее целое, не меньшее х.
Если / ^ 1 — целое, то
[/ и 0! = 1;
1
О, если х < /,
Д(л: —/)//!, если x^t\
для всех х.
Множества
Если X — множество, то
| X | — обозначает мощность, т. е. число элементов
множества X,
2х — множество всех подмножеств множества X, т. е.
2*=* {Y: Y^X}\
[X]' = {Y: Ys=X, \Y\ = r);
[n]='{x: x — целое, 1^*^я} = {1, ..., n}> часто будет
использоваться как «стандартное» n-элементное
множество;
i
(О-
14
2. Обозначение
[n)r=\[n]Y = {Y: Ys[n]9 | ГI-г};
П, U — знаки пересечения и объединения множеств;
X-Y = {x: xezX, хфУ}\
X AY= (X (J Y) — {X (J Y) — симметрическая разность множеств
1иУ.
[«г-множество» («г-подмножество») — множество
(подмножество) мощности г. — Перев.]
Графы
Граф G на множестве вершин V определяется как
произвольное подмножество [V]2. Элементы графа называются
ребрами. Если x^V, то степенью вершины х в графе G
называется число deg (л:) = |{j/gI/: {х9 у} е G} |. Если W г К, то
граф G|U^ = Gfl[^r]2 называется подграфом, порожденным
множеством И^ (иногда также говорят, что граф G\W
генерирован W, и называют Н^-генератором). Подграф Я графа G
определяется как подмножество множества G. Множество
вершин W^V называется независимым относительно графа G,
если G[)[W]2= 0. Кликой называется такое множество W,
для которого G(] [W]2=[W]2. Кликовым числом,обозначаемым
через co(G), называется мощность | W | максимальной клики
графа G. (В теории графов кликой, вообще говоря, принято
называть любой максимальный полный подграф графа G; см.,
например, Харари [1973]. — Перев.)
Раскрашивание
> r-раскрашиванием графа G назовем такое отображение
h: V-*{r]f что для всех е = {х, у) е G выполняется
неравенство /г(х)фН(у). То наименьшее г, для которого
осуществимо г-раскрашивание графа G, называется хроматическим
числом этого графа и обозначается через %(G).
Подчас нам будет удобнее рассматривать 2-раскраши-
вание как отображение A: F->{1, — 1}.
Расцвечивание Al)
г-расцвечиванием гиперграфа G s 2V называется
отображение h: G->[r]. Запись Dr(G) = (К\, ..., Кг) обозначает
некоторое г-расцвечивание графа G, причем Ki — множество
г
ребер цвета /, £/f* = G. Ясно, что всякое г-расцвечивание
графа G является некоторым г-раскрашиванием графа [G]\
*) Здесь и далее знаком А отмечен материал, добавленный при
переводе. — Прим. перев.
2. Обозначения
15
Гиперграфы
Гиперграфом G на множестве вершин V будем называть
всякое подмножество множества 2V. Элементы гиперграфа,
называются гиперребрами. Гиперграф G называется &-гра~
фом, если G s [V]k, так что 2-графы суть просто графы.
Если G есть &-граф, а УеУ таково, что G\W — [W]k, то W
называется кликой. Кликовое число (o(G) определяется как
мощность наибольшей клики. Если G-^ гиперграф, то под
его r-раскрашиванием понимается такое отображение ft: V ->-
->[/*], что в любом гиперребре e^G найдется пара вершин
х, у ее, удовлетворяющая условию h(x) ф h(y)1).
Хроматическое число %(G) и независимое множество вершин
определяются так же, как для графов.
Турниры
Диграф D на множестве V определяется как некоторое
множество упорядоченных пар (х, у), ху у gF, х Ф у.
Турниром Т на множестве V называется такой диграф, что для
всяких х9 у е V, х ф у, либо (jc, у) е Т9 либо {уу х) е Г,
ноне одновременно. Естественно интерпретировать множество V
как множество игроков, а наличие ребра (х, у) е Г — как по^
беду х над у. Элементы множества [V]2 называются играми
турнира Т.
Если граф, гиперграф, диграф или турнир заданы на
множестве V = [п]у мы будем обозначать это через Gnf Кп, Dn9 Тп^
Вероятность
Сейчас мы хотим связать понятие вероятностной структуры
с только что введенными. Для обозначения случайных
величин будут использоваться жирные буквы (например, х, X, G,
Т). Поскольку мы имеем дело с конечными объектами, наши
случайные величины могут принимать лишь конечное число
возможных значений, так что для данной случайной величины
имеется s возможных значений хи ..., xSJ которые реали-
г
зуются с вероятностями 0 ^ ри ..., ps ^ 1 = £ ph т. е.
P[x = xi] = pi.
1) Иногда для r-раскрашивания гиперграфа G будет использоваться:
обозначение Gr (G) = (Ки • • •» #/■)• Здесь Ki — множество вершин цвета.
г
i(l </</*), причем I) Ki = V. — Прим. перев.
16
2. Обозначения
Случайные графы
Для О^р^ 1 случайный граф GntP определяется как
случайная величина, чьи допустимые значения — суть элементы
множества всех графов на [я], причем если ее [я]2, то
P[^g Gmр] =р и для различных ребер е эти вероятности
независимы. Таким образом,
P[Gn,p = G]=pioi(l-p)G)-1G1.
Для О^^Го) случайный граф Gntl определяется как
случайный член множества [[п]2] . То есть Grt, / — случайный
граф с я вершинами и / ребрами. Эти два вида графов
будут различаться при использовании.
Случайные турниры
Через ТЛ будем обозначать случайный турнир на [я]. Для
любого Тп выполняется Р[Тп = Тп] = 2 ^2Л Если х, */е[я],
хфу, то Р [(а:, у) еТп] = 1/29 причем эти вероятности
независимы для всех игр, кроме (х9 у) еТп, тогда и только тогда,
когда (х, у) <?Ё 1п.
Случайные объекты
Для краткости назовем х случайным членом класса С,
если каждый xgC реализуется с равной вероятностью.
Например, «S — случайное r-подмножество множества [я]»,
означает, что для всякого Ss[rt], |S| = r,
p[s=5j=(;)"'.
О-болыиое, о-маленькое.
Иногда будем пользоваться обозначениями о и О. Если
f(n) и g{ri) — две функции, причем lim / (n)/g (я) = 0, пишем,
Л->оо
что f (п) = o(g(n)). Мы пишем, что f(n) = 0(g(n))> если
существуют С и яэ, такие, что | / (n)/g(n) \ <С для всякого я > я0.
Как правило, я будет обозначать число вершин в наших
совокупностях. Если обозначения о и О записываются без
указания переменных, это значит, что переменной является я.
3, БИНОМИАЛЬНОЕ РАСПРЕДЕЛЕНИЕ
В этом параграфе приводятся те факты о биномиальном
распределении, которые, как правило, без специальных
оговорок используются на протяжении всей книги.
Пусть X;, 1 <л^я, — независимые случайные величины
и р [х, = + 1] = Р [X, = - 1] = 1/2. Положим
S*=£x,. (3.1)
Пусть Yf, 1 <С/^/г, —- независимые случайные величины и
р [у, = 1] = Р [Y, = 0] = 1/2. Положим
Тогда
P[u„=;] = CV(i-pr', К'<я- (з.з)
Будем пользоваться хорошо известной формулой Стирлинга
п\ = nne-n ^2ллГ (1 +о(1)). (3.4)
Роббинс [1955] преобразовал (3.4) к виду
nne~n л/2тт £?|/<12я+1) < п\ < nne~n <у/2лп ет2п. (3.5)
Хотя мы нигде в этой книге и не пользуемся (3.5), формула
весьма помогает при доказательстве теорем для всех п
(например, теорема 15.1).
Если X и Y — две случайные величины, имеющие
одинаковое распределение, то пишем, что X~Y. Таким образом,
2U„ — n~ S„.
Воспользуемся общепринятым обозначением В (п, р) для
биномиального распределения. То есть В (п, р) — это
распределение числа успехов в п независимых испытаниях, где
вероятность успеха в каждом испытании равна р. Так, например,
\}п имеет распределения В (/г, 1/2).
Пусть N (\х> о) обозначает нормальное распределение со
средним \х и стандартным отклонением а. Для больших^ п
случайную величину Sn можно аппроксимировать N(0, л/п ).
18
3. Биномиальное распределение
В частности, если
lima (п)п~ч* = с, (3.6)
п
ТО
оо
lim Р [S„ > а (п)] = Ф (с) = -i=- J е-*'/2 d*.
Нас интересует и хвост биномиального распределения.
Чернов [1952] показал, что если р и # —положительные числа»
такие, что р + <7=1, то
£ (7) Р*Ят~* <ехР К" ~ *) 1оё (Щ1(* ~ *)) +
+ A log (тр/А)], (3.7)
где сумма берется либо по всем t, таким, что t^k> либо по
всем if, таким, что t^kt в зависимости от величины A: k^pm
или k^ptn. Мун [1971], положив р = ^ = 1/2, k = m/2 + Xr
показал, что
J (7)<2техр[-2Л2/т], (3.8)
t>m/2+X
0^Х^1/2т. В наших обозначениях, если Л>0, то
P[Sm>X]<e-^/« (3.9)
Эта формула используется по всей книге.
Мы также будем часто применять следующую
элементарную асимптотическую формулу:
k% fe3
(*)~^п—(1 + М1)). (зло)
справедливую для k = o{n3/*).
4. СВОЙСТВО В
Пусть У={Аа}—гиперграф на множестве вершин A1=|J Аа,
а
Определение. Говорят, что гиперграф 2/ обладает
свойством В, если %{У)^2. Это эквивалентно тому, что
существует такое множество вершин S s М, которое для всякого
гиперребра А е 2/ удовлетворяет условиям
0с=5ПЛс=Л,
где cz — собственное включение.
Это свойство впервые было рассмотрено Миллером [1937].
Для его обозначения он использовал букву В в честь Феликса
Бернштейна. Эрдёш и Хайнал [1961] определили ш(п) как то
наименьшее | & |, для которого существует /г-граф, не
обладающий свойством В. Поскольку /г-граф Ь = [2/г—1]п является
таковым, то ш(п) существует.
Теорема 4.1. m {п) > 2я"1.
Доказательство. Пусть 9 фиксирован и |ЗЧ = /. Через
С = (К\, К2) обозначим 2-раскрашивание множества М, т. е.
К1[)К2 = М, К\ П^2 Ф 0- Если р (С)— число
монохроматических ребер А ^У относительно раскрашивания С, то
Р(С)- Е t I I- (4.1)
Пусть теперь C = (Ki> Кг) обозначает случайное
2-раскрашивание М; тогда
EIP(C)]= Е Ер[а = к,] =
= £ Z2-"= (т.к.|Л| = п)
= /2""+l. (4.2)
Но если 2/ не обладает свойством В, то р (С) ^ 1 для
всякого С. Таким образом,
1<Е1{ЦС)1 = /2-я+1 (4.3)
20
4. Свойство В
и, следовательно,
2n~l<f. (4.4)
Мы улучшим этот результат, используя метод Шмидта.
Пусть & — некоторый /г-граф, не обладающий свойством В.
В теореме 4.1 мы производили случайное раскрашивание М.
Если при случайном раскрашивании М одноцветным
оказывается какое-то ребро N е^, то этому ребру приписывается
цвет одной из его вершин xN е N. Другими словами, каждому
одноцветному ребру N ^ У мы ставим в соответствие такую
его вершину xN е N, что
| {L е= Э% L П N = {%}} | < fn-\ (4.5)
Такая вершина xN е Л/" (удовлетворяющая (4.5)) всегда
найдется, поскольку в противном случае
\Sf\>\{L^Sfy |in#l=l}l>/i(//H).
Для всякого конкретного раскрашивания С = (К\, К2) либо
Р (С) ^2, либо существует единственное ребро N ^У, /=1
или 2, N^Kt. Положим С/=(/С1А{%}, /С2Л{%}). Так как
р(С')^1> некоторое L е с7 одноцветно в С. Это возможно
только тогда, когда L f) К/ = {%}> откуда следует L(]N = {%}.
Таким образом, для всех С==(/С1, /Сг)
f+Г Е I I !>■• (ад
Пусть С —случайное раскрашивание. Как и раньше, Е [р(С)]=
= /2"л+1. Имеется менее чем f(fn~l)(2) способов выбрать
N, L, L И для каждого такого выбора
Р [N s К„ £ П К, = {xN}] = 2- {2п~1). (4.7)
Тогда
ЕГЕЕ 1/21 <f(fn-') (2)2-(2""1)2-1, (4.8)
L(D (2) J
где суммирование £ производится по N, L е &, N {\L = {%},
(1)
i = 1 или 2, а суммирование 2 — по ЛА ^ К^, L П К; = {%}.
(2)
Взяв среднее в (4.6), получим
/2"n + /2/i"l2"(2n"I)>l (4.9)
следствием чего является
Теорема 4.2 (Шмидт [1964]). m (л) >2"(1 +2/1-1)"1.
4, Свойство В
21
TEOPEMA4.3(3pAem[1964]).m(/z)<(l + o(l))e(log2)/z22rl"2.
Доказательство. Положим г = [п2/2]. Пусть At, А2, ... —
независимые случайные члены множества [г]п. Положим
F = F^ = {At, ..., А^}. Для любого раскрашивания С =
= (К\> К2) и любого / согласно элементарным вычислениям:
получаем
Р1А,од„оцве™о1 = [('«;') + (^')]/(;;)>
>2{Г'п)/{п)>[п0 Л6ММе 12'2]
>2e^l2"n{l + o(l)). (4.10)
А поскольку Af независимы, то
Р [F раскрашиваемо при помощи С] <
<(1-2<Г12-'г (1+о(1))/ (4.11)
и, следовательно,
Е[|{С: F 2-раскрашиваемо при помощи С}|]<
< 2Г (1 - ЪГхТп (1 + о (1))/. (4.12)
Положим f = (1 + o(l))e(log2) п2п~2, тогда математическое
ожидание числа 2-раскрашиваний F меньше единицы.
Следовательно, существует Ff, \ Ff \ < /, не обладающий 2-рас-
крашиванием. ■
Венгерский математик Бек (J. Beck) недавно показал, чта
m(n)>[r3log2n].
Упражнения '
Эрдёш [1969] определяет mN(n) (N^2n — 1) как то
наименьшее 134, для которого существует п-граф 2/, не
обладающий свойством В, где N = | U & | — число вершин я-графа 9'..
1. Используя метод теоремы 4.2, показать
m2N (л) < - 2JV log 2/log [l - 2 ( * )/(2f )].
2. Показать
(Указание: Обозначим через C = (Ki> К2) случайное 2-раскра~
шивание U &, выбираемое равновероятно среди тех
раскрашиваний, для которых | К\ | = | /С21= N. Использовать метод
теоремы 4.1.)
22
4. Свойство В
3. Существует ли /г-граф Э\ не обладающий свойством В
и такой, что Аь A2^2f влечет | А{ (] Л2 К 1? (Эта задача
может показаться весьма трудной, если не воспользоваться
методами теоремы 11.2. (см. § 11, упр. 4). Для
конструктивного решения см. Аббот [1965].)
4. (?) Существует ли для данного k такое п < m и такое
семейство F^[m]n, которое удовлетворяет следующим
свойствам:
(a) F не обладает свойством В;
(b) Т7-—«минимально», т. е. для любого А е F семейство
F — {A} уже обладает свойством В;
(c) Л, SgF влечет |ЛПВ|<1;
(d) для любой вершины х е [пг]
\{А: xe=A<=F}\>k?
Этот вопрос был поставлен Б. Тафтом.
5. Герцог и Шёнхейм [1972] определили, что У обладает
свойством Вг, если х(^~)^г- Они определили mr(n) как то
наименьшее | & |, для которого существует я-граф #", не
обладающий свойством Вг. Найти оценки, аналогичные
теоремам 4.2, 4.3 для пгг{п) при фиксированном г. В частности,
доказать, что
lim tnr(n)Vn = r.
6. Преобразовать (4.9) к виду
/2"я + /[(/-1)/л]2"(2я-1)> 1
и, используя это неравенство, показать, что т(3) > 6.
7А. Эрдёш [1963b] определил свойство Вг как
существование такого S£M, для которого всякое ребро Ле^
удовлетворяет условию 0 < | S П А | < г. Определить тГ (п) для Вг,
как тг (п) для Вг в упр. 5, и найти оценки для тг (п).
В частности, показать, что
m»<n+;+1).
5. ТЕОРЕМА РАМСЕЯ
Следующая теорема, впервые сформулированная и
доказанная Рамсеем [1930], лежит в основе многих
комбинаторных исследований.
Теорема Рлмсея. Для всяких целых /, ku ..., ft/
существует такое наименьшее целое r = Rt (ku ..., fey), что для
любого множества S, содержащего не менее чем г членов
(|S|^r), и любого ^раскрашивания C = (/Ci, ..., /С/)
множества [[S]1]1 найдется такой номер i (1^/^/), для
которого имеется такое к^элементное подмножество А^ S
(IЛ !=■*,), что [A]l<=Ki.
А Для большей четкости сформулируем эту теорему в
кванторах: V/, &ь ..., ft/ 3 минимальное г = Rt (ku ..., fty):
VS(|S|>r), VC/([[S]']') = (*i, .... К/)
3* «=[/]: ЗЛе[^: [A]lsKt..
Различные доказательства теоремы Рамсея можно найти
во многих комбинаторных текстах (см., например, Райзер-
[1966]). Нас будет интересовать тот специальный случай этой
теоремы, когда / = / = 2.
Теорема Рамсея (частный случай). Для любых двух
целых чисел kt 1^2 существует такое наименьшее r=/?(ft, /),.
что для любого r-множества S (| S |) = г) и любого 2-расцве-
чивания D ([S]2) = (К\, К 2) графа [S]2 либо
(a) существует такое Т е [S]k> что [Т]2^К\, либо
(b) существует такое U^[S]1, что [Щ2^К2.
Доказательство. Будем доказывать теорему по индукции.
Очевидно, R(k> 2) = R (2, k) = k. Пусть ft, I > 2;
предположим, что и R(k— 1, /), и R(k, 1—1) существуют. Положим
Г = R (ft - 1, I) + R (ft, I - 1), и пусть | S | > г, a D = (Ки К2) -
некоторое 2-расцвечивание графа [S]2. Зафиксируем x^S
и положим
A = {ys=S: {хуу}^К^
B = {y<=S: {x,y}s=K2b
24
5. Теорема Рамсея
Так как \А\ + \В\ = г — 1, то либо |Л|>Я(й—1, /),
либо \B\^R(k> I— 1). Допустим, что имеет место первое
неравенство (другой вариант симметричен). Согласно
индукционному предположению, либо
(Ь') найдется U^[A]1, [£/]2£/С2; но тогда UsS и тем
самым (Ь) выполнено; либо
(а') найдется Тх е [Л]*"1, [Txf^K\\ но положим в этом
случае Т = Тх\]{х}\ тогда \T\ = k, [Г]2^/^ и тем самым (а)
выполнено. ■
Исходя из неравенства
R(k, /)</?(*— 1, /) + /?(*, /-1), (5.1)
можно показать по индукции, что
л(мх(*£!т2)- <5-2)
Но прежде всего рассмотрим нижние оценки для R(k> /).
Предположим, что £ = /; обозначим в этом случае R(k> к)
через г; положим М = [г]2, и пусть
ЗГ = {[Т]2: Ге[г]*}. (5.3)
Тогда 5^ не обладает свойством В. А поскольку & является
| 2 J-графом, то, согласно теореме 4.1,
(D-i'is-Os»^"'- №■*)
Применение элементарных оценок к (5.4) приводит к
следующей теореме.
ТгоРЕМА 5.1 (Эрдёш [1947])')•
R(k, k)>k2kl2[-±T-o(l)].
Зафиксируем k и /. Пусть п— целое, a D = (Ki, К2) —
случайное 2-расцвечивание графа [п]2> такое, что Ki = GrtiP,
где 0<р<1. Если Ле=[я]\ то Р [[A]2 s Ki] = pw. В силу
того что К2 имеет распределение Gn,\-P (Кг~Ол. i-р)» то
Р [[A]2 s К2] = (1 — РГ2' при Л е= [л]'. Положим р (D) равным
числу тех ^-множеств, чьи ребра все суть „1", плюс число
') См. также Спенсер [1975], где описывается некоторое улучшение
теоремы 5.1 и обобщение вероятностного метода, сделанное Л. Ловачём.
5. Теорема Рамсея
25
тех /-множеств, чьи ребра все суть „2". Тогда
E[p(D)]=(;)/*)+(;)(i-/>)(*). (5.5>
Если E[P(D)] < 1, то найдется такое расцвечивание D, для
которого p(D)=0, т. е. п </?(&, /). Следствием последнего
неравенства является
Теорема 5.2. Если существует р, O^p^l, для которого
(;)p(J)+(")o-p>(!)<i.
то м</?(£, /).
Если fe = 3, то, согласно (5.2), имеем
/?(3, /)<(/ + 1)-/2/2.
Теорема 5.3 (Эрдёш [1961]).
Я(3, D>cll2/(\ogl)2.
Доказательство. В силу монотонности R достаточно
показать, что _
R (3, с2 У л log п) > п. (5.6)
Рассмотрим расцвечивание D2( [я]2) = (/Ci, /С2) как граф
G = /Ct. Нам надо найти такой граф G на [я], который бы не
содержал как ни одного треугольника,_так и ни одного
независимого множества объема х = [с2 У я log /г]. Во-первых, мы
ослабим это условие. Если Z е [я]*, то будем писать а (X, G),
если 3i, /gI, {/,/}eG, так что k ф X влечет {i,k}&G
или {у, £}^G. Очевидно, а(Х, G) обозначает наличие ребра
в [A"]2flG, не являющегося стороной никакого треугольника,
одна из вершин которого не лежит в X.
Лемма 5.1. Если для любого X е [п]х выполняется а (X, G),
то найдется подграф Я ^ G, не содержащий как ни одного
треугольника, так и ни одного независимого множества на х
вершинах.
Доказательство. Пусть G = {e{, ..., es) и Яо=0. Для
1</<s положим #i = #r-i и{еЛ> если #i-tU{£i} не
содержит треугольников; в противном случае Hi = Hi-l.
Обозначим граф Hs через Я. По построению граф Я не содержит
треугольников и в то же время Я s G. Пусть сейчас X е [я]*.
Поскольку а(Х, G), мы находим ребро ^ = {/,/}gO, не
являющееся стороной треугольника, выходящего за X. Если
et ф Я, то Я/-! U {£*} содержит треугольник и, значит, для
некоторого k выполняются включения: {/, k), {/, k) е Ht-{ ^ G.
26
5. Теорема Рамсея
Таким образом, если а(Х, G), то е необходимостью
существует k^X, для которого {/, k] е Я Л [X]2 и, стало быть, X не
является независимым множеством. ■
Для доказательства теоремы 5.3 нам осталось убедиться
в справедливости следующей леммы.
Лемма 5.2. Пусть G = G„tP, где р = 2с2Чгп~Х1\ Тогда для
достаточно большого с2 имеет место неравенство
Р[а(Х, G) VX<=[n]x]>0.
Доказательство. Зафиксируем некоторое X е [п]х. Нам
достаточно показать, что
Р[нео№С)1<(;)"'. (5.7)
Положим
Hi=t У*к/ щ Х: {i'/} е G}]2' "2=G'х- (5*8)
Тогда (5.7) эквивалентно неравенству
P[H2sH,]<(^)"!. (5.9)
По теореме Адама1)
P[H2sHi] = P[h2=H,||HJ<4-(0]P[|HiI<KO] +
+ p[h2sh1||h,i>1(J)]p[|hii>1(J)]<
<p[H, = H,||HI|<l(J)] + P[|H1|>i(J)]. (5.10)
Мы докажем (5.9), оценивая слагаемые в (5.10). Согласно
теореме Адама,
P[H2sHI||HI|<l(J)]<maxP[H2sH1|H1 = tf1]<
<тахР[Н2ЕЯ!]<
') Теорема Адама утверждает, что если события В и 1^/</, —
несовместимые и взаимно дополняющие, то
Р(Л)=£Р(Л|д,)Р(в,).
Как следствие этого находим
Р(Л)<тахР(Л|В<).
i
Этот результат называют теоремой Адама, потому что он многократно
переоткрывался.
5. Теорема Рамсея
27
(поскольку Hj и Н2 независимы по определению)
<тах(1-р)й)-|//'1<(1-р)Кт)<^«)-1 (5.11>
(здесь максимум берется по всем Нх ^ [л;]2, | Нх |<у ( 1)) •
Из (5.8) следует, что
iH'i< E(Y2')' <5л2>
где
Yf=lOeI: {/,/}eG}|. (5.13)
Случайные величины Yt независимы и имеют биномиальное
распределение В (х, р). Мы воспользуемся чисто
вероятностным результатом.
Лемма 5.3.
Доказательство (набросок). Очевидно, Е(^) = л:р~
~2c2Mogrt, т. е. с точностью до множителя с2 сумма
Y^Y? должна вести себя как (1/2) /z (2с2* log/z)2 < (1/4) х2,
»2 У Y? имеет нецентральное ^-распределение. Положим
z. = 2{с\* (log /г), 0 ^ i ^ log2 /г, и определим w. следующим
образом:
\nVl(i+l)-\ 0^i^±\og2n,
т = \ . . , (5.14)
| /г4 i , -j log2 /г < / < log2 /г.
Тогда
£Р[><»« из Y/>^]<1(;)"!. (5.15)
Если для всех / меньше чем w{ из Y/ > ziy то
E(v2')<Z-(2r)<T(0- <516'
i i
Мы возвращаемся к доказательству леммы 5.2.
Комбинируя лемму 5.3 и (5.12), находим
р[|".|<т(.*)]<тО)"'- (517)
28
5. Теорема Рамсе я
Формулы (5.10), (5.11) и (5.17) приводят к (5.9), что и
доказывает лемму 5.2. Щ
Следующий результат даст некоторое усиление верхней
оценки (5.2).
Теорема 5.4 (Гравер и Якель [1968]).
R (3, у) < с3у2 log log у/log у.
Доказательство. Будет более удобно показать, что
R (3, у + 1) < с4у2 log log у/log у.
Пусть п = R (3, у + 1) — 1. Пусть G — граф на [/г], не
содержащий ни треугольников, ни независимых множеств объема
у+1. Для исключения треугольника все точки, смежные
с данной, должны быть независимы. Следовательно, каждая
вершина имеет степень ^у. Зафиксируем независимое
множество А е [п]у. Мы знаем, что такое множество существует,
потому что мы не можем добавить изолированной вершины
к G. Для O^t^y положим
А,, = {Ь е= [п] -' А: |{ае=Л: (а, b) e=G} | = /},
pi = \Ai\y el = \G\Ai\.
Таким образом,
/?(3, y+l)=n+l = l+y+tpi. (5.18)
/-о
Поскольку A U А0 — независимое множество, то Ло=0, Ро =
= е0 = 0. Предположим теперь, что | А{ | > | А | (рис. 1).
Согласно принципу Дирихле, найдутся ft, с<=:Аь {a, b}> {а, c}gG.
Множество А —{а}-\-{Ь> с} является независимым сг/+1
элементами —получили противоречие. Значит, Р\=\ А{\^.у.
Тогда формула (5.18) приводит к
/?(3, y+l)<l+2y+£Pi. (5.19)
«-2
Оценим теперь \,Gf] {АУ^АС) | двумя способами. Поскольку
каждое а^А имеет степень ^t/, то
£ipi=£ t. i= Е \{а*=А: {a,b}e=G}\ =
= |ОПМХД')'1И'21-|{*еЛс:{а,6}еО}|<^. (5.20)
5. Теооема Рамсея
29
В частности, это влечет
tpi<y2/h. (5.21)
Полагая Л = 2, находим
/?(3, t/+l)<l+2t/ + t/2/2. (5.22)
Для усиления (5.22) оценим pt при малом />2.
Лемма 5.4. Для 2^/^у справедлива оценка p/^2t/2_1//.
Доказательство. Мы хотим так „трансформировать"
вершины множества Л, чтобы получилось столь же большое
V/.6V
•А,
vX:>::::::>Xv.a
Рис. L [Mi|>M|]
независимое множество, как и при i=\. Для каждого Ь еЛ/
положим Sb = {a^A: {a, b) е G}, так что |S6| = /. Пусть
А — случайное подмножество множества Л, в котором все
aG^ имеют независимые вероятности Р [а е А] = #"ш.
Положим Х(А) = {6^Л,-: S^sA}. Тогда имеем
Е[\\\] = у{-41,
Е[\Х(\)\]=Р1[У^У = Р1у-{. (5'23)
Поскольку ребра могут наличествовать в Х(А), множество
А — \ + Х(А) не обязательно независимое (рис. 2). Если
{Ьу c}^G\X (А), то Sb(J Sc s Л. А поскольку G не содержит
треугольников, то Sb[)Sc= 0 и, таким образом,
Р [Sb U Sc <= А] = (г/-1^)2' = У'2- (5.24)
Следовательно,
E[|GU(A)|] = ^-2. (5.25)
30
5. Теорема Рамсе я
А так как каждая вершина из А{ имеет степень ^уу та
ei^-gPif/ и, следовательно, (5.25) приводит к
E[|G|*(A) !]<-£-pdr«
(5.26)
Весьма просто показать, что я-вершинный граф, имеющий
е ребер, обладает независимым множеством на я — е
вершинах. Значит, существует независимое множество К (A) s X(K)f
•улАо
..;:&«Г::*ДШ!^^^^
Рыс. 2. [/ = 2]
| У(А) |>| *(А) | — | G |*(А) |. Тогда множество Л-А + Г(А)-
тоже независимое и
Е[|Л-А + Г(А)|]>
>|Д|-Е[|А|] + Е[|*(А)|]-Е[|С|*(А)|]>
>у-у1-|/| + 4-лу"1- (5-27)
Если (1/2) р(у~1 > */1~ш, то существует такое значение Л*
случайной величины А, что | Л — Л* + К (Л*) | > у, а это
недопустимо. Значит, р^ <С2#2~Ш, что завершает
доказательство леммы 5.4. ■
Из леммы 5.4, (5.19) и (5.21) следует
(5.28)
Полагая h = log *//log log у, получаем утверждение
теоремы 5.4. ■
5. Теорема Рамсея
31
Следствие 5.1 (Якель [1972]). Для 3<*<*/
Мы опускаем трудное, хотя и элементарное, доказательство
этого следствия, основывающееся лишь на использовании
теоремы 5.4 и соотношения (5.1).
Упражнения
1. Комбинирование (5.2) и теоремы 5.1 приводит к
V2"<lim/?(£, k)llk ^Ш R (kt £)1/fe<4.
(a) Доказать или опровергнуть, что lim R (k, k)l/k
существует. ($25)
(b) Найти lim/? (k, k)uk, если таковой существует. ($25)
k
2. Пусть k^3 фиксировано и /z->oo. Доказать
существование /г-вершинного графа G, не содержащего fe-клики и
независимого множества на [Ckn2/{k~l) log/г] вершинах.
Показать, что это влечет неравенство
R(k, n)>C'k[nl\oenf-m.
3. (?) Пусть е > 0, k > 3. Доказать или опровергнуть,
что для достаточно большого п
R(k, n)>nk~x-\
4. (Трудн.). Положим G'=G„,p-{{/, /}: 3k {i9 /, *}2sC„iP}f
где р = 2с2~Ч2пГ',\ Иными словами, G' —это граф Gmp без
треугольников. Показать, что для достаточно большого с2
при х = [_с2 л/п log /г] справедливо неравенство
P[G' содержит л: независимых вершин] < 1.
5. Пусть с — расцвечивание [/г]2. Мы рассматриваем с как
отображение множества упорядоченных пар (х, */), х<у на
множество цветов. Будем называть с каноническим на А ^ [я],
если хотя бы одно из следующих условий выполняется для xh
Vi е Л:
(a) с{хи х2) = с(уи у2) ¥>Х[=у{ и х2 = у2,
(b) с (xlf *г) = с (ylf */2) 4Ф X! = г/!,
(c) с (*!, *2) = с (у19 у2) #% *2 = #2,
(d) с(а:1э *2) = c(#i, #2).
32
5. Теорема Рамсея
Обозначим через
*->(*)2 (•)
то утверждение, что всякое расцвечивание (с любым числом
цветов) множества [п]2 является каноническим для
некоторого А е [n]k. Эрдёш и Радо [1956] показали, что для всех k
существует такое /г, что (*) имеет место. Доказать (Ф. Галь-
вин, частное сообщение), что если
то (*) не имеет места. (Указание: рассмотреть IГ J — 11-
расцвечивание [/г]2.}
в. ТЕОРЕМА ВАН ДЕР ВАРДЕНА
Теорема ван дер Вардена [1925]. Для всякого
натурального t существует такое наименьшее целое m = tn (t), что при
любом 2'раскрашиванйи множества {1,2. ..., ш} в этом
множестве найдется монохроматическая арифметическая
прогрессия длины t.
Доказательство этой теоремы основывается на
мажорировании m(t) функцией mx (t), которая возрастает крайне
быстро. Безосновательно искать верхние оценки для m(t)*
Мы будем: заниматься исключительно нижними оценками.
Положим А (а, б, t) = {а, а + б, ... , а + (t— 1)6}; для
фиксированных т и t множество 3f = {А (а, б, /): б > О,
I ^а < а +(/—1)6^т) есть множество всех
арифметических прогрессий длины ty содержащихся в [fa]. Тогда
\&\^m*J2t (см. упр. 2А), и 2/ есть /-граф. Если n^m(t)>
то 3f не обладает свойством В. Таким образом, согласна
теореме 4.2, справедлива
Теорема 6.1 (Эрдёш, Радо [1952]).
« ... - . . - ■ .
m(0>V2ffi7(l-"o(l)).
. Этот результат был улучшен Шмидтом [1962]. Пусть
т и t фиксированы; положим u = [£tl\6gt)l**]9 й пусть
С = (Ки К2)-— раскрашивание множества {1, ..., т). Мы
попытаемся посредством С слегка разрушить
монохроматические арифметические прогрессии. Если Р — прогрессия
длины tt а /=Г или 2, мы называем Р „близкой /", если
\'P'flKi\>t-r'u. Из каждой „близкой Iй прогрессии Р
выберем, произвольным образом элемент х(Р) ^р(]К>. Положим
C*=(/C,AiV, *2AJV), где
N = {х (Р): Р „близка Iй для / = 1 или 2}.
Цели С* содержит монохроматическую арифметическую
прогрессии Q (скажем, цвета /), то Q не может быть „близка **
относительно раскрашивания С, поскольку в противном случае
34
6. Теорршщн дер: Барде на ' t, ■•<
нашлись бы такие /== 1 или 2, г(/^г^и+1)и прогрессии
Ри •••> Л, Q = {?i> ?2> ..., <7*}> что
1. Каждая Ру „близка /".
2. g^PfiMd для 1</<г.
3. qj<£Ki для г</</.
При помощи лемм о комплексных рядах Шмидт показал,
что для
m<2*-c(*log*)V*
случайное раскрашивание С не обладало бы этим свойством
и поэтому С* не содержало бы монохроматических
арифметических прогрессий длины t. Следствием этого является
Теорема 6.2 (Шмидт [1962]).
m(0>2^(Mog^
Однако этот параграф нужно рассматривать как победу
конструктивистов.
Теорема 6.3 (Берлекэмп [1968]). Если t — простое, то
Доказательство Берлекэмпа полностью конструктивно и
основано на использовании поля Галуа GF(2f). Поскольку
неизвестно, всегда ли существует простое р, t — yt < p<t,
мы не можем утверждать, что результат Берлекэмпа является
усилением результата Шмидта для всех достаточно больших ^
Упражнения
1. Пусть W (k> t) обозначает то наименьшее т, для
которого всякое ^-раскрашивание множества {1, ..., пг) содержит
монохроматическую арифметическую прогрессию длины /.
Доказать, что
W(k, 0>(2/*'"1)1/"(1-о(1)).
(Замечание. Мозером [1960] при помощи конструктивных
методов показано, что W {k, t) >tkclogk. Для фиксированного t
и й->оо это улучшает упр. 1.)
2А. Показать, что
7. КВАЗИРАМСЕЕВСКИЕ ТЕОРЕМЫ
Теорема Рамсея заключается в нахождении большого
монохроматического подграфа в расцвеченном полном графе Кп.
В этом параграфе мы рассмотрим ее для преимущественно
одноцветных подграфов.
Обозначим 2-расцвечивание графа Кп через Л. Будет
удобно понимать h как функцию, определенную на
множестве [/г]2, со значениями в множестве {+1, —1}. Мы
индуцируем функцию, также обозначаемую через Л,
определяемую на подмножествах множества [/г], следующим образом:
h(S)= I h(A). (7.1)
Ae=[S\2
Тогда | h (S) | является мерой пестроты расцвечивания Л.
Положим
g (п, t) = min max | h (S) |. (7.2)
h Ss=[n]
\S\<t
Теорема 7.1. Пусть n^t достаточно велико) тогда
если t<-^;, то *(п, *) = (£); (7.3)
. ^ log п
еСШ '>2П*Г-' Т°
10-Y/2Vk)g(5/i/0<g(/i, 0<'3/2Ylog(5/i/0. (7.4)
Доказательство. Если t <! 2°Я "2 , то, согласно (5.2),
выполняется /? (*, 0 < ( ~ j )<«и, стало быть, g (if 0 = ( 2 ) '■
Зафиксируем * > °gn , и пусть h —случайное
расцвечивание. Если |S| = 5</, то, согласно (3.1), /*(S)~S/*y
Таким образом,
P[h (S) > а] < е~а'12(*) < *-«'/<Y (7.5)
и поэтому
Р [3S, | S|<U h (S) > а] < n*e-«t* < 1. (7.6)
36
7. Квазирамсеевские теоремы
Для
a = /3/2Vlog(5n//); (7.7)
следовательно,
g(n9 0<'3/2Ylog(5fl/0. (7.8)
Введем функцию, также обозначаемую через А,
определенную на парах непересекающихся подмножеств множества [п],
а именно
h(ST)= Z А ({*,*/}). (7.9)
xesS
Мы сейчас доказываем нижнюю оценку в (7.4).
Предположим, что t^.n/2 и п = / = 0(2). Во-первых, найдем
такие непересекающиеся множества Jf и В, что |A"(J£l^f
и h(XB) велико.
Разобьем множество [п] на два равновеликих
подмножества: [п] = А1 + Л2, | А! | = | А21 = /г/2. Пусть В ^ Л2
определяется следующим образом: для всякого у е Л2
Р[уЕ=В] = р = //4Аг. (7.10)
Зафиксируем л: е Л2; тогда
Л (хВ) ~ В (пХ9 р) - В (-- - л„ р) , (7.11)
где /1х==| {*/еЛ2: A({x, у})=1}\. Положим a=10~V/2<\/log(5n/t).
Согласно элементарным вероятностным вычислениям,
P[|A(xB)|>a] >t/n. (7.12)
Положим
Х(Ъ) = {хе=А1: | Л(л:В) | > а>. (7.13)
Тогда
E[|Z(B)|] = £ P[IA(*B)|>a]>//2. (7.14)
А так как |Х (В) К/г/2, то
Р[|*(В)|>//4]>*/2л. (7.15)
Простые вычисления приводят к
Р[|В|<//2]>1-1/п. (7.16)
Комбинируя (7.15) и (7.16), получаем существование
требуемого В s Л2, |В|<*/2, |Л(В)Г>*/4. Таким образом, либо
|{*е=Л,: А(*В) >а}|>//8,
либо
<' . |{jcs4 А(хВ)< —а}|>//8. .
7. Квазирамсеевские теоремы
37
Исходя из симметрии (между А и —А), предположим
выполнимость первого из этих неравенств. Зафиксируем множество
Х^{х^А{: h(xB)>a), U| = [//8].
Тогда
Л (ХВ) = Z А (*В) >\Х\а> 1(ГУЛ Vlog (5л//), (7.17)
Выразим пестроту h(XB) из (7.17) через A (S).
Заметим, что
Л (*) + А (В) + Л (ХВ) = А (X U В); (7.18)
следовательно,
g (л, 0 > A (S) = Ai|*L> (ЗОО)"1 /3/2 Vlog (5л/0, (7.19)
где S —одно из множеств X, В, Х[}В.
Мы предполагали, что t^.n/2. Для t > п/2 имеем
Я (л, 0 > «Г (л, л/2) > 1(Г3 ^Vlog(5n/«). ■ (7.20)
Следствие 7.1. Я*/сгб g (/г) = min max | A (S) |. Тогда
h Ssfn]
a\nVt^g{n) <a2n3\
■где ab a2 — положительные абсолютные константы.
Следствие 7:2. Пусть 1 ^ е > 0 и
g(n, 8) = mmmax||S|: Ss[n], |A(S) |>e('2')}.
Тогда для п> п(г)
b{e~2 log п *Ц g (п, е) < 62е-2 log /г,
.где &i, Ь2 — положительные абсолютные константы.
Теорему 7.1 можно обобщить на £-графы. Пусть k
фиксировано и n>n{k). Пусть h — hk есть некоторое 2-расцвечи-
вание полного й-графа на [п], т. е. A: [я]*->{+ 1, — 1}. Мы
индуцируем функцию, также обозначаемую через А,
определяемую на подмножествах множества [п] следующим образом:
A(S)= £ AM). (7.21)
Если теперь определить gk (п, t) как
8k ("> 0 = min max | A (S) 1, (7.22)
h Ss[n]
то имеет место
38
7. Квазирамсеевские теоремы
Теорема 7.2. Если /< (logn)mk~l), то
c«(ft)<ft(rt»')<Q); (7.23>
ес/ш n>/>(logn)1/(fe"0, го
cjk+m Vlog(6/i//)<fo(/if 0 <<W(*+M Vbg (Б/|Д). (7.24>
Верхняя оценка в (7.23) тривиальна. Нижняя оценка:
в (7.23) составляет содержание теоремы 12.3.
Доказательство (7.24) представлено упражнениями 1 и 2.
Упражнения
1. Доказать верхнюю оценку в (7.24).
2. (Трудное.) Ознакомиться с доказательством (Эрдёш иг
Спенсер [1972]) нижней оценки в (7.24) для t = n. Доказать
нижнюю оценку в (7.24) для всех t.
3. Пусть \Ах\ = \А2\ = п9 A{f]A2=0t
f (п) = min max | h (В{В2) |.
Доказать неравенство
л3''
*!*'/■>/ (Л) > -^(1-0(1))*
2 у Я
8. МОДИФИКАЦИЯ ТЕОРЕМЫ ВАН ДЁР ВАРДЕНА
Мы представляем 2-раскрашивание множества [п] как
«функцию Л: [я]->{+!> —1}. Так же как ив предыдущем
параграфе, рассмотрим преимущественно одноцветные
арифметические прогрессии. Более точно, положим
<? (п) = min max
h a, d, т\
£ h (а + ud)
ы-0
(0<a<a + dm<rt). (8.1)
Рот [1964] показал, что для достаточно большого п имеет
вместо оценка G (п) > я,/4. Для данного h он ввел
S(a) = Sft(/)^/a, 1 = л/~1, (8.2)
:и воспользовался теорией комплексного переменного. Мы
найдем некоторую верхнюю оценку для G{n). Воспользуемся
вероятностными методами для первоначального получения
трубой оценки, а затем улучшим ее.
Пусть h —случайное раскрашивание; тогда
т
£h(a + rd)~Sm+1., (8.3)
Таким образом,
Р Г S h (a + ud) \> al < e-W <m+I>. (8.4)
LIм=о I J
Так как m + 1 ^ /z, то эта вероятность < /z~3 для a = с -уп log /г,
а поскольку имеется < /г3 различных „троек" a, d, m, то
Р
л, следовательно,
Г max f) h (а + ud) > а I < 1 (8.5)
La, d. т |«=0 I J
G (л)< с V« log «. (8.6)
40 ? ■■ -4 -г А- Модификация теоремы ван дер Вардена
Как можно улучшить этот результат? Суммы 2J h (а + ud)
сильно зависимы. Действительно,
Р[э/,/jih(a + «rf)|>a]<
<р[э/\£h(a + itd) >a/2l<
. r I l(n~a)/d] l-i
2P[| -Z h(a + ud)l>a/2y
<
<2e~da*/s{n+d\ (8.7)-
Первое неравенство элементарно. Второе обусловлено
неравенством А. Н, Колмогорова ]). Третье неравенство осно-
вано на (3.2) и на том, что 1 + [(п — a)/d] < (п'+ d)/d.
Поскольку для каждого d имеется d возможных значений аг
l^a^d, то при a= 10Vn посредством простых
вычислений находим
[\ m 1 "I п
3a, rf, m 5} h(a+'ud) \>а \< £ г*-**1*<»+*> < 1. (8.8>
|л«=0 I J d«l
Таким образом, G(n)< 10V^.
Имеется и дальнейшее усиление (Спенсер [1971b]).
Последовательности, наиболее близкие имеющим высокую-
пестроту, имеют малое d. Предположим, что A (2t — 1) =
= — Л (2/) для 1*0'^[/г/2]. Тогда все последовательности
с d= 1 должны иметь пестроту 0, +1, — 1. Некоторые
вычисления приводят к надлежащему обобщению. Положим
k — [(logn)/4], N = gcd(l, ..., k). Согласно теореме о
простых числах, N~ek < п\ (В действительности мы могли бы
с тем же успехом положить N = k\.) Пусть
ЛГ={А:0</< N влечет Л((2/+ 1) N + ]) =
= -h(2iN + j)}. (8.9>
Иначе говоря, множество [п] разбивается на блоки по 2ЛГ
в каждом, причем первая и вторая половины блока
противоположны по знаку.
*) Общий результат таков:
P[Sm^? a]>—-P[Sj>a для некоторого 1</<т].
Это можно показать, положив wt = „S. < a, 1 </ < /, S^ ^a" и замечая*
что wi разлагают правую часть выражения и что
P[Sm>a|wil«PISm>o|S|>a]>Y.
8. Модификация теоремы ван дер Вардена 4\
Пусть h — случайный элемент Ж. Если d \ N, то для
всякого АеЛГ
' m 1
Z h (а + ud) < 2N/d < 2п\ (8.10)
|ll-0 I
Бели d не делит N и l^a^rf, то последовательность
а, а + d, ... не содержит двух элементов, отличающихся
на N. Следовательно, h — случайное раскрашивание этой
последовательности и
Р Гзу Е h (а + ud) \> а] < 2e"d^ <»+*>, (8.11)
L \w-i I J
как и ранее. Полагая a= 100 ^Jn Vlogbgn/Vlogft, находим
[| m I 1
3a, d, m E h (a + ud) > a < £ fe-^Oi+rf) < 1.
I a-0 I J d > k
(8.12)
Из этого следует
Теорема 8.1. Аг^<0(л)< 100д/я Vloglog Аг/л/log /г.
Имелась гипотеза, что G (я) > я7*-8 для любого а > 0 и
достаточно большого /г.
Эта гипотеза недавно была опровергнута следующим
замечанием Шаркози1). Пусть р — большое простое число.
Пусть Zp обозначает кольцо целых по модулю р. Можно
найти такое A: Zp->{—1, -fl}> что
(a) £ h(i)=o,
i Ф О
(b) I 2 Л (01 < £ Vp У log p, где Л — некоторая арифме-
тическая прогрессия в Zp.
Такое А может быть построено неконструктивными
средствами. Можно положить А (0) произвольным, а А (/) ==? ("-*) ~
•символ Лежандра для / Ф 0. Тогда, согласно результату
аналитической теории чисел, (Ь) имеет место с заменой
л/рл/logp на VР 1°ё Р-
Предположим теперь, что п = [р3/« лЛ°£ р]. Определим
Л*: [л]->{-1, +1} как A*(/ + tfp) = А (/), 0</<р,
/С-- целое. Можно показать, что наибольшая пестрота равна
Vp У l°g Р- Таким образом, Я (п)^.<у/р У log р=0 ((/г log п)ч*)>
1) Результаты, которые излагаются ниже, были получены, когда книга
*уже печаталась., ■• ■ • -
9. ТУРНИРЫ
Турниры были определены в § 2. Мы уже доказали
в § 1 две теоремы о турнирах. Монография Муна [1968f
содержит эти и многие другие результаты о турнирах.
Говорят, что турнир обладает свойством S(k), если для
всякого множества А из k его игроков найдется
какой-нибудь другой игрок, победивший всех х^А. Отмечается
трудность определения k ведущих игроков такого турнира.
Положим s\k) равным наименьшему числу игроков в турнире
со свойством S{k). Шютте поставил задачу о
вычислении s(k)y если таковое существует. Конструктивными
методами Е. и Г. Секереш [1965] показали, что s{k) ^2k(k + 1) — U
Теорема 9.1 (Эрдёш [1963]).
s(k)^2kk2(log2 + o(l)).
Доказательство. Пусть Т = Тл — случайный турнир. Если.
А е [n]k фиксировано, то для каждого у ф. А
Р[Ва-е=Л, (у, а)фТ] = \-2-\ (9.1>
причем эти вероятности независимы для у ф. А; таким
образом,
1 Pity фА За ее А, (у, а) ф Т] = (l - 2-*)""*, (9.2),
Следовательно, при rt = 2*^2(log2 +о(1))
Р[не S(k)]^P[3A€=[n]kVy<£A3a<=A, (у, а)£Т]<
.<(j)(l-2-*r*<l. (9.3>
Стало быть, для этого п
Р [Т обладает свойством S (k)\ > О, (9.4)'
и, следовательно, s(k)^n. Щ
Для всякого турнира Т = Тп естественна попытка
ранжировать (упорядочить) его игроков. Всякое ранжирование
определяется перестановкой а на {1, 2, ..., п). (Здесь а (х)
и есть ранг игрока х.) Это ранжирование индуцирует
транзитивный турнир Р = Ра на {1, 2, ...tn) по правилу::
9. Турниры
43
\х, у)^Р тогда и только тогда, когда о (х) <о(у).
Показателем качества ранжирования служит число \Р(]Т\. Для
данного Т хотелось бы найти турнир Р, максимизирующий
iP(]T |. Положим
f (n) = minmax|Pn7,|. (9.5)
т р
Это определение предложено Эрдёшом и Муном [1965]*
Они назвали Р[\Т совместимым множеством дуг. Для
всякого Т и любого Р
|РПЛ + |РСПЛ = (^)
<(РС есть тот же Р, но с обращенными дугами), так что
jw>t(;)-
Теорема 9.2 (Спенсер [1971а])
l(^) + Cln%</(n)<l(^)+(-^ + o(l))n^Vbg^,
•где с{ — абсолютная положительная константа.
Доказательство. Обе оценки докажем вероятностными
методами. Для получения верхней оценки будем считать,
-что Т==ТП есть случайный турнир. Для фиксированного Р
|TnP|~U/„4~-iS/„4+4-(;), (9.6)
где U и S определены в (3.1) и (3.2). Тогда, согласно (3.9),
P[|TnP|>}(;)+a] = P[S(.„4>2«]<e-^"M (9.7>
И, таким образом, для а = уя3/2 У log п
Р[ЗР, |TnP|>Y(J) + a]<nte-w»i<l. (9.8)
Мы улучшим эту оценку, воспользовавшись сильной
зависимостью Tf|Pi и TflP2, когда Р{ и Р2 „близки"* Для
удобства предположим, что /z = m2. Положим
£> = {Р = Ра: a(im+\)<a(im + 2)< ... <a(im + m)
для 0</<т — 1}. (9.9)
Тогда
|*| = ^г <«*<■**>>, ■ (9.ю)
44
9. Турниры
и, таким образом, для ^ = {^л—Ь o(l)J/z3/2 Ylog п
Р[ЭРе=^, |ТПР|>у(2) + а]<^(1+°(1))^а^< 1. (9.11)
Теперь зафиксируем Т\ тогда \ТПРКу^)^-** для всех
Р^&*. Пусть or — некоторая перестановка. Определим о' так>
что для 1 ^ / ^ m
{a (im + 1), .. •, о (im + m)} = {a" (wi +1), ..., a' (im + m)\
и
/o'(im + 1)< ... <o'(im + m).
Тогда Po>s=& и
Таким образом, для всех а
|ГПРа|<|ГПРо'1 + |РаАРаЧ<
<а + /z3/'/2 <(^ + о(1))^ Vlog^. (9.12)
Нижняя оценка следует из нашей квазирамсеевской
теоремы. Зафиксируем Т = Тп и определим А: [п]2—>{ + 1, — 1}
следующим образом:
({*,#}) = { *
+ 1, если (х,у)<=Т и дс<у,
1 в противном случае.
Согласно следствию 7.1 найдется множество Bs[n], для:
которого | h (В) | > ^я3'2. Положим В* = [/г] — В. Если Л (В) >
^-слпг,\' то ра«г В будет меньше. Если Л (В) ^ — С\Пг,\ то
ранг В будет больше. Если Л(Вс)^0, то ранг Вс будет
меньше, в противном случае —- больше. Если h(BX,tf)>Or
то ранг В<ВСу в противном случае ранг Вс < В. Вводя <т>
окончательно оцениваем ранжирование:
I ГП Ра 1>|(2)+ ^Ч
Уменьшение промежутка между оценками теоремы 9.2
представляется нам весьма трудной задачей. Неизвестен
даже ответ задачи, приведенной в упр. 3.
В турнире Т £:циклом называется множество дуг
следующей формы: {(*,, х2), (х2, х3), ..., (a:*-!, xk), (xkj хх)}^Г
(здесь хи ..., л^ — различные вершины). Пусть Ck(T)
обозначает число ^-циклов в турнире 7\ пусть Ck(n) = тахС(Гл).
9. Турниры
45
Теорема 1.2 дает оценку для Сп (я). Рассмотрим случай
фиксированного k при /г->оо.
Теорема 9.3. Для фиксированного ky /г^/г, функция
С* (л)/( nk) является монотонно убывающей по п.
Доказательство. Зафиксируем п < т. Пусть турнир .Гт
таков, что Ck(Tm) = Ck(m). Пусть А —случайный член
множества [т]п. Тогда
Е1С»(ГЖ|А)]=£РК*„ .... *»} = А] =
(здесь суммирование ведется по всем й-циклам {(л^, х2), ...
..., (xkt хх))^Тт.) Следовательно, найдется такое А^[т]п,
для которого
С*(«)>С»(ГЖ| А) >Я[С»(Гж|А)1 = С*(т) (;)/(*). в
(9.14)
Теорема 9.4.
С* (я) — ( J ) (Л — 1)! 2-*.
Мы предлагаем доказательство этой теоремы в качестве
пятого упражнения. Из теорем 9.3 и 9.4 следует, что
предел
ак = ПтСк(п)п~к (9.15)
П->оо
существует.
Для fe = 3 многими авторами (см. Мун [1968]) было
показано, что
-jj- (я3 — п), если п нечетно,
1 , (9.16)
-^•{п3 — 4п), если /г четно.
Для k = 4 Коломб [1964], Байнеке и Харари [1965] (см,
Мун [1968]) показали, что
"7£"я(л+ 1) {п— 1) (л — 3), если я нечетно,
c4(/i)H 1 (9-17>
— п (п + 2) (/г — 2) (/г — 3), если /г четно.
С3(/г) =
48
48
1$
Таким образом, а4 = ^"« Вероятностный метод и теорема 9.4
дают лишь оценку сц^-^. Поведение а* при k ^5 остается
открытой задачей.
46
Р. Турниры.
Упражнения
1. Турнир T = TV транзитивен тогда и только тогда, когда
существует такая перестановка его игроков а, для которой
I Т(]Р0 | = Г ^ ) • Для 1/2<р^1 назовем Т р-транзитивным,
если существует в, при котором
\тпра\>р(°2).
Положим v = vp(n) равным тому наибольшему целому, для
которого всякий Тп содержит р-транзитивный подтурнир Tv.
Для фиксированного р найти оценки для vp(n) при /z->oo.
2. Скажем, что Т обладает свойством S*(k), если для
всякого множества Л из k его игроков и любого В^А
найдется х ф Л, такой, что х побеждает всех Ь е= В и побеждаем
всеми аЕ Л — В. Положить 5*(£) равным наименьшему числу
игроков в турнире со свойством S* (k) и показать, что
s*(k)<:2kk2(loe2 + o(l))t
3. (?) Пусть h{T)=max\T(]Pa\. Верно ли, что
а
1[т[Е(Л(Т„))-|(;)]^=оо?
4. Пусть F —семейство турниров с k игроками. Пусть
С (Ту F) — число подтурниров турнира Г, принадлежащих
этому семейству F; С(п, F) = тах С (Tnt F). Доказать, что
т
л п
величина С (п, ^)/(£) монотонно убывает по п.
5. Доказать теорему 9.4. (Указание. Найти Е[С*(Тл)].)
10. РЕГУЛЯРНЫЕ ТУРНИРЫ
Определим частичный порядок Р как множество
упорядоченных пар {х9 у), хфу, таких, что (х, у), (у, г)<=Р
влечет (х, z)^P. Заметим, что подмножество частичного
порядка не обязано быть частичным порядком. Если А и В
не пересекаются, то все подмножества множества ДХ#
являются частичным порядком. Энтринджер, Эрдёш и Харнер
искали то наибольшее целое q = q(n), такое, что каждый
турнир Т=Тп обладает некоторым частичным порядком
Р^Т с \P\^q. В этом параграфе будет доказана
Теорема ЛОЛ. -£ + (1 - о (1)) log2 п < q (п) <-£ +
+ c{\og2n.
Доказательство будет беглым. Для детального
ознакомления см. Спенсер [1972b]. Предположим, что /z = 2m+l;
случай четного п аналогичен. Доказательство нижней оценки
вынесено в упр. 1.
Если Т = Тп есть турнир, а /е[п], то положим Wt =
= {/: (/,/)еГ}, Li = {j\ (/,/)£?} и назовем s^lWJ
баллом (очком) игрока I. Упорядоченная /г-выборка (sb ..., sn)
называется балловой последовательностью турнира Т. Если
все Si=m9 то турнир Г называется регулярным. Обозначим
через 31 класс всех регулярных турниров на [п].
Определим Тг как случайный член из Ж,
Мы хотим получить навык в обращении со свойствами Тг.
Например, мы знаем, что Р[(1, 2), (2, 3), (3, 1)gT]=1/8.
Какова будет эта вероятность, если Т заменить на Тг?
Интуитивно мы ощущаем, что эта вероятность должна быть
больше 1/8, но очень ненамного. Отправной точкой будет
служить
Теорема 10.2. Пусть f {sl9 ..., sn) обозначает число
турниров с балловой последовательностью {su ..,, sn). Если,
I st — m | < /z3/s, 1 < / < /г, то
f{su ..., sn) =
= f(S[ + \} s2-l,..., 5j(l + 51 ? + 1 (4 + o(l))).
48
10. Регулярные турниры
Доказательство (Спенсер [1972]) весьма запутанное и
здесь не приводится. Поскольку / — симметрическая
функция, то равенство остается в силе, если 5/ и Sj заменить
на st+l и 5/—1. Условие \si — m\<ni,i можно ослабить,
но это не отразится на наших результатах. Если V st = ( £ )
и \st — m\ < /га/«, то многократное применение теоремы 10.2
приводит к
/(*„..., «„)-/(«. .... т)е-*+0™*(Ч-тГ'\ (10.1)
Для Л s [п] определим множества
TA = Tf]{(xf у): хе=А или уеЛ},
Т\А = Т[\{{хгу): *е=Л и у&А).
Положим
9>{А) = {Т\ А: Т е= <#}, g? (Л) = {ТА: Т <= Щ.
Ограничимся случаем, когда | A \ = k < п\ Тогда У (А)
обозначает класс турниров на Л, а 9 (А) — класс множеств
игр, сыгранных игроками Л, каждый из которых (/ е Л)
выиграл ровно m игр.
Следствие 10.1. Пусть \ А \ = k < /i9\ Г| е ^ (Л). Тогда
1^(Л)Г1^/2<Р[Тгл = Г1]<|^(Л)Г,^,/2.
Доказательство. Для удобства будем считать, что Л =
■={1, ...,&}. Данный Тх дополним до Те$ добавлением
некоторого подтурнира Т2 на [п] — Л. Турнир Т принадлежит 31
тогда и только тогда, когда каждый / е А° выиграл в
точности *,==т—-|{ае Л: (/, а)^Т{}\ игр в В. Значит,
Л1 о
< 2" И
1{ГеЙ: Гл = Г,}| = /(а:,+1, ..., *я). (10.2)
Согласно (10,1), максимальное отношение двух таких
•/(**+!»•••» *я) равно £fe2/2, что и дает утверждение
следствия ЮЛ.
Следствие 10.2. Пусть \ А \ = k <п*'\ Txs=l9> (Л). Тогда
| 9> (Л) Г1*-2*'"* < р [Г | Л = Г,] <| 9 (Л) Г 1в8*1/я.
Доказательство. Как и в следствии 10.1, достаточно
показать, что наибольшее отношение Р [Тг | Л = Т\\ для двух
значений Тх ограничено e2k4n. Если /, /^Л, положим 7,}/ =
^=Г1А{(/>/)» (/> 0}- Поскольку всякий Т2 может быть полу-
tO. Ре&1Аярные турниры 49
(10.5)
чен из Т{ при помощи ( 2 J таких операций, достаточно
показать, что
Р[ТГ|Л = Г1]>Р[ТГ|А = Г{/]^4Ш, (10.3)
то есть
|{ГеЖ: Т\А = Т{}\^\{т*еМ: Т|А = 7f}|<T4fe"\ (10.4)
Положим В = Л —{/,/}. Достаточно показать для каждого
значения Т'в^&(В) совместно с Т\А = Ти что, полагая
Н(Ти П) = {Те=&: Т\А = Ти Тв = Т'в}9
Н (Г(;, Тв) = {Ге= #: Г|Л = Г}', Та = Га},
мы получим
|Я(ГЬ ГЬ)|>|я(г{/| Гв)|^4Ш. (10.6)
Можно считать, что («,/) е 7*,. Пусть /=1, / = 2, и для
простоты Л = [£]. Пусть т — а и т — Ь суть очки игроков
i и /■ в турнире Тх. Тогда в турнире Ту они будут иметь
баллы m — а — 1 и m — 6 + 1 соответственно. Для ^ Л
положим
•х^т-1-\{ущВ: У,у)*=Т'в}\. (Ю.7)
Тогда
\Н(Ти Гв) 1= 5]/(^+i — вл+1, ..., хл — »«) ( //2 + б )'
(/С. *)
(10.8)
(К. о
где /С = а + Ь + /г — /г, 6=(а —Ь)/2, a 2 обозначает сум-
мирование по всем в*+1, ..., ett = 0, ± 1, сумма которых
равна /Сив точности t из них равны нулю. В
доказательстве этих формул, детальное изложение которого мы
опускаем, прежде всего демонстрируется, что ТАс должен иметь
балловую последовательность вида xk+l — ek+u ..., хп — гп
с £е^ = /С; на втором этапе показывается, что пополнить
эти балловые последовательности до Т можно (//24-б ) или
( у/о 4- 6 4-1 ) спос°бами соответственно.
Таким образом, согласно элементарным вычислениям,
теореме 10.2, (10.8) и тому факту, что [6[^£, мы получаем
(10.6), а значит, и следствие 10.2.
50
10. Регулярные турниры
Следствия 10.1, 10.2 используются для демонстрации того,
что турнир Тг обладает многими из „локальных" свойств
турнира Т. Будем говорить, что турнир Т обладает
свойством I, если не существует пересекающихся множеств Ау
В<=[п], \A\ = \B\ = t=[3log2n], таких, что АХВ<=Т.
Лемма 10.1. Р [Тг обладает свойством I] > 1 —• о (1).
Доказательство. Очевидно,
Р[ТГ не обладает свойством I] < £Р[ЛХЯ^ТГ], (10.9)
л, в
суммирование ведется по всем \А\ = \ B\ = t, ЛП#=0*
Зафиксируем такие А и В; тогда
Р[АХВ<=Г]= Z Р[Тг|(ЛиВ)=7,1]<
Ti=>AxB
<2^2' тахР[Г|(ЛиВ) = Г,]<
Ту
<2(22)"V(2i2№<2-"(l+o(l)). (10.10)
Основной шаг заключается в использовании следствия 10.2
для доказательства неравенства
Р[Тг|ЛиВ = Г1]<Р[Т|Лив = 7,1](1+о(1)).
Все остальное доказывается так же, как и для Т. Таким:
образом,
ЕР[ЛХВдТг]<ЛЛ1+о(1)) = о(1). ■ (10.11)
а, в
. Нам нужна еще одна подобная лемма. Скажем, что Т
обладает свойством II, если существование непересекающихся
множеств Ли В, | А \ = \ В | = /> 10 log п влечет |(ЛХВ)П
ПГ|>40/.
Лемма 10.2. Р [Тг обладает свойством И] = 1 — о(1).
Доказательство. Вновь покажем, что
Р [Тг не обладает свойством П] = о(1). (10.12)
Предположим, что | Л | = | В | = /> 10 \ogti и | (АХВ)(]Т\<
< 40/. Положим /0= [10 log/г]. Согласно упр. 2, существуют
непересекающиеся множества
Л0 и Во, \A0\ = \B0\ = t0,](A0XB0)nT\<40t0.
10. Регулярные турниры
51
Таким образом, достаточно доказать соотношение
Р [ЗЛ0, В0€= [п]'\ Л0П Во= 0, I (Л0Х Во) ПТГ | < 40^] = о(1),
(10.13)
которое сводится к
Р[|(Л0ХВо)ПТг|<404] = о(Аг-2^). (10.14)
Последнее доказывается так же, как и в лемме 10.1. ■
Следствие 10.1 понадобится для доказательства более
болной леммы. Пусть Se[n], /, j е [п], i ф у. Для
фиксированного Т будем писать {Si}), если либо
(1М, /e=S и \{Sc[\Wi)-{Sc(\Wi)\<2№\ogn>
либо
(2)/,/e=Sc и I (S П ^) — (S П ^у)! < 200 /г.
Скажем, что Т обладает свойством III, если из выполнения
неравенства 11 S | — п/2 | < 5 л/п л/logn следует существование
ilf ..., /10 €= [п], таких, что (Sjk) влечет {/, k} П {iu • • •» *\о}=0-
Лемма 10.3. Р[ТГ обладает свойством III] = 1 — о(1).
Доказательство. Если турнир Тг не обладает
свойством III, то он должен обладать свойством Q: „3
различные iu ..., is, /i, ..., /5, (Sitjt) для 1 ^^ ^5". Следовательно,
достаточно показать,что
Р [Тг обладает свойством Q]—o(l). (10.15)
А так как имеется менее 2пп10 способов выбрать S, iu ..., /5,
достаточно показать для фиксированных S, 1и ..., /5, что
P[(SitJt\ для 1</<5] = о(2-/1/г"ю). (10.16)
В силу следствия 10.1 мы можем предположить в пределах
множителя (1+о(1)), что Wif и Wit суть т-элементные
подмножества. Таким образом,
Р[(ЗД<(!+о(1))\ (Ю.17)
т. е.
P[(Sitjt) для 1</<5]<(| + о(1))5п=о(0,487'г) =
= о(2~я/Г10). (10.18)
Посредством лемм 10.1, 10.2, 10.3 мы находим и
фиксируем турнир 7\ такой, что
ГеЙ, Т обладает свойствами I, II, III. (10.19)
52
10. Регулярные турниры
Оставшаяся часть доказательства не вероятностная. Пусть
Р — частичный порядок, Р ^Т. Нам надо показать, что
IPK^- + c,log/i. (10.20)
Покажем, что Р — „по существу" подмножество двудольного-
графа. Пусть
L = {x:\{y: (у, х) е Р) \ > 10 log/г}, ^
w? = тс (W.21)
Все игроки являются победителями (UP) или
побежденными (L). Победители проигрывают менее 10 logп игр в Р
согласно определению. Пусть xgL, A = {z: (xtz)^P}y,
В = {у: (у, х)€=Р). Тогда ВХА^Р, т. е., поскольку |В |>
> 10 log л и в силу свойства I, | А\< 10 log п. Значит, для
всякого А
Т[\{АХАС)== £ 5,-(>^)=-1|Л|| Л<|. (Ю.22>
так как все ^ = т. Таким образом, полагая |И7| = ~ + <^
| L | = ~ — а, находим, что
ipn(rxi)i<|i^iui<4-^T"- (10-23>
(В этом месте мы пользуемся тем, что Ге$!.) Если x^Lr
z^W и (x,2)gP, то (уу z)^P для по крайней мере
10 log п игроков у, так что (у9х)^Р исключается.
Следовательно,
\P{](LXW)\ = 09\P(](WXW)\=Z\{y^W: (м)еР}<
■<(ioiog/i)iiia
Аналогично |Pfl (L X Ц K(101ogAz)|L |, т. е.
\P\^-^L+I0nlogn. (10.24)
Мы предполагаем, что а <^ л/20п log я, поскольку противное
очевидно приводит к (10.20). Согласно свойству III, находим
и фиксируем S={iu ..., il0}9 такое, что (Wxy) влечет
{xy}(]{ii, ..., ''ш} = 0-
Положим Р' = (W X £) П Г. сравним | Р | и | Р[ |. Элементы
множества Р — Р' имеют вид (#, //), х, y^W—- S, или (s, х),
seUPnS, яеЯГ— S, или аналогичные пары для L плюс
не более чем 100logп пар вида (х, s), sg #П5, лге U^ — S
10. Регулярные турниры
53
и (s, х)9 seLQS, x^L — S. Для каждого y^W —S
имеется не более 10 log п элементов x^W — S, {х9у)^Р.
Если найдется по крайней мере один такой х9 то для всех
ze(L-S)()(Wy-Wx) имеем {y,z)<=T, (х,г)фТ% т.е.
(уу z) gP — Р'. А согласно свойству III, существует по
крайней мере 200 log п таких (у, z). Если seSfl^ так, что
\{x^W: (s, х) е Р} |< 20 log п + 2а, то мы игнорируем эти
(stx)^P — P' (имеется не более 200 log п + 2а таких пар
(s, х)). Если нет, то положим Bs = {x^W: (s,x)^P}r
Cs = {y& L: (у, х)еГ}иЯ = (ЙД Cs) f| Г. По определению*
Н £ Р'. Если (jc, г/) е= Р, то (5, х) е= Р влечет (5, у)£РсГ-
противоречие. Таким образом, Н ^Р' — Р. Так как BJU
U (L—C5) <= №5 и |№J = m, |L| = |—а, то мы имеем |С,|>
>|В,| — а > 20 log/г. И, согласно свойству II, | Я |>20| BJ.
С каждой парой в Р — Р\ за исключением не более чем
300 log/Z +20а пар, мы можем связать по крайней мере-
20 пар в Р' — Р. Можно проверить, что нет пары в Р' — Р,
посчитанной более чем 12 раз. Значит,
|P|-|P'l<3001ogrt + 20a. (10.25>
А в силу (10.24)
IP'Kyl^ll^Kx^T-v - (10'26>
Следовательно,
lP|<X + (20a~4") + 300IoS^<4 + 3011oS^"(10-27>
Основная идея этого доказательства заключается в
манипулировании турниром Тг. Благодаря следствиям ЮЛ и 10.2
мы обращались с Тг так же, как с Т. Подобные случайные
величины встречаются в § 14, посвященном асимметрическим
графам.
Упражнения
1. Пусть Т — фиксированный турнир на [п]. Показать,
что существует частичный порядок Р ^Т, I Р I ^ -g~ + ( ^ —
— o(l))log2tt. (Указание. Если не выполнено условие Si — mr
то положить W = {m игроков с наивысшими баллами}^
Р = (WX We) П Т. Предположим, что st = m. Если | (L£X Wt) П
ПЛ<я2(-|--о(1)), то положить P=(WiXLi)(]T. В про-
54
10. Регулярные турниры
тивном случае, согласно следствию 12.1, найдется A^Lh
B<=Wh |4| = |fl|>(l-o(l))Iog2n, BXAST. Полагая
W = WX + A-B, отмечаем, что либо Р, = (W X Vе) П Т.
либо Р2= {{W X W) ПТ) П {{Ь, i): Jefl} достаточно велико.)
2. Пусть A(]B=0, GsAXB, |Л| = а, |В| = 6.
Зафиксируем О^с^а, Q^.d^b. Доказать существование
С €= [А]с, D €= [В]", таких, что
I О П (С X /?) I > I G | (с/а)
11. ХРОМАТИЧЕСКОЕ ЧИСЛО
В этом параграфе рассматриваются оценки для
хроматического числа %{G). Будем использовать G для значения
случайной величины G. Для получения этих оценок нами
будут применяться два следующих метода.
Метод 1. Если граф на п вершинах можно раскрасить
в k цветов, то некоторый цвет использовался по крайней
мере n/k раз. Следовательно, этот граф обладает множеством
из по крайней мере n/k независимых вершин. Используя
этот метод, мы сможем показать, что граф со сравнительна
небольшим числом ребер может иметь высокое хроматическое
число.
Метод 2. Предположим, что %{G)^k. Пусть S —то
наименьшее множество, для которого %(G\S) = k. Для всех
x^S справедливо неравенство %{G] $ — {*})^&— 1. Если х
имеет в S степень, меньшую k ■— 1, то (£ — 1)-раскрашивание
S — {х} порождало бы (k —- 1)-раскрашивание S, что
противоречит предположению. Значит, каждая вершина xgS имеет
в S степень, не меньшую k—\. Следовательно, если
x(G)^fe, то найдется такое число и и подграф на и
вершинах, у которого число ребер не меньше u(k—l)/2. Этот
метод позволяет получить верхнюю оценку для
хроматического числа.
Мы сейчас рассмотрим задачу, решение которой требует
обращения к обоим методам. Определим /(га, й, п) как та
наибольшее %(G) графа G на п вершинах, что все era
m-вершинные подграфы ^-раскрашиваемы. Нам интересен
случай &==3.
Теорема 11.1 (Эрдёш [1962]). Найдется такое Сх > 0, что-
для /г^га^З выполняется неравенство
f (т, 3, п) > Сх (n/m)4z (log (2n/m))~1..
В частности, следствием этой теоремы может служить,
тот, возможно несколько неожиданный факт, что для
всякого k существует такое е>0 и такой /г-вершинный граф G
(п > п(k, е)), что %(G)^ky в до время как всякий era
[e/zj-вершинный подграф 3-раскрашиваем.
*56
//. Хроматическое число
Вначале рассмотрим случай „малых" параметров.
Положим
С2= mm f{m, 3, n)l[{nlm)4>(log{2h/m))-{]. (11.1)
3</t<1010
3<m</i
Тогда C2>0. Если C{^C29 то теорема 11.1 для 3</г<1010.
Аналогично положим
C3==[ sup al/41og(2a)rTl. (11.2)
l<a<1010
Здесь a заменяет n/m. Если C{^C3, то
f (m, 3, n) > 1 > С, (/i/m)Vl (log (2п/т)Г1
для n/m^ lO10. Это есть то место доказательства, в котором
log(2n/m) нельзя заменять на log (п/т). Таким образом, для
доказательства теоремы 11.1 достаточно найти такое С4>0,
чтобы при п > 10ю, п/т> 10ю выполнялось неравенство
7(т, 3, /i)> C4(n/m)l,i(log(2n/m)r\.
и, положив C1 = min(C2, С3, С4), получим требуемое.
Зафиксируем я > 1010, т < /zl0~10. Пусть G = Grtt р при
пока еще не определенном р\ используем метод 2. Если
m-вершинный подграф графа G требует 4 цвета, то
некоторый ы-вершинный, А^и^Шу подграф содержит ^Зм/2
ребер. Граф G содержит такой подграф с вероятностью
т
£„(«, "*)<£ £ Р[|0|Л|>Зи/2]<
а-4 АЩп\и
<|(:)(21)""<|(^)"йГ'""в<
т т
<2][C5n«V/2r<£[C5n'ttV/l]a<l/101 (11.3)
и=4 ы=»4
когда С5пт1*2рч* < 1/10, что имеет место при р^.С6п-а/*т-4*.
Теперь зафиксируем р = C6az~vW",/3.
Р[если |Л|<т, x(GM)<3] > 9/10. (11.4)
Для оценивания %(G) мы используем метод 1.
Вероятность того, что G содержит множество из х независимых
//. Хроматическое наело
ЪТ
вершин, равна
hJLn9m)< £ Р[ОПИ]2=0]<
<{"x)V-p№<К«А)«-р)(дс-,)/2Г- 01.5>
Поскольку п> 10ю („достаточно велико"), то р<С6п~',%< 1(TS
(„достаточно мало"), а так как я/т>1010, то рп =■
= С6(п/т)1/*> 102. Мы можем сейчас показать с большим
запасом, что если jc^4log{рп)/р, то Ар(/г, т)< 1. Если G
не содержит ас независимых вершин, то %(G)^n/x. Т^ким
образом,
Р [%(<*)> рп/4 log (рп)}> 9/10. (11.6)
Комбинируя (11.4) и (11.6), можно отыскать такой граф Gy
все ^/л-вершинные подграфы которого 3-раскрашиваемы,.
3
и, стало быть, для C^^-^Cq
% (G) > рп/4 log (рп) - { Сб (/i/m)'/8 [log (я/т)]"1 >
>CA(nlm)\log(2n/m)rl. ■
Обратимся теперь к теореме, доказательство которой
требует усиления метода 1. Положим <o(G) равным клико»
вому числу графа G. При любом раскрашивании G каждая
вершина клики должна быть раскрашена по-своему; таким
образом, x(G)>co(G). Татт [1947], Зыков [1949], Дж. Б. Келли
и Л. Б. Келли [1954] независимо построили для любого т
граф G, у которого 0(G) = 2, a %(G)^m. Такой граф не
должен содержать циклов длины ^5. Дж. Б. Келли и
Л. Б. Келли [1954] предположили, что для любых k и /
существует граф G, у которого %(G)^k и нет циклов длины
^/. Эту гипотезу с использованием вероятностных методов
впервые доказал Эрдёш. Конструктивное доказательство
было позже предложено Лова чем [1968]. Доказательство
Эрдёша позволяет получить и следующий, много более
сильный результат.
Теорема 11.2 (Эрдёш [1959]). Если /, 9 и ц фиксированы*
6 < 1//, 0 < г] < в/2, то для достаточно большого п найдется
п-вершинный граф G, не содержащий циклов длины ^ / w
%(G)>n\
58
//. Хроматическое число
Доказательство. Пусть G = G„,P, где р = п*~1. Положим
= [п1~% и а = Р [Л е= [л]* влечет |G|i4|>л]. Тогда
£ Р[|0|ЛК/|]<(;)((2))(1-р/^. (11.7)
1-а<
5[П]
Мы оцениваем
С)«»««-Л (G))<(if)"<„» (11.8)
и аппроксимируем ♦
(1 —р)\2' ~e-p*i/2~ е 9
(П.9)
Поскольку 8 — 2rj > О и не зависит от /г, то 1— а = о(1).
Следовательно, а= 1 -— о(1).
Прежде всего рассмотрим маленькие циклы графа G.
Цикл длины / (/-цикл) определяется /-выборкой (хи ..., xi)
различных вершин из [п]. Имеется < п* таких /-выборок,
каждая из которых образует цикл тогда и только тогда,
когда (л;/, ^+1)eG, 1^/^/ (mod/), который наличествует
с вероятностью р1. Положим c(G) равным числу ребер графа G,
содержащихся в /-циклах, 3^/^/. Тогда
E(c(G))<£m<y</V' = o(/i). (11.10)
То есть с вероятностью 1 — о(1) имеет место оценка c(G)<n.
Комбинируя эти результаты, мы находим такое
значение G' случайной величины G, что
(1) Ае=[п]х влечет \G'\A\^n9
(2)c(G')<n.
Положим G = G' — {все ребра в циклах длины ^/}. По
построению граф G не содержит циклов длины ^/. А
поскольку с (G') < /г, то мы удаляем из G менее чем п ребер,
и, следовательно, А ^[п]х влечет G\ АФ 0,Согласно методу 1,
это влечет неравенства % (G) ^п/х^пц, Щ
Мы возвращаемся к сравнению %(Gn) и со(0Л). Во-первых,
рассмотрим max%(Gn) по всем Gni у которых (u(Gn)^2. Из
теоремы 5.3 следует существование такого Gni для которого
со (G„) = 2, со (Gcn) <C7nh log п.
Таким образом,
% (G«) > л/со (Gn) > Сед* log п.
11. Хроматическое число
59
Для мажорирования %{Gn) нам потребуется
Лемма 11.1. Пусть Gn — фиксированный граф.
Предположим, что для каждого А е [п]х существует В^ А, такое, что
\B\^f(x)t Gn\B=0 (l<x</z, х и f \х) целые). Положим
а0 = п, ai+{ =at — f (at). Тогда если а* = 0, то %(Grt)^/.
Доказательство. По индукции мы находим А ^ [п] —
— Ах— ... — Лм, \Ai\ = f(ai^x), G/Ai = 0. Но тогда
разбиение [п] = Ах + ... + Ап является /-раскрашиванием
графа Gn. ■
Очевидно, если co(Grt)^2, то и всякий подграф Gm имеет
(o(Gm)^2. Поскольку по теореме 5.3
R(C9[mlogm/loglogm]y\ 3)<m,
то Gm содержит множество из C9[m log m/log log m]'/2
независимых вершин. Применение леммы 11.1 дает: %(G)^
<^Cl0[nlog log/z/log/z]'/2. В итоге получена
Теорема 11.3. Положим $n = {Gn: co(Grt)<2}; тогда
С8/г,/г log п < max % (G) < C10/zV2 [log log n/log n\h.
Мы можем также рассмотреть max%(GJ/cD (Gn). По
теореме 5.1 существует такой граф Gn, у которого и co(Grt), и
© (Gcn) не превосходят log4 л. А поскольку % (Gn) ^ я/со (G^),
то X(GJ/co (Gn)^Cnn/(logn)2. Согласно (5.2), для всякого Gm
/co(Gw) + co4Gcw)^2\
I |>m. (11.11)
V *(Gm)-l )
Лемма 11.2. £слы (a^)>m> ™ ab>C12(logm)2.
Доказательство. В силу симметрии мы можем
предположить, что а=а/Ь^1.
m < (а Г) < (2*) < m'jw*=(2^)6>
аЬ = Ь2а >(log m)2a/(log 2m)2 > C,2 (log m)\
где C12=mina/(log2ea)2==e/8. ■
Применяя лемму 11.2 к (11.11) при a —<o(Gm) — 1, Ь =
= (o(Gm)—1, получаем
(о (Gm) cd(G^)> aft >Ci2 (log m)2. (11.12)
60
11. Хроматическое число
Пусть Gn фиксирован. Положим (o = (n(Gn). При /(т) =
= {C12(logm)2/o&} выполняются условия леммы 11.1,
применение которой приводит к неравенству
%(Gn)<C[3rm(Gn)/(\ogn)2. (11.13)
В итоге получаем следующий результат.
Теорема 11.4 (Эрдёш [1967]).
c"o^<maxx(G")M^
Упражнения
1. Пусть /^4 фиксировано, ft(n)=max%(G), где J^ —
класс /г-вершинных графов без циклов длины ^/. В силу
теоремы 11.2 если ц < 1/2/, то fi(n)^n^ для достаточно
•большого /г. Сократить доказательство теоремы 11.2 для
оценивания // (/г) снизу.
2. Используя обозначения предыдущего упражнения,
показать, что
//(")</г1/га +2.
{Указание. Подсчитать вершины подграфа, фигурирующие
в методе 2.)
3. Пусть G — случайный /г-вершинный граф с
вероятностью появления ребра, равной 1/2. Доказать, что
существуют такие положительные константы с{ и c2f что с
вероятностью 1 — о(1)
C\tl (С\ ^У ^гЛ
]^T<X(G)< logn •
А2, ..., As) ребер этого графа 5^, такое, что
<(fc-l)s.
4. (Эрдёш и Хайнал [1966]) (обозначения см. в § 4).
Всякий 5-цикл в &-графе 2f определяется как семейство {А[9
'lUl
Доказать, что если k и s фиксированы, то найдется &-граф &
без /-циклов, /^5, который не обладает свойством В.
(Указание. Это обобщение теоремы 11.2 на &-графы. Пусть п
велико; возьмем ls[n]k, полагая Р[Л е I] = р = /г,-/г+6, где &
очень мало. Тогда среднее число ^s-циклов меньше Cns6.
€ вероятностью 1 г-о (1) каждая п1~е вершина содержит
^ n\+r\-ek членов графа 3f. Удалить маленькие циклы,из &
для нахождения %2Р% у которого %(&')^пг > 2 для е < (1 —
-(s-Dv)/p.> -
//. Хроматическое число
61
5. Заметим, что упр. 4 сводится при $==2 к упр. 3 § 4.
Определим т*{п) как наименьшую мощность /г-графа &л
не обладающего свойством В и такого, что У/А{, А2^&,
I А П Л21 < 1. Доказать, что пС (п) < Кп, где К — некоторая
абсолютная константа.
6. (?) Верно ли, что
limJ2i^).==log2?
П П
7. Пусть G — трехдольный граф на трех
непересекающихся множествах вершин Л, В и С, каждое мощности п.
То есть G s [Л U В [} С]2, G^ = G|B = G|C=0.H.3 ауер
(частное сообщение) утверждал, что граф G должен содержать
либо треугольник, либо независимое множество на п + 1
вершинах.
(a) Доказать, что для достаточно большого п найдется
трехдольный граф G, не содержащий ни треугольников, ни
л+1 независимых вершин. (Указание. Положить G = GP —
— [Л]2-[В]2 —[С]2, р = /ге"1 и G*=G — {все треугольники}.)
(b) Пусть k ■— фиксированное целое. Доказать, что для
достаточно большого п найдется трехдольный граф G, не
содержащий ни циклов длины *^k, ни л+1 независимых
вершин.
8. (?) Ответ на следующий вопрос Б. Грюнбаума
неизвестен. Верно ли, что для любых k и / существует
регулярный граф степени k с хроматическим числом k, наименьший
цикл которого имеет ^/ ребер? Нам этот вопрос
представляется весьма трудным и неразрешимым вероятностными
методами.
12. ПРОБЛЕМА ЦАРАНКЕВИЧА
И РАМСЕЕВСКИЕ ТЕОРЕМЫ
ДЛЯ ДВУДОЛЬНЫХ ГРАФОВ
Определение. Предположим, что 2^а^/я, 2^6^/г,
а, Ьу m, п — целые числа. Тогда kab{m, п) обозначает то
наименьшее ky для которого все (0— 1)-матрицы размера тХ«,
содержащие по крайней мере k единиц, обладают
подматрицей размера а X Ь, сплошь состоящей из единиц. Для
удобства введем обозначения: ka (т, п) = kaa(m, ri), kab(n) = kab(n, я),
ka{n) = kaa{n,n).
Проблема Царанкевича [1951] заключается в нахождении
каь (т, п). Гаи и Знам [1969] охарактеризовали связь проблемы
Царанкевича с аффинными и проективными плоскостями,
тройками Штейнера и т. п. и приложение ее к этим
областям. Гаи и Знам [1971] представили исчерпывающий обзор
известных оценок функции k. Нас, в частности, интересует
граф-теоретическая интерпретация. Зафиксируем два
непересекающихся множества А{1 А2> \А{\ = т, \А2\=п.
Любую (0—1)-матрицу размера тХя можно
рассматривать как матрицу инцидентности двудольного графа (?£
s А\ X А2. (На протяжении всей этой главы мы
рассматриваем элементы множества Ах X А2 как неупорядоченные пары.)
Тогда k = kab{m, п) есть то наименьшее целое, что при G^
^ А\ X А2, \G\^k, найдутся два множества B{^Ah для
которых | В{ | = а, \В2\ — Ь и Вх X В2 г G.
Для нахождения оценок величины kab (m, п) удобнее
рассматривать более общую функцию.
Определение. В (т: п, а, Ь\ е) есть то наибольшее целое,
что при | Ах | = т, | А2\ = п, A{[)A2=0, Gs А{ X Аъ \ G |>е
найдется по крайней мере В (т, /г, а, Ь\ е) пар (Вь В2), В\ е
е[Ах]а9 В2^[А2]\ BXXB2^G.
Очевидно,
В (т, /г, а,^)>0О kab (/и, п) >е. (12.1)
Теорема 12.1.
/ тп— ab \
>
(;)(m("")/(J)).. (ад
12. Проблема Царанкевича и рамсеёвские теоремы 63
Верхняя оценка есть среднее число пар (В,,В2), B[XB2^G,
где G — случайный член множества [А{ XА2]е (см. упр. 1).
Для вывода нижней оценки воспользуемся некоторыми
элементарными результатами о выпуклых функциях. Пусть
t — неотрицательное целое. Функция Г * Л для
действительных х определена в § 2.
Лемма 12.1. Если f (х) — выпуклая функция, то g(x) =
= Г ' \*' J — тоже выпуклая функция.
Доказательство. Вычисляя вторую производную, легко
показать, что функция fx (х) = ( t Л выпукла. Но тогда, если
0О<1,
л('<;>) + (1-*,) ('?>)>( VW + O-W/Cif)^
(так как fx выпуклая)
^,f(Xx + (\-k)y)\
(так как f выпуклая). ■
г
Неравенство Иенсена. Если 0^А,*^1, Ця,==1, a f —
выпуклая функция, то
Использование неравенства Иенсена для /M = (f)>
Я/ = 1/г, 1</<г, приводит к следующей лемме,
г
Лемма 12.2. Если £ xt = N, то
Г
ЮМГ)-
*~1
Доказательство теоремы 12.1 (нижняя оценка).
Зафиксируем граф G ^ А{ X А2, | G | = е, для которого имеется в
точности В (ш, п, ау Ь\ е) пар (Bl9 В2), Si ^ [ЛГ, В2е[Л2]ь,
В! X #2 ~ G* Для каждого I € At положим
X (/) = {/€Е Л2: (itj)<=G). (12.3)
Тогда
* = |G| = £ U(0J. (12.4)
64 12. Проблема Царанкееича и рамсеевские теоремы
Для Bi^[A2y положим
У(В2) = {/6=Д: »X52sG}. (12.5)
Тогда ■ .
{(С,В2):»еЛ„В2е[Х(«)]к} =
= {(/,52): В2<=[А2)Ь, iesY(B2)}. (12.6)
Следовательно,
Z irwi-Z(,Tl)>"Cim) ' <12-7>
(неравенство следует из леммы 12.2). Итак, вновь
пользуясь леммой 12.2, получаем
*<«.....»■..)- е (",<«l)>C)Wt)/a)Y
в2е(л/ \ a /
(12.8)
Применим условия (12.1) к теореме 12.1 для оценивания
kab(m,n). Заметим, что
(»)(4t)/W)>0^M(t)/(J)>«-M.2.9)
Обратимся к случаю, когда a = b фиксировано, m = я->оо.
Следствие 12.1.
^П2"2/в(1 + 0(1))<4аМ<(а--1),/в«2-|/а(1+о(1)).
Мы можем усилить следствие 12.1, когда а = 2. Пусть
п — р2.4- Р + 1 > где р — степень простого числа. Известно
(см., например, Холл [1967]), что .существует проективная
плоскость с п точками и п прямыми. Занумеруем точки
Ри ..., Рп и прямые L,, ;.., Ln произвольным образом.
Пусть А = (аи), где аи—19 если Рь^Ь}у и аи = 0 в
противном случае. Поскольку две точки не могут лежать на
двух прямых, А не может содержать подматрицу размера
2X2, состоящую только из единиц. Поэтому
Mp2 + P+l)>l-bi:%=l + (p2 + P+l)(p+l) (12.10)
(см. упр. 3). Для всех п существует m = p2-f-p+l>
п (1 — о (1).) < m ^ п. Следовательно,
Ы«)>Ы/п)>л8/'(1-о(1)) (12.11)
В (Ковари, Шош, Туран [1954])
limM«)rt-3/s=l. (12.12)
12. Проблема Царанхевича и рамсеевские теоремы 65
Брауном [1966] был построен л-вер шинный граф
с (я/з/2) (1 + о (1)) ребрами, не содержащий полного 3X3-
двудольного подграфа. Согласно приведенному ниже
следствию 12.4, это влечет кг(п/2)^(п^/4) {I+о{1)). Таким
образом,
n5/32~,/3(l+o(l)X^W<^/82,/3(l+o(l)). (12.13)
Неизвестно, существует ли lim k3 (п) п~ъ/\ Представляется
вероятным, что
ka(n) + 0(n*-u*>) (?), (12.14)
но это не доказано для а > 3.
Исходя из вероятностных соображений, мы улучшим
нижнюю оценку в следствий 12.1. Ради краткости назовем
подматрицу размера аХ#, сплошь состоящую из единиц,
al-матрицей. Если А — {ац) — некоторая матрица размера
/гХя» то определим t (А) как число al-матриц в А. Пусть
Л* = (а*) обозначает матрицу Л, в которой какая-нибудь „1"
из каждой al-матрицы заменена на „О". Если одна и та же „1"
входит во многие al-матрицы, то она заменяется лишь
единожды, причем выбор той „1" в а 1-матрице, которая
подлежит замене, может быть совершенно произвольным
(например, „левый верхний угол" al-матрицы). Тогда Л* не
содержит al-матрицы и, стало быть, не более t (А) единиц
матрицы А были заменены, т. е.
ЕаЬ>2>,,-'М). (12.15)
Пусть теперь А = Ар= (ах/) — случайная матрица размера
п X п с Р [ai7 = 1] = р. Тогда
Е(1а,/) = ЕЕ(а,/)-/г2р (12.16)
и
Е« (А))-=(;)>'. (12-17)
поскольку имеется 'Г j матриц размера аХа, каждая из
которых есть а 1-матрица с вероятностью ра\ Отсюда, исполь*
зуя (12.15), получаем, что
e(EO»v-(:)V. (12Л8)
Для больших п мы аппроксимируем (пЛ величиной па/а\.
Для максимизации правой части неравенства (12.18) положим
66 12. Проблема Царанкезича а рамсеевские теоремы
р=(а—l)!2/(fl2 ° 2/(а+1). Тогда существует матрица Л*, не
содержащая а 1-матриц, и
>(1-а^)(а-1)!етп2~. . (12.19)
При выводе (12.19) мы пользовались общим принципом
вероятностного метода. Вообще мы стараемся отыскать
„структуру" (например, матрицу, граф, раскраску), которая
не содержала бы „запрещенной подсистемы" малого цикла
монохроматического подграфа. Для этого прежде всего
обращаемся к случайной структуре, содержащей лишь небольшое
число запрещенных подсистем. Потом преобразуем структуру
так, чтобы все имеющиеся запрещенные подсистемы
разрушались, а новые не возникали. Этот метод уже
использовался нами при доказательстве теорем 4.2, 11.2 и будет
использоваться вновь в теореме 13.2.
Следствие 12.2. Пусть \ А{ | = | А2\ = п, Ai[)A2=0. Если
G^AiXAz, |G|>~-(1 — о(1)), то существуют BtsAh
B{XB2<=G, |BJ>(l-o(l))log2/i.
Следствие 12.2 дает некий аналог рамсеевского
результата (5.2). Пусть g (п) — то наибольшее целое t, что если
некоторый /г X ^-двудольный граф 2-расцвечен, то существует
монохроматический/X ^-Двудольный его подграф. При любом
2-расцвечивании один цвет должен быть использован по
крайней мере п2/2 раз. Таким образом, g(n)^(l — о(1)) log2n.
Случайное 2-расцвечивание содержит в среднем (пЛ 21"'*
монохроматических t X ^-двудольных графов. Для t=*
= (2 + о (1)) log2/z это число меньше единицы, т. е.
(1 — o(l))log2/z<gr(n)<(2 + o(l))log2n. (12.20)
Представляется трудным получить обе оценки для g(n)
с постоянными множителями.
Следствие 12.3 (Эрдёш и Мун [1964]). Пусть f (пг, п, а, 6) —
число монохроматических В{ХВ2, \ Вх | = а, | В21 = 6, при
.любом 2-расцвечивании Ах X Л2, | Аг \ = гп, \А2\ = п. Тогда
"для фиксированных а и b
. 7<w,t>_2i-.»
12. Проблема Царанкевича и рамсеевские теоремы 67
г Доказательство. Пусть А: Л, X А2 -> {1, 2} — некоторое рас-
цвечивание. Положим et = | /Г1 (/) |, / =* 1, 2. Тогда ех -\-е%=тпу
и число монохроматических ВХУ^В2 не меньше, чем
(нижняя оценка в (12.2) выпукла по е)
-(;)(i)2,'*<i-<><i>>. (i2-21)
Обратно, пусть h — случайное расцвечивание. Тогда
среднее число монохроматических ВХХВ2 равно ( д)(^)21~а&,
тем самым для некоторого h имеется ^Г ^ J f? J 2х~аЬ
монохроматических ВХ X &2- Ш
Аналогичный результат для полных графов неизвестен.
В частности, пусть f (п, а) обозначает число
монохроматических [S]2, \S\ = a9 в некотором 2-расцвечивании графа [я]2*
Гудман [1959] получил соотношения
f(2/t,3) = n(n-l) (я-2)/3,
f (4/i+l,3) = 2n(/i-l)(4/i+l)/3, (12.22)
f (4n + 3, 3) = 2/г (n + 1) (An - l)/3,
полностью определяющие / (n, 3). Оценивая среднее для а >3,
легко показать, что f (л, а) < Г * J 2 ^2 л Представляется
вполне вероятным, что
lim ii^ = 2l"(~^)(?), (12.23)
^ С)
но это не доказано (см. упр. 2).
Следствие 12.4. Пусть п четно (для нечетного п —
аналогично). Если Gs[az]2, | G |>£, то число пар (Ви В2), Bxy,B2^Gy
fiifl^—0> |5il = a> |B2I = &> № меньше, чем
(»f)("'2(T)/(f)). (ИЛ)'
Доказательство. Зафиксируем G. Пользуясь упр. 6,
разлагаем множество [п] в сумму А{ + А2 так, что
68 . 12. Проблема Царанкевича и рамсеевские теоремы
\G(](AlXA2)\>e/2. Число пар fi, X S2 ^ G, В{ 65 [Л,]а,
В2&[А2]Ь, не меньше чем В (/г/2, /г/2, а, Ь; г/2). ■
Обобщение теоремы 12.1 на &-граф дает
Теорема 12.2. Пусть n^t целые, a O^a^l. Положим
go = go(n,at t) = a и
gi+l = gi+l (/г, a, О -(Я? )/(*)• (12.25)
Пусть Аи ..., Ak~- непересекающиеся множества, \А{\= .. .
... =|Л*| = /1. Гогда если Os^X ... XAk, |G|>an*,
то число различных k-произведений В{ X ... X Вь s G, | В J = t,
не меньше gk I . 1 .
Доказательство. Во-первых, отметим, вновь применяя
лемму 12.1, что g{ (/г, a, t) — функция, выпуклая по а. Докажем
теорему индукцией по k. Она тривиальна для 6 = 1.
Предположим, что утверждение имеет место для k — 1 и
фиксированного G s А\ X ... X Ль | G |> a/z*. Для x&Ak положим
d(*)=|{(*i. ..-> *a-i): (*i, ..., ^i^lsC}^-1. (12.26)
Тогда
a/i*<|G| — Z d(x)nk-{; (12.27)
значит,
а/г< £ <*(*). (12.28)
xesAk
Положим
£/ = {(Bb ,,.,BH^): S^^f, x&Bk9
BiX ... XBhXWsO}. (12.29)
Каждая вершина x s Л^ индуцирует некоторый граф
G* г Л1 X ... X Ak-lf | Gx | = flf (a:) nk~l. Согласно
индукционному предположению,
\{(Bi9 ..., Bh-X)i (Bl9 ..., Bfr-lf x)€=£/}|>
>ftw(*.tf(*).0(J)*"\ (12.30)
т. е., согласно лемме 12.2,
1у1>(*)*~' Z Sk-i(n,d(x),t)>
*sAk
>(")k~[ngk-l(n,a,t). (12.31)
12. Проблема Царанкееича и рамсеевские теоремы 69
Положим
у(Ви ..., B*-,)«|{*i (Вь ..., B^ux)gU)1 (12.32)
Тогда
£*/(Вь ..., Bfe-,) = |t/|>(^)fe"1^-1(n,a,/). (12.33)
Таким образом, число fe-произведений Bi X ... X B^-i XBfesG,
5/ s [Л^]' равно
(вновь пользуемся леммой 2)
■*(J)*ft(*,af0 (12.34)
(согласно 12.26). ■
Для использования теоремы 12.2 заметим, что если a/г > tt
то (Т)/(?)~«'
Следствие 12.5 (Эрдёш [1965]). Пусть h —некоторое 2-рас-
цвечивание множества А{ X . •. X Аъ \ At \ = п. Тогда найдется
монохроматическое множество i^ X ... X Bk> #* s Ai9 | В/1 =
-/-d9ga«)I/(*"!) (l~o(l)).
Доказательство. Докажем более сильное утверждение
о том, что если Gs^X ... X Ак, \G\^nk/2, то такие
В[, ..., Bk существуют. Положим a* = gt (/г, 1/2, t), т. е.
ав«1/2, в*+1^(Я"')/(")• Для 0</<fc-2 имеем
а<+1 >-j-a^a^+1 (подробности опущены). Таким образом,
ц^х > 2~{Ш)к~{ = /Г1+0 (,) > t/n. Стало быть, ak >0, gk> О,
и по теореме 12,2 такие Вь ,.., Bk существуют. ■
Следствие 12.5 близко к наилучшему. Пусть h — рлучайг
ное 2-расцвечивание А{ X... X Л*. Среднее число
монохроматических В{Х ...XBfe равно ( J)*2-2"'*< nk2~fk~l < 1
для /=(felog2n)1/(fe"1). Значит, имеется расцвечивание h
с немонохроматическим Bj X ... X Bk, \Bt\> (k log2/z)l/( _1.
Соответствующий результат для теоремы Рамсея уже не
столь точен. Пусть Rk (п) — то наибольшее t, для которого
всякое 2-расцвечивание [n]k включает монохроматический
граф [S]k, | S |>f. (Обратим внимание, что это не R, определен-
70 12. Проблема Царанкевша и рамсеевские- теоремы
ное в § 5.) Из § 5 мы знаем, что C2logn< R2(n) <C2logft,
где C2 = (21og2)-1, C^ = 2(log2)-1. Для k = 3
С3 log log п < R3 (ft) < С'ъ (log /i)v', (12.35)
и для &>4
Ck log log .. log ft < Rk (ft) < C'k log log ...log ft. (12.36)
Кроме того, Rk+\ (ft) < Cklog(Rk(n)) для &>3. Таким
образом, если бы было показано, что
R3(n)< С log log az,
то Rk (/г) было бы известно с точностью до постоянного
множителя. Вычисление порядка величины /?3(я) является
в этой области одной из важнейших нерешенных задач.
Мы не в состоянии улучшить оценки для Rk(n). Однако,
используя теорему 12.2, можно найти „по преимуществу"
одноцветное подмножество. Положим Rk(n9e) равным тому
наибольшему t, для которого всякое 2-расцвечивание [ft]*
содержит множество S£[n], \S\^tt такое, что ((1/2) -f-е))
из &-ребер графа [S]k одноцветны. Ясно, что Rk(n, l/2) = Rk(n).
Rk (ft, e) монотонна по n и е. Оценки для R2 (ft, е) даются
следствием 7.2.
Теорема 12.3. Для k^3 существуют е'(k) и c(k), такие,
что для больших п
Rk(n,B'(k))>c(k)(log2n)mk-{).
Доказательство. Зафиксируем k, и пусть п велико. Пусть
h — некоторое 2-расцвечивание [n]k. Для Du ,,„/),-
непересекающихся подмножеств [ft] и аь ..., as г- неотрицательных
целых, Y*ai — ky определим сумму
A(D?«, .... D?)-Z*(B). (12.3П
которая берется по всем В е [n]k, \ В П D ь\ ===== at. Через h (S)
будем обозначать h(S]k. Пусть А^ ..., Ak — пересекающиеся
подмножества множества [ft], | At \ = [nlk]. Применяя
следствие 12.5, находим и фиксируем Ви ..., Bkt
\Bi\ = t = (log2(n/k))mk^)(l-o(l))9
такие, что | h (В{ ... Bk) \ = tk. Мы хотим преобразовать это
в большее h(S).
Для 1 ^i^£ пусть Hi будет подмножеством множества В/;
таким, что каждое x^Bt входит в В* с вероятностью р^
12. Проблема Царанкевша и рамсеевские теоремы 71
Здесь Pi — константы, 0 ^ р* ^1,-чьи значения будут
определены позже. Тогда *
Л (В, U ... U В,) = £ h (Bfi ... bafy (12.38)
суммирование ведется по всем неотрицательным ah y£4ai=k.
Для любых аь ..., ak
Е[Л(В^ ...В^)]=1Л(\Г)Р[1Г^В1и ... UBJ; (12.39)
здесь суммирование ведется по всем W е [n]kt \W(\Bi\ = ai9
Таким образом,
P[W^B{[} ... l)bk] = P[W[)Bis=;Bi для 1<*<£]==
= UpV (12.40)
не зависит от W. Применяя (12.40) к (12.39), находим
е [а(в;.... в;*)]=(ПPV) Е h {W) = (П К1)h{Щ\ ■ ■ ■ в».
(12.41)
Усредняя (12.38), видим, что
Е[Л(В,и ... иВ,)] = Ел(в;>...В^)(Пр^). (12.42)
Желательно подобрать значения ft так, чтобы E.[h(bx\} ...
• •• U Вд,)] было велико. Для этого воспользуемся одним
результатом полиномиальной аппроксимации.
Пусть Tk — множество действительных полиномов
G(xv ..., xk) = Y,Ca а Т[х"1у где суммирование ведется
по всем неотрицательным целым а^О, Yaai = k. Положим
|G| = max|Cei...eJ> l|G||= max \G(xx. ..., xk)\.
- Лемма 12.3. Существует такое e = e{k), что ||G||^e|G|
для всех Ое1Га.
Доказательство. Tk является метрическим пространством
е нормой | • |. Положим
- H = {G: I G Г— 1>.
Тогда Тк компактно. Если Gt=T'ky $Ф0, то ||G||>0,
Функция || • || непрерывна и положительна на компактном
множестве T'k, т. е» существует е = е (k), || G || ^ е для G■'& Г£у;•- ^
Если G = 0r то очевидно ||G||^e[G|. Если G ф 0, то
G„==|G |Gi, Gi ЕГк Тогда, поскольку функция || • || динейна,
■ilCIMOHIOi-ll^-efOI. Н - -
?й 12. Проблема Царанкевича и рамсеевСкие теоремы
Видимо, хотя мы и не делаем этого, можно дать точное
выражение для е(£).
Посредством леммы 12.3 находим и фиксируем ри ..., Pk>
такие, что в (12.42)
|Elft(B,U ... UBk)]|>|A(B, ...Bk)\e(k)=e(k)tk. (12.43)
Таким образом, существуют фиксированные множества
В,', ..., В'*, S = B\[) ... ив*,
|A(S)|>e(*)f\ (12.44)
Известно, что (SKI^U ... [}Bk\ = kt. А так как | h (S) ]<
^('f1), то \S\^[kle(k)]llkt. Полагая с (k)< [k\ e(*)]l7\
e' (£) > e(k) k\ £ /2, получаем утверждение теоремы. ■
Теорема 12.3 приводит к заманчивой задаче. Пусть,
например, £ = 4. Для малого е величина R4(n, е) имеет
порядок (log/z),/3. (Читатель может это проверить, рассмотрев
такое случайное расцвечивание, что для фиксированного е,
е>0,Rk(n, e)<c(k, e){logn)m~l).) Для 8=1/2, R4(nt e) =
= /?4(^) = О (loglogп). Как ведет себя функция R4(n> е) при
изменении е? Имеется ли „точка перелома" е0, т. е. такая,
что для е < е0 величина R4(n> г) имеет порядок (logn)4\
а для е > 80 величина R4 (/г, е) имеет порядок log log/г? Каков
порядок величины R4(ny 0,5 — е) для малых е? Нам
неизвестны ответы на эти вопросы.
Упражнения
1. Используя обозначения теоремы 12.1, показать, что
/ mn — ab\
й<«...«.»;.><(:)(;)^=2^.
Сравнить оценки В для т, п, е, „много больших", чем а й 6.
2. Показать, что f (h9 а) > (4* )/( J" \ ) . т. е. что
f (/г, а) > ( па J (а! 4а*) (1 — о (1)) для фиксированного а. (У/са-
за*ш£. Число Рамсея R(a, а)<Аа.) Показать, что предел
в (12.23) существует.
Много работ (см. Гаи и Знам [1969]) было посЪящейа
нахождению точного значения kab (w, п) для малых а, Ь, ш, п.
12. Проблема Царанкевича а рамсеевские теоремы 73
Лемма 12.2 переформулируется так: „Если Vjt^Af, то V ( Xi j
минимизируется при насколько это возможно равных х".
Мы. применяем эту модификацию к (12.9).
3. Рейман [1958]. Доказать, что
к2(р2 + р+1)<1+(р2 + р+1)(р+1).
Это дает равенство в (12.10).
4. Доказать, что &2 (5)^13.
5. Доказать, что k2 (9) ^ 30. (Это потребует некоторых
комбинаторных манипуляций*)
6. (а) Пусть G ^ [/г]2. Доказать, что существует такое
разбиение [п] = Ах+ Аъ что
|Gn04,X;42)|>|G|/2.
(Указание. Пусть [п] = Aj + А2. Отметим, что получится
некоторое усиление, если считать At случайным членом
множества [п][п,2].)
(Ь) Пусть G ^ [п]г. Доказать существование
представления [п] s== А{ + ... + ЛГ, для которого
■\G{\(AiXA2X.-.XAr)\>\G\rlr-'.
7. Зафиксируем целое число г и с, 0<с<1. Пусть
/ (п) — такое наименьшее целое, что если G^ [n]2, | G | ^
^cv2"J' то на**Дется ГХ / (п)-двудольный подграф в G.
Показать, что
f(n) = (l+o(l))/i2-r. (*)
Расширить условия на г и с, так что (*) имеет место
(например, r<Klogn, с>п~г).
8. Зафиксируем а, 0 < а < 1. Пусть/ (я) обозначает такое
наибольшее целое, что если А — некоторая (0 — 1)-матрица
размера /гХя с по крайней мере а/г2 единицами, то найдется
подматрица размера rXs из единиц, причем rs^f(n).
Найти f (п) с точностью до множителя (1+о(1)). (Эта
задача принадлежит Г. А. Рейду.)
13. УПАКОВКИ, ПОКРЫТИЯ И ТЕОРЕМА ТУРАНА
Пусть 2^/^k^п — натуральные числа. Мы будем
обозначать через Т (п, k, I) (Г —от Турана) то наименьшее q,
для которого существует /г-вершинный /-граф с q ребрами,
не содержащий независимого множества объема k. Другими
словами, Т (n, k9 I) — это такое наименьшее число /-нод-
множеств п- множеств а V, что всякое ^-подмножество
множества V содержит по крайней мере одно из этих
/-подмножеств.
При 1 = 2 значения Т даются следующей известной
теоремой Турана.
Теорема Турана [1941]. Пусть n = {k— l)m-fa, 0^.а<
< k — 1. Тогда
Г(л,*,-2) = (Л-1)(™)+/иа. (13.1)
Мы опускаем ее доказательство как не содержащее
вероятностных аспектов.
Эта теорема часто формулируется следующим образом.
Пусть / (/г, k) обозначает наибЪлынее возможное число ребер
/г-вершинного графа, не содержащего клики объема k. Тогда
f(n,k) = (n2)-(k-\)(™)-ma, (13.2)
где m и а определены выше. Эти две формулировки туранов-
ской теоремы эквивалентны, поскольку граф не содержит
клики объема k в том и только том случае, когда его
дополнение не содержит k независимых вершин.
Теорема Турана являет собой первый пример задачи из
„экстремальной теории графов". Одна из общих проблем
этой теории заключается в нахождении для данного графа Н
того наибольшего | G |, для которого существует /г-вершинный
граф G, не содержащий Н. Случай Н = Каь был рассмотрен
в § 12.
Обобщение функции Т на большие / было впервые
предложено Тураном [1941, 1961]. Хватал [1970] составил обзор
известных результатов по Г (/г, k, I). Конструкция,
предложенная Тураном, дает верхнюю оценку
r(n^,o<(;)[-^f]'"' 03,3)
13. Упаковки, покрытия и теорема Турана 75
(см. Хватал [1970] или Катона, Неметц и Симонович [1964]).
Нижнюю оценку для Г дает
Теорема 13.1 (Катона, Неметц и Симонович [1964]).
Г (/г, ft, 1)>{] )/(*). (13.4)
Доказательство. Пусть G — наименьший /-граф на [/г],
не содержащий ft независимых вершин. Каждое /-ребро
графа G содержится ровно в f ^__/ J ft-множествах. А
поскольку любое ft-множество включает в себя некоторое
/-ребро, то
ю|(::',)>С) <13-6>
и, следовательно,
>м.о-|0|>(;У(;:!)-(;У(;)-и««»
Перефразируем это доказательство в вероятностное. Пусть
G фиксирован, а А —случайный член множества [n]k. Тогда
искомое число /-ребер графа G, содержащихся в А, равно
|Gl(bZ/)/(fc)- Если это число < 1, то некоторое А
является независимым множеством, что противоречит
условию. Это дает теорему 13.1 и служит отправной точкой для
следующего результата.
Теорема 13.2 (Спенсер [1972а]). Если n^^yly то
г («.ft, /»(£)' [-Й-]
Доказательство. Зафиксируем граф G г [п]1 (| G | =
= Г(/г, ft,/)), не содержащий ft независимых вершин. Пусть
А = Ар — случайное подмножество множества [/г], где для
любого / е [п]
Р[/еА] = р,
и эти вероятности независимы. Здесь р — константа, чье
значение будет определено ниже.
Далее,
Е(| АI) = £ Pp€=A]=pnf
Ш[п] ПЗ-7>
Е(|ОЩА]/|)= Z P[B = A]=|Glp'. Л '•■'
76
IS. Упаковки, покрытия и теорема Турана
А сейчас зафиксируем функцию выбора v, ставящую в
соответствие каждому непустому подмножеству Ss[rt]
некоторый элемент v (S) е 5. Тогда, если А ^ [п]9
А* = А- (J iv(B)} (13.8)
есть независимое множество. Так как
\А*\>\А\-\0№]11, (13.9)
то
E[\A*\]>pn-\G\pl. (13.10)
Но | Л*|^&— 1, поскольку А* независимо. Следовательно,
*-1>Е[|А'|]>ря-|0]р,| (13.11)
|G|>(p/*-(ft-l))p4 (13.12)
И поскольку ri^(k—\)//(/— 1), то, полагая P=={k—\)\j—A]n^
*^1, получаем утверждение теоремы. ■
Для получения следующего результата мы комбинируем
методы теорем 13.1 и 13.2.
Теорема 13.3. Для всякого a (k^a^n)
r(ntft,0>(a-(A-l))(J)/(;).-
ДoкAЗAtEльcтвo. Зафиксируем G s [п]19 не содержащий
k независимых вершин, | G | = Г (/г, fc, /). Пусть А = АЛ —
случайный член множества [я]а. Имеем
Е(|А|)=а, (13.13)
Е(|ОП[А]'|)*= £ P[BsA]-|G|(;)/(;). (13.14)
Be=G
Определим Л*, как в (13.8). Тогда
ft-l>E(|A'|)>a-|0|(;)/(J). (13.15)
что приводит к теореме 13.3. ■
Другое доказательство теоремы 13.3 дается в качестве
упражнения (упр. 4).
Полагая a—k в теореме 13.3, получаем теорему 13.1.
Мы утверждаем, что теорема 13.3 всегда дает несколько
улучшенный или по крайней мере такой же результат, что и
теорема 13.2, т. е.
max (а-{к-1))(пА/(аА^п1{к-Л)1-!(1-1)1-Ч-1.
(13,16)
13. Упаковки, покрытия и теорема Турана 77
Рассмотрим сначала более общий результат. Пусть
/ — произвольная действительная функция, определенная на
семействе всех подмножеств множества [п]. Тогда
E[f(Ap)] = EP(|Ap| = a)E[/(Ap)||Ap| = a] =
= SP(|Ap| = a)E[/(Aa)]. (13.17)
Здесь мы пользовались тем, что условное распределение слу-
чайной величины Ар при данном |Ар| = а совпадает с Afl.
п
А так как £ Р(| Ар| = а) = 1, то
min E[f(A*)]<Etf(Ap)]< max E[f(Aa)). (13.18)
Теперь мы можем доказать неравенство (13.16). Зафиксируем
k, I, /z>(fe — 1)//(/ — 1), р = (А — 1) (jzzj)/n- Положим
/(Л) = |Л|-(рп-(^- 1))р-^( '^' )/(7)- <13-19)
Мы требуем, чтобы
Е [('?')]= I P[B = AJ-(;)p«. (13.20)
Согласно (13.18), существует а (O^a^/z), такое, что
a«(^«(^l))r/^)/(«)sE[f(A«)]>
>E[f(bP)] = pn-(pn-{k-l))p-lpl = k-\f (13.21)
а последнее влечет (13.16).
Во многих задачах имеется выбор между использованием
Ар и Аа. В граф-теоретических задачах — выбор между GrttP
и случайным я-вершинным графом с / ребрами. Мы
предпочитаем иметь дело с Ар и Grt> р как отвечающими
стремлению выразить решение не в биномиальной, а в
экспоненциальной и, стало быть, более удобной форме. Однако, как
мы продемонстрировали, использование Afl дает лучшие
результаты. Поэтому их естественно применять там, где
требуются точные ответы, главным образом в конечных задачах.
Пока мы обсуждали Г (/г, k, I) лишь в граф-теоретическом
смысле. Из общих же комбинаторных соображений Т ста*
новится одной из четырех исследуемых ниже функций.
78
/3. Упаковки, покрытия и теорема Турина
Определения. Пусть n^k^l^2.
T(n,k, l) = min\F\: Fs[n]l9 VS<=[n]k3At=F: A s S,
t(n, k9 l) = max\F\: F^[n]1,
VAl9 A2.*=F: Au A^sS€= [/i]*==>A{ = Л2,
Af(M.0 = min|F|: F£[/if, VSeM'^eF: 4=>S,
m (n, &, /) = max | F |: > s [n]k9
VAl9A2ezF: Al9 A2 => Se= [л]'=Ф Л, = Л2.
Большей интуитивности этих определений можно
достигнуть, говоря, что множество А покрывает множество В9
если А 3 В или Л£б. Зафиксируем [п] как универсальное
множество. Тогда Т (/г, &,/) —наименьшее число /-множеств,
покрывающих все ^-множества; /(я, k, I) — наибольшее число
/-множеств, покрывающих /^-множества не более чем
единожды; М (/г, ky /) — наименьшее число ^-множеств,
покрывающих все /-множества; пг(П, k, I) — наибольшее число &-мно-
жеств, покрывающих /-множества не более чем единожды.
Теорему 13.1 легко обобщить, показав, что
*(nt*t о<(7)/(1)<зг(/|» *•
fn\tfk\ (13*2?)
Отметим, * что /(/г, k9 /)= 1, если 2/^6. Функции Mum
исследовались Шёнхеймом [1966].
Определение, (л, k, /фактической конфигурацией (т.к.)
называется такое семейство Fe [n]k, что всякое /-множество
покрывает в точности один член из F.
Если такая т. к. существует, то М (п, k9 l)=m(nt k, l) =
= v / )/( / )' Подробно изучались вопросы существования
и строения тактических конфигураций. (Например, (/г, 3,2)-т. к.,
называемые ^системами Штейнера, впервые исследовались
в 1847 г. (см. Холл [1967]).) Оценочные рассуждения
показывают, что если (п9 k9 /)-тактическая конфигурация
существует, то
(я-| + /)/(*"5+/)-целое число для /=1,..., / (13.23)
(см. Ханани [I960]). В частности, (13.23) влечет, что п для
фиксированных k и / должно удовлетворять определенному
конгруэнтному условию, Ханани [1960, 1961] было показано,
что условие (13.23) является и достаточным для существова-
13. Упаковки, покрытия и теорема Турана
79
ния (я, fe, /)-т. к. при {k, 0 = (3.2), (4.2), (5.2), (4.3). Однако
условие (13.23) не всегда является достаточным. Например,
(/г2 + я+ 1, /t+ 1, 1)-тактическая конфигурация эквивалентна
проективной плоскости порядка п. Условия (13.23) выполнены,
а знаменитая теорема Брука и Райзера [1949] дает
бесконечный класс тех /г, для которых проективные плоскости не
существуют. *
Нетрудно показать, что для тех фиксированных k и / и /г,
стремящегося к бесконечности, которые удовлетворяют
условиям (13.23), число неизоморфных (n, k, /):т. к. стремится
к бесконечности очень быстро. Дойеном [1970] этот факт был
доказан для троек Штейнера (k = 3, 1 = 2). Возможно, такие
схемы и можно построить при помощи вероятностных методов.
Но, вероятно, все-таки здесь потребуется новая идея, потому
что конструируемые схемы являются „точными" объектами.
Заметим также, что построения схем другого типа, например
матриц Адамара, может допускать использования
вероятностных идей. К сожалению, способности авторов оказались
недостаточными для построения такой конструкции.
Эрдёш и Ханани [1963] предполагают, что для
фиксированных k и I
HmM(n,M(f)/(^ (13.24)
(см. упр. 1 и 2). Конструктивными методами они доказали
(13.24) для 1 = 2 при всех k и для 1 = 3 при k = p или р+ 1,
где р—-степень простого числа. Эта гипотеза также
представляется подходящим кандидатом для использования
вероятностного метода, хотя мы пока и не в состоянии
применить его здесь. Вероятностные методы позволяют получить
следующую верхнюю оценку для М.
Теорема 13.4. М(п, *,/)<[( * )/( *)][l + log ( *)].
Доказательство. Нам надо найти семейство F^[n]k,
которое покрывает все /-множества. Пусть Sj, S2, ...
—случайные члены множества [п]1; положим Fx = {S^ ..., S*}.
Пусть и (Fx) = {А е [п]1: А ^ Si? 1 ^ i ^ х) — множество
непокрытых /-множеств. А поскольку
PMSU<F,)l = [l-(«)/(»)]*,
Eii«(F,)i]=(;)[i-(^)/c;)f. 03.25)
80
13. Упатвки, покрытия и теорема Турана
Пусть v: [n]l->[n]k — функция выбора, такая, что v(A)^A.
Тогда для всякого F семейство
F**=F[){v(A): As=u(F)} (13.26)
покрывает все /-множества. Таким образом,
епкп<*+(?)[1-(*)/(;)]". сад
Положим * = [( "i )/( / )1 log Г А (см. упр. 3). Выберем FX9
такое, что | F^ |<Е [| К I] <[( J)/( J)][l + log ( {)]. ш
Получение столь же хорошей нижней оценки для m(/z, k> I)
представляется затруднительным. Лучшее, что мы можем
показать, это
m(n, k, 1)>Т(п, k, /)/({)• (13-28)
Для доказательства(13.28) заметим, что семейство из tn(n,k,l)
^-множеств покрывает m (n, k, l)( , J /-множеств. Поскольку
больше нет /г-множеств, которые можно добавить, не
покрывши какое-то /-множество дважды, то /-множества должны
покрывать все ^-множества. Таким образом, m(п,k, I) ( А^
>Т(п, k, I).
Упражнения
1. Доказать, что Mm М{п, k, 1)( /)/(*) и lim пг'(п, k, /)Х
Х( /)/(/) существуют. (Указание. Для М достаточно
показать, что функция М(п, k, I) ( /)/(/) является
монотонно убывающей по /г. Пусть щ<пъ a F S [n2]k покрывает
все /-множества. Тогда для каждого S^[n2]ni справедливо
\F(][S]k]\>M(nly ft,/)-)
2. Доказать, что lim М (n, k, 1) ( 1 )[{ * ) = 1 тогда и только
тогда, когда lim/n (/г, £,/)(/ )/( "А = 1.
3. Доказательство теоремы 13.4 не совсем точно, потому
что х = Г Г " V Г - J] log ( l J не всегда целое число.
Привести точное доказательство, заменив F* на Fp S [n]k, такое,
что-Р И eF,] = p = */(;).
13. Упаковки, покрытия и теорема Турана
81
4. (Катона, Неметц и Симонович [1964]). Доказать
"(а) Г(n, k, l)^n — k + 1, \Т(п, k, I) — п — &+ 1 тогда
и только тогда, когда п — fe+1^14" •
(b) Т(п9 k, l)( * J монотонно возрастает по п. Используя
(а) и (Ь), доказать теорему 13.3.
5. Пусть п^1 целое, O^p^l. Доказать
Ёкгуо-^-кгьоу.
(Указание. Использовать (13.17) при / (А) = ( ' ' ' J . J
6. Доказать
п2п < Т (2/г2, /г2, п) < п22п (2 log 2 + о (1)).
7. Доказать
Т(2г, г, k)>m(k),
где m определено, как в § 4.
8. (Эрдёш и Хайнал 1968]). Пусть f: 2W-+[n], причем
для всякого 1д[п], \(Х)фХ. Назовем S независимым, если
X ^ S=#f (X) 9= S. Положим g* (/г) равным тому наибольшему
целому, для которого у всякого таким образом
определенного отображения f существует независимое множество S,
\S\^g(n)- Доказать, что
log2 п — сх log log п < g (п) < log2 п + с2 log log /г.
9. Пусть f: 2ln]-+[ri\. Назовем множество X^[п] полным,
если
U f(S)=[n].
Назовем f r-цолным, если из \Х\^г следует полнота X.
Пусть g(n) —-то наименьшее целое, для которого существует
r-полное f; 21п]->[п]. Доказать
log2п <g (л)< log2/г + log2log2n-f 0(1),
Верно ли, что
g(n) = log2n + 0(l) (?).
14. АСИММЕТРИЧЕСКИЕ ГРАФЫ
Автоморфизмом графа G называется такая перестановка
его вершин а, для которой а (G) = G, т. е. {л;, у} ^ G тогда
и только тогда, когда {а (х), а (у)} е G. Граф называют
симметрическим, если он обладает автоморфизмом, отличным
от тождественного, в противном случае он называется
асимметрическим.
Мы приведем несколько простейших результатов о
перестановках. Всякая перестановка а допускает циклическое
представление
а = (&ц, ..., Ь\сх)(Ь2и •-., Ь2с2) ... (bru ..., brcr), (14.1)
которая означает, что
а (Ьц) = Ь,, /+1. (1 </ < ch mod с().
Если or имеет аЛ циклов длины &, то будем говорить, что а
'имеет циклический тип
1^ ... па*. (14.2)
Число различных g с одним таким циклическим типом равно
-ТГ^ • 04.3)
Если граф G асимметрический, то его можно сделать
симметрическим посредством добавления и (или) удаления
Некоторых ребер. Асимметрия графа G, обозначаемая через
-4(G), определяется как то наименьшее количество ребер,
удаление и (или) добавление которых приводит к
симметрическому графу. Иными словами, A(G) = mih\D\9 где D
—такое множество ребер, что граф GAD — симметрический.
Теорема 14.1 (Эрдёш и Реньи [1963]). Пусть G = Gn —
граф на п вершинах. Тогда
i4(G)<(/i-l)/2.
Доказательство. Для 1<д:</г положим
§* = {!/: {х, у} ezGl
14. Асимметрические графы
83
Тогда
{х,у} г
= Z|Sz|(n-l-|SJ)<
<Аг(я-1)2/4. (14.4)
А поскольку левая qacfb неравенства (14.4) имеет п{п—\)[2
слагаемых, то | Sx hSy — {*, у) |^ (п — 1)/2. Зафиксируем х>у
и положим
D = {{*, 2}: гфх, у; zs=lSz &Sy}. (14.5)
Но тогда граф G AD обладает автоморфизмом а = (ху) (для
краткости мы не записываем циклы единичной длины).
И, кроме того,
{DKIS^AS,-!*, 0}l<(/i-l)/2. ■ (14.6)
Теорема 14.2 (Эрдёш и Реньи [1963]). Если С > 1, а п
достаточно велико, то найдется такой п-вершинный граф G, что
Л (G)>-J —С У я log я.
Доказательство. Пусть G = Gn, уж — случайный граф на п
вершинах. Покажем, что
Р[За=тМ, 3D, |D|<|-~Cy^bg^,a(GAZ)) = GAZ)]<l.
(14.7)
Для каждого аф\ положим m(G, а) равным тому
наименьшему j D |, для которого a (G AD) = G AD. Кроме того, положим
р (а) = Р [m (G, a)< ~ - С У* log я]. (14.8)
Итак, нам достаточно показать, что
£Р(а)<1. (14.9)
Для доказательства (14.9) будем оценивать Р (о) при
а=5^1. Во-первых, воспользуемся условием, что a(G AD)=G AD.
Предположим, что a =^= 1 имеет циклический тип l0^*2... azV
Введем в рассмотрение граф Н (а). Его вершины суть все Г g )
элементов е множества [/г]2. Ребро fo, е2} принадлежит Н(о)
тогда и только тогда, когда е2 = о(ех). Вершина e = {i, j)
является изолированной в Н (а) тогда и только тогда,, когда
о(е) = е. А последнее имеет место в том и только том слу-
84
14. Асимметрические графы
чае, если а (/) = / и а (/) =/ (что имеет место в ( а* J случаях J
или если {/, /} является 2-циклом (что имеет место в а2
случаях). Остальные ( *) — ( ^ J — а2 вершин все имеют
степень 2 и, следовательно, образуют систему
непересекающихся циклов.
Переобозначим нефиксированные члены [п]2 через eif
(1</<*, 1</<^), так, что (eify ^,/+1)^Я(а), где /+ 1
йодсЧйтывается по модулю йь. Тогда (x(GAD)=GAZ) в том
и только том случае, когда для 1 ^/^ либо все ец eGAi),
либо все ец 9= О AD. То наименьшее £>, для которого a (G Д£>)=
==GAZ), определяется из условий (1^/<!/):
ОПЫ^ЫПО или ЫПО6 (НЛО)
в зависимости от того, что меньше. Положим
если ^gG,
в противном случае.
Тогда X// суть независимые случайные величины и
dt dj
tn'~ ч ^
Положим
'«"{о1
(14.11)
(G, <т)= £ min [2 Х,у, dt- £ X J . (14.12)
Y, - min \ £ X,„ d, - Z Xt7l. (14.13)
Сейчас мы оценим P(а). Пусть q(a) = n — ax = | {i: a (t)^*} |.
Случай 1. <7(a)*=2. Тогда a =*(//) й Я (a) являет собой
объединение я — 2 циклов длины 2 ({^ я}, {/, а:} для хф-i, /),
В этом случае Yt суть независимые (0— 1)-случайные
величины и, значит,
р (?) - р Ё Y* < Т ^ С V^iTTI = о (п-2), (14.14)
поскольку С > 1.
Случай 2. (7 (а) = 3. Тогда a = (tjk) и Я (а) есть
объединение п — 2 циклов длины 3 ({«, /}, {/, £}, {/, k) и {/, *}, {/, л:},
{k, х) для хфг, U Ь). Тогда Y^ ^= 0 или 1, P(Y,= l) = 3/4
и Y* — независимые, следовательно,
р («) * Р [Е Y< < Т ~ С V^i71 < (V3/2)". (14.15)
14. Асимметрические графы
85
Случай 3. q{o)^4. Как и в случае q(а) = 3, Р(а)
„экспоненциально мало" для q(a)^4. Действительно (см. упр. 6),
Р(о)<п-<*М-2 для ?(а)>4. (14.16)
Число тех а, у которых q(o) = q> равно
(aMil-l№~Tir$fiT~*-- П4Л7)
Таким образом,
Z Р(а)< л2 (о (/г-2)) + /г3(л/з/2)Л+ Z я*/г-*-2 < 1. И (14.18)
Мы предполагаем, что существует такая , константа С,
что для всякого п найдется /г-вершинный граф Я, у
которого А (#) > /г/2 — С. Следующие абзацы посвящены
обсуждению вероятностного доказательства „в развитии" 1).
Пусть п — простое и /z = 1 (mod 4). Пусть G — граф с
вершинами [/г], причем {/, /} е G тогда и только тогда, когда
*' — / есть точный квадрат по модулю п. Пусть G^G^p, где
р= Ю000 logф. Положим H = GAG. Тогда
а (Н) ЛН = (a (G) AG) А (а (G) AG). (14.19)
Случай 1. <7 (<*) ^ я/50. Можно отыскать * таких ребер
*и • • •> еь t > /г2/1000, что все эти et и a""1 (et) различны. Для
1^/<^ положим
если ^^а(Н)Д(Н),
если е^а(Н)А(Н). (Й'20)
Тогда Yt — независимые (0 — 1)-случайные величины, причем
^ г^ ч Г 2р — p2t если et е a (G) AG,
р у,-1 =±=< „ р* ' '/ (14.21)
1 * J ( (1— р)2, если et<^a(G)AG, х '
и, значит,
Р [ | а (Н) АН |< /г] < Р [ £ Y< < /г] < (/г!)"1. (14.22)
Случай 2. З^^(а) </г/50. Здесь и в случае 3
используется тот факт (Сторер [1967]), что для всех 1Ф]
\{k+l,j: {/,*}е04Ф{Д*}^0}| = ^1.- (14.23)
'-{»:
*) О существенном улучшении этих результатов, полученном младшим
автором, можно узнать у него.
86
f4. Асимметрические графы
Таким образом, мы можем показать, что| GAa(G) \^0>45nq(o).
Значит, поскольку | {е: о(е) фё\ \ <nq (а), вероятность
Й[|Н Aa(H)|<y]<P[|G Aa (G)|>n [0.459(a)-0,5]] (14.24)
очень мала.
Случай 3. ^(а) = 2. Тогда a =■(//)., G Aa(G) ==-!Цр-.
Следовательно, для достаточно большого С
Р [ | G Да (G) | > С (log я)2] < /г-2. (14.25)
Комбинирование этих случаев (см. упр. 2) приводит к
Р[Зоф1, |HAa(H)J<n/2-C(log/i)2J<lf (14.26)
т. е. существует граф //, у которого
А (Н) >±- С (logл)2. (14.27)
Вероятно, этот результат можно усилить различными
способами.
(1) Положим р = 10 000//г. Случай 2 остается прежним.
Случай 1 может дать Р [ | а (Н) АН | < п] < е~ш. Если a
таково, что \G Aa (G)|>nH6, то Р [ | а (Н) АН |<л] <
< рп1+ <С п\~х. Случай 1 можно усилить, если показать, что
<еш из а имеют | GAa (G) |</г1+б. Тогда случай 3 мог бы
дать, что А (Н) > у — С log п.
(2) Пусть G — случайный регулярный граф, в котором
каждая вершина имеет степень 10 000. Результаты о G
аналогичны результатам о регулярных турнирах (§ 10),
которыми и можно воспользоваться. Случай 3 мог бы дать
A'(H) > у -20000.
(3) Для непростого я ===1 (mod 4) нужно найти G на [/г],
такой, что все вершины имеют степень у + a с \а\<Сх
и для всех /, /:
\(k:{i9k)<=G&{l9k}&G)\ = % + b |р|<С2.
Обратимся к задаче Гольдберга. Он определяет объем
графа ка;< наибольшее число неизоморфных подграфов этого
графа. Затем он полагает v (п) равным наибольшему объему
графа на п вершинах. Очевидно v (п) ^2пу так как всякий
граф имеет 2п подграфов. Гольдберга заинтересовал предел
iim v{n)2~n.
14. Асимметрические графы
87
Задача Гольдберга приведена у Визинга [1968],, а
решение дано Коршуновым [1971].
Пусть G = G/lti/2. Посредством весьма грубых оценок
покажем, что G имеет объем >2"(1 — о(1)) с вероятностью,
стремящейся к 1. Это дает равенство lim v{n)2"n= 1. Более
точные оценки для v (/г), использующие этот метод,
приведены в качестве упр. 5.
Пусть S^{1, ..., м}, |S| = f. Оценим вероятность того,
что найдется некоторый другой подграф, изоморфный
подграфу G|S. Пусть р — функция от вершин графа S со
значениями в {1, ..., п). Положим g(p) = | {/: р(1)ф1}1
Подсчитаем число тех ребер полного графа на S, для которых
р(е)фе. Если p(i)=i и р (/) ф /, то {/,/}•—именно такое
ребро. Также все, кроме не более чем g (р)/2 ребер {/, /},
Р (О Ф *\ Р (/) Ф /» являются таковыми. Полагая g== g (р),
получаем по крайней мере
g«-g) + (|)~| = g(^-4~l) ^(14.28)
таких ребер. Введем граф Н (р); его вершины суть ребра е
полного графа на S, а ребра — р(е). Мы связываем е с р(е).
Все вершины имеют степень <J2, т. е. граф состоит из
изолированных вершин, циклов и путей. Можно найти
еи ..., es, такие, что е{ ..., es, р {ех)у ..., р (es) все различны,
W - s>e(f-|-.l)/3. (И.29)
Тогда Р [S изоморфен р (S)] < 2" \ Имеется менее чем n2g
функций р с g (р) = g. Следовательно, вероятность того, что
некоторое р Ф 1 дает изоморфизм с G|S, оценивается для
t^CXogn так:
tng2-s{t-g,2-m = o(l). (14.30)
Значит, почти все |S|^Clog/z, и
и (л) > 2* (1-о(1)). (14.31)
Упражнения
1. Положим А{ (G) =min| G Aa(G) |. Исследовать связи
между A (G) и А{ (G) и доказать для последнего результаты,
аналогичные теоремам 14.1 и 14.2.
2. Дать подробное доказательство того, что для
я== 1 (mod 4), п — простое, существует граф Н на п вершинах,
для которого /т^Л ,w, л2
88
14. Асимметрические графы
3. (Тема диссертации.) Доказать или опровергнуть
существование константы С, такой, что для всех п существует
n-вершинный граф Н, для которого
л(#)>|-с.
{Отречение. Авторы не гарантируют, что успешное решение
этого вопроса будет приемлемой диссертацией. Даже если
руководителем будет один из авторов.)
4. В теореме 14.1 граф можно симметризовать удалением
многих ребер, исходящих из одной вершины. Было бы
интересно исследовать асимметрию, в которой число ребер,
удаляемых из данной вершины, лимитировано. Например, пусть
d (D) обозначает наибольшую степень вершины в графе D.
Положим
/ (п) = max min d (D).
Oc[n]J Dcz[nY
G AD симметричен
Доказать, что f(n) = 0(n).
5. Найти точные оценки для наибольшего объема v{n).
6. Доказать (14.16). Это в действительности очень слабая
оценка для Р (а).
Задачи 7 и 8 касаются вариантов теоремы 14.1.
7. Назовем граф Gs[/z]2 нетривиально симметричным,
если существует перестановка 6gS„ с нефиксированными
точками (т. е. q(o) = n)> такая, что <r(G) = G. Положим
f (п)= max min | Z> |,
G & [п]'
где GAD — нетривиально симметричен. Доказать, что
/(")=£ (i+o(D).
{Указание. Для нижней оценки рассмотреть случайный граф G.
Для верхней оценки зафиксировать G и рассмотреть
случайную перестановку о с циклическим типом 2п/ ).
8. Назовем граф G s [п]2 циклически симметричным, если
существует цикл а е Sn, такой, что a (G) = G. Положим
f{n) = max min | D |,
G s [n]'
где G AD — циклически симметричен. Полагая D = G или Gct
видим, что ДяХу^)-
(a) Доказать, что f{n) = |(£) (1 + о(1))..
(b) (?) Дать оценки для j ( * ) — / (я),
15. ЗАДАЧИ О БАЛАНСИРОВКЕ МАТРИЦ
Пусть А = (а,ц), ац = ±1, обозначает матрицу размера
лХл. (На протяжений этого параграфа элементы всех
матриц суть + 1 или — 1.) Допустимо умножить любую строку
или столбец на — 1 с целью минимизации абсолютной вели*
чины суммы всех элементов матрицы,
сбалансировать количество +1 и — 1,
можно. Например, пусть п = 8 и
То есть мы хотим
насколько это воз-
Х =
Г +
+
+
+
+
+
+
L+
+
+
—
—
—
+
—
+
+
+
+
—
—
—
+
—
+
—
+
+
—
—
—
+
+
+
—
+.
+
—
—
—
+
—
+
—
+
+
—
—
+
—
—
+
—
+
+
+
пос
с
+ -
—
—
—
+
—
+
трочные
уммы
[8
0
0
0
0
0
0
+ -U
общая сумма = 10
Меняя знаки во втором столбце, получаем следующие
построчные суммы: 6, —2, 2, 2, 2, —2, 2, 0 соответственно;
общая сумма остается равной 10. Перемена знаков в строке —
замена строки ее негативом — меняет знак построчной суммы.
Перемена знаков в третьей и четвертой строках да^т
построчные суммы 6, —2, —2, —2, 2, —2, 2, 0 при полной сумме 2.
Это и есть наименьшее возможное значение абсолютной
величины полной суммы. Поскольку п четно, то все линии (строки
или столбцы) имеют четную сумму 2k. Следовательно,
перемена знаков в линии меняет полную сумму на 4k. Таким
образом, после любого числа перемен знаков в линиях
полная сумма = 2 (mod 4).
Нас интересует то наименьшее Snt при котором в любой
данной матрице А размера /гХ^ можно переменить знаки
в линиях так, чтобы абсолютное значение полной £уммы tie
превзошло Sn. Более точно, положим
Sn = max min
(ац) *г уi
(15.1)
90
15. Задачи о балансировке матриц
где xh i/j — zLl представляют собой операцию изменения
знаков в строке и столбце соответственно. Если п четно, то,
полагая, что А — матрица размера ^/гХя с суммой,
равной 2, получаем, что Sn^2. Если п нечетно, то Sn^l,
поскольку сумма любого нечетного числа плюс или минус
единиц не может обращаться в 0. Следующий результат был
впервые в качестве гипотезы сформулирован Мозером.
Теорема 15.1. (Комлош и Шуёк [1969]). Существует такое щ,
что для п^п0
если п четно,
если п нечетно.
«•-{ I
Доказательство. Мы выбираем п0 достаточно большим,
чтобы иметь возможность аппроксимировать. Зафиксируем
матрицу А = (а,ц) размера п X /г. Обозначим строки мат-
-> -> -> •> .
рицы А через ги ..., гп. Если Ь = (Ьи ..., Ьп) и с = (си ...
• ••» сл)~-Два каких-то вектора, то определим
bc = (bLcu ..., bncn) (15.2)
s(b) = Zbi. (15.3)
Пусть у = (ylf ..., уп) — случайный вектор с координатами
±1. Тогда s(y) имеет распределение Sni определенное в § 3.
Отметим, и это существенно, что для любого
фиксированного г{ вектор у г,- имеет распределение случайного вектора
-> ->
с координатами ± 1 и, следовательно, s (yrf) имеет
распределение Sn.
Лемма 15.1. С вероятностью > 1 — 1/п выполняется
неравенство
->-> . ~_
\s{yrt)\< ySnlogn для 1</</г. (15;4)
Доказательство. Р [3/, 1 < / < п, \s (yrt) | > *Jbn log п\ <
</tP[|SJ>V5nlogAz]<~. я
Нам потребуется следующая лемма, представляющая и
самостоятельный интерес.
Лемма 15.2. Если X — случайная величина со средним
Е(Х)=Ф и тах(Х) = #, то для h^.\x
>1Х>Л]>(и-Я)/(^-Я). (15.5)
15. Задачи о балансировке матрице 91
■-Ъ
Доказательство. Пусть
если Х>Я,
в противном случае.
Тогда
ZXX-ЩАГ-Я) (15.6)
и, значит,
PlX>X] = E(Z)>El(X-X)/(iV-X)] = (|i-a,)/(Ar-^ ■
(15.7)
* Лемма 15.3. Положим
X = \{i: |5(y^)|<Vl0001og«}|/ (16.8)
Тогда с вероятностью > \\п
X>V70nlogn. (15.9)
Доказательство. Ясно, что
Е [X] = пР [ | Sn | < V Ю00 log/i]> VlOOnlogn
и (15.10)
max (X) = п.
Лемма 15.3 немедленно следует из леммы 15.2. ■
Зафиксируем */, удовлетворяющий (15.4) и (15.9).
Положим M = (aifyI) = {mij). Обозначим строки матрицы М через
ri, ..., г*п> а их построчные суммы через г*, . .<, г*п.
Положим t = {<y/l000logn}. Тогда мы перенумеруем для удобства
строки так, чтобы
., | г}\ < г для 1 < i < <\/70п log п,
1 ,- Г^ (15.11)
I U I ^ уЬп log п для всех «.
Начиная с этого места, мы отходим от оригинального
доказательства. Пусть z = (zb ..., zn) — случайный ±1-век-
тор с числом компонент Z/ = -—1, равным [(* — 1)/2].
Случай 1. я нечетно. Если г — некоторый я-вектор из ±1
Q | S (Г) К*, ТО
Р[|вЙ|=1]=-2Ч('-1)/21. (15.12)
Поэтому
EtJ{*: l<*<Y70/ilog/i, | s(r?z) |= l}|] > V70nlogAz2-(^1)/2.
(15.13)
92
IS. Задачи о балансировке матриц
Следовательно, можно отыскать такой вектор г, положив
N = (muZf) с построчными суммами г**, ..., г*п% для которого
(1) все | гТ I <У5я log п + 2 [(# — 1)/2],
(2) К|гП<< + 2[(/-~1)/2] для 1 < / < V70n log «,
(3) | гГ | = 1 для по крайней мере л/lQn log п 2~('~"1)/2 строк.
(В (2), 1<|г?*1 потому, что сумма нечетного числа плюс
или минус единиц не может быть нулем. Поскольку лишь
[(/—1)/2] столбцов меняют знаки своих членов, то все
построчные суммы меняются не более чем на 2[(t— 1)/2], что
и дает верхние оценки (1) и (2).) Разбор случая 1
завершается упр. 1.
Случай 2. п четно. Как и в случае 1, можно найти
такую матрицу N, чьи построчные суммы удовлетворяют
условиям
(1) все |гГКл/^П^ + 2[(^1)/2],
(2) |/Л<* + 2[(*-1)/2] для K/<y70/ilog/i,
(3) |r**l = 2 для по крайней мере V^Onlog n2~{i~~m строк.
Здесь допустимо некоторое уточнение, потому что может
статься, что многие г?* —О в (2). Если меньше половины
всех гГ^О в (2), то мы можем заменить (2) на
(2') 2<|гГК' + 2[(*-1)/2] для K/<y[V70nlog4
и доказательство завершается упр. 1. Если же половина всех
г** = 0 в (2), то переменим знаки в одном любом столбце.
Тогда, обозначая новые построчные суммы через г***, имеем
(Г) все |г™|<<y/5nlogn +2[(t- 1)/2] + 2,
(2) |г***| = 2 для по крайней мере -%<^70nlogn строк,
и вновь доказательство завершается упр. 1. ■
Сейчас мы попытаемся использовать замену негативом
для максимизации разницы между количеством +1 и — 1.
Каково то наибольшее целое Вп, что для всякой матрицы А
размера /гХя существует замена линии ее негативом, при
которой полная сумма будет не меньше Вп? Более точно,
положим
firt = minmax £ а//ад. (15.14)
15. Задачи о балансировке матриц
93
Теорема 15.2 (Браун и Спенсер [1971]).
(л/т + о(1))я3/2<Вл<(1 + о(1))п3/з-
Доказательство. Докажем сначала нижнюю оценку. За-
фиксируем матрицу X размера пУ^п со строками ги ..., гп.
Для всякого у = {у\у ..., уп) можно подобрать такое xh что
п
Yuanxi\l\^§ для 1</<я. (15.15)
Поэтому
(15.16)
WMi = £ | S aiiVt = Z U (рт*)
Пусть у —случайный вектор, тогда
Ж [ 15 (у г) I ] = Е [ I Srt | ] = V^" д/1"(1+о(1))- (15Л7)
Таким образом,
е|£|5Й|1 = ^д/Х[(1 + о(1)). (15.18)
Следовательно, мы можем зафиксировать такие уи ..., уп,
Х\9 ..... *я, что
£ я*/ЗД/>/*3/2д/т (1+о(1)). (15.19)
Для доказательства верхней оценки рассмотрим
некоторое обобщение. Пусть В (т, п) — то наибольшее целое, для
которого во всякой матрице А размера тХя можно так
заменять линии негативом, чтобы ее полная сумма была не
меньше чем В(туп). Тогда Вп = В(п, п). Для данных т
и п имеется 2тп различных матриц Л. Образуем классы
эквивалентности, полагая, что Ах ~ Л2, если от А{ к А2 можно
перейти посредством замены линий негативом. Легко
показать, что имеется некоторое рекурсивное соотношение и что
в каждом классе содержится 2т+п"х матриц. (Отметим, что
замена всех строк и всех столбцов негативом даст исходную
матрицу.) Таким образом, есть 2тп~т~п+{ классов
эквивалентности, каждый из которых содержит матрицу с полной
суммой ^В(т, /г). Следовательно,
P[Smrt>B(m, /г)]=|{А: Е ац>В (m, п) |/2W,I>2!-W-*.
(15.20)
9!" 15, Задачи о балансировке матриц
Применяя (3.2), находим, что
В (пг, п) < 2 У log 2 <yjmn(m + n — l), (15.21)
и в частности
Brt = B(/i, л) < 28Vlog2""8V (15.22)
Для усиления (15.22) используем специальную матрицу.
Матрица Н = {кц) размера /г X я называется матрицей Ада-
мара, если и л ее строк взаимно ортогональны, и п ее
столбцов взаимно ортогональны. Матрицы Адамара являлись
объектом многих исследований (см., например, Холл [1§67]).
Для всех б > 0, если п достаточно велико, существует
матрица Адамара некоторого порядка т, п(1—б)<т^д.
(Это следует из существования матриц Адамара порядка 4*12'
и теоретико-числового результата о том, что эти числа плотны
в определенном смысле.)
Предположим, что матрица Адамара порядка п
существует; зафиксируем ее. Замена негативом сохраняет свойство
адамаровости. Покажем1)» что Вп*^.п*1г, доказав, что дЛя
любой матрицы Адамара H = (hlf) имеет место неравенство
X) hu^n4K Пусть ги ..., гп обозначают строки матрицЫ'Я.
Для v = (vlt ..., vn) пусть || v || = ( £ v\ 1 — евклидова
норма. Положим 1 = (1, ..., 1). Тогда
Efy-f&rATdZrJllTll (15.23)
по неравенству Коши — Шварца. Поскольку Я адамарова,
то rf ортогональны и, стало быть,
1А ■> II Г А -> T/f
Zrt - ZlIMP -п. (15.24)
i-i y Li—i J
Поэтому
ЕА//<|Ег||||Т||-я\ (15.25)
и l llz-i II
У Это рассуждение принадлежит Дж. X. Линд сею.
J5. Задачи о балансировке матриц 95
Предположим теперь, что п не является порядком матрицы
Адамара. Положим n = m + s, и матрица Адамара Нт
существует, а 5==о (/г).
m
s
т
Нт
s
Al
А2
Мы определяем матрицу размера /гХя ее тремя
компонентами так, как это показано на рисунке. Нт — матрица
Адамара. Ах такова, что после любой замены негативом ее сумма
^J3(m, s). А2 такова, что после всякой замены негативом
ее сумма ^ В (s, п). Значит, после любой такой операции
сумма матрицы не будет превосходить m3'2 + B(m? s)+
+ B(s,/i)<.(i+o(l))/i''«. ■
Гордоном и Витшенхаузеном [1972] были получены
обобщения этого результата.
Упражнения
1. Пусть tu ..., tn — такие целые, что
(1) все l/iK^i,
(2) 1^|^|^а2 для по крайней мере А2 штук,
(3) 1<|^|^а3 для по крайней мере Л3 штук.
Предположим, что Аъ^а2, А2^а{. Показать
существование таких хи ..., хЛ = ± 1, что
п
Применить этот результат для завершения доказательства
теоремы 15.1.
2. . (Спенсер [неопубликовано]). Применить
доказательство теоремы 15.2 для доказательства теоремы 15.2 при всех
п>0.
(Для решения этой задачи, видимо, потребуется
небольшая вычислительная машина. Использовать леммы 15.1 —г 15.3
для отыскания такого fn{k,l)> что всякая матрица А
размера /гХя может быть преобразована так, что все |г*|^&,
а для fn(k, I) из них |rj|^/. Этот способ, видимо, лучше,
чем преобразование более [(/— 1)/2] столбцов для получения
многих (г* 1=1 или 2.)
96
15. Задачи о балансировке матриц
3. (а) Обобщить (15.18) для доказательства
В (я, m)>mEllSJ].
(b) Доказать, что если 2n~l\m, то в (а) имеет место
равенство. То есть, что
\п12\
(c) Пусть п фиксировано. Доказать, что для достаточно
большого m
В (/г, щ + Г^К) = В(п, т) + КВ(п, 2п~[) (К>0, целое).
Поэтому В (/г, т) можно рассматривать как линейную форму
„малых значений" т и 2я"1.
(d) Найти В (2, т), 5(3, т) и В (4, т) для всех т.
16. ЭВОЛЮЦИИ СЛУЧАЙНЫХ ГРАФОВ
В предыдущих параграфах мы показали, каким образом
можно использовать случайные объекты (графы, матрицы,
раскраски и т. п.) для доказательства комбинаторных
теорем. В этом параграфе свойства случайных объектов
изучаются непосредственно. Здесь уже понадобится в некоторой
степени большее знание теории вероятностей, нежели
в предшествующих параграфах. Доказательства будут либо
поверхностными, либо не будут приводиться вовсе, и много
материала будет представлено в качестве упражнений.
Большинство результатов этой главы принадлежит П. Эрдёшу и
А. Реньи.
Сильным орудием при изучении случайных объектов
служит „метод вторых моментов". Мы приводим пример из § 5.
Пусть C=*(Ki, К2)—случайное расцвечивание множества [п]2.
Мы уже показали, что С не содержит полного
монохроматического подграфа на (2 log2п) (I + е) вершинах. (Мы
говорим, что С (или G) присуще какое-то свойство, если С (или G)
обладает этим свойством с вероятностью 1 — о (1).)
Покажем, что этот результат является наилучшим из возможных
в следующем смысле.
Теорема 16.1. Пусть е>0 фиксировано, a t = [(2 log2/z)X
Х(1—-е)]. Тогда С содержит полный монохроматический
подграф на t вершинах.
Доказательство.' Пусть Sh 1 < i ^ ( " J , пробегает все
члены множества [n]f. Мы доказываем более сильный
результат, что некоторое [S*]2sKi. Положим
1, если [S,]2sKi,
О в противном случае.
"-{
(16.1)
Пусть
Положим
(?)
Y=ZX,. (16.2)
1 = 1
-«)=
Е(Х,). (16.3)
98
16. Эволюции случайных графов
Тогда
Е(¥) = (?)ц>1.
(16.4)
В§5 E(Y)<1 при / = (21og2/t)(l+е), откуда
очевидно следует, что P[Y > 0]=<E(Y) -С 1. Из полученного
соотношения (16.4) автоматически не следует, что
P[Y = 0] = o(l) (?) (16.5)
(см. упр. 8). Мы должны рассмотреть второй момент Var(Y).
Вообще
P[Y = 0]<Var(Y)/E(Y)2. (16.6)
Следовательно, для доказательства (16.5) и тем самым
теоремы 16.1 нужно показать, что
Var(Y) = o(E(Y)2) (?).
(16.7)
Но
Var (Y) = Е (Y2) - Е (Y)2
■■*, i-t
(")
~£ [Е(Х;Х,)]-^]
~[Ш=
(16.8)
/. /-1
Отсюда
E(XiX,) = P[Xi=l=Xt]^
= P[X,= 1|X/ = 1]P[X/=1] =
Var(Y) = (^)2EIJlE[X,XJ]-ti2] =
CM
Р[Х,=*1|Х, = 1]
]•
P[X, = 1]
где 1, J — независимые случайные члены множества
Таким образом, достаточно показать, что
Р[Х,-1|Х,-1]
(16.9)
(16.10)
к;)]-
Е
[•
-] = 1 +о(1) (?). (16.11)
P[X|=V]
Левая часть выражения (16.11) равна Е , гдеиНйПЗ)!-
Из соображений симметрии можно предполагать, что Sj =
16. Эволюции случайных графов 93
= Sj — фиксированное /-множество. Тогда, согласно
элементарным вычислениям, левая часть выражения (16.11) равна
' г(жгг:у
I
С)
,G)_
1+0(1). ■ (16.12)
Вообще, если Y есть сумма одинаково распределенных
(О—1)-случайных величин X, и E(Y)->°o, то (16.11) влечет
(16.5) (см. упр. 1 и 2).
Пусть G = Grtte—случайный /г-вершинный граф с е ребрают.
Мы интересуемся эволюцией G при растущем е. Приведенные
далее без ссылок результаты принадлежат Эрдёшу и Реньи
{I960]. Пусть А — некоторое свойство графа (например,
связность, планарность). Положим
Pn,e{A) = P[Gn.e обладает свойством Л]. (16.13)
А(п) называется пороговой функцией для свойства Л, если
ГО, если N{n)/A{n)-+0,
11тРп,Ы(п)(А) = <. А7/ ,1Л, ч (16.14)
л-х» n'NKn' (1, если N(п)/А{п)->оо. \ '
В отдельных случаях имеется функция распределения G(x)
и функции Ai(n)y А2(п), такие, что
N(n)- Ах{п)
я>оо /г>оо
limPntN{n)(A) = G(x), если lim ла(я) "*■ (16.15)
Если G имеет п вершин и е ребер, то будем говорить, что
G имеет степень 2е/п. Граф G называется уравновешенным
(сбалансированным), если степень (//) ^ степени (G) для всех
подграфов И г G. В частности, деревья, циклы, полные графы
и полные двудольные графы являются таковыми.
Если е = о (л]п), то G = Grtt е состоит из непересекающихся
ребер. Если e = c^Jny то деревья на трех вершинах
появляются с положительной вероятностью. Общее условие нали-
чествования небольших подграфов дает
Теорема 16.2 (Эрдёш и Реньи [I960]). Пусть Н — связный
уравновешенный граф на k вершинах с I ребрами. Пороговая
функция для свойства обладания подграфом, изоморфным Я,
равна n2~k/l.
Доказательство см. упр. 4. В частности, деревья на k
вершинах появляются при e = n{k~2)/{k^[\ а полные двудольные
аХа-графы при е = гС'21а (ср. с § 13).
Предположим теперь, что е = сп, где с фиксировано.
Природа графа Grt,e драматически изменяется при с = 1/2.
iod
16. Эволюции случайных графов
Если с < '/i» то наибольшая компонента G имеет объем
(1 + о(1)) 1о^ п/(2^ — 1 — log 2с) (см. упр. 5). Если с = [/2, то
наибольшая компонента имеет порядок пг/\
Если с>1/2, то наибольшая компонента имеет объем
h (с) п (1 + о (1)), где h — некоторая непрерывная функция,
h(72) = О» А(1)= 1- Этот „двойной скачок" — один из наиболее
удивительных результатов теории.
Планарность тоже изменяется при с=*/2. Если с<1/2, то
G планарен (упр. 6). Если с > 1/2, то G не планарен (упр. 7).
Более того, если ^ = лг/2 + д/лг со (лг), где <d-(/i)-*oo, то G не
планарен. Если е = п/2 + Я л/п , то Р [G планарен] = g (Я) > 0.
Функция g{X) неизвестна (за исключением того, что g(X)>0
для — оо < Я и lim g (Я) = + 1). Возможно даже, что g (Я) = 1
А.->оо
для всех Я, хотя это кажется и сомнительным. Если бы
lim #(Я)=0, то мы бы имели функцию распределения (16.15).
Эти результаты для е = п/2 + Я <\] п настолько тонкие, что они
могут не иметь приложения к G = G„>P, P—^/fo)*
И хроматическое число %(G) тоже меняется при с=*/2.
Если с < 7г> то Р [G является лесом] = р(с)> 0, т. е. Р [х (G) =з
= 2] > 0. Если с = 1/2, то %(G)!>3. Теперь предположим, что
с велико, но фиксировано. Тогда
21^7(1+ о(1))<х(0)^1~(1 + оа)). (16.16)
В (16.16) о(1) относится к с (см. упр. 9).
Положим сейчас е~ -^п log п. При этом изолированные
точки исчезают и граф становится связным. Имеется
неожиданно точный результат. Если А — связность, то (16.15)
выполняется при Al{n) = jnlogn, А2(п) = п, G{x) = e~e~2x. Более
интуитивно, случайный граф на п вершинах с -~п \ogn + хп
ребрами (х фиксировано) является связным с вероятностью
е~е~2х (см. упр. 13).
Пусть теперь число вершин, равное /г, будет четным
(тривиальные модификации рассмотрены при нечетном п). 1-фактор
в графе G определяется как множество из -j вершин
непересекающихся ребер. Эрдёш и Реньи [1966] доказали, что если
е==-2 п \ogn + со (/г)-> оо, то G обладает 1-фактором (см.
упр. 10, 11).
16. Эволюции случайных графой
101
Граф называется гамильтоновым, если он содержит цикл,
проходящий через каждую вершину только единожды.
Отметим, что если G гамильтонов, то он содержит 1-фактор. Одна
из наиболее интересных нерешенных задач этой области —
нахождение пороговой функции для гамильтоновости. Видимо,
e = rc1+8 (е > 0) достаточно, и мы предполагаем, что п log п
является пороговой функцией (см. упр. 12). Венгерские
математики Е. Поша. Л..Ловач и Е. Семереди разрешили эту
гипотезу положительно (см. упр. 15)
Упражнения и замечания
1. Если D есть 2-расцвечивание [л]2, положим k{D) —
= max | S |, [S]2 s Kt для / = 1 или 2. Положим / равным тому
наименьшему целому, для которого f j2 w>'l. Доказать,
что
|&(D)~/|<2.
2. Если Т—турнир, положим и(Г)=тах /,3 А, В, А ПВ=0,
|Л| = |В| = /, АХВ^Т. Положим t равным тому
наименьшему целому, для которого^ " J ( . J 2 ^2'>1. Доказать, что
\v{T)~t\^2.
3. Если о — перестановка на [п], положим v(o) равным
длине наибольшей монотонной подпоследовательности в
последовательности сг(1), ..., сг(п). __
Эрдёш и Г. Секереш [1935] доказали, что v (а) ^ {<у/п } для
всех а. Улам предполагает, что
о(а) = (2+ о(1)) УМ?)
(см. АСтечкин [1973]).
[Замечание: В оригинале Эрдёша и Реньи многие из
следующих упражнений были сделаны для G = Gn ei случайного
я-вершинного графа с е ребрами. Здесь вместо него мы
рассматриваем Оп,ру гдер^е/Г^)-]
4. Пусть G = G^P, а Н — связный уравновешенный &-вер-
шинный граф с I ребрами.
(a) Если р = o{ri'k/l), доказать, что G не содержит подграфа,
изоморфного Я. (Н не обязательно уравновешенный.)
(b) Если p/n~k/l-> оо, доказать, что G содержит подграф,
изоморфный Н. [Указание. Пусть St пробегает все [n]k\ 1 </^
<kJ. Положим Хг = 1, если G|S; содержит подграф,
изоморфный Н9 Х; = 0 в противном случае. Доказать (16.11).]
102 16. Эволюции случайных графов
5; Рассмотрим следующий процесс Галтона — Ватсона!
Начнем с одного (активного) члена. При каждой генераций
всякий активный член „порождает" X (активных) членов|
а сам становится инертным. Пусть X имеет распределений
Пуассона со средним к<\. Порождения предполагаются;!
независимыми. Пусть Рг равно вероятности того, что после!
остановки процесса имеется только г членов. Оттер [1949J]
доказал, что ^
Гг ~ г! е •
Пусть G = G„, р, р = 2с/п, с < 1/2 — фиксировано.
Используя этот результат, доказать, что наибольшаяикомпонента
вектора G имеет объем
(1 + 0(1» l0£T/t/(2c — 1 —
6. Пусть G = Оп> р, р — 2с/п, с< 112. Пусть ©.(я) — функция»
медленно стремящаяся к бесконечности [например, ю(я) =
= log log п].
(а) Доказать, чте менее чем со (/г) вершин графа G
присутствуют в циклах.
(Ь)' Показать, что не существует компоненты объема ^сй(я),
имеющей ребер больше, чем вершин.
;ч. (с) Используя (а) и (Ь), доказать, что G — плоский.
7. Пусть G = Grt,p, р=*2е/п, с>% Положим *—["^щ-].
Пусть X —число fe-циклов в G, которые содержат вершины
Я, Р', Q, Q', R, R', т.е. (Р, П (Q, Q'), (Л ЯОеО.
(a) Доказать, что Е(Х)->оо.
(b) Используя (16.11), показать, что Р[Х>0]-*1.
(c) Используя (а) и (Ь), доказать, что G — не плоский.
8. Положим, р — п\ G = GrtfP. Обозначим через/(G) число
максимальных деревьев на п — 5 вершинах.
(a) Доказать, что Е (t (G)) = ( J ) (л-БГУ^О-р)8*-*
[Указание. Число помеченных деревьев на т вершинах равно
т"1-2.]
(b) Доказать, что P[/(G) > 0] < (J) (l-*-1)*"8 —о(1).
9. Пусть р=*2с/п, с фиксировано и велико, G = Grt,р.
(а) Доказать, что x(G) >-~^ (1+о(1)), где о(1)
относится кс, [Указание. Использовать метод 1 из § П.]
16. Эволюции случайных графов * 103
2с
(b) Показать, что x(G) ^ . (1 + °(1))- [Это потребует
новой техники. Выбрать Ри Ръ ... из [л], где Pt выбирается
случайно из {Я: (Р, Р/) g G, P=£Ph 1 </</}. * Показать,
что это дает независимое множество Ki ={Pi, ..., Ра},
в = л[-|—^1(1 — о(1)) с вероятностью 1— o(tv~l). Обратить
внимание на тот факт, что G — Ki~Grt-a, р, и воспользоваться
индукцией по с (по всем действительным с).]
(c) (?) Пусть с = с (п) — функция от п9 причем.с (п) ->оо,
с(п) = о{п). Доказать, что
■K^U + odJKxtox-i^rli + od)!,
где о(1) относится к п.
10. (Эрдёш и Реньи [1963]). Пусть А = Ая, р = (а,/) —
случайная (0. — 1)-матрица размера «Х^ с Р [а,7= 1] = р.
Пусть р = log п/п + с/п. Доказать, что
P[Perm(A)>0]=e-2*-c.
[Указание. Perm (Л) — 0#^Э полностью 0-подматрица
размера kX{n — k+\) (Кёниг [1950] или см. М. Холл [1967],
теорема 5.1.4). Показать, что Р [3 полностью 0-подматрица
размера kX(n — k+\)9 кф\,п, которая не может быть
дополнена до нулевой строки] = о (1).]
11. (Эрдёш и Реньи[1966]). Пусть G = G„,P, р = logп/л +
+ (д{п))п, co(rt)-*oo. Доказать, что G содержит 1-фактор.
^казанце. Татт [1947] доказал, что G обладает 1-фактором
тогда и только тогда, когда G — {Ри ..., РГ) имеет ^г+1
связных компонент с нечетным числом вершин.
Доказательство этсго упражнения длинно даже при использовании
результата Татта.]
12. Хватал [частное сообщение] называет граф G f-ком-
пактным, если для любого k после отбрасывания ^.tk
вершин остается <£ компонент. Он предполагает, что если G
является 2-компактным, то он гамильтонов.
Положим G = GrtfP, p = c\ogn/n. Доказать, что для вся?
кого t найдется c = c(t), такое, что G является
/-компактным.
13. Пусть G==Gn,p, р = log п/п + 2х/п, х фиксировано.
Доказать, что
P[G связный] *»e-«~2V
(Указание. Прежде показать, что G состоит из связной ком*
поненты и изолированных вершин.)
1б4
1ё. Эволюции случайных графов
14. Пусть с (G) обозначает число клик в G. Положим G =
= G„, i/2. Найти Е [с (G) ], Var [с (G) ] и доказать, что Var [с (G) ] =
= о[ЕИО))].
151). G(«,/) обозначает я-вершинный граф с / ребрами.
Реньи и я предположили, что если / = [сп log п], то почти
все графы G (/г, /) являются гамильтоновыми I „почти все"
означает: „все, за исключением о
Эта гипотеза была недавно доказана Л. Поша. Улучшая
его метод, Комлош и Семереди доказали, что это имеет место
уже для с = 1/2 + е.
Наиболее сильное предположение, которое можно было бы
сделать, звучит так: пусть l=1/2n log п + п log log п + сп.
Верно ли, что с положительной вероятностью граф G(/z,/)
гамильтонов?
16. Пусть A (G) обозначает длину наибольшего цикла
в графе G. Верно ли, что существует такая функция /(с), что
для почти всех графов G (л, сп)
A(G(n,cn)) = (f(c) + o(l))n?
Известно, что /(1/2) = 0; это следует из наших
результатов с Реньи. Мне кажется, f(c) должна быть непрерывной
и строго возрастающей для 1/2 < с < оо и /(с)-И при с->оо.
17. Насколько мне известно, не рассматривался
следующий вопрос. Так, хорошо известно, что почти все графы G (/2,сп)
— несвязны, но верно ли, что почти все они содержат
подграф Gj высокой связности (т. е. G{ остается связным, если
удалить из него не слишком много его вершин)?
18. Рассматривая графы G(n,tnn), tn-> оо (/г-> оо ),
Спенсер и я высказали гипотезу, что для почти всех из этих
графов их хроматическое число лежит между CitJ\ogtn и crtn/logtn.
Возможно, даже верно, что существует такая константа с,
что для почти всех графов хроматическое число равно
c + o(l))tn/\ogtn.
19. Единственным образом раскрашиваемые графы.
Используя методы теории графов и теории вероятностей, Артри и я
[1959] показали, что для любых k и / существует
^-хроматический однозначно раскрашиваемый граф обхвата I
(обхватом называется длина кратчайшего цикла графа).
1) Пункты 15—19 написаны П. Эрдёшом специально для русского
издания. — Прим. перев.
е •
16. Эволюции случайных графой 1415
Основа нашей конструкции: пусть | At |= л, 1 ^/ ^ k.
Определим „случайный граф" следующим образом. Между At и
Л/, 1^Г</^6, проводим случайным образом л1+е ребер (е —
=е(/, к))> причем так, что, стоит возникнуть „далеким"'
небольшим (длины ^/) циклам, мы пропускаем какое-нибудь ребро
в каждом из них. Простое вычисление показывает, что почти
все получившиеся графы fe-раскрашиваемы единственным
образом; это происходит из однозначности выделения
независимых множеств объема л, а именно одного из Аь \<^i*^k*
Это уже обсуждалось на конференции по теории графов в
Праге. Я разумею Мюллера, давшего явную конструкцию
единственно /^-раскрашиваемого графа обхвата /.
17. ЛОСКУТКИ
Этот последний параграф представляет собой попурри из
задач и результатов, не вошедших в предшествующие
параграфы. Доказательства будут даваться очень схематично.
А. БЕСКОНЕЧНЫЕ СЛУЧАЙНЫЕ ГРАФЫ
Пусть N — множество положительных целых чисел.
Попытаемся ввести меру jli на множестве всех графов G^[jV]2.
Естественно представлять бесконечный случайный граф
посредством бросания идеальной монеты для каждого ee[JV]2,
определяя тем самым принадлежность е графу G. То есть
li[{G:ee=G}]=%
и события eeG независимы для различных es[N]2. Мы
индуцируем каноническую лебегову меру, задаваемую этими
условиями. Теперь можно говорить о случайном графе G е [N]2.
Однако теорию бесконечных случайных графов разрушает
Теорема 17А (Эрдёш и Реньи [1963b]). Существует граф
G0^[N]29 такой, что
P[G0~G] = 1.
То есть бесконечный случайный граф всегда одинаков.
Будем говорить, что граф G ^ [N]2 обладает свойством U (от
универсальности), если для различных ии ..., uni vu ..., vm^N
найдется аде N, отличное и от ut и от vf (1 </^/г, 1 </<т),
такое, что {w, ut} е G, l^i^n, a {wy vf) ф. G, 1^/</тг.
Лемма. Если графы Gx и G2 обладают свойством £/, то
GX^G2.
Доказательство. Построим о: N-> N, последовательно
определяя а(1), а-1(1), а (2), а-1 (2), .... Когда надо определить a(i)t
тогда а определяется на конечном множестве V. На
основании свойства U находим и фиксируем такое а(/), что
17. Лоскутки
107
Аналогично определяется а_1(/). Конечно, если для
некоторого / o~l(i) определяется как /, то a{i) полагается равной /';
аналогично для сг1 (*')■. По окончании этой счетной процедуры а
оказывается корректно определенным изоморфизмом Gx на
С2. Ш
Доказательство теоремы. При любых /г, т'щ, ..., unf v[f ..., vm
\х [ {G : не существует w, {w, щ) eG, {до, Vj} ф G) ] ^
^(l — 2~{m+n))K
для всех К, следовательно, мера равна нулю. Имеется лишь
счетное число таких т, /г, щ ..., ип, vu ..., vm.
Объединение счетной совокупности множеств меры нуль имеет меру
нуль. Отсюда
\x[{G:G не обладает свойством £/}] = 0;
таким образом, фиксируя граф G0, обладающий свойством U,
имеем
Р [G0 £ё G] = |li [ {G : G обладает свойством U) ] = 1. 0
В. ТРЕХСОТДОЛЛАРОВАЯ ЗАДАЧА
Эрдёш и Мозер поставили следующий вопрос: каково то
наибольшее число целых 0 < ах < ... <ak^n, для которого
все суммы Y<ai(S — №]) различны? (Для полноты считаем,
что пустая сумма равна нулю.) Обозначим через g {п) это
наибольшее значение k. Полагая at. = 2*~~1, видим, что
g(/2)>l + [l0g2/2].
Таким образом, имеется 2g{n) сумм между 0 и ng(n),
2e{n)^ng(n)t
т. е.
g (/г) < log2 п + log2 log2 п + о (1). (•)
Неизвестно, верно ли, что
g(n) = log2n + o(l) (?).
IL Эрдёш предлагает 300 долларов за доказательство либо
опровержение (?). Когда это писалось, доллар находился под
сильным давлением1). Поэтому приз может быть изменен
в соответствии с позднейшим курсом.
1) Эти слова были первоначально написаны в 1970 г., спустя три года
они сохраняют свою прежнюю силу.
108
17. Лоскутка
Гаи и Конвей [неопубликовано] показали
конструктивными методами, что g(2m)^m + 2 для /п>23.
Некоторое усиление (*) дает следующий результат Эрдёша
и Мозера (см. Эрдёш [1955]).
Теорема 17В. g(n)<^\og2n + у log2 log2n + о (1).
При доказательстве используется „метод вторых моментов".
Пусть 0 <хх < ... <xk^.n таковы, что все суммы ^xi раз-
личны. Пусть s = ][]**> где S — случайное подмножество мно-
жества [k]. Тогда
k
E(s)=l£^ = n, Var(s)=£*2/4<fcrt2/4-
Таким образом,
Р[| s -|х |< al > 1 - Var (s)/a2> 1 -kn2/4a2.
Но поскольку, согласно предположению, все 2J xi различны,
Р [ | s — ^i |< а] = | {Л: | Z v, — ^ |< а} |2-л < 2а2~л
и, следовательно,
2o2-k^l-kn2l4(f-
Полагая в^пл/k, получаем утверждение теоремы.
С. ЗАДАЧА О ВЗВЕШИВАНИИ МОНЕТ
Совокупность {S,, ..., Sm) подмножеств множества [п]
называется определяющей совокупностью, если произвольное
подмножество Т^[п] однозначно определяется
кардинальными числами | S{ П Т |, l^i^tn. Нас интересует то
наименьшее значение D{n) числа /п, для которого такая
определяющая совокупность существует1).
Эта задача часто предлагается как задача о взвешивании
монет. Пусть даны п монет с весами 0 и 1. Имеется также
шкала, позволяющая взвешивать любое подмножество монет.
Вопрос заключается в определении весов монет за
наименьшее число взвешиваний. Взвешивания должны быть
предопределенными, т. е. информацию, накопленную на
предыдущих взвешиваниях, нельзя использовать в последующих.
,' Точнее, речь идет о восстановлении по упорядоченной
последовательности чисел Ц5*Г)^1Ь» Для неупорядоченной см. упр. {. — Прим.
лерев.
17. Лоскутка
109
Взвешивая по отдельности каждую монету (Sf = {*}), мы
видим, что D(n)^.n. Имеется, однако, и асимптотический
результат.
Теорема 17С. D (п)=п log (4)/log {п)+0 (п log log(rt)/log2 (п)).
Для каждого / имеется лишь п + 1 возможных значений
JS/firi* Следовательно, согласно принципу Дирихле, если
{Su ..., Sm) — определяющая совокупность, то {п + 1)т < 2".
Это дает оценку D{n) > n\og2/log (п+ 1). Отметим^ что эта
оценка имеет место даже при использовании информации
о предыдущих взвешиваниях.
Мы можем улучшить нижнюю оценку, пользуясь методом
вторых моментов. Это доказательство принадлежит Мозеру
(см. Линдстрём [1965], стр. 488f). Пусть {Sb ..., Sm} —
определяющая совокупность с m = D(n). Пусть А обозначает
матрицу инцидентности размера лХ/п множеств St (т. е.
а,/=1 тогда и только тогда, когда /eSy). Для удобства
предположим, что веса принимают значения — 1 и +1. Тогда
х = (х{ хп) однозначно определяется через хА. Пусть
х = (Х|-э ..., xrt) — случайный л-вектор, xt = =Ь 1. Пусть, | • |
обозначает евклидову норму в Rm. Положим y = (yi, ..., ут)=
= хЛ, тогда
^ г m "I m
е[1уП-е[Еу?]-1е[уЯ-
Для всякого А вектор yt имеет распределение S„, т. е.
е[уЯ-е[Ч]-«
и
Е[11у!121 = '"/г.
Следовательно,
P[llyll2<2mn]>-|-.
То есть найдется по крайней мере 2 векторов х> таких,
что || хА ||2 ^ 2тп. Но все хА различны и имеют целые
коэффициенты. Число точек у е Rm с целыми коэффициентами,
|| у ||2 <; 2тпу ограничено объемом шара радиуса {2тп) в Rm9
который в свою очередь равен {с{п)т12. Таким образом,
2п-1<{с{п)т,\
т. е.
D (п) = т> [п log 4/logп] (1 + о (1)).
no
17. Лоскутки
Можно получить верхнюю оценку из вероятностных со-
ображений. Предположим для удобства, что Si = [n]. Пусть
S2, ..., Sm — случайные подмножества множества [п]. Пусть
А* и В*—различные не сепарированные множества. Тогда
А = А* — В*, В = В* — Л* суть непересекающиеся не
сепарированные множества;
El\{A9B): А(]В=0, Л, В не сепарированы} |] <
/г/2
^i](/X'i7')p[i4, в не сепаРир°ваны пл|=|в|=^
/г/2
если m^2nlog4/logn. Таким образом, £> (дг) ^2дг log4/logлг^
Верхняя оценка, однако, должна рассматриваться как
победа конструктивистов. Кантор и Миллс [1966] и Линд-
стрём [1965] доказали, что
' D(n)<!i^- + 0(n^glogn/logn).
Их методы были полностью конструктивными.
Эта книга заканчивается на меланхолической ноте —на
проблеме, по которой вероятностные методы не могут дать
наилучшего ответа. Мы желаем нашим читателям более
полных успехов.
Упражнения А
1. Если совокупность {Sh .... Sm} подмножеств
множества [п] однозначно определяет всякое подмножество Т^[п}
неупорядоченной последовательностью чисел {| St П Т I }l<i<mr
то чему равно наименьшее возможное m = D(n)?
Доказать, что D {п) = п и найти экстремальный гиперграф.
2. (?) Доказать или опровергнуть единственность
экстремальной конструкции в упр. 1.
Список литературы
Аббот (Abbot Н. L.) (1965), An Application of Ramsey's Theorem. To a
Problem of Erdos and Hajnal, Canad. Math. Bull., 8, 515—517.
.Байнеке, Харари (Beineke L. W., Harary F.) (1965), The Maximum Number
of Strongly Connected Subtournaments, Canad. Math. Bull., 8, 491-—498.
(Русский перевод: Максимальное число сильно связных подтурниров,
сб. Теория графов (покрытия, укладки, турниры), «Мир», М., 1974.)
Берлекэмп (Berlekamp Е. R.) (1968), A Construction For Partitions which
Avoid Long Arithmetic Progressions, Canad. Math. Bull, 11, 409—414.
Браун, Спенсер (Brown Т. A., Spencer J. H.) (1971), Minimization of ±1
Matrices Under Line Shifts, Colloq. Math. (Poland), 23, 165—171.
Брук, Райзер (Bruck R. H., Ryser H. J.) (1949), The Nonexistence of
Certain Finite Projective Planes, Canad. J. Math., 1, 88—93.
Ван дер Варден (van der Waerden B. L.) (1952), Beweis einer Baudet'schen
Vermutung, Niew Archie] voor Wiskunde, 15, 212—216.
Визинг В. Г. (1968), Некоторые нерешенные задачи в теории графов, УМНУ
23, №6, 117—134.
Витшенхаузен, Гордон (Witsenhausen Н. S., Gordon Y.) (1972), On
Extension of the Gale — Berlekamp Switching Problem and Constance of lP-
spaces, Israel J. of Math., 11, 211—229.
Гаи l), Знам (Guy R., Znam S.) (1969), A Problem of Zarankiewicz, in Recent
Progress in Combinatorics, Ed. by Tutte W., Academic Press, New York—
London.
Галлаи (Gallai T.) (1963), Kritische Graphen I, Magyar Tud. Akad. Mat. Ku-
tato Int. KozL, 8, 165—192 (esp. 172—175).
Герцог, Шёнхейм (Herzog M., Schonheim J.) (1972), The Br Property and
Chromatic Numbers of Generalized Graphs, /. Comb. Theory (B), 12,
41—49.
Гордон, Витшенхаузен — см. Витшенхаузен.
Гудман (Goodman A. W.) (1959), On Sets of Acquaintances and Strangers
at any Party, Amer. Math. Monthly, 66, 778—783.
Гравер, Якель (Graver J. E., Yackel J.) (1968), Some Graphs Theoretic
Results Associated with Ramsey's Theorem, Journal of Combinatorial
Theory, 4, 125—175.
Бланш Декарт — см. Татт.
Дойен (Doyen J.) (1970), Sur la Croissance du Nombre de Systemes Triples
de Steiner non Isomorphes, /. Comb. Theory, 8, 424—441.
Знам, Гаи — см. Гаи.
Зыков А. А. (1949), О некоторых свойствах линейных комплексов, Мат.
сборник, новая серия, 24 (66), 163—188.
Кантор, Миллс (Cantor D. G., Mills W. Н.) (1966), Determination of a
Subset from Certain Combinatorial Properties, Canad. J. Math., 18, 42—48.
Катона, Неметц, Симонович (Katona G., Nemetz Т., Simonovits M.) (1964),
On a Graph-problem of Turan (in Hungarian), Mat. Lapok, 15, 228—
238.
Келли Дж., Келли Л. (Kelly J. В., Kelly L. В.) (1954), Paths and Circuits
in Critical Graphs, American J. of Math., 76, 786—792.
Кёниг (Konig D.) (1950), Theorie der endlichen un unendlichen Graphen,
Chelsea, New York.
Ковари, Шош, Туран (Kovari Т., Sos Т. V., Turan P.) (1969), On a Problem
of K. Zarankiewicz, Colloqium Mathematicum, 3, 50—57.
x) В русской литературе встречается разночтение: Гай, — Прим. перев%
112
Список литературы
Коломб (Colombo U.) (1964), Sui Circuiti nei Grafi Completi, Boll. Un. MaL
Hal., 19, 153—170.
Комлош, Шуёк (Komlos J., Sulyok M.) (1969), On the Sum of Elements of
zfcl Matrices, in the Proceedings of the Combinatorial Colloquium in Ba-
latonfured, Hungary, 1969.
Коршунов А. Д. (1971), Число неизоморфных подграфов в r-вершинном
графе, Мат. заметки, 9, 263—272.
Линдстрём (Lindstrom В.) (1965), On a Combinatorial Problem in Number
Theory, Can. Math. Bull., 8, 477—490.
Ловач (Lovasz L.) (1968), On Chromatic Number of Finite Set-Systems,
Acta Math. Acad. Sclent. Hung., 19, (1—2), 59—67.
Миллс, Кантор — см. Кантор.
Мозер (Moser L.) (1960), On a Theorem of van der Waerden, Canad. Math.
Bull., 3, 23—25.
Мозер, Эрдёш (Moser L., Erdos P.) (1964), A Problem on Tournaments,
Canad. Math. Bull., 7, 351—356.
Мотцкин, Штраус (Motzkin Т. S., Strauss E. G.) (1965), Maxima for Graphs
and a New Proof of a Theorem of Turan, Canad. I. Math., 17, 533—540.
Мун (Moon J. W.) (1968), Topics on Tournaments, Holt, Rinehart, and
Winston, New York.
Мун, Эрдёш (Moon J. W., Erdos R.) (1964), On Subgraphs of the Complete
Bipartite Graph, Canad. Math. Bull., 7, 35—39.
Мун, Эрдёш (Moon J. W., Erdos P.) (1965), On Sets of Consistent Arcs in
a Tournament, Canad. Math. Bull., 8, 269—271. (Русский перевод:
О множествах согласованных дуг в турнире, сб. Теория графов
(покрытия, укладки, турниры), «Мир», М., 1974.)
Неметц, Катона, Симонович — см. Катона.
Оттер (Otter R.) (1949), The Multiplicative Process, Annals of Math. Stat.y
50, 206—224.
Радо, Эрдёш (Rado R., Erdos P.), (1952), Combinatorial Theorems on
Classifications of Subsets of a Given Set, Proc. of the London Math. Soc>
(3) 2,417—439.
Райзер (Ryser H. J.) (1963), Combinatorial Mathematics, Carus Monograph
Number 14, John Wiley and Sons, New York. (Русский перевод:
Комбинаторная математика, «Мир», М., 1966.)
Райзер, Брук — см. Брук.
Рамсей (Ramsey F. Р.) (1930), On a Problem of Formal Logic, Proc. of the-
London Math. Soc, 2nd series, 30, 264—286.
Рейман (Reiman I.) (1958), Uber ein Problem von K. Zarankiewicz, Acta
Math. Acad. Sci. Hung., 9, 269—279.
Реньи, Эрдёш (Renyi A., Erdos P.) (1960), On the Evolution of Random
Graphs, Mai. Kutato Int. Kozl., 5, 17—60.
Реньи, Эрдёш (1963a), On Random Matrices, Publ. Math. Inst. Hung. Acad.
Sci., 8, 455—461.
Реньи, Эрдёш (1963b), Asymmetric Graphs, Acta Math. Acad. Sci. Hung., 14,.
295—315.
Реньи, Эрдёш (1966), On the Existence of a Factor of Degree one of
Connected Random Graphs, Acta Math. Acad. Sci. Hung., 17, 359—379.
(Русский перевод: О существовании 1-фактора у связного случайного-
графа, сб. Теория графов (покрытия, укладки, турниры), «Мир», М.^
1974.)
Рот (Roth К. F.) (1964), Remark Concerning Integer Sequences, Acta Arith-
metica, 9, 257—260.
Симонович, Катона, Неметц — см. Катона.
Секереш Г., Секереш Э. (Szekeres G., Szekeres Е.) (1965), On a Problem of
Schutte and Erdos, Math. Gazette, 49, 290—293.
Список литературы
113
Секереш Г., Зрдёш (Szekeres G., Erdos P.) (1935), A Combinatorial Problem
in Geometry, Compositio Math., 2, 463—470.
Селе (Szele T.) (1943), Kombinatorikai vizsgalatok az iranyitott teljes graf-
fal kapcsolatban, Mat. Fiz. Lapok, 50, 223—256.
Спенсер (Spencer J.) (1971a), Optimal Ranking of Tournaments, Networks,
1, 135—138.
Спенсер (1971b), A Remark on Coloring Integers, Canad. Math. Bull, 14,
45—47.
Спенсер (1972a), Turan's Theorem for ^-graphs, Discrete Math., 2, 183—186.
Спенсер (1972b), Random Regular Tournaments, Rand Corp. Paper, P-4479-1.
Спенсер (1975), Ramsey's Theorem— A New Lower Bound, /. of Comb.
Theory (A), 18, 108—115.
Спенсер, Браун — см. Браун.
Спенсер, Эрдёш (Spencer J., Erdos P.) (1972), Imbalances in ^-Colorations,
Networks., 1, 379—385.
^Стечкин Б. С. (1973), О монотонных подпоследовательностях в
перестановке п натуральных чисел, Мат. заметки, 13, 511—514.
Сторер (Storer Т.) (1967), Cyclotomy and Difference Sets, Markham.
Тарри (Tarry G.) (1900), Les problemes des 36 officiers, C. R. Assoc. Frang.
Av. Sci., 1, 122—123 and 2, 170—203 (1901).
Татт (под псевдонимом Бланш Декарт) (Tutte W. Т.) (1947), (under
pseudonym Blanche Descartes), A Three-colour problem, Eureka (April 1947,
solution March 1948) and Solution to Advanced Problem No. 4526, Amer,
Math. Monthly, 61, 352 (1954).
Татт (1947), The Factorization of Linear Graphs, /. London Math. Soc, 22,
107—111.
Туран (Turan P.) (1941), Egy grafelmeleti szelsoertek feladatrol, Mat. Fiz.
Lapok, 48, 436—452; см. также On the Theory of Graphs, Colloq. Math.
3, 19—30 (1954) иМотцкин, Штраус (1965).
Туран (1961), Research Problems, Publ. Math. Inst. Hung. Acad. Sci., 6,
417—423. (Русский перевод: Некоторые нерешенные проблемы,
Математика, 7 : 4 (1963), 101—107.)
Туран, Ковари, Шош — см. Ковари.
•Феллер (1957), An Introduction to Probability theory and its Applications,
Vol. I, John Wiley and Sons, New York. (Русский перевод: Введение
в теорию вероятностей и ее приложения, «Мир», М., 1964.)
Хайнал, Эрдёш (Hajnal A., Erdos Р.) (1961), On a Property of Families of
Se'ts, Acta. Math. Acad. Sci. Hung., 12, 87—123.
Хайнал, Эрдёш (1966), On Chromatic Number of Graphs and Set Systems,
Acta Math. Acad. Sci. Hung., 17, (1—2), 61—99 (esp. 94—99).
Хайнал, Эрдёш (1968), On a Combinatorial Problem (in Hungarian), Mat.
Lapok, 19, 345—348.
Ханани (Hanani H.) (1960), On Some Quadruple Systems, Canad. J. of
Math., 12, 145—157.
Ханани (1961), The Existence and Construction of Balanced Incomplete
Block Designs, Annals of Math. Statistics, 6, 362—386.
Ханани, Эрдёш (Hanani H., Erd5s P.) (1963), On a limit theorem in
Combinatorial Analysis, Publ. Math. Debrecen, 10, 10—13.
-АХарари (Harary F.) (1969), Теория графов, «Мир», M., 1973.
Харари, Байнеке — см. Байнеке.
Харнер, Энтринджер, Эрдёш (Harner С, Entringer R. С, Erdos P.), Some
External Properties Concerning Transitivity in Graphs, Periodica Mathe-
matica Hungarica (в печати).
Хватал (Chvatal V.) (1970), Hypergraphs and Ramseyian Theorems, Ph. D.
Thesis, University of Waterloo, Waterloo, Ontario, Canada.
Хватал (1971), Hypergraphs and Ramseyian Theorems, Proc. Amer. Math.
Soc, 27, 434—440.
114
Список литературы
Холл (Hall М.) (1967), Combinatorial Theory, Ginn and Blaisdell, Walt-
hem— Toronto — London. (Русский перевод: Комбинаторика, «Мир», M.^.
1970.)
Чернов (Chernoff Н.) (1952), A Measure of Asymptotic Efficiency for Tests
of a Hypothesis Based on the Sum of Observations, Ann. Math. Stat., 23,.
493—509. ... .
Шёнхейм (Schonheim J.) (1966), On Maximal Systems of 2-Turles, Studia.
Sci. Math. Hung., 1, 363—368.
Шёнхейм, Герцог — см. Герцог.
Шмидт (Schmidt W. М.) (1962), Two Combinatorial Theorems on
Arithmetic Progressions, Duke Math. J., 29, 129—140.
Шмидт (1964), Ein kombinatorisches Problem von P. Erdos und A. Hajnal„
Acta Math. Acad. Sci. Hung., 15, 373—374.
Шош, Ковари, Туран — см. Ковари.
Штраус, Мотцкин — см. Мотцкин.
Шуёк, Комлош— см. Комлош.
Энтринджер, Харнер, Эрдёш — см. Харнер.
Эрдёш (Erdos Р.) (1947), Some Remarks on the Theory of Graphs, Bulletin.
Amer. Math. Soc, 53, 292—294.
Эрдёш (1955), Problems and Results in Additive Number Theory, in Colloq..
sur la Theorie des Nombres (Bruxelles), 127—137.
Эрдёш (1959), Graph Theory and Probability, Canad. J. of Math., 11, 34—
38
Эрдёш (1961), Graph Theory and Probability II, Canad. J. of Math., 13, 346—
352.
Эрдёш (1962), On Circuits and Subgraphs of Chromatic Graphs, Mathema-
tika, 9, 170—175.
Эрдёш (1963a), On a Problem in Graph Theory, Math. Gazette, 47, 220—223.
А Эрдёш (1963b) Л On a combinatorial problem, Nord. mat. tidskr., 11, No. 1
5—10.
Эрдёш (1964), On a Combinatorial Problem II, Acta Math. Acad. Sci. Hung.>.
15, 445—447.
Эрдёш (1965), On Extremal Problems of Graphs and Generalized Graphs,.
Israel J. of Math., 2, 189—190.
Эрдёш (1967), Some Remarks on Chromatic Graphs, Colloquium Mathemati-
cum, 16, 253—256.
Эрдёш (1969), On a Combinatorial Problem HI, Canad. Math. Bull, 12, 413—
416.
Эрдёш, Мозер — см. Мозер.
Эрдёш, Мун — см. Мун.
Эрдёш, Радо — см. Радо.
Эрдёш, Реньи — см. Реньи.
Эрдёш, Секереш — см. Секереш,
Эрдёш, Спенсер — см. Спенсер.
Эрдёш, Хайнал — см. Хайнал.
Эрдёш, Ханани — см. Ханани.
Эрдёш, Харнер, Энтринджер — см. Харнер.
Якель (Yackel J.) (1972), Inequalities and Asymptotic Bounds for Ramsey
Numbers, /. Comb. Theory, 13, 56—68.
Якель, Гравер — см. Гравер,
Дополнение
ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ О ПОДМНОЖЕСТВАХ
КОНЕЧНОГО МНОЖЕСТВА1)
Л. Эрдёш, Д. Дж. Клеит мен
0. Введение
Подмножества (конечного) множества образуют решетку
^или булеву алгебру). Длг. них естественны следующие понятия:
(A) Пересечение.
(B) Объединение.
(C) Непересекаемость (разделенность).
(D) Дополнение.
(E) Включение.
(F) Мощность (ранг, объем, размер).
В данной работе дается обзор имеющихся в настоящее время
задач о максимальных и минимальных объемах семейств
подмножеств, наделенных ограничениями, связанными с этими
понятиями.
Задачи такого рода возникают во многих областях
математики. Например, делители числа, свободного от
квадратов, соответствуют подмножествам множества всех простых
делителей этого числа, так что определенные
теоретико-числовые задачи о делимости имеют эту форму. Оптимальные
коды, исправляющие ошибки, и блок-схемы могут
рассматриваться как экстремальные совокупности подмножеств,
удовлетворяющие ограничениям такого рода.
Поскольку понятие множества столь же фундаментально
з математике, как и понятие числа, исследовать
рассматриваемые здесь свойства можно так же, как рассматриваются
подобные задачи в теории чисел. То есть мы вправе
спросить: к какому сорту ограничений на семейства объектов
множества приводят простые ограничения на объединение,
объем и (или) включение членов этого семейства?
Вопросы такого рода имеют одно дополнительное
значение. Поскольку введенные здесь свойства легко понятны
нематематикам, то результаты и элегантные доказательства
в этой области имеют поучительное значение иллюстрации
•силы математического метода, доступной неспециалистам.
') Erdos P., Kleitman D. J., Extremal problems among subsets of a
-set, Discrete Mathematics, 8 (1974), 281--294.
© North-Holland Publishing Company, 1974.
© Перевод на русский язык, «Мир», 1976.
116
Дополнение
Для удобства мы разделили все рассматриваемые здесь
задачи на пять типов.
1. Неразделенные семейства.
2. Ограничение на объем пересечения.
3. Ограничение на пересечение и объем.
4. Ограничение на включение.
5. Ограничение на объединение и пересечение.
6. Смесь.
Задачи и результаты этих типов рассматриваются ниже
в соответствующих разделах.
1. Неразделенные семейства
Пусть S — конечное л-элементное множество (| S | = /г).
Среди простейших ограничений, которые можно наложить
на семейства подмножеств множества S, имеется условие
отсутствия двух непересекающихся членов. Точнее, если
F = {Ai), / = 1, ..., Я, A/CiS, то можно потребовать, чтобы
Ai {]Aj=£0 для всех /, /.
Даже одного этого ограничения достаточно для
постановки целого ряда вопросов. Среди них, например, такие:
(a) Сколь велико может быть F1
(b) Если F „насыщенно", т. е. не существует
подмножества множества S, добавление которого к F не повлекло бы
нарушения этого ограничения, то сколь мало может быть
такое F?
(c) Сколько существует насыщенных F заданного объема?
(d) Сколько вообще всех таких семейств?
Эти четыре рода вопросов могут быть поставлены не
только относительно семейств подмножеств, ограниченных,,
как это F, но и для семейств, удовлетворяющих вариантам
рассматриваемого ограничения.
Среди возможных вариантов ограничений столь же общего
вида отметим следующие:
1.1. Пусть F определено, как и ранее, a G состоит иа
минимальных членов F, т. е. из членов, не содержащих
Других.
1.2. Пусть G2k есть объединение k определенных выше
семейств F.
1.3.-Пусть G3k есть семейство, не содержащее k членов,
чьи попарные пересечения пусты.
1.4. Пусть G4aj —такое семейство, что пересечение любых
k его членов не пусто.
Приведем некоторые результаты. Не существует
совокупности неразделенных подмножеств, содержащей и множество,
и его дополнение. Так как наше семейство F не может иметь
П. Эрдёш, Д, Дж. Клейтмен
117
более половины всех подмножеств, то |F|^2n~1.
Максимальное семейство F состоит из всех подмножеств, содержащгх
один фиксированный элемент из S. Так как каждое
множество, не пересекающееся с Л, принадлежит его дополнению,
то, если А не может быть добавлено к насыщенному
семейству F, это означает, что в F уже есть некоторое непустое
подмножество из Л. Значит, все насыщенные семейства
содержат в точности 2П^] подмножеств, для каждого А по
одному: из А или из Л.
Таким образом, вопросы (а) и (Ь) для неразделенных
семейств F решаются легко. С другой стороны, число
максимальных (а значит, и насыщенных) семейств, удовлетворяющих
условию неразделенности, вычислено не так хорошо. При
вычислении величин такого сорта есть несколько различных
уровней точности. Некоторые из них приведены здесь. Можно
иметь:
(1) точную формулу,
(2) приближенную формулу (стремящуюся к точному
результату при больших л),
(3) асимптотическую формулу (отношение к точному
результату имеет предел),
(4) асимптотическую формулу для логарифма.
Вдобавок можно получить оценки для всякого из этих
уровней, равно как и для любых других.
Можно легко получить 4-й уровень для полного числа
семейств F\ это есть n (F) ==ехр2[2/г"1 (1 + о (I))]1).
Доказательство будет приведено ниже.
Аналогичный результат для числа максимальных семейств,
вероятно, есть ехр2| ( г ?21) (1 + о (1))/2J, но это не доказано.
Однако легко получается, что это выражение служит
нижней, а ехр2[(г ?21) (1 + о (1))J — верхней оценкой.
Для иллюстрации рассуждений, используемых при выводе
выражений такого типа, мы вкратце приводим
доказательство.
Максимальное F может быть охарактеризовано его
минимальными членами. Обозначим через G (F) семейство,
состоящее из членов семейства F, не содержащих других, и
G (F) определяет F. Такое семейство G (F) иногда называют
„шпернеровым семейством" или „антицепью"; нет члена
семейства G, содержащего другой. (ШпернеровУ семейства
обсуждаются в разд. 4.)
) Будем обозначать 2х через ехр2*.
118
Дополнение
Некоторая имеющаяся информация о числе шпернеровых
семейств позволяет получить верхнюю оценку для числа
максимальных F в виде ехр2| Г г *L J (1 + о (1))1.
Для вывода нижней оценки разделим все /г/2-элементные
подмножества S на содержащие данный элемент а0 и
остальные („остальные" здесь означает дополнения членов,
образующих совокупность). Имеется ехргГу ( гл?2] )1
совокупностей Q из /г/2-элементных подмножеств, содержащих а0.
Каждая из них определяет совокупность F, состоящую из всех
множеств с более чем я/2-элементами, этих я/2-элементных
множеств, содержащих а0 из Q, и дополнений я/2-элементных
множеств, содержащих а0 не из Q. Рассуждения для
нечетного п аналогичны.
Можно надеяться, что рассуждение, позволившие
получить выражение ехр2[( ", ) (1 + о (1))] для числа
шпернеровых семейств, можно использовать для демонстрации того,
что число шпернеровых семейств, которые не содержат
разделенных членов, равно ехр2[Г г *L J (1 + о (1))/21. Всякое
максимальное семейство, имеющее 2п~1 членов, имеет 22П~1
подмножеств. Полное число подмножеств всех максимальных
семейств, а следовательно, и полное число семейств F не
может превысить expslV"1 + ( хп?2] ) (1 + о (1))1, что и есть
ехр2 [2"-1(1 + о (1))], как это утверждалось выше.
Не все ограничения (1.1, ..., 1.4) исследованы столь
детально. Во-первых, приведем имеющиеся результаты по этим
вопросам, а потом выпишем открытые задачи.
I. 1. Свойства семейств G (F) тесно связаны со свойствами
максимальных семейств F. Они могут меняться в объеме от 1
( п—\ \
до I г/ __ jw2i 1; их число можно оценить приведенным выше
способом. Все они максимальны.
'I 1.2. Было показано, что число членов в объединении k
семейств F не может превышать 2Л — 2п~~к (см. [18}). Эта
оценка может быть достигнута, если положить в качестве
k семейств все подмножества, содержащие а$г Г^/^&.
1.3. Были получены оценки и для объема G^ (я) —
семейства, не содержащего k членов (см. [21]). Для п = тк— I
эти оценки реализуемы; для других значений <ши
представляются несколько завышенными по сравнению5 с лучшими
возможными результатами. Эти результаты можша получать.
Я. Эрдёш, Д. Дж. Клейтмен
119
отмечая, что во всяком разбиении S на k блоков по крайней
мере один блок должен отсутствовать в G3k(n). Этот факт
для данной системы размеров блоков приводит к
лимитированию числа членов таких размеров в G3k(n). Комбинируя
ограничительные тождества, можно получить результаты,
приведенные выше.
Наименьший объем насыщенного G3k{n) не превосходит
2п — 2n~k. Это, вероятно, может быть и точным результатом.
1.4. Среди максимальных семейств F имеются семейства,
состоящие из всех подмножеств, содержащих один какой-то
элемент. Такие семейства обладают тем свойством, что
всевозможные пересечения его членов непусты. Значит, то
ограничение (на G4fc(ft)), что всякие k членов имеют непустое
пересечение, не делает максимальный объем GAk(n) меньшим
2п~\ Возникают два естественных вопроса. Каков
максимальный объём GAk(n), в котором существуют {k+l)
членов, имеющих пустое пересечение? Каков наименьший объем
насыщенного G4fc(tt)? Милнер [33, 34] имеет некоторые
результаты по первому из них, а второй открыт.
Приведем несколько открытых задач в этой области.
(1) Каково число максимальных семейств без
разделенных элементов?
(2) Сколь малым может быть насыщенное семейство с тем
свойством, что в объединении k различных максимальных
семейств нет двух разделенных членов? Верно ли, что
асимптотически это равно 2п~{ для больших пс?
(3) Сколько таких семейств?
(4) Верно ли, что наименьшее насыщенное Gzk(n) имеет
2п - 2n~k членов?
(5) Какова точная верхняя оценка для G3k(n)?
(6) Каков наименьший объем насыщенного GAk(n)?
(7) Каковы более точные выражения для числа семейств
каждого из указанных типов?
2. Ограничение на объем пересечения
В задачах, рассматривавшихся до сих пор, основным
ограничением было то, что пересечение непусто. Такие
ограничения могут быть заменены лимитированием объема
пересечений. Таким образом, мы могли бы вместо этого потребовать,
чтобы не было At и Aj из F, удовлетворяющих условиям:
I Л, П Л, |< k, | At U Лу | -1 Аь П Лу | < k,
I Л, П Л; | > k, | At U Л, | -1 At П Aj | > k,
I Л, П Л71 Ф k,
|Л,ГМ,| = Й.
120
Дополнение
Имеется целый круг задач из рассмотренных ранее,
которые можно сформулировать как задачи о семействах,
определяемых посредством каждого из этих ограничений.
Обобщением, придающим наибольшую широту первому разделу,
служит первое из них. Максимальное семейство Fk(n)f
которое подчиняется этому первому ограничению, состоит из всех
подмножеств, имеющих (л + &+ 1)/2 или более элементов,
с другими ( . , k — i)i2j множествами, если n + k нечетно.
То, что это наибольший возможный объем, показано Като-
ной [12]. Некоторые из других задач можно рассматривать
при этом же ограничении.
Противоположное ограничение о том, что подмножества
не пересекаются „столь сильно", имеет приложение к
укладкам и задачам кодирования. Число членов объема ^k
семейства, ограниченного условием отсутствия двух членов,
удовлетворяющих | At П Aj | ]> k, не превосходит Г £ J и
достигается при выборе всех подмножеств мощности k. Если мы
обозначим через fq число членов такого семейства, имеющих
q элементов, то получим
it< VXD
как ограничение на его объем.
Задача кодирования может быть описана как изучение
семейств, лимитированных тем условием, что
„симметрическая разность" между всякими двумя членами не меньше k.
Симметрическая разность между At и Af есть At U А} —• At П Л/.
Имеется много результатов о наибольшем объеме кодов при
таких ограничениях и о конструкциях оптимальных кодов.
Многие из них описаны, например, в [4].
Есть и другая задача столь же общего вида: как велико
может быть семейство подмножеств множества 5, если
симметрическая разность между членами всегда ^q<n? Для
четного q показано, что наибольшее по объему семейство
состоит из произвольного множества а и всех множеств, чьи
симметрические разности с а не превышают q/2. Для
нечетного q можно также подключить (/^.Гп/г) подмножеств,
чьи разности с а равны (q+ 1)/2 (см. [19]).
3. Ограничение на пересечение и объем
Другой класс задач относится к семействам подмножеств
данного объема, наделенным ограничениями описанных ти-
П. Эрдёш, Д. Дж. Клейтмен
121
пов. Эрдёш, Ко и Радо [7] показали, что максимальный объем
семейства подмножеств S, удовлетворяющих условиям
(i) все подмножества имеют объем ^.k^.n/2 (\S\ = n),
(ii) нет двух непересекающихся, ни одно не содержит
другого,
равен Г bZiJ* оптимум достигается при выборе всех
/^-элементных подмножеств, которые содержат данный элемент.
Если 2k = n9 то имеется большое число, ехр2 Г ^ Т^| J,
таких семейств. Если же 2k < п, то максимальное по объему
семейство единственно с точностью до перестановки^
элементов.
Наименьший объем насыщенного семейства здесь равен
(или не равен) Г k J.
Среди возникающих в этой области вопросов имеются
следующие.
(1) Каково наибольшее семейство, если исключить все
семейства, члены которых содержат фиксированный
элемент?
(2) Даны два таких семейства, что все члены одного
пересекаются с членами другого и подчиняются описанному выше
ограничению на объем; что можно сказать об их объемах?
В этом направлении был получен [23] следующий несколько
более общий результат.
Пусть F и G — два семейства подмножеств множества S;
члены F имеют по k элементов, а члены G — по q элементов.
Пусть k + q не превосходит п\ если k не больше чем {п + 1)/2,
то F может иметь k или менее членов, пока нет члена,
содержащего другой; то же самое допустимо и для G. Тогда
либо
|^<(Г!)- либ° igk(;:!)-
Милнер [33, 34] по первой задаче получил некоторые
результаты.
Для достаточно большого п и данного k семейство,
состоящее из всех /^-элементных подмножеств, включающих
один фиксированный элемент, много больше (т. е. порядка
cnk\k\ в противоположность c'nk-l/(k—l)l) всякого другого.
Пользуясь этим обстоятельством, легко ответить на многие
вопросы, относящиеся к этой тематике.
Таким образом, для достаточно большого п и
фиксированных k и q мы можем показать следующее.
122
Дополнение
(A) Число членов в объединении q множеств /^-элементных
неразделенных подмножеств множества S (| S| = /z) не больше
чем
(:::)+(:=;)+••■+(::;)•
(B) Число членов множества ^-элементных
подмножеств S, наделенных тем ограничением, что нет (q + l)i
попарно не пересекающихся, ограничено той же величиной.
(C) Числю членов множества ^-элементных подмножеств,
из наделенных тем ограничением, что пересечение каждой пары
имеет по крайней мере q элементов, не превосходит (!!Zj)-
Можно предположить, что аналогичные результаты имеюг
место, пока 2k<^n — q+l для (А) и (В), и что лучшим
результатом для (С) служит максимум по т следующей:
суммы:
k-m
Е/ 2m — q\( n + q~2m \
\ m + p ) \ k~ m — p — 1 /'
i
Однако результаты такого сорта еще не были получены.
Родственная задача, которая также не решена, поставлена
Кнезером [28]. Сколько семейств /^-элементных подмножеств,,
каждое из которых состоит из подмножеств, не отделенных
одно от другого, необходимо для покрытия всех ^-элемент-
ных подмножеств? Ответ предполагается равным л — 2k + 1
(если это число по крайней мере единица).
Ограничения вида
объем подмножества = г,
объем пересечения <<7
представляют задачи об укладках или задачах кодирования,
включающие в себя слова „фиксированного веса". Задачи вида
объем подмножества = й,
объем пересечения =q
описывают такие структуры, как проективные плоскости (q = 2),.
системы Штейнера и блок-схемы. Существует обширная
литература по этим вопросам. Ни тот, ни другой класс задач
здесь не рассматривается. Эрдёш, Ко и Радо [7] высказали
гипотезу, что если \S\ = 4kf a F состоит из подмножеств S
объема 2kf которые пересекаются по крайней мере по двум
элементам, то
|"-((2)-(?)*)А
П. Эрдёш, Д. Дж. Клеит мен
123
4. Ограничение на включение
В этом разделе мы рассматриваем семейства
подмножеств, наделенные ограничениями на включения. Прототипом
таких ограничений может служить „шпернерово семейство",
шли „антицепь", ни один член которой не содержит другого.
Шпернер [37] в 1927 г. показал, что такое семейство может
зшеть не более ( г /2i ) членов. Любель [30] в 1959 г. и
независимо Мешалкин [32] в 1963 г.]) получили несколько более
усиленное ограничение. Если fk — число /j-элементных членов
шпернерового семейства подмножеств S(|S| = /z), то имеет
место неравенство
iv(i)<'-
Равенство может реализовываться лишь при fk=(ll) для
некоторого k. Результат Шпернера является тривиальным
следствием этого неравенства, поскольку
Рассуждение Любеля столь просто, что мы повторяем его
здесь. Максимальная цепь является множеством из п+1
подмножеств множества 5, вполне упорядоченным по
включению. Каждое /^-элементное подмножество присутствует
в одной и той же доле максимальных цепей Г 1/( £))•
Поскольку нет цепи, содержащей более одного члена
шпернерового семейства, то сумма долей максимальных цепей,
содержащих каждый элемент, не может превосходить единицы,
что и дает неравенство Любеля — Мешалкина2).
То же самое рассуждение приводит к тому, что
наибольшее число членов семейства, которое имеет не более q
членов, входящих в какую-нибудь цепь, есть сумма q
наибольших биномиальных коэффициентов. Этот результат следует
из неравенства
EVC)*:*
Л-0
1) По-видимому, первым это сделал Ямамото [38] в 1954 г. — Прим.
перев.
2) „Невероятностное" доказательство см. [40] и [42]. — Прим, перев.
124
Дополнение
которому должно удовлетворять такое семейство.
Рассуждение Любеля можно применять и для других целей. Так,
например, при его использовании с привлечением некоторых
дополнительных рассуждений был получен следующий
результат [27]. Пусть / — некоторая функция, определенная на
членах частично упорядоченного множества, и пусть F —
семейство, которое имеет не более k членов во всякой цепи
этого частично упорядоченного множества. Пусть G
обозначает группу подстановок, определенную на частично
упорядоченном множестве, которая сохраняет / (т. е. VgeG
f (gA) = f (Л)), и симметричную относительно частичного
упорядочения (т.е. Vg«=G A^B^gA^gB). Тогда
максимальное значение суммы / по всем членам семейства F
достигается для некоторого F, которое есть ^объединение орбит
группы G. То есть существует семейство F, такое, что
Z f(A)<Z f(A),
где F — объединение полных орбит группы G. Любелем [31J
были получены еще большие обобщения его результата.
Следующие вопросы тоже естественны для шпернеровых.
семейств. Пусть F — шпернерово семейство и G+ — семейство,
состоящее из всех подмножеств, содержащих по крайней мере
один член F, a G/ — семейство всех подмножеств,
упорядоченных по включению относительно по крайней мере однога
элемента F. Сколь велико может быть | F | при данном | G+ I?
Данном | G/1? Если | F \ > ( * . J, то сколько пар А, В, A zd В
должно быть в F?
В этих направлениях получены следующие результаты..
к
(1)Еслит>(£)для£<л/2, то | G+ | > £ (^) (см.[24]).
в-0
(2)|F|/|G/|<(J2])/2't (см. [17]).
(3) Число „цепных пар" минимизируется, если F состоит
из всех подмножеств, содержащих [/г/2], [/г/2]+1, [п/2] — 1,
[/г/2] + 2, ... элементов, а остальные члены F все имеют
число элементов, равное следующему значению этого ряда [20].
Наименьшее число „цепных троек" пока не найдено, хотя
можно предполагать то же самое (см. [43—44].
Шпернерово выражение может получиться, когда
ограничение на отсутствие включения значительно ослаблено.
Предположим, например, что S есть объединение двух
непересекающихся множеств Тх и Т2 (см. [13, 17]),
S-r,Ur2, Тг()Т2=0,
П. Эрдеш^ Д. Дж. КлейтмеН
125
и предположим также, что F ограничено так, что если А =э В
для Л, BeF, то Л — В\Т{ и А — Вд$Т2. Тогда |Л<
^( г ^01 J • т* е* шпеРнеРова оценка по-прежнему приложима
и с этими ослабленными условиями на F.
Интересная нерешенная проблема является аналогом
приведенной для. S = 7^! [}Т2\]ТЪ, где Tt не пересекаются: при
этих обстоятельствах аналогичного ограничения на F
недостаточно для получения такой же оценки для | F |. Можно
поинтересоваться: какова наилучшая оценка? А также: при
каких условиях на F эта оценка все-таки будет иметь место?
Можно также спросить: какой аналог неравенства Любеля
можно получить для S = TX\}T2 задачи?
Катона [15], Шёнхейм [36] и Эрдёш [11] получили
дальнейшие обобщения теоремы Шпернера.
Число шпернеровых семейств подмножеств S
исследовалось многими авторами, начиная с Дедекинда. Лучший
недавний результат [25] заключается в том, что это числа
больше чем
exp2[(J2])(l+cn-^logn)].
Катона [14] и Краскал [29] рассматривали подобный вопрос.
Дано /-членное семейство F из fe-элементных подмножеств
множества S. Пусть G состоит из (k + 1)-элементных
подмножеств, которые содержат один или более членов
семейства F. Сколь малым может быть | G | при данном /? Их
результат точен: / можно однозначно выразить как
(»2,) + (t22)+. ••+(,?.)•
где г{ > г2 > ... > rm. Тогда
i°i>-(;)+(*-2)+•••+(*-»)•
Мешалкин [32] получил результат о семействах разбиений
я-элементного множества на k помеченных блоков,
ограниченных так, что нет блоков, определенным образом
содержащих блок с той же меткой. Его результат, наибольший
/^-номинальный коэффициент, есть в действительности
следствие неравенства Любеля — Мешалкина.
5. Ограничение на объединение и пересечение
Имеются задачи, в которых накладываются ограничения
на пересечение трех или более подмножеств. Будут
рассматриваться следующие типы ограничений.
126
Дополнение
(a) Fx — ограничено так, что нет трех членов Л, В, С,
удовлетворяющих условию А\}В — С (А()В — С было бы
эквивалентно).
(b) F2 удовлетворяет тому ограничению, что никакие
четыре члена Л, Л, С, D не удовлетворяют условиям Л [)В = С,
ЛП£ = £>.
(c) Никакие три члена Л, В, С семейства F3 не
удовлетворяют условию Л U В = С или Л П В = С.
(d) Никакие три члена F4 не удовлетворяют условию
A\JBzdC (А (} В а С — равносильно).
(e) Никакие три члена F5 не удовлетворяют условию
A\)BczC.
(f) Никакие 2k членов F6k не образуют булеву алгебру
ло объединению и пересечению.
(g) Любые k членов Аи ..., Ak семейства F7k имеют
непустое пересечение, и это же выполняется при замене
некоторых или всех Л/ на их дополнения.
(h) Никакая пара непересекающихся членов семейства Fs
не дает при своем объединении член семейства F8; член
А П В = 0 исключается.
По этим вопросам были получены следующие результаты.
(a) Ограничения А\}ВФС, видимо, лимитирует
семейство Fx числом членов, равным i , *L J (1 + err1). Лучшие
оценки, полученные в [26], дают Г *, J (1 + с/я~1/2).
(b) При ограничении Л [} В ф С или Л П В ф D семейство F2
может иметь с2пп~114 членов. Имеются верхние и нижние
оценки, они могут быть или не быть равными [8].
(c) Из этого ограничения, вероятно, следует, что F3 может
иметь не более Г f ,21 J + 1 членов для четного п. Клементе
(частное сообщение) построил примеры семейств, имеющих
столько членов.
(d) Число членов семейства F4 экспоненциально мало по
сравнению с 2п. Мало известно об этом ограничении.
(e) При условии А[)В^С объем семейства F5 не может
превышать Г , /2, J (1 + с/п), каковая граница и может
достигаться.
(f) Мало что известно, помимо случая (Ь), об этом
ограничении.
П. Эрдеш, Д. Дж. Клейтмен
127
(g) Эта задача была рассмотрена Джоэлом Спенсером
(частное сообщение). Для k = 2 выяснено, что границей
является [(n—\\i2\)% ^ля ^=^ были получены
двусторонние оценки в виде Сп, 1 ^ с ^ 2, однако они не близки. Это
ограничение включает в себя (d), а именно А{ П А2 ^? А3
для &^3.
(h) Грубо говоря, при этих ограничениях семейство G
1 2
может содержать все множества, имеющие от -r/i до -/i
элементов. Наилучший результат получен для n = 3k + 1. Для
п = 3&, /г = 3/г + 2 имеется незначительное расхождение между
наилучшей оценкой и наилучшими полученными результатами.
Другой круг задач рассмотрен Эрдёшом и Мозером [9].
В распоряжении первого из авторов имеются награды за их.
решение „Найти оценки для / (/г), равного тому наибольшему
числу подмножеств я-элементного множества Л, для которога
каждое подмножество А представимо как объединение двух
из / (п) подмножеств. Легко доказать, что
д/2" • Т < f (2п)< 2 • 2\
Мы предлагаем 25 долларов ответившему (с
доказательством) на вопрос: / (2п)/2п больше или меньше 1,75 для
достаточно большого я?"
„Найти оценки для / {п) — того наибольшего числа
подмножеств Аи ..., Af („) множества из п элементов, что все:
V 2 ) мйожеств At U Л/, 1 < / < /^ f (п), различны. Мы.
можем доказать, что при достаточно большом п
(1+е^</Ы<(1+е2Г,
где 0 < в{ < е2 < 1, и предлагаем 25 долларов за нахождение е^
и е2 с точностью ejei^ 1,01".
6. Смес^
Есть еще иного типа задачи о семействах подмножеств
заданного объема из множеств, которые не обязательно строго
определены. Вот две такие задачи:
(1) Предположим, что никакие три подмножества не имеют
одинаковых попарных пересечений и каждое из них объема k.
Как много их может быть?
(2) Предположим, что всякое подмножество, которое
пересекает все члены семейства, содержит по крайней мере одна
элемент. Сколь мало членов может иметь такое семейство?
128
Дополнение
Свойство, фигурирующее в (2), так называемое „свойство Б",
интенсивно исследовалось. Для п = 3 можно найти 7-членное
семейство с этим свойством. Для я = 4 наименьший объем
•семейства неизвестен, но, вероятно, он около 20. Эрдёш [5, 6]
лолучил верхнюю оценку сп22п, а Шмидт [35] — нижнюю
2п(I + 4/п)~1. Эти результаты были недавно несколько
улучшены Герцогом и Шёнхейном (частное сообщение).
Наилучшей оценкой для первой задачи должна, видимо,
быть с*. Пока удалось получить лишь оценку в виде k\ck
13, 10].
Упражнения А
1. Семейства разделенные и неразделенные. Семейство
JF = {Ai} называется р-неразделенным,г если любая система
из р его членов имеет непустое пересечение; семейство
называется q-разлелешъш, если любая система из q его членов
имеет пустое пересечение. Будем рассматривать
р-неразделенные и <7"РазДеленные семейства Fn{p,q). Как велико может
быть семейство Fn(p,q)? Легко показать, что
max|F„(2,3)| = [l±I^±I].
Кроме того, при q = p+l искомый max ведет себя как
{р\п){!р при р = const. Вопрос остается открытым для
„средних" р и q > р + I.
2. (Осколков [39].) Пусть F = {Ai) — семейство
подмножеств л-элементного множества S = {au ал}, a i^ =
= |{/leF: Лэ at) I, причем vx > v2 ^ ... ^ vn > 0. Доказать,
что если ft = \{A^F: |Л|^/}|, то имеет место неравенство
п Lji v. ^
Список литературы
[1] Н. L. Abbott, Some remarks on a combinatorial theorem of Erd5s and
Rado, Can. Math. Bull, 9 (2) (1966), 155—160.
[2] H. L. Abbott and B. Gardner, On a combinatorial theorem of Erdos and
Rado (в печати).
[3] H. L. Abbott, D. Hanson and N. Sauer, Intersection theorems for
systems of sets (в печати).
[4] E. Berlekamp, Algebraic Coding Theory (McGraw-Hill, New York, 1968).
(Русский перевод: Э. Берлекэмп, Алгебраическая теория кодирования,
«Мир», М., 1971.)
[5] P. Erdos, On a combinatorial problem И, Acta. Math. Acad. Set. Hun*
gar., 15 (1964), 445—449.
Список литературы
129
[6] P. Erdos, On a combinatorial problem III, Can. Math. Bull, 12 (1969),
413-416.
[7] P. Erdos, Chao Ко and R. Rado, Intersection theorems for systems of
finite sets, /. Math. Oxford, Sec, 12 (48) (1961).
[8] P. Erdos and D. Kleitman, in Proc. Am. Math. Soc. (в печати).
[9] P. Erdos and L. Moser, in: Proc. Calgary Conference, 1969.
[10] P. Erdos and R. Rado, Intersection theorems for systems of sets, Л
London Math. Soc, 35 (I960), 85—90.
[11] P. Erdos and J. Schonheim, in: Proc. of Balutonfured Conference, 1969
(в печати).
[12] G. Katona, Intersection theorems for systems of finite sets, Acta Math^
Acad. Scu Hangar., 15 (1964), 329—337.
[13] G. Katona, On a conjecture of Erdos and a stronger form of Sperner's
theorem, Studia Sci. Math. Hungar., 1 (1966), 59—63.
[14] G. Katona, A theorem on finite sets, in: Theory of Graphs, Proc. Colloq.
held at Tihany, Hungary, 1966 (Akademiai Kiado, Budapest, 1968), 187—
207.
[15] G. Katona, Sperner type theorems, Dept. Statistics, University of North
Carolina, Chapel Hill, N. Car., 1969.
[16] G. Katona, A generalization of some generalizations of Sperner's
theorem, Dept. Statistics, University of North Carolina, Chapel Hill, N. Car.,
1969.
[17] D. Kleitman, On a lemma of Littlewood and Offord on the distributioa
of certain sums, Math. Z., 90 (1965), 251—259.
[18] D. Kleitman, Families of non-disjoint subsets, /. Combin. Theory, 1
(1966), 153—155.
[19] D. Kleitman, On a combinatorial conjecture of Erdos, /. Combin.
Theory, 1 (1966), 209—214.
[20] D. Kleitman, A conjecture of Erdos —Katona on commensurable pairs.
among subsets of an я-set, in: Theory of Graphs, Proc. Culloq. held at
Tihany, Hungary, 1966 (Akademiai Kiad6, Budapest, 1.968), 187—207.
[21] D. Kleitman, Maximal number of subsets of a finite set no k of which
are pairwise disjoint, /. Combin. Theory, 5 (1968), 152.
[22] D. Kleitman, On families of subsets of a finite set containing no two-
disjoint sets and their union, /. Combin. Theory, 5 (3), (1968).
[23] D. Kleitman, On a conjecture of Milner on /г-graphs with non-disjoint.
edges, /. Combin. Theory, 5 (1968).
[24] D. Kleitman, On subsets contained in a family of non-commensurable-
subsets of a finite set, /. Combin. Theory, 7 (1969), 18h—183.
[25] D. Kleitman, On Dedekind's problem: the number of monotone Boolean,
functions, Proc. Am. Math. Soc, 21 (3) (1969), 677—682.
[261 D. Kleitman, Proc. Am. Math. Soc (в печати).
[27] D. Kleitman, M. Edelberg and D. Lubell (в печати).
[28] R. Kneser, Aufgabe 360, Jber. Deutsch. Math.-Verein., 58 (2) (1955).
[29] F. B. Kruskal, The number of simplices in a complex, in: R. Bellman,,
ed., Mathematical Optimization Techniques (1963), 251—278.
[30] D. Lubell, A short proof of Sperner's lemmas, /. Combin. Theory, 1
(1966), 299.
[31] D. Lubell (в печати).
[32] Л. Д. Мешалкин, Обобщение теоремы Шпернера о числе подмножеств
конечного множества, Теория вероятн. и ее примен., 8 (2) (1963), 219—
220.
[33] Е. С. Milner, Intersection theorem for systems of sets, Quart. J. Math^
Oxford, Ser. 18 (1967), 369—384.
[34] E. С Milner, A combinatorial theorem on systems of sets, /. London.
Math. Soc, 43 (1968), 204—206.
130
Список литературы
[35] W. М. Schmidt, Eine Kombinatorisches Problem von P. Erdos und
H. Hajnal, Acta. Math. Acad. Sci. Hungar., 15 (1964), 373—374.
[36] J. Schonheim, A generalization of results of P. Erdos and G. Katona,
/. Combin. Theory (1970).
[37] E. Sperner, Ein Satz tiber Unterrnengen einer endlichen Menge, Math.
Z.,27 (1928), 544—548.
[38A] K. Yamamoto, Logarithmic order of free distributive lattice, /. of
Math. Soc of Japan, 6 (3—4) (1954), 343—353.
[39A] К. Осколков, Обобщенная вариация, индикатриса Банаха и
равномерная сходимость рядов Фурье, Матем. зам., 12(3) (1972), 313—324.
{40А] G. Katona, Extremal problems for hypergraphs, Reprint of the Math.
Inst, of the Hungar. Acad, of Sci., No. 79/1974.
{41 A] C. Greene, G. Katona, D. J. Kleitman, Extensions of the Erdos —Ко —
Rado theorem, Preprint of the Math. Inst, of Hungar. Acad, of Sci.,
No. 97/1974.
[42А]Б. С. Стечкин. Неравенство Ямамото и наборы. Матен. зам., 19,
155—160.
[43А] P. Frankl, On Sperner Families Satisfying Additional Condition,
/. Comb. Theory (A), 20 (1976), 1—11.
(44Aj C. Greene, D. J. Kleitman, The Structure of Sperner /г-Families,
J. Comb, Theory (A), 20 (1976), 41—68.
Содержание
Предисловие к русскому изданию 5
Предисловие &
1. ДВА ПРИМЕРА 7
2. ОБОЗНАЧЕНИЯ 13
3. БИНОМИАЛЬНОЕ РАСПРЕДЕЛЕНИЕ • 17
4. СВОЙСТВО В 1»
5. ТЕОРЕМА РАМСЕЯ 23
6. ТЕОРЕМА ВАН ДЕР ВАРДЕНА 33
7. КВАЗИРАМСЕЕВСКИЕ ТЕОРЕМЫ 35
8. МОДИФИКАЦИЯ ТЕОРЕМЫ ВАН ДЕР ВАРДЕНА 3»
9. ТУРНИРЫ 42
10. РЕГУЛЯРНЫЕ ТУРНИРЫ . ; 47
11. ХРОМАТИЧЕСКОЕ ЧИСЛО 55
12. ПРОБЛЕМЫ ЦАРАНКЕВИЧА И РАМСЕЕВСКИЕ ТЕОРЕМЫ ДЛЯ
ДВУДОЛЬНЫХ ГРАФОВ 62
13. УПАКОВКИ, ПОКРЫТИЯ И ТЕОРЕМА ТУРАНА 74
14. АСИММЕТРИЧЕСКИЕ ГРАФЫ 82
15. ЗАДАЧИ О БАЛАНСИРОВКЕ МАТРИЦ 89
16. ЭВОЛЮЦИИ СЛУЧАЙНЫХ ГРАФОВ 97
17. ЛОСКУТКИ 106
Список литературы ш
Дополнение. Я. Эрдёш, Д. Дж. Клейтмен, ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ О ПОД- .-
МНОЖЕСТВАХ КОНЕЧНОГО МНОЖЕСТВА И5
УВАЖАЕМЫЙ ЧИТАТЕЛЬ!
Ваши замечания о содержании книги, ее
оформлении, качестве перевода и другие
просим присылать по адресу: 129820, Москва, И-110,
ГСП, 1-й Рижский пер., д. 2, издательство «Мир».
П. Эрдёш, Дж. Спенсер
ВЕРОЯТНОСТНЫЕ МЕТОДЫ
В КОМБИНАТОРИКЕ
Редактор И. Маховая
Художник Н. Фильчагина
Художественный редактор В. Шаповалов
Технический редактор Н. Панфилова
Корректоры Т. Пашковская, А. Рыбальченко
Сдано в набор 6.08.75. Подписана к печати 13.05.76.
Бумага тип. № 2 60X907ie-4,25 бум. л. 8,50 печ. л^
Уч.-изд. л. 6.86. Изд. № 1/8519
Цена 47 к. За к. 806
ИЗДАТЕЛЬСТВО «МИР»
Москва, 1-й Рижский пер., 2
Ордена Трудового Красного Знамени
Ленинградская типография № 2
имени Евгении Соколовой Союзполиграфпрома при
Государственном комитете Совета Министров СССР
по делам издательств, полиграфии
и книжной торговли
198052, Ленинград, Л-52, Измайловский проспект, 29