Оценка количества максимальных расширений в случайном графе

В работе изучается классическая задача об асимптотическом поведении вероятностей свойств случайных графов в модели, впервые рассмотренной П. Эрдешем и А. Реньи. Исследуются различные расширения подграфов случайного графа. Число так называемых надежных расширений подграфов в случайном графе было оценено в 1990 г. Дж. Спенсером. В его работе был поставлен вопрос, для каждого ли набора вершин существуют расширения, которые в определенном смысле не расширяются дальше. Мы ввели понятия нейтральной и максимальной пары, оценили число максимальных пар и дали тем самым исчерпывающий ответ на поставленный Спенсером вопрос.
Задача о числе расширений находит свое применение в обосновании справедливости законов нуль–единица для случайных графов. Наш результат также используется для доказательства некоторых таких законов.
В исследуемой нами задаче о распределении малых подграфов в случайном графе до сих пор оставалась одна неразрешенная ситуация, которую мы и рассмотрели. Таким образом, наша теорема не только служит новым инструментом в доказательстве законов нуль–единица, но и закрывает брешь в изучении малых подграфов в случайном графе.