Дискретный анализ 1. Числа Рамсея

• Приветствие и обсуждение заказа фермы.  

• Введение в числа Рамсея и их важность для теории алгоритмов.  

• Упоминание о том, что некоторые студенты уже знакомы с этой темой.  

• Теория Рамсея включает множество объектов, но на лекциях будут обсуждаться только числа Рамсея.  

• Числа Рамсея обозначаются буквой р и параметрами ст, где ст - натуральные числа.  

• Определение чисел Рамсея через раскраски ребер полного графа.  

• Минимальное натуральное число н такое, что при любой раскраске ребер полного графа на н вершинах либо найдется полный подграф на с вершинах с красными ребрами, либо найдется полный подграф на т вершинах с синими ребрами.  

• Логика задачи: при любой раскраске ребер рано или поздно найдется полный подграф с красными или синими ребрами.  

• Переформулировка определения через клики и независимые множества.  

• Минимальное натуральное н такое, что для любого графа на н вершинах либо альфа ж больше или равно с, либо омега ж больше или равно т.  

• Объяснение, почему это определение эквивалентно предыдущему.  

• Пример с графом на одной вершине: клика и независимое множество на одной вершине.  

• Пример с графом на двух вершинах: либо клика на двух вершинах, либо независимое множество на т вершинах.  

• Пример с графом на трех вершинах: либо треугольник на трех вершинах, либо независимое множество на трех вершинах.  

• Общая формула для чисел Рамсея пока не найдена, но найден порядок роста.  

• Пример с числами Рамсея для шести человек: либо трое попарно знакомы, либо трое попарно незнакомы.  

• Утверждение о том, что среди шести человек либо трое попарно знакомы, либо трое попарно незнакомы, является чисто математическим утверждением.  

• В графе нет треугольника или независимого множества из трех вершин.  

• Теорема доказана в 1935 году Эрдешем и Секерешем.  

• Они улучшили результат Рамсея, не зная о его работе.  

• Доказательство основано на индукции по двум параметрам.  

• Рассматривается полный граф с красными и синими ребрами.  

• Доказывается, что из каждой вершины выходит не менее определенного количества красных или синих ребер.  

• Теорема позволяет получить явную оценку на величину аратест.  

• Неравенство, фигурирующее в теореме, похоже на второе комбинаторное тождество.  

• База индукции для бесконечно большого количества тэ и с равна единице.  

• Диагональные числа Рамсея стоят по диагонали в таблице значений.  

• Точные значения известны в очень маленьком количестве случаев.  

• Понимание структуры чисел Рамсея важно для понимания хаоса и порядка в раскраске графов.  

• Центральная цешка числа Рамсея оценивается через формулу Стирлинга.  

• Оценка может быть завышена или занижена, что требует дальнейшего изучения.  

• Методы, связанные с теорией Рамсея, важны для других областей науки.  

• В прошлом семестре обсуждалась теорема о случайных графах.  

• Для случайного графа альфа-дже меньше или равно двум лок двоичный, а омега-дже меньше или равно с два лок двоичный.  

• Обсуждение лучшей оценки хроматического числа: омега или дробь альфа.  

• Оценка дроби альфа лучше при разумных значениях n.  

• Пример с числами Рамсея и теоремой о вероятности отсутствия клик.  

• Теорема утверждает, что для достаточно больших n существуют графы с альфа меньше и омега меньше.  

• Число Рамсея больше n, если в графе нет с-клик и с-независимых множеств.  

• Пример графа с n вершинами, где альфа меньше с и омега меньше с.  

• Доказательство существования графа с n вершинами без с-клик и с-независимых множеств.  

• Рассмотрение случайного графа и перечисление всех с-элементных подмножеств.  

• Оценка вероятности наличия с-клик и с-независимых множеств в случайном графе.  

• Оценка вероятности объединения с-клик и с-независимых множеств.  

• Математическое ожидание числа вредоносных множеств.  

• Проверка, что при n больше или равно 4, вероятность меньше единицы.  

• Теорема утверждает, что если вероятность меньше единицы, то число Рамсея больше n.  

• Доказательство через вероятностное отрицание.  

• Отрицание события состоит из графов без с-клик и с-независимых множеств, что подтверждает существование контрпримера.  

• Обсуждение различных методов получения оценок.  

• Упоминание о дополнительных фишках, улучшающих результаты.  

• Важность общезначимых следствий в других науках.  

• Огрубление экспоненты и использование теоремы двух штрихов.  

• Утверждение, что оценка наилучшая с точностью до малого от единицы.  

• Пример функции, которая выглядит хорошо при всех разумных значениях с.  

• Объяснение важности констант в науке.  

• Утверждение о том, что функция стремится к нулю при больших значениях с.  

• Пример записи функции в симпатотическом виде.  

• Объяснение, как читать неравенство и его асимптотику.  

• Пример подстановки функции в теорему.  

• Использование формулы Стирлинга для факториала.  

• Обсуждение подбора функции, стремящейся к нулю.  

• Пример функции, которая при больших значениях с равна минус один на с.  

• Утверждение, что при всех с оценка больше нуля, но правильная.  

• Важность понимания асимптотического роста функции.  

• Ожидания от функции и её поведение.  

• Подчеркивание важности жонглирования асимптотическими выражениями.  

• Автор устал от теоремы 1 и предлагает теорему 2.  

• Теорема 2 формулируется аналогично теореме 1, но с улучшением.  

• Утверждается, что для любых n и s, произведение n-s и 2 в степени 1-s больше единицы.  

• Автор объясняет, почему теорема 2 лучше теоремы 1.  

• В теореме 1 произведение n-s меньше единицы, что может быть улучшено.  

• Автор утверждает, что теорема 2 позволяет лучше оценить произведение.  

• Автор начинает доказательство теоремы 2, используя идею из прошлого семестра.  

• Рассматриваются с-элементные подмножества и их математическое ожидание.  

• Доказывается, что существует граф с заданным числом вершин, где число клик и независимых множеств не превышает определенное значение.  

• Автор переходит к следствию из теоремы 2.  

• Следствие утверждает, что из теоремы 2 вытекает оценка с некоторым малым от единицы.  

• Автор объясняет, как улучшить оценку, используя симтоматические методы.  

• Автор показывает, как улучшить оценку, исключая корень из двойки.  

• Объясняется, почему это улучшение важно и почему оно работает.  

• Автор завершает доказательство, подчеркивая, что это лучшее, что можно получить в рамках текущего подхода.