Графы Джонсона, их случайные подграфы и некоторые их экстремальные характеристики

Одним из очень важных объектов современной теории графов является так называемый граф Джонсона $G(n,r,s)$. Его вершинами служат все $C_n^r$ подмножеств мощности $r$ множества $\{1,\dots,n\}$, а ребром две вершины соединяются тогда и только тогда, когда пересечение соответствующих подмножеств имеет мощность $s$. Такие графы играют огромную роль в теории кодирования, в экстремальной комбинаторике и теории Рамсея, в комбинаторной геометрии и др. В обзоре рассказывается о применениях этих графов и о нескольких их характеристиках, среди которых число независимости, кликовое число и хроматическое число. Также мы уделяем внимание большому и активно развивающемуся в последнее время разделу теории, связанному с рассмотрением случайных подграфов графов Джонсона.
Библиография: 135 названий.