Аннотация:
Дистанционным графом G(n,2,1) называется граф, вершины которого отождествляются с двухэлементными подмножествами множества {1,2,…,n}, а ребро между вершинами проведено в том случае, если соответствующие подмножества имеют ровно один общий элемент. Случайный подграф Gp(n,2,1) в модели Эрдеша–Реньи получается включением каждого ребра графа G(n,2,1) с вероятностью p независимо от остальных ребер. Найдена нижняя оценка числа независимости случайного подграфа G1/2(n,2,1).
Поступила в редакцию: 25.02.2017 После переработки: 04.05.2017
Образец цитирования:
Н. М. Деревянко, С. Г. Киселев, “Числа независимости случайных подграфов некоторого дистанционного графа”, Пробл. передачи информ., 53:4 (2017), 3–15; Problems Inform. Transmission, 53:4 (2017), 307–318
J. C. Buitrago Oropeza, “Maximum Induced Trees in Sparse Random Graphs”, Dokl. Math., 109:2 (2024), 167
А. М. Райгородский, В. С. Карась, “Асимптотика числа независимости случайного подграфа
графа $G(n,r,<s)$”, Матем. заметки, 111:1 (2022), 107–116; A. M. Raigorodskii, V. S. Karas, “Asymptotics of the Independence Number of a Random Subgraph of the Graph $G(n,r,<s)$”, Math. Notes, 111:1 (2022), 124–131
В. С. Карась, П. А. Огарок, А. М. Райгородский, “Асимптотика числа независимости случайного подграфа графа $G(n,r,<s)$”, Докл. РАН. Матем., информ., проц. упр., 499 (2021), 17–19; V. S. Karas, P. A. Ogarok, A. M. Raigorodskii, “Asymptotics of the independence number of a random subgraph of the graph $G(n,r,<s)$”, Dokl. Math., 104:1 (2021), 173–174
Dmitry Kamaldinov, Arkadiy Skorkin, Maksim Zhukovskii, “Maximum sparse induced subgraphs of the binomial random graph with given number of edges”, Discrete Mathematics, 344:2 (2021), 112205
М. М. Пядёркин, “О пороговой вероятности для устойчивости независимых
множеств в дистанционном графе”, Матем. заметки, 106:2 (2019), 280–294; M. M. Pyaderkin, “On Threshold Probability for the Stability of Independent Sets in Distance Graphs”, Math. Notes, 106:2 (2019), 274–285
A. Kupayskii, “Degree versions of theorems on intersecting families via stability”, J. Comb. Theory Ser. A, 168 (2019), 272–287
N. M. Derevyanko, M. E. Zhukovskii, M. Rassias, A. Yu. Skorkin, “The size of a maximum subgraph of the random graph with a given number of edges”, Dokl. Math., 100:2 (2019), 478–479
M. M. Pyaderkin, “On the chromatic number of random subgraphs of a certain distance graph”, Discret Appl. Math., 267 (2019), 209–214
S. Kiselev, A. Kupavskii, “Sharp bounds for the chromatic number of random kneser graphs”, Acta Math. Univ. Comen., 88:3 (2019), 861–865