Минимальное число клик в индуцированных подграфах графа Джонсона

Настоящая работа посвящена изучению экстремальных свойств графов Джонсона $G(n,r,s)$. Вершины такого графа соответствуют всем возможным $r$-элементным подмножествам $n$-элементного множества, а ребро между вершинами проводится тогда и только тогда, когда мощность пересечения соответствующих им подмножеств равна $s$. В общем виде задача состоит в нахождении асимптотики минимального числа клик мощности $k$ в подграфах $G(n,r,s)$ с $l$ вершинами. Особое внимание мы обратим на случай наименьшего количества треугольников, т.е. $k=3$, а также на случай $r=3$, $s=1$. Для случая $r=3$, $s=1$, $k=2$ поставленная задача была решена практически во всех режимах, в данной работе мы обобщим соответствующие теоремы на случай любой константы $k$. Также нами найдена асимптотика наибольшего числа вершин в подграфе $G(n,3,1)$, не содержащем треугольников. Такая величина в некотором смысле является обобщением числа независимости графа.
Библиография: 23 названия.