Графы Джонсона и их случайные подграфы. Семинар 1

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

Школьникам тематика будет вполне доступна.