Файл: Элементы комбинаторики.pdf

11. ПРОГРАММА КУРСА ДА 2014-16 УЧ. ГОДОВ
235 16.
(5) Многоцветные числа Рамсея R
k
(l
1
, . . . , l r
)
и их рекуррент- ная верхняя оценка. Следствие для R
3
(s, t)
. Нижняя вероятностная оценка для R
3
(s, s)
. (Задачи 4.2.2.b, 4.2.7.)
17.
(8) Верхняя оценка Конлона для двудольных чисел Рамсея:
лемма с конкретными l, m, r, s и ее аналог с последовательностями
(б/д); доказательство оценки с использованием леммы. (Есть ори- гинальная статья Conlon’а, скачивается с его домашней страницы.)
18.
(8) Конструктивная нижняя оценка Франкла–Уилсона для R(s, s).
[R3]
19.
(6) Замечание о распределении простых в натуральном ряде и его роли в аккуратном доказательстве нижней оценки Франкла–
Уилсона для R(s, s). [R3]
Глава 5. Системы множеств (гиперграфы) (20-23 1-й се- местр, 24-31 2-й семестр)
20.
(5) Гиперграфы. Гиперграфы t-пересечений. Теорема Эрдеша–
Ко–Радо (о максимальном числе ребер в гиперграфе 1-пересечений);
б/д. (Задача 5.1.3.)
21.
(7) Теорема Эрдеша–Ко–Радо. (Задача 5.1.3.)
22.
(7) Пример
(
n
−t k
−t
)
подмножеств n-элементного множества, в каж- дом из которых ровно k элементов и любые два из которых пересе- каются не менее чем по t элементам.
23.
(7) История последовательных продвижений в задаче: теоре- ма Эрдеша–Ко–Радо (общий случай), теорема Франкла, теорема
Уилсона, теорема Алсведе–Хачатряна (все б/д, но с подробными комментариями). (Задачи 5.1.2, 5.1.3.)
24.
(2) Системы общих представителей (с.о.п.). «Тривиальные» ниж- ние и верхние оценки.
25.
(5) Верхняя оценка (размера минимальной) с.о.п. с помощью жадного алгоритма. (Задачи 5.2.1, 5.2.5, 5.2.6.a.)
26.
(9) Конструктивная нижняя оценка с.о.п. (Задача 5.2.6.b.)

236
Элементы дискретной математики в задачах
27.
(7) Нижняя оценка с.о.п. с помощью обобщенных с.о.п. (Задача
5.2.6.c.)
28.
(10) Вероятностная нижняя оценка с.о.п. (Задача 5.2.6.def.) След- ствие из нее.
29.
(6) С.о.п. в геометрии (теорема о треугольниках на плоскости).
Размерность Вапника–Червоненкиса. (Задача 5.5.1.) Теорема Радо- на (б/д). Подсчет размерности семейства полупространств (Задача
5.5.2.bc.) Оценка числа подмножеств в семействе заданной размер- ности на n-элементном множестве. (Задача 5.5.9.) Лемма о размер- ности измельчения (с не очень подробными выкладками).
30.
(8) Эпсилон-сети. Теорема Вапника–Червоненкиса об эпсилон- сетях и теорема о треугольниках как частный случай.
31.
(6) Теорема Вапника–Червоненкиса (б/д). Приложения в стати- стике: равномерная сходимость в ЗБЧ (УЗБЧ) и теорема Гливенко–
Кантелли как частный случай.
Глава 6. Аналитические и вероятностные методы (32-36 1-й семестр, 37-49 2-й семестр)
32.
(3) Оценки для факториалов и биномиальных коэффициентов.
(Задача 6.1.7.a.) Оценки для
(
n n/2
)
с помощью тождества. (Задача
6.1.5.ab.)
33.
(5) Асимптотика ln n! и n
√
n!
с доказательством без использова- ния формулы Стирлинга. Формула Стирлинга (б/д). (Задача 6.1.6.)
34.
(5) Оценка биномиальных коэффициентов вида
(
n
[an]
)
, a ∈ (0, 1).
Аналогичный результат для полиномиальных коэффициентов. (За- дача 6.1.5.cdef.)
35.
(5) Асимптотика для
(
n k
)
при k
2
= o(n)
. Оценки той же ве- личины при больших k. Асимптотики для
(
n n/2
)
/
(
n n/2
−x
)
. (Задача
6.1.7.bcde.)
36.
(7) Асимптотика числа унициклических графов. (Задача 6.1.12.b.)

11. ПРОГРАММА КУРСА ДА 2014-16 УЧ. ГОДОВ
237 37.
(5) Симметричный и несимметричный случай ЛЛЛ (б/д). Вы- вод оценки диагонального числа Рамсея (теорема Спенсера). (За- дачи 6.2.15, 6.2.21.b и 6.2.26.а.)
38.
(6) Симметричный и несимметричный случай ЛЛЛ (с дока- зательством симметричного — либо напрямую, либо с доказатель- ством несимметричного и выводом из него). (Задачи 6.2.15 и 6.2.26.а.)
39.
(9) Вывод из несимметричного случая ЛЛЛ нижней оценки для
R(3, t)
: Самые точные известные оценки для R(3, t) (б/д). (Задача
6.2.26.b и замечание после нее.)
40.
(5) Двудольные числа Рамсея: нижние оценки простым веро- ятностным методом и с помощью ЛЛЛ. Отличие нижних оценок для двудольных чисел Рамсея от аналогичных нижних оценок для
R(s, t)
. (Литературы нет; делается совершенно аналогично тому,
как то же самое делается для обычных чисел Рамсея.)
41.
(5) Случайные графы. Неравенства Маркова и Чебышёва. Нера- венство для случайного блуждания. (п. 6.3, [R4, п. 1.11 и 1.12])
42.
(5) Связность случайного графа (б/д). Случайные величины и вероятностные неравенства, необходимые для доказательства. [R4,
п. 2.5]
43.
(7) Связность случайного графа: случай p = c ln n/n при c < 1.
Теоремы о ln n + γ + o(1)
n и о гигантской компоненте (б/д). [R4, п.
2.5]
44.
(8) Связность случайного графа: случай p = c ln n/n при c > 1.
[R4, п. 2.5]
45.
(3) Теоремы Боллобаша о хроматическом числе случайного гра- фа (б/д). Пояснения к ним: случаи p = o(1/n
2
)
и p = o(1/n). [R4,
п. 2.6]
46.
(9) Пояснения к теоремам Боллобаша о хроматическом числе случайного графа: случай p = c/n, c < 1 (б/д) и случай, когда функция из второй теоремы Боллобаша может стремиться к беско- нечности. [R4, п. 2.6]

238
Элементы дискретной математики в задачах
47.
(7) Сравнение оценок хроматического числа через кликовое число и число независимости в терминах случайных графов: одна
«почти всегда» значительно лучше другой (распределение клико- вого числа и числа независимости). [R4, п. 2.7]
48.
(10) Теорема о том, что почти наверное жадный алгоритм най- дет множество, размер которого лишь, как максимум, в 2 раза от- личается от реального. Теорема Кучеры о слабости жадного алго- ритма на специальных графах (б/д). (А. Райгородский, "Экстре- мальные задачи теории графов и Интернет" , Интеллект.)
49.
(9) Теорема Эрдеша о графе с большим обхватом и большим хроматическим числом. (Задача 6.3.3.c.)
Глава 7. Алгебраические методы (50-58 1-й семестр, 59-
64 2-й семестр)
50.
(4) Граф пересечений для полного однородного гиперграфа.
Его кликовое число и число независимости (б/д). (Задача 5.1.3.)
51.
(5) Кнезеровский граф. Верхняя оценка его хроматического числа. Простые нижние оценки. Примеры конкретных кнезеров- ских графов. Кликовое число и число независимости кнезеровского графа. ([R7] := А. Райгородский, "Гипотеза Кнезера и топологиче- ский метод в комбинаторике МЦНМО.)
52.
(6) Верхняя оценка хроматического числа кнезеровского графа.
Теорема Ловаса о хроматическом числе кнезеровского графа (б/д;
с доказательством — на ‘8’). [R7]
53.
(7) Теорема Борсука–Улама–Люстерника–Шнирельмана в раз- ных формулировках, но с доказательством только в случае плоско- сти и трехмерного пространства. [R7]
54.
(6) Максимальное число m(n, k, t) подмножеств n-элементного множества, в каждом из которых ровно k элементов и среди кото- рых любые два множества пересекаются не по t элементам. Точное значение для m(n, 3, 1): явная конструкция и оценка по индукции.
Линейно-алгебраическая оценка для m(n, 3, 1). Аналогичная оценка для m(n, 5, 2) и ее асимптотическая неулучшаемость. [R1]

11. ПРОГРАММА КУРСА ДА 2014-16 УЧ. ГОДОВ
239 55.
Общая теорема Франкла–Уилсона об m(n, k, k − p) при k < 2p
(6). Замечание о непростом «модуле» (10). (Задача 7.1.8 и [R1].)
56. (только в 2015)
(9) Теорема Франкла–Уилсона об m(n, k, k−p)
при k
> 2p. [R1]
57. (только в 2015)
(7) Точность обеих теорем Франкла–Уилсона при постоянных k, t. Максимальное число k-элементных подмно- жеств n-элементного множества, из которых любые два множества пересекаются не более чем по t элементам. Связь с теорией кодиро- вания, теорема Редля (б/д). [R1]
58.
(6) Хроматические числа пространств. Историческая справка.
Интерпретация величины m(n, k, t) как числа независимости ди- станционного графа. Нижняя оценка хроматического числа про- странства с помощью результатов для m(n, k, t). Возможные улуч- шения. ([R1] и А. Райгородский, "Хроматические числа".)
59.
(3) Матрицы Адамара. Необходимое условие существования.
Гипотеза Адамара. Нормализация. (Задачи 7.2.1-7.2.3, определения и гипотеза в §7.2, [Hal].)
60.
(5) Неудачная попытка построить матрицу Адамара «строчка за строчкой».
61.
(5) Теорема о плотности порядков матрицы Адамара в нату- ральном ряде (б/д). [Hal, AS]
62.
(6) Приложения матриц Адамара к задаче о раскраске гипер- графа: определение уклонения, верхняя оценка вида
√
2n ln(2s)
с доказательством и оценка вида 6
√
n
(б/д). [R3]
63.
(8) Приложения матриц Адамара к задаче о раскраске гипер- графа: нижняя оценка с помощью матриц Адамара. [R3]
64.
(6) Интерпретация в терминах дистанционного графа, возника- ющего в теореме Франкла–Уилсона (клики и независимые множе- ства).

240
Элементы дискретной математики в задачах
ОБРАЗЦЫ ВОПРОСОВ НА ЭКЗАМЕНЕ
Предварительная часть (вариант 2014 года).
Нужен толь- ко ответ/формулировка; доказательства приводить не нужно.
1. Найдите асимптотику биномиального коэффициента
(
n k
)
при k
2
= o(n)
2. Найдите количество деревьев с данными n вершинами, с точ- ностью до изоморфизма.
3. Дайте определение гамильтонова цикла в графе. (Можно ис- пользовать только определение графа. Если Вы используете другие определения — например, цикла — то их тоже нужно дать.)
4. Сформулируйте теорему о хроматическом числе случайного графа в модели G(n, p) при p = o(1/n) и n → ∞.
5. У дистанционного графа на плоскости 4n вершин, и среди любых n+1 вершин есть ребро. Сформулируйте наилучшую оценку на количество ребер такого графа, доказанную в курсе.
6. Найдите кликовое число графа, вершины которого — все 5- элементные подмножества 20-элементного множества, и ребро меж- ду вершинами проводится в том и только в том случае, когда мно- жества не пересекаются?
7. Найдите R
4
(15, 4, 4, 4)
8. Найдите максимальную VC-размерность семейства подмно- жеств множества {1, . . . , 10} в каждом подмножестве которого бо- лее 5 элементов.
Основная часть (точно таких вопросов на экзамене не будет).
Здесь главное — не ответы, а доказательства. В частно- сти, формулировки и доказательства всех используемых студен- том результатов из курса ДА (в частности, всех результатов из курса ДА, используемых для доказательства других результатов из курса ДА). При этом можно пользоваться без доказательства результатами из других курсов.
Вопрос из билета.
Существует ли 57 подмножеств 60-элементного множества, в каждом из которых 30 элементов, и любые два из ко- торых пересекаются по 15 элементам?
(Если используется задача 7.2.4, то ее нужно доказать.)
Доп. вопрос попроще.
Каково наибольшее число ребер в

11. ПРОГРАММА КУРСА ДА 2014-16 УЧ. ГОДОВ
241

графе с 52 вершинами, в котором среди любых 5 вершин есть 2, не соединенные ребром?
(Если используется теорема Турана, то ее нужно доказать.)
Доп. вопрос посложней.
Укажите функцию f(n), для кото- рой R(n, n)
& f(n). (Чем больше функция, тем выше Ваша оценка.)
(Если используется неравенство n!
> (n/e)
n
(6.1.6.с) или ЛЛЛ
(6.2.15.b), то их нужно доказать; это неравенство доказывается без использования формулы Стирлинга.)