Том 8, серия 1, номер 4, 2001 г., Стр. 54-67

УДК 519.179.4
А. Д. Коршунов
При каких $k$ в почти каждом $n$-вершинном графе имеются все неизоморфные $k$-вершинные подграфы

Аннотация:
Пусть $\mathscr G(n)$ обозначает множество неориентированных графов без петель и кратных ребер с $n$ помеченными вершинами, $\mathscr G(n,k)$ – множество таких графов из $\mathscr G(n)$, в каждом из которых содержатся все неизоморфные $k$-вершинные подграфы, и $k_0=k_0(n)=\lfloor2(\log_2n-\log_2\log_2n+\log_2e)\rfloor-1$. Доказывается, что если $k=k(n)\geqslant k_0(n)+2$, то $\lim_{n\to\infty}|\mathscr G(n,k)|/|\mathscr G(n)|=0$, а если $k=k_0(n)$, то $\lim_{n\to\infty}|\mathscr G(n,k)|/|\mathscr G(n)|=1$.
Библиогр. 4.

Коршунов А. Д. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: korshun@math.ncs.ru

Статья поступила 28 февраля 2001 г.
Исправленный вариант — 25 сентября 2001 г.