Теорема Краскала — Катоны. MATH 492/529 Экстремальная комбинаторика, Университет Виктории.

Это видео взято из курса MATH 492/529 «Экстремальная комбинаторика», который ведёт Джонатан Ноэль в Университете Виктории. Тема — теорема Крускала-Катоны. Доказательства некоторых лемм были пропущены. Первоначальная дата: 18/20/21 января 2021 года. Конспекты лекций по этому курсу можно найти по адресу https://extremalcombinatorics.com/notes/. Веб-страница курса: https://extremalcombinatorics.com. Были предприняты усилия по удалению любой личной информации студентов из этого видео. Если вы обнаружите подобную информацию, пожалуйста, свяжитесь со мной по адресу noelj@uvic.ca, чтобы я мог решить эту проблему. 00:00 Тени 06:42 Колексикографический порядок 16:09 Теорема Крускала-Катоны 18:52 Вычисление позиции множества в колексе 35:45 Переформулировка теоремы Крускала-Катоны 40:04 Сжатия 48:17 Сжатия не меняют мощность множества 1:01:53 Сжатия не увеличивают тень 1:11:34 Сжатия завершаются 1:14:42 Доказательство теоремы Крускала-Катоны