Линейно-алгебраический метод в комбинаторике

А.М.Райгородский

Линейно-алгебраический
метод в комбинаторике

Издание второе, дополненное

Электронное издание

Москва
Издательство МЦМНО
2016

УДК 519.1
ББК 22.15
Р18

Райгородский А. М.
Линейно-алгебраический метод в комбинаторике
Электронное издание
М.: МЦНМО, 2015
144 с.
ISBN 978-5-4439-2489-2

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

Подготовлено на основе книги:
Райгородский А. М. Линейно-алгебраический метод в комбинаторике. —
М.: МЦНМО, 2015. — 2-е изд., доп. — 144 с. — ISBN 978-5-4439-0275-3

Издательство Московского центра
непрерывного математического образования
119002, Москва, Большой Власьевский пер., 11,
тел. (499)241–08–04.
http://www.mccme.ru

ISBN 978-5-4439-2489-2
c⃝ Райгородский А. М., 2016.
c⃝ МЦНМО, 2016.

Оглавление

1. Введение
5

2. Задачи о пересечениях конечных множеств
8
2.1. Немного истории и формулировка теоремы Франкла—
Уилсона
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
2.2. Доказательство теоремы Франкла—Уилсона . . . . . . . .
10
2.3. Точность теоремы Франкла—Уилсона и ее неожиданность
15
2.4. Вокруг теоремы Франкла—Уилсона . . . . . . . . . . . . .
18
2.5. О точности оценок в теореме 3 . . . . . . . . . . . . . . . .
25

3. Задачи о скалярных произведениях векторов
30
3.1. Постановка одной из задач и формулировка одного из
результатов
. . . . . . . . . . . . . . . . . . . . . . . . . . .
30
3.2. Доказательство теоремы 11 . . . . . . . . . . . . . . . . . .
33
3.3. Смысл оценки из теоремы 11 . . . . . . . . . . . . . . . . .
36
3.4. Точна ли теорема 11? . . . . . . . . . . . . . . . . . . . . . .
42
3.5. Вокруг теоремы 11 . . . . . . . . . . . . . . . . . . . . . . .
52
3.6. Еще одно замечание к теореме 12 . . . . . . . . . . . . . . .
59

4. Применение полученных результатов в комбинаторной
геометрии
61
4.1. Постановки основных задач . . . . . . . . . . . . . . . . . .
61
4.2. Задача Нельсона—Эрдёша—Хадвигера . . . . . . . . . . . .
65
4.3. Задача Борсука . . . . . . . . . . . . . . . . . . . . . . . . .
74
4.4. О числах Борсука и Нельсона—Эрдёша—Хадвигера . . . .
82
4.5. О хроматических числах с несколькими запретами
. . . .
86
4.6. Вокруг задачи Нельсона—Эрдёша—Хадвигера . . . . . . .
92

5. Теория Рамсея
100
5.1. Круг задач и формулировка результата . . . . . . . . . . . 100
5.2. Доказательство теоремы 20 . . . . . . . . . . . . . . . . . . 108

6. Задача об отклонении
111
6.1. Постановка задачи и краткий исторический экскурс
. . . 111

Оглавление

6.2. Доказательство теоремы 23 . . . . . . . . . . . . . . . . . . 114
6.3. Доказательство теоремы 24 . . . . . . . . . . . . . . . . . . 117
6.4. Дополнение 1. «Свойство B» Эрдёша
. . . . . . . . . . . . 121
6.5. Дополнение 2. Матрицы Адамара и проблема Борсука . . 123

7. Теорема Эрдёша—Гинзбурга—Зива и ее окрестности
131
7.1. Классический результат . . . . . . . . . . . . . . . . . . . . 131
7.2. Вспомогательные факты . . . . . . . . . . . . . . . . . . . . 133
7.3. Доказательство оценки Роньяи f(n, 2) ⩽ 4n − 2
. . . . . . 135
7.4. Доказательство оценки Райхера f(n, 2) ⩽ 4n − 3 . . . . . . 137

Литература
141

Введение

Комбинаторика — один из наиболее увлекательных, многогранных
и нетривиальных разделов современной математики. Имея множество
приложений, она развивается настолько бурно, что даже простая попытка перечислить ее основные направления, по-видимому, обречена
на провал. Десятки специализированных журналов ежемесячно публикуют сотни новых статей, каждый год выходят в свет монографии
и учебники, и уследить за всем этим колоссальным потоком информации весьма нелегко. Вряд ли найдется человек, имеющий право
заявить, что знает все последние достижения в комбинаторике.
В то же время многие из тех, кто не совсем хорошо ориентируется
в области «дискретных» (т.е. в сущности комбинаторных) задач, полагают, что комбинаторика, так сказать, «не вполне научна». Считается,
что если формулировки задач доступны школьнику, а объекты, с которыми приходится иметь дело, не требуют знания того, что такое
интеграл Лебега или когомология, то и развивать соответствующую
теорию незачем. При этом бытует мнение, что задачи в комбинаторике
разрозненны и для их решения не существует единых содержательных подходов. Правда, иной раз вспоминают о методе производящих
функций, который активно используется при перечислении различных объектов, — но и только. Такой взгляд, с одной стороны, способствует чрезмерной мифологизации комбинаторики — дескать, только
гениям под силу решать «штучные» задачи-головоломки, — а с другой стороны, он ведет к возникновению пренебрежительного отношения к комбинаторным проблемам, которые якобы «олимпиадны»
и в контекст «серьезных» исследований включены быть не могут. Действительно, постановка многих комбинаторных вопросов носит весьма
олимпиадный характер, и известного рода изобретательность (если не
изощренность) очень важна для успешной работы с ними.
И тем не менее, методология этой работы отнюдь не исчерпывается
одним лишь методом производящих функций. В XX веке — веке наиболее активного развития комбинаторики и внедрения ее идей во всевозможные области знания (компьютерные технологии, биоинженерия
и пр.) — был построен мощный аппарат, позволяющий эффективно
бороться с комбинаторными трудностями.

1. Введение

Одновременно с быстрым ростом числа направлений и специальных проблем комбинаторики шло становление целых «наук в науке», группировавшихся вокруг общих методов, приводивших, в частности, к решению классических дискретных задач. Среди таких методов и вероятностный метод в комбинаторике, который сам заслуживает долгого и тщательного обсуждения, и линейно-алгебраический
метод, вынесенный в название этой книги.
Казалось бы, какая может быть связь между комбинаторикой
и весьма геометричной линейной алгеброй? Однако связь есть, и она
удивительно глубока и красива. Мысль о том, что линейно-алгебраические факты можно увязать с фактами дискретной математики, как
раз «олимпиадна». Нужно было обладать большим остроумием, чтобы
породить ее. Некоторые наиболее яркие результаты, полученные с
помощью линейно-алгебраического метода, кажутся на первый взгляд
и вовсе невероятными.
Знаменитый венгерский математик Поль Эрдёш, благодаря которому современная комбинаторика в значительной степени выглядит
такой, какой мы ее знаем, заявлял даже, что подобные результаты
хранятся в некоей особой божественной Книге. Эрдёш, разумеется,
шутил, но результаты эти настолько изящны, что «Книгу» (или часть
ее) издали в 1998 году (см. [35]), и она уже переведена на несколько
различных языков, включая русский (см. [1]), а также выдержала
четыре (!) издания (см. [36]). Впрочем, для нас главное — это наличие
метода и тонких фактов, установленных за счет него.
В этой книге рассматривается несколько наиболее популярных
и интересных задач комбинаторики, решаемых с помощью линейной
алгебры. Среди решений рассмотрены и те, что удостоились упоминания в «Книге», и другие. Наша цель — через призму этих удивительных задач и решений увидеть суть общего метода, его многоплановость и перспективность. Мы должны понять, что комбинаторика —
это в первую очередь красивая наука и что задачи ее можно и стоит
решать. Например, посредством линейно-алгебраического метода.
Завершая введение, скажем несколько слов о структуре книги.
В книге семь глав, каждая из которых посвящена какой-нибудь известной задаче комбинаторики, решаемой с помощью того или иного варианта линейно-алгебраического метода. Основные результаты
формулируются в виде теорем; однако приводятся и менее значимые
утверждения, называемые в тексте предложениями, а также доказывается ряд вспомогательных фактов (лемм).
Практически все теоремы в книге именные, и их авторство указано
в заголовках теорем. Там же даются ссылки на оригинальные ста

1. Введение
7

тьи, в которых содержатся доказательства (вне зависимости от того,
приводится ли доказательство теоремы в книге). Есть и несколько
безымянных теорем. Будучи глубокими, но не слишком трудными,
они давно вошли в математический фольклор, и установить, кому они
принадлежат, мы не можем. В конце каждой главы есть задачи. Иногда они сводятся к доказательству известного утверждения. В этом
случае мы пишем в скобках имя его автора.

Задачи о пересечениях конечных
множеств

2.1. Немного истории и формулировка теоремы
Франкла—Уилсона

Ответ на следующий вопрос многие знают еще со школы — как раз
из олимпиадной деятельности. Пусть Rn — некоторое конечное множество, состоящее из n различных элементов. Например, мы можем считать, что Rn = {1, . . . , n}. Рассмотрим в Rn произвольную совокупность трехэлементных подмножеств (сочетаний) M = {M1, . . . , Ms},
обладающую таким свойством:
Mi ∩ Mj
̸= 1 для любых несовпадающих индексов i, j ∈ {1, . . . , s}. Здесь «модуль» множества — это
его мощность, и, в частности, |Mi| = 3 для каждого i ∈ {1, . . . , s},
в то время как |M| = s (совокупность — это ведь тоже множество,
элементы которого суть Mi). Понятно, что заведомо s ⩽ C3
n. Однако
на элементы совокупности M (3-сочетания в Rn) наложено дополнительное ограничение, состоящее в том, что никакие два из них не
могут иметь в пересечении ровно один общий элемент. Разумеется,
далеко не всякая совокупность M подчиняется указанному ограничению, и, стало быть, возникает обещанный вопрос: а насколько большой
может оказаться величина s = |M| в сделанных предположениях?
Вопрос этот совершенно типичен для так называемой экстремальной комбинаторики (ищутся экстремальные значения тех или иных
комбинаторных характеристик), и в естественности его усомниться
трудно. Впрочем, любые сомнения отпадут позже, когда мы не только
изучим общую проблематику подобного рода, но и приведем красивые
приложения соответствующих результатов в геометрии.
Итак, как мы уже говорили, ответ на поставленный вопрос многим
известен. Те же, кто с ним еще не знаком, вполне способны обосновать
его самостоятельно. Посему мы лишь приведем его формулировку,
а доказательство оставим за читателем. Заметим только, что проще
всего воспользоваться стандартным методом математической индукции. Кстати, именно так действовал венгерский математик Жигмунд
Надь, который и был, по-видимому, автором следующего утверждения, полученного им в 60-е годы прошлого века.

2.1. Немного истории и формулировка теоремы Франкла—Уилсона
9

Теорема 1 (Ж.Надь, [48]). Если в совокупности M, состоящей из
трехэлементных подмножеств множества Rn, никакие два множества не пересекаются в точности по одному общему элементу, то
s = |M| ⩽ n′, где

n′ = n
при n = 4k,

n′ = n − 1
при n = 4k + 1,
n′ = n − 2
при n = 4k + 2 и n = 4k + 3.

Конечно, k принимает в теореме любые натуральные значения.
Имеется в виду попросту, что остаток от деления числа n на 4 может
оказаться нулем, единицей, двойкой или тройкой. В зависимости от
этого остатка и находится величина оценки в теореме. В дальнейшем
же мы будем использовать обозначения, принятые в теории чисел:
n ≡ i (mod p) (читается «n сравнимо с i по модулю p») означает, что
n − i делится на p или, в терминах теоремы 1, n = pk + i (i — остаток
от деления n на p).
С одной стороны, замечательно то, что теорема неулучшаема.
Иными словами, для каждого n ничего не стоит построить совокупность M, обладающую всеми нужными свойствами и, тем не менее,
содержащую в аккурат n′ элементов (проделайте это!). С другой
стороны, разочаровывает то, что мы как бы сами себе противоречим:
вроде бы, во введении мы заявляли, что комбинаторика не есть чисто
олимпиадная дисциплина и что задачи в ней не решаются одними
«изысканными», олимпиадными методами; однако налицо обратная
ситуация, ведь мы сами признаем, что теорема 1 как раз относится
к олимпиадной вотчине. Впрочем, довольно-таки очевиден тот факт,
что постановка вопроса, исчерпывающий ответ на который мы только
что привели, весьма специальна. Действительно, настоящая проблема,
на которую лишь намекает теорема 1, куда как более общая, и сейчас
мы к ней обратимся.
Опять-таки, пусть M = {M1, . . . , Ms} — это произвольная совокупность подмножеств (сочетаний) в Rn. Однако теперь мы будем
считать, что |Mi| = k, i = 1, . . . , s, где k — некоторое наперед заданное число. Более того, мы предположим, что при каком-нибудь
фиксированном t, 0 ⩽ t ⩽ k, выполнено условие
Mi ∩ Mj
̸= t, i ̸= j,
i, j ∈ {1, . . . , s}. Обозначим через m(n, k, t) величину max |M|, где
максимум берется по всем совокупностям M с указанными ограничениями. Ясно, что m(n, 3, 1) — это число, изученное в теореме 1 Ж.Надем, и что работать с m(n, k, t) в общем случае намного увлекательнее
и труднее.