Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Покупка
Артикул: 686625.01.99
Современная комбинаторика это весьма многогранная и ак- тивно развивающаяся область математики. В XX веке был разра- ботан ряд мощных методов, позволяющих решать многие трудные задачи комбинаторики. Среди этих методов особое место занимает линейно-алгебраический метод. С его помощью удалось добиться прорыва в таких классических проблемах, как, например, пробле- ма Борсука о разбиении множеств на части меньшего диаметра. В книге излагаются основы метода и описываются наиболее яркие примеры его применения. Для понимания материала достаточно знания элементарных понятий линейной алгебры и математиче- ского анализа. Книга будет полезна студентам и аспирантам, ин- тересующимся комбинаторным анализом, а также специалистам в области дискретной математики.
Райгородский, А. М. Линейно-алгебраический метод в комбинаторике: Учебное пособие / Райгородский А.М., - 2-е изд., доп. - Москва :МЦНМО, 2015. - 144 с.: ISBN 978-5-4439-2489-2. - Текст : электронный. - URL: https://znanium.com/catalog/product/970187 (дата обращения: 29.03.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
А.М.Райгородский

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

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

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

Москва
Издательство МЦМНО
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) в общем случае намного увлекательнее
и труднее.

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

По-видимому первым, кто стал активно исследовать m(n, k, t), был
Поль Эрдёш, которого мы упоминали во введении. Мы не станем
вдаваться здесь в подробности «кустарного», так сказать, периода
в истории проблемы отыскания величины m(n, k, t) или хотя бы ее
оценок. Заметим только, что проблема очень быстро сделалась крайне
популярной. Ею занимались многие выдающиеся «дискретчики», но
даже, скажем, при k = 5, t = 2 полного решения ее найти не удавалось.
Что уж говорить о ситуациях, когда k = k(n) и t = t(n), например,
k = [n/2], t = [n/4]! И вот тут линейная алгебра пришла на помощь:
в конце семидесятых — начале восьмидесятых годов XX века два великолепных «комбинатора» П.Франкл и Р.М.Уилсон разработали целый линейно-алгебраический метод, позволивший отыскать m(n, k, t)
при очень многих значениях параметров n, k, t.
Мы поступим следующим образом. Сперва сформулируем частный
случай теоремы Франкла—Уилсона. Уже он будет исключительно
нетривиален, и все изящество, всю глубину линейно-алгебраического
подхода можно будет наблюдать в процессе его доказательства, которое мы проведем в п. 2.2. Затем в п. 2.3 мы еще раз убедимся
в силе метода, установив, что результат, полученный с его помощью,
неулучшаем. В то же время мы увидим там, насколько неожиданным
и почти невероятным является этот результат. Далее, в п. 2.4 мы дадим общую формулировку теоремы Франкла—Уилсона и постараемся
развернуть панораму многочисленных результатов, которые возникли
в связи с ней и около нее — в том числе (и в первую очередь) за счет
линейно-алгебраического метода. Наконец, в п.2.5 мы обсудим вопрос
о точности общей теоремы Франкла—Уилсона из п.2.4.
Итак, имеет место
Теорема 2 (П. Франкл и Р. М. Уилсон, [42]). Пусть p — некоторое
простое число, n = 4p, k = 2p, t = p. Тогда

m(n, k, t) ⩽ 2Cp−1
n−1.

Повторим еще раз, что пока сформулирован лишь весьма специальный случай теоремы. Тем не менее уже он не может не производить
впечатление (ср. п. 2.3). Правда, немного странным выглядит появление простого числа в формулировке, но оно там существенно, и в этом
мы тоже потом убедимся.

2.2. Доказательство теоремы Франкла—Уилсона

Доказательство.
Пусть M = {M1, . . . , Ms} — это совокупность
k-элементных подмножеств множества Rn, где k = 2p, n = 4p, причем

2.2. Доказательство теоремы Франкла—Уилсона
11

никакие два множества Mi, Mj ∈ M не пересекаются ровно по p
элементам из Rn. Сперва мы применим простой технический трюк.
Рассмотрим отдельно те множества из M, которые содержат элемент
1 ∈ Rn, и отдельно — те множества, которые этот элемент не содержат.
Таким образом, совокупность M распадется на две непересекающиеся
подсовокупности — скажем,

M1 = {M ∈ M: 1 ∈ M}

и
M2 = {M ∈ M: 1 ̸∈ M}.

Если нам удастся показать, что |Mν| ⩽ Cp−1
n−1, ν = 1, 2, то утверждение
теоремы 2 будет обосновано. На самом деле все равно, с какой из двух
совокупностей работать в дальнейшем. Дабы не загромождать текст
одинаковыми рассуждениями, мы проведем их во всех подробностях
лишь для M2. А уж разобраться с аналогичными выкладками для
M1 заинтересованный читатель сможет без труда. К тому же так
и метод будет понятнее. К нему мы теперь и перейдем.
Итак, мы можем считать отныне, что наша новая совокупность

N = M2 = {N1, . . . , Ns}

состоит из k-элементных подмножеств множества Rn \ {1}, которое
ничто не мешает нам отождествить с Rn−1 = {1, . . . , n − 1}. При этом
Ni ∩ Nj
̸= p
для любых i, j ∈ {1, . . . , s}.

Нетривиальная идея, которую мы будем реализовывать, сводится
к тому, чтобы k-элементным подмножествам Rn−1 сопоставить некоторую матрицу и векторное пространство размерности не более Cp−1
n−1,
порожденное ее строками. Если нам удастся сделать это достаточно
хитро, то затем мы сумеем так преобразовать нашу матрицу, что
мощность совокупности N окажется не превосходящей ранга новой
матрицы, а он, в свою очередь, будет не выше размерности нашего
векторного пространства, т. е. как раз ожидаемой нами величины
Cp−1
n−1. В этом суть линейно-алгебраического метода, но как ее воплотить в жизнь? Ниже мы ответим на поставленный вопрос.
Пусть A1, . . . , ACj
n−1 — это все возможные j-элементные подмножества, а B1, . . . , BCi
n−1 — это все возможные i-элементные подмножества в Rn−1. Будем считать, что 0 ⩽ i ⩽ j ⩽ n − 1, и потенциальное
равенство нулю величин i и j никого не должно смущать: «нольэлементные подмножества» какого-либо множества — это ровно одно
его пустое подмножество, и мы просто доопределим значения биноми
альных коэффициентов, полагая (стандартно) C0
m =
m!
m! 0! = 1 и, более