О кликовом числе случайного подграфа одного кнезеровского графа
Автор: Гусев А.С.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Математика
Статья в выпуске: 1 (69) т.18, 2026 года.
Бесплатный доступ
В этой статье мы рассмотрим кликовое число случайного подграфа кнезеровского графа G(n,r,0) в случае r = n2 f (n), где f (n) = nо(1). В работе показано, что в завимимости от f (n) кликовое число соответствующего случайного подграфа может как с асимптотической вероятностью 1 совпадать с кликовым числом исходного графа, так и быть асимптотически меньше, а также приведены оценки на функцию f (n), при которых выполнены соответствующие свойства.
Дистанционный граф, случайный граф, кликовое число
Короткий адрес: https://sciup.org/142247881
IDR: 142247881 | УДК: 519
On the clique number of a random subgraph of some Kneser graph
In this paper, we consider the clique number of a random subgraph of Kneser’s graph G(n,r,0) in the case when r = n2 f(n), where f(n) = no(1). In our work, we show that depending on f(n) the clique number of the corresponding random subgraph can, with asymptotic probability 1, coincide with the clique number of the initial graph as well as become asymptotically smaller. Also we present bounds on the function f (n) guaranteeing the corresponding properties.
