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

Автор: Кошелев М.М., Шабанов Д. А.

Журнал: Труды Московского физико-технического института @trudy-mipt

Рубрика: Математика

Статья в выпуске: 4 (60) т.15, 2023 года.

Бесплатный доступ

В работе исследуются предельные распределения размеров и сложностей компонент связности случайного гиперграфа в биномиальной модели Н(n,k,p). Рассматривается ситуация «внутри фазового перехода», где p = p(n) представляется в виде p = l/(k-1)(n-1) при l = l(n), удовлетворяющем соотношению (l - 1)n1/3 ~ (k - 1)2/3а при фиксированном а G R. Основной результат работы состоит в получении обобщения результата Д. Олдоса (1997) о совместных предельных распределениях размеров и сложностей компонент случайного графа на случай Н(n,k,p).

Случайные гиперграфы, компоненты связности, броуновское движение, слабая сходимость

Короткий адрес: https://sciup.org/142239465

IDR: 142239465

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

  • Xapapu Ф. Теория графов / пер. с англ. Москва: УРСС, 2018. 304 с.
  • Erdos Р., Renyi A. On the evolution of random graphs // Publication of the Mathematical Institute of the Hungarian Academy of Sciences. 1960. V. 5. P. 17-61.
  • Степанов B.E. О вероятности связности случайного графа Qm(t) f f Теория вероятн. и ее примен. 1970. Т. 15, > 1. С. 55-67.
  • Luczak Т., Pitted, В., Wierman J. The structure of a random graph at the point of phase transition // Transactions of the American Mathematical Society. 1994. V. 341. P. 721-748.
  • Bollobas B. Random graphs. Cambridge University Press, 2001.
  • Jansen S., Luczak T., Rucinski A. Random graphs. New York: Wilev-Interscience, 2000.
  • Aldous D. Brownian excursions, critical random graphs and the multiplicative coalescent // The Annals of Probability. 1997. V. 25. P. 812-854.
  • Schmidt-Pruzan J., Shamir E.Component structures in the evolution of random hvpergraphs // Combinatorica. 1985. V. 5. P. 81-94.
  • Behrisch M., Coja-Oghlan A., Kang M. The order of the giant component of random hvpergraphs // Random Structures and Algorithms. 2010. V. 36. P. 149-184.
  • Bollobas B., Riordan O. Asymptotic normality of the size of the giant component in a random hvpergraph // Random Structures and Algorithms. 2013. V. 41. P. 441-450.
Еще
Статья научная