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

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