|
Эта публикация цитируется в 11 научных статьях (всего в 11 статьях)
Оценка количества максимальных расширений в случайном графе
М. Е. Жуковский
Аннотация:
В работе изучается классическая задача об асимптотическом поведении вероятностей свойств случайных графов в модели, впервые рассмотренной П. Эрдешем и А. Реньи. Исследуются различные расширения подграфов случайного графа. Число так называемых надежных расширений подграфов в случайном графе было оценено в 1990 г. Дж. Спенсером. В его работе был поставлен вопрос, для каждого ли набора вершин существуют расширения, которые в определенном смысле не расширяются дальше. Мы ввели понятия нейтральной и максимальной пары, оценили число максимальных пар и дали тем самым исчерпывающий ответ на поставленный Спенсером вопрос.
Задача о числе расширений находит свое применение в обосновании справедливости законов нуль–единица для случайных графов. Наш результат также используется для доказательства некоторых таких законов.
В исследуемой нами задаче о распределении малых подграфов в случайном графе до сих пор оставалась одна неразрешенная ситуация, которую мы и рассмотрели. Таким образом, наша теорема не только служит новым инструментом в доказательстве законов нуль–единица, но и закрывает брешь в изучении малых подграфов в случайном графе.
Статья поступила: 13.10.2010
Образец цитирования:
М. Е. Жуковский, “Оценка количества максимальных расширений в случайном графе”, Дискрет. матем., 24:1 (2012), 79–107; Discrete Math. Appl., 22:1 (2012), 55–90
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1174https://doi.org/10.4213/dm1174 https://www.mathnet.ru/rus/dm/v24/i1/p79
|
Статистика просмотров: |
Страница аннотации: | 616 | PDF полного текста: | 237 | Список литературы: | 72 | Первая страница: | 31 |
|