Дискретный анализ 14. Теоремы Франкла-Уилсона и Эрдеша-Ко-Радо.

• Лекция посвящена обобщению метода, примененного в прошлый раз.  

• Рассматривается задача о линейной независимости алгебраических объектов.  

• Авторы результата - Франкл и Уилсон, 1981 год.  

• Теорема: максимальное количество ребер в однородном гиперграфе не превосходит суммы от нуля до p в степени альфа минус один.  

• Сравнение с предыдущим результатом: теорема обобщает предыдущие результаты.  

• Доказательство для случая, когда альфа равно единице.  

• Переход от множества ребер к векторам и многочленам.  

• Обобщение многочлена, используемого в прошлый раз.  

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

• Обобщение на случай, когда скалярное произведение не совпадает по модулю p.  

• Пример с многочленом, состоящим из единиц и нулей.  

• Фокус: замена квадратов и попарных произведений на нолики и единички.  

• Многочлены остаются линейно независимыми после подстановки.  

• Преобразование многочленов с помощью раскрытия скобок.  

• Пример преобразования многочлена с использованием степеней и констант.  

• Преобразование многочлена путем замены степеней на единицы.  

• Многочлены с волной имеют те же значения, что и исходный многочлен.  

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

• Линейная независимость многочленов с волной.  

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

• Доказательство, что произведение многочленов не делится на простое число.  

• Вывод, что многочлены с волной не делятся на простое число.  

• Многочлены с волной линейно независимы и имеют размерность пространства.  

• Базис многочленов с волной и их линейная независимость.  

• Размерность пространства многочленов и их линейная независимость.  

• Переход к задаче о графах с общими ребрами.  

• Временное переключение на задачу о графах с непересекающимися ребрами.  

• Важность задачи о графах с общими ребрами и ее асимптотическое решение.  

• Асимптотика задачи о графах с общими ребрами.  

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

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

• Если взять слагаемые меньше, чем p-c-2, то асимптотика суммы будет совпадать с асимптотикой самого большого слагаемого.  

• Нижняя асимптотика совпадает с предыдущей, рассмотренной ранее.  

• Пример гиперграфа с ребрами, пересекающимися по c+1 вершинам, показывает асимптотику.  

• Рассказ о Пранкле, венгерском математике, который живет в Японии.  

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

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

• Лекция Пранкла была посвящена комбинаторным результатам и сравнению количества объекций.  

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

• Пранкл нарисовал козла, чтобы объяснить слово "баран" на русском языке.  

• Пранкл продолжил лекцию, несмотря на возникшие трудности.  

• Пранкл активно сотрудничает с лабораторией и является соавтором многих работ.  

• Асимптотика гиперграфа с ребрами, пересекающимися по c+1 вершинам.  

• Гиперграф используется для кодирования и исправления ошибок в каналах связи.  

• Простая верхняя оценка для этой величины.  

• Рассуждение о том, почему оценка меньше или равна.  

• Пример с ребрами гиперграфа, пересекающимися по c+1 вершинам.  

• Объяснение, почему мощность подмножеств, пересекающихся с ребрами, меньше, чем c+1.  

• Объяснение, что множества с малой пересечением не могут иметь общих подмножеств с мощностью больше, чем их мощность плюс один.  

• Объяснение оценки мощности объединения множеств как суммы их мощностей.  

• Упоминание о границе теории кодирования, доказанной в 1980-х годах.  

• Упоминание о теореме Ределя, доказанной в начале 1980-х годов.  

• Объяснение асимптотики верхней границы, достигаемой на границе Дирихле.  

• Упоминание о методе доказательства, использующем вероятностные конструкции.  

• Упоминание о достижении точного равенства в 2010-х годах.  

• Описание метода доказательства, включающего вероятностную и алгебраическую технику.  

• Обсуждение границ в теории кодирования, включая границы Варшамова-Гилберта и Ливенштейна.  

• Упоминание о нерешенных проблемах в этой области.  

• Объяснение теоремы Эрдаша-Корадо, утверждающей, что функция f равна c(n,r) при определенных условиях.  

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

• Введение вспомогательных множеств для доказательства теоремы.  

• Упоминание о вкладе Дьюлы Катаны в эту область.  

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

• Объяснение, как эти множества могут пересекаться с исходными множествами.  

• Подведение итогов и объяснение, что среди исходных множеств могут быть элементы, пересекающиеся с вспомогательными множествами.  

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

• Пример: система сарделек, расположенных по кругу, где не более m сарделек могут попасть в пересечение.  

• Если пересечение пусто, лемма верна, так как ноль не больше, чем m.  

• Если пересечение не пусто, то все остальные множества должны пересекаться с ним.  

• Множество a1 принадлежит пересечению, и все остальные множества должны пересекаться с ним.  

• Все множества, пересекающиеся с a1, образуют пары, из которых можно взять не более одного множества.  

• Нумерация вершин может быть любой, например, сигма.  

• Вводим обозначение aσ для множества a с индексом сигма.  

• Доказательство: эн факториал одинаковых клемм.  

• Цель: доказать, что t не превосходит n-1 по p-1.  

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

• Индикатор: если ef принадлежит aσ, то единица, иначе ноль.  

• Сумма индикаторов не превосходит эн факториал.  

• Суммирование по всем σ не превосходит p умножить на эн факториал.  

• Фиксируем множество мощности p.  

• Считаем, сколько перестановок начинаются с множества fyt.  

• Обсуждается, как перестановки влияют на гиперграфы.  

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

• Существует шесть вариантов перестановок, начинающихся с 1, 2, 3.  

• Утверждается, что количество перестановок равно n! * (n - r)!.  

• Перестановки можно переставлять, но число 1, 2, 3 всегда будет в начале.  

• Перестановки считаются как обычные, а не циклические.  

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

• Перестановки считаются как обычные перестановки, а не круги.  

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

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

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

• Подведение итогов и завершение обсуждения.