Числа независимости случайных подграфов дистанционных графов

В данной работе рассматривается так называемый дистанционный граф $G(n,r,s)$, вершины которого можно отождествить с $r$-элементными подмножествами множества $\{1,2,\dots,n\}$, а ребро между двумя вершинами проводится в том случае, если размер пересечения соответствующих подмножеств равен $s$. В случае $s=0$ такие графы называются кнезеровскими. Данные графы тесно связаны с задачей Эрдеша–Ко–Радо, а также играют важную роль в комбинаторной геометрии и теории кодирования.
Мы изучим некоторые свойства случайных подграфов графа $G(n,r,s)$ в модели Эрдеша–Реньи, в которой каждое ребро включается в подграф с некоторой фиксированной вероятностью $p$ и независимо от остальных ребер. В работе найдена асимптотика числа независимости случайного подграфа $G(n,r,s)$ в случае постоянных $r$ и $s$: в случае $r \le 2s+1$ размер такого в $\Theta(\log_2n)$ раз больше, чем размер такового в самом графе $G(n,r,s)$, а в случае $r > 2s+1$ наблюдается асимптотическая устойчивость: число независимости случайного подграфа асимптотически совпадает с числом независимости исходного графа $G(n,r,s)$.
Библиография: 28 названий.