More Related Content
Similar to Теорема Рамсея, оценки чисел Рамсея (20)
More from Alex Dainiak (11)
Теорема Рамсея, оценки чисел Рамсея
- 1. Дискретные структуры МФТИ, весна 2014 Александр Дайняк www.dainiak.com
- 2. Теорема Рамсея Теорема Турана оценивает, сколько рёбер достаточно добавить в граф, чтобы в нём появилась клика — «область плотности». Верно ли, что в любом большом (очень) графе найдётся либо большая «область плотности» (клика), либо большая «область неплотности» (независимое множество)? —Да, верно!
- 3. Теорема Рамсея Теорема (F.P. Ramsey). Для любых 𝑠 и 𝑡 найдётся такое 𝑁, что для любого графа 𝐺, имеющего не менее 𝑁 вершин, выполнено хотя бы одно из неравенств 𝛼 𝐺 ≥ 𝑠, 𝜔 𝐺 ≥ 𝑡. Переформулировка в терминах раскрасок: Для любых 𝑠, 𝑡 найдётся 𝑁, такое, что в любой раскраске рёбер 𝐾 𝑁 в красный и синий цвета найдётся полностью красный 𝐾𝑠 или полностью синий 𝐾𝑡 (возможно, и оба одновременно).
- 4. Теорема Рамсея Теорема (F.P. Ramsey). Для любых 𝑠 и 𝑡 найдётся такое 𝑁, что для любого графа 𝐺, имеющего не менее 𝑁 вершин, выполнено хотя бы одно из неравенств 𝛼 𝐺 ≥ 𝑠, 𝜔 𝐺 ≥ 𝑡. Минимальное такое 𝑁 называется числом Рамсея и обозначается 𝑅 𝑠, 𝑡 Тривиальные равенства: • 𝑅 𝑠, 1 = 𝑅 1, 𝑡 = 1 • 𝑅 𝑠, 2 = 𝑠, 𝑅 2, 𝑡 = 𝑡
- 5. Доказательство теоремы Рамсея Индукцией по 𝑠, 𝑡 докажем неравенство 𝑅 𝑠, 𝑡 ≤ 𝑅 𝑠 − 1, 𝑡 + 𝑅 𝑠, 𝑡 − 1 Пусть 𝑅 𝑠 − 1, 𝑡 и 𝑅 𝑠, 𝑡 − 1 существуют. Пусть 𝐺 — произвольный граф, такой, что 𝐺 = 𝑅 𝑠 − 1, 𝑡 + 𝑅 𝑠, 𝑡 − 1 . Пусть 𝑣 ∈ 𝑉 𝐺 — произвольная вершина, 𝑁 — множество соседей 𝑣, 𝑁 — множество вершин, не смежных с 𝑣.
- 6. Доказательство теоремы Рамсея Так как 𝐺 = 𝑅 𝑠 − 1, 𝑡 + 𝑅 𝑠, 𝑡 − 1 , то 𝑁 ≥ 𝑅 𝑠, 𝑡 − 1 или 𝑁 ≥ 𝑅 𝑠 − 1, 𝑡 . Пусть 𝑁 ≥ 𝑅 𝑠, 𝑡 − 1 . Тогда, по предположению, либо в 𝑁 есть н.м. размера 𝑠, и тогда 𝛼 𝐺 ≥ 𝑠, либо в 𝑁 есть клика 𝐾 размера 𝑡 − 1 , и тогда 𝐾 ∪ 𝑣 — клика в 𝐺, то есть 𝜔 𝐺 ≥ 𝑡. Случай 𝑁 ≥ 𝑅 𝑠 − 1, 𝑡 разбирается аналогично. 𝑣 𝑁 𝑁
- 7. Верхняя оценка чисел Рамсея Утверждение. 𝑅 𝑠, 𝑡 ≤ 𝑠 + 𝑡 − 2 𝑠 − 1 Доказательство: При 𝑠 = 1 или 𝑡 = 1 неравенство выполнено. При 𝑠, 𝑡 ≥ 2 по индукции получаем: 𝑅 𝑠, 𝑡 ≤ 𝑅 𝑠 − 1, 𝑡 + 𝑅 𝑠, 𝑡 − 1 ≤ 𝑠 + 𝑡 − 3 𝑠 − 2 + 𝑠 + 𝑡 − 3 𝑠 − 1 = = 𝑠 + 𝑡 − 2 𝑠 − 1
- 8. Верхняя оценка чисел Рамсея Утверждение (Рамсей ’1930, Эрдёш, Секереш ’1935). 𝑅 𝑠, 𝑡 ≤ 𝑠 + 𝑡 − 2 𝑠 − 1 Следствие. 𝑅 𝑠, 𝑠 ≤ 2𝑠 − 2 𝑠 − 1 ∼ 4 𝑠−1 𝜋𝑠 = 4 𝑠−Ω log 𝑠 Лучшая известная оценка (Конлон ’2009). 𝑅 𝑠, 𝑠 < 4 𝑠−Ω log2 𝑠 log log 𝑠
- 9. Нижняя конструктивная оценка чисел Рамсея Теорема. (Франкл, Уилсон) Для любого достаточно большого 𝑠 существует граф 𝐺, такой, что 𝛼 𝐺 ≤ 𝑠 и 𝜔 𝐺 ≤ 𝑠, и при этом 𝐺 ≥ exp ln 𝑠 2 72 ln ln 𝑠 Отсюда сразу следует, что 𝑅 𝑠, 𝑠 ≥ 𝑒 ln 𝑠 2 72 ln ln 𝑠 — то есть числа Рамсея растут сверхполиномиально.
- 10. Задание графа Пусть 𝑝 — простое, и пусть 𝑚 ≔ 𝑝3. Рассмотрим граф 𝐺 = 𝑉, 𝐸 , в котором 𝑉 ≔ 𝒂 ∈ 0,1 𝑚 ∣ 𝒂 = 𝑝 (т.е. в каждом векторе из 𝑉 ровно 𝑝2 единиц) 𝐸 ≔ 𝒂, 𝒃 ∣ 𝒂, 𝒃 = 𝑝 0 Оказывается, • 𝛼 𝐺 ≤ 𝑙=0 𝑝−1 𝑚 𝑙 • 𝜔 𝐺 ≤ 𝑙=0 𝑝 𝑚 𝑙
- 11. Оценка 𝛼 𝐺 : многочлены 𝑃𝒂 • 𝑉 ≔ 𝒂 ∈ 0,1 𝑚 ∣ 𝒂 = 𝑝 , где 𝑚 ≔ 𝑝3 • 𝐸 ≔ 𝒂, 𝒃 ∣ 𝒂, 𝒃 = 𝑝 0 Каждому вектору 𝒂 ∈ 𝑉 сопоставим многочлен 𝑃𝒂 𝒙 ≔ 𝑖=1 𝑝−1 𝒂, 𝒙 − 𝑖 ∈ ℤ 𝑝 𝑥1, … , 𝑥 𝑚 Для любых 𝒂, 𝒃 ∈ 𝑉 имеем 𝑃𝒂 𝒃 = 𝑝 0 ⇔ 𝒂, 𝒃 ≠ 𝑝 0
- 12. Оценка 𝛼 𝐺 : переходим от 𝑃𝒂 к 𝑃𝒂 𝑃𝒂 𝒙 ≔ 𝑖=1 𝑝−1 𝒂, 𝒙 − 𝑖 ∈ ℤ 𝑝 𝑥1, … , 𝑥 𝑚 Раскроем скобки в определении 𝑃𝒂 𝑥 , и каждый моном вида 𝑥𝑖1 𝑡1 ⋅ … ⋅ 𝑥𝑖 𝑙 𝑡 𝑙 заменим на 𝑥𝑖1 ⋅ … ⋅ 𝑥𝑖 𝑙 (т.е. «забудем» про степени). Получим новый многочлен 𝑃𝒂, такой, что • deg 𝑥 𝑘 𝑃𝒂 ≤ 1 для каждого 𝑘 ∈ 1, … , 𝑚 , • 𝑃𝒂 𝒄 = 𝑃𝒂 𝒄 для любого 𝒄 ∈ 0,1 𝑚 .
- 13. Оценка 𝛼 𝐺 : свойства 𝑃𝒂 для независимых множеств • 𝑉 ≔ 𝒂 ∈ 0,1 𝑚 ∣ 𝒂 = 𝑝 , где 𝑚 ≔ 𝑝3 • 𝐸 ≔ 𝒂, 𝒃 ∣ 𝒂, 𝒃 = 𝑝 0 Построили набор многочленов 𝑃𝒂, таких, что • deg 𝑥 𝑘 𝑃𝒂 ≤ 1 для каждого 𝑘 ∈ 1, … , 𝑚 , • для любых 𝒂, 𝒃 ∈ 𝑉 имеем 𝑃𝒂 𝒃 = 𝑝 0 ⇔ 𝒂, 𝒃 ≠ 𝑝 0 Пусть 𝒂1, … , 𝒂 𝑟 — независимое множество в 𝐺. Тогда ∀𝑖, 𝑗 ∈ 1, … , 𝑟 имеем 𝑃𝒂 𝑖 𝒂𝑗 ≠ 𝑝 0 ⇔ 𝒂𝑖, 𝒂𝑗 = 𝑝 0 ⇔ 𝑖 = 𝑗
- 14. Оценка 𝛼 𝐺 : размерность пространства, в котором лежат 𝑃𝒂 По любому независимому множеству 𝒂1, … , 𝒂 𝑟 можно построить многочлены 𝑃𝒂1 , … , 𝑃𝒂 𝑟 , такие, что ∀𝑖, 𝑗 ∈ 1, … , 𝑟 𝑃𝒂 𝑖 𝒂𝑗 ≠ 𝑝 0 ⇔ 𝑖 = 𝑗 Т.к. deg 𝑥 𝑘 𝑃𝒂 𝑖 ≤ 1 для каждого 𝑘 ∈ 1, … , 𝑚 , то каждый из многочленов лежит в пространстве с базисом из произведений вида 𝑥 𝑘1 ⋅ … ⋅ 𝑥 𝑘 𝑙 , где 0 ≤ 𝑙 ≤ 𝑝 − 1 и 1 ≤ 𝑘1 < 𝑘2 < ⋯ < 𝑘𝑙 ≤ 𝑚. Если мы покажем, что 𝑃𝒂1 , … , 𝑃𝒂 𝑟 линейно независимы, сразу получим оценку 𝑟 ≤ 𝑙=0 𝑝−1 𝑚 𝑙 .
- 15. Оценка 𝛼 𝐺 : доказываем л.н.з. 𝑃𝒂 для независимого множества ∀𝑖, 𝑗 ∈ 1, … , 𝑟 𝑃𝒂 𝑖 𝒂𝑗 ≠ 𝑝 0 ⇔ 𝑖 = 𝑗 Доказываем, что 𝑃𝒂1 , … , 𝑃𝒂 𝑟 л.н.з. Допустим, что ∃𝑐1, … , 𝑐 𝑟 ∈ ℤ 𝑝, такие, что 𝑐1 𝑃𝒂1 𝒙 + ⋯ + 𝑐 𝑟 𝑃𝒂 𝑟 𝒙 ≡ 𝑝 0 Подставим в это тождество 𝒂𝑖 вместо 𝒙. Получим: … + 𝑐𝑖−1 ⋅ 0 + 𝑐𝑖 ⋅ 𝑃𝒂 𝑖 𝒂𝑖 + 𝑐𝑖+1 ⋅ 0 + … = 𝑝 0 Отсюда 𝑐𝑖 = 0. Так как 𝑖 произвольно, то 𝑐1 = 𝑐2 = ⋯ = 𝑐 𝑟 = 0, что и требовалось доказать.
- 16. Оценка 𝜔 𝐺 : многочлены 𝑃𝒂 • 𝑉 ≔ 𝒂 ∈ 0,1 𝑚 ∣ 𝒂 = 𝑝 , где 𝑚 ≔ 𝑝3 • 𝐸 ≔ 𝒂, 𝒃 ∣ 𝒂, 𝒃 = 𝑝 0 Для оценки 𝜔 𝐺 введём многочлены 𝑃𝒂 𝒙 ≔ 𝑖=0 𝑝−1 𝒂, 𝒙 − 𝑖 ⋅ 𝑝 ∈ ℝ 𝑥1, … , 𝑥 𝑚 Опять же, из условий получаем, что для любой клики 𝒂1, … , 𝒂 𝑟 ⊆ 𝑉 выполнено свойство ∀𝑖, 𝑗 ∈ 1, … , 𝑟 𝑃𝒂 𝑖 𝒂𝑗 ≠ 0 ⇔ 𝑖 = 𝑗
- 17. Оценка 𝜔 𝐺 : переход к 𝑃𝒂 и оценка 𝜔 По клике 𝒂1, … , 𝒂 𝑟 построили многочлены 𝑃𝒂1 , … , 𝑃𝒂 𝑟 ∀𝑖, 𝑗 ∈ 1, … , 𝑟 𝑃𝒂 𝑖 𝒂𝑗 ≠ 0 ⇔ 𝑖 = 𝑗 Как и раньше, «забываем» про степени переменных в 𝑃𝒂1 , … , 𝑃𝒂 𝑟 и тем самым получаем многочлены 𝑃𝒂1 , … , 𝑃𝒂 𝑟 . ∀𝑖, 𝑗 ∈ 1, … , 𝑟 𝑃𝒂 𝑖 𝒂𝑗 ≠ 0 ⇔ 𝑖 = 𝑗 Многочлены 𝑃𝒂1 , … , 𝑃𝒂 𝑟 л.н.з. и лежат в пространстве, порождённом мономами вида 𝑥 𝑘1 ⋅ … ⋅ 𝑥 𝑘 𝑙 , где 0 ≤ 𝑙 ≤ 𝑝 и 1 ≤ 𝑘1 < 𝑘2 < ⋯ < 𝑘𝑙 ≤ 𝑚. Теорема полностью доказана.
- 18. Завершение доказательства теоремы: подбор параметров — арифметика Итак, мы построили для простого 𝑝 граф, в котором • 𝛼 𝐺 ≤ 𝑙=0 𝑝−1 𝑝3 𝑙 • 𝜔 𝐺 ≤ 𝑙=0 𝑝 𝑝3 𝑙 • 𝐺 = 𝑝3 𝑝2 При 𝑝 > 4 имеем 𝛼, 𝜔 ≤ 𝑝 ⋅ 𝑒𝑝3 𝑝 𝑝 < 𝑝3𝑝 и 𝐺 > 𝑝3 𝑝2 𝑝2 = 𝑝 𝑝2
- 19. Завершение доказательства теоремы: подбор параметров — арифметика При простом 𝑝 > 4 есть 𝐺, в котором 𝛼, 𝜔 < 𝑝3𝑝 и 𝐺 ≥ 𝑝 𝑝2 . Зафиксируем 𝑠 и посмотрим, насколько большим можно взять 𝑝, чтобы выполнялось неравенство 𝑝3𝑝 ≤ 𝑠 Возьмём 𝑝 ∈ ln 𝑠 6 ln ln 𝑠 , ln 𝑠 3 ln ln 𝑠 . Тогда 𝑝3𝑝 = 𝑒3𝑝 ln 𝑝 ≤ 𝑒 3⋅ ln 𝑠 3 ln ln 𝑠 ⋅ln ln 𝑠 = 𝑠 и 𝑝 𝑝2 = 𝑒 𝑝2 ln 𝑝 ≥ exp ln 𝑠 6 ln ln 𝑠 2 ⋅ 1 2 ln ln 𝑠 = exp ln 𝑠 2 72 ln ln 𝑠
- 20. Неконструктивная оценка чисел Рамсея с помощью вероятностного метода Теорема. 𝑅 𝑠, 𝑠 ≳ 1 𝑒 2 ⋅ 𝑠 ⋅ 2 𝑠 Идея: Чтобы доказать нижнюю оценку вида 𝑅 𝑠, 𝑠 > 𝑛, достаточно доказать, что существует граф на 𝑛 вершинах, в котором нет ни клик, ни независимых множеств размера 𝑠. Возьмём случайный граф и покажем, что с ненулевой вероятностью он нам подойдёт.
- 21. Нижняя оценка чисел Рамсея: вводим вероятностную модель Пусть 𝑛 ≔ 20.5 𝑠 , и пусть 𝑉 ≔ 𝑣1, … , 𝑣 𝑛 — фиксированное множество вершин. Построим на этих вершинах случайный граф, проводя каждое из 𝑛 2 рёбер независимо от других с вероятностью 1 2. Вероятность получить при этом любой конкретный граф на вершинах 𝑣1, … , 𝑣 𝑛 равна 2− 𝑛 2
- 22. Нижняя оценка чисел Рамсея: «плохие» события и их вероятности Для каждого множества 𝑈 ⊂ 𝑉 размера 𝑠 рассмотрим события 𝐴 𝑈 ≔ «множество 𝑈 независимое» 𝐵 𝑈 ≔ «множество 𝑈 образует клику» Для каждого 𝑈 имеем Pr 𝐴 𝑈 = Pr 𝐵 𝑈 = 2− 𝑠 2 Тогда Pr 𝑈⊂𝑉 𝐴 𝑈 ∪ 𝑈⊂𝑉 𝐵 𝑈 ≤ 𝑈⊂𝑉 Pr 𝐴 𝑈 + 𝑈⊂𝑉 Pr 𝐵 𝑈 = 2 ⋅ 𝑛 𝑠 ⋅ 2− 𝑠 2
- 23. Неравенство, при котором вероятность возникновения плохих событий < 1 • Pr 𝑈⊂𝑉 𝐴 𝑈 ∪ 𝐵 𝑈 ≤ 𝑛 𝑠 ⋅ 21− 𝑠 2 Если мы подберём 𝑛 так, чтобы выполнялось 𝑛 𝑠 ⋅ 21− 𝑠 2 < 1, то тем самым докажем, что 𝑅 𝑠, 𝑠 > 𝑛. При этом хотим, чтобы 𝑛 было побольше. 𝑛 𝑠 < 2 𝑠 2 −1 Нам хватит и такого неравенства: 𝑒𝑛 𝑠 𝑠 < 2 𝑠 2 −1
- 24. Нижняя оценка чисел Рамсея Всё хорошо, если 𝑒𝑛 𝑠 𝑠 < 2 𝑠 2 −1 Берём корень из обеих частей: 𝑒𝑛 𝑠 < 2 𝑠−1 2−1 𝑠 Видно, что можно взять 𝑛 ≔ 𝑠⋅2 𝑠 2 𝑒 2⋅21 𝑠 − 1 , откуда 𝑅 𝑠, 𝑠 ≳ 1 𝑒 2 ⋅ 𝑠 2 𝑠
- 25. Нижняя оценка чисел Рамсея: ещё раз основная идея • Случайный граф содержит клику или независимое множество размера 𝑠 с вероятностью не более 𝑛 𝑠 ⋅ 21− 𝑠 2 . • При 𝑛 < 1 𝑒 2⋅21 𝑠 ⋅ 𝑠 2 𝑠 выполнено неравенство 𝑛 𝑠 ⋅ 21− 𝑠 2 < 1, и тогда с положительной вероятностью случайный граф не содержит ни клик ни независимых множеств размера 𝑠. • Это и означает существование искомого графа. • Отсюда делаем вывод, что 𝑅 𝑠, 𝑠 > 𝑠 2 𝑠 𝑒 2⋅21 𝑠 .