RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические заметки // Архив

Матем. заметки, 2020, том 107, выпуск 1, страницы 49–58 (Mi mzm12043)

Медиана количества простых путей на $3$ вершинах в случайном графе

М. Е. Жуковский

Московский физико-технический институт (государственный университет), г. Долгопрудный, Московская обл.

Аннотация: В этой работе мы исследуем асимптотическое поведение случайной величины, равной количеству простых путей на $3$ вершинах в биномиальном случайном графе с вероятностью проведения ребра, являющейся пороговой для возникновения таких путей. Мы доказываем, что для любого фиксированного целого неотрицательного числа $b$ и при достаточно большом числе вершин графа $n$ вероятность того, что количество простых путей на трех вершинах в рассматриваемом случайном графе равно $b$, убывает по $n$. Как следствие этого результата, мы находим медиану количества простых путей на трех вершинах при достаточно больших $n$.
Библиография: 25 названия.

Ключевые слова: случайный граф, строго сбалансированные графы, простые пути, медианы, предельная теорема Пуассона, функция Рамануджана.

УДК: 519.175.4

Поступило: 15.04.2018
Исправленный вариант: 05.02.2019

DOI: 10.4213/mzm12043


 Англоязычная версия: Mathematical Notes, 2020, 107:1, 54–62

Реферативные базы данных:


© МИАН, 2024