Графы Джонсона и их случайные подграфы. Семинар 2 // Андрей Райгородский / ЛШСМ 2023

В лекциях я расскажу о некотором классе графов, которые возникают в самых разных областях дискретной математики — теории кодирования, теории Рамсея, комбинаторной геометрии и др. Акцент будет сделан на поведении чисел независимости этих графов и их случайных подграфов (число независимости — это количество элементов в самых больших множествах вершин, внутри которых отсутствуют ребра). Будут доказаны удивительные теоремы о том, что во многих случаях даже при удалении «почти всех» ребер из исходного графа число независимости не меняется. Если хватит времени, то я расскажу, как полученные результаты помогают поставить и частично решить ряд новых задач, обобщающих классическую задачу Рамсея. Школьникам тематика будет вполне доступна. Райгородский Андрей Михайлович — доктор физико-математических наук. Летняя школа «Современная математика», г. Дубна, 22-28 июля 2023 г.