1304.0900.tex
\documentclass[12pt,a4paper,russian,titlepage]{article}
\usepackage{babel,amsmath,amssymb,amsthm,graphicx,amsfonts,latexsym,epsfig,longtable,wrapfig}

\textwidth=165mm

\footskip=23mm


%\mathsurround=2pt \frenchspacing \righthyphenmin=2
%\emergencystretch=1em \hoffset=0pt \voffset=0pt
\oddsidemargin=-1mm \evensidemargin=0pt \topmargin=0pt
%\headheight=3mm \headsep=10mm \textheight=230mm \marginparsep=0pt
\marginparwidth=0pt

\newtheorem{theorem}{�������}
\newtheorem{lemma}{�����}

\newcommand{\EHR}{{\mathrm{EHR}}}


\begin{document}


\begin{center}{\Large ���������� $k$-������ ���� ��� �������}
\end{center}

\vspace{0.1cm}

\begin{center}{\large �.�. ���������}
\end{center}

\vspace{0.5cm}

\section{��������}
\label{intro}

� ������ ������ ��������� ���������� ����������� ������� �������
������� ���������� ����� � ������ ������--�����. ����� ���� ���
���������� $k$-����� ���� ��� �������, ������� ��������� ���������
������������ ������� ������� �������, ���������� ��������� �
������������ ������ $k$ ���������� �������� (��. \cite{Zhuk2}).
����� �������� ��� ���������� ����� $G(N,N^{-\alpha})$ ���
$\alpha\in(0,1/(k-2))$. � ��������� ������ �� ��������� ����������
���������, �������� �������� �������� $\alpha$, ��� �������
���������� $k$-�����. � ���� ������� �� ������������ ��������
���������, �� ������ ����� ��� ����������� �����������, � �����
������ ������ ������� ����������� ������.

����� $N\in\mathbb{N}$, $0\leq p\leq 1.$ ���������� ���������
$\Omega_N=\{G=(V_N,E)\}$ ���� ����������������� ������ ��� ������
� ������� ����� � ���������� ������ $V_N=\{1,...,N\}$.
\emph{��������� ���� � ������ ������--�����} (��.
\cite{Erdos}--\cite{Alon}) ��� ��������� ������� $G(N,p)$ ��
���������� �� ��������� $\Omega_N$ � �������������� ${\sf
P}_{N,p}$ �� $\mathcal{F}_N=2^{\Omega_N},$ ������������ ��������
$$
 {\sf P}_{N,p}(G)=p^{|E|}(1-p)^{C_N^2-|E|}.
$$

�������, ��� ��������� ���� {\it ����������� ������ ���� ���
�������} ��� ������ ������� $\mathcal{C}$, ���� �����������
���������� ������� �������� �� ����� ������ ��������� ���� � $0$,
���� � $1$.

�������, ����� ��������� � ���� ����������� �������� �����
�������, ���������� ��������� ������� ������� (��. \cite{Veresh},
\cite{Usp}). ��� ������� �������� � ������� �������� ���������
$\sim,=$; ���������� ������
$\neg,\Rightarrow,\Leftrightarrow,\vee,\wedge$; ����������
$x,y,x_1...$; ��������� $\forall,\exists$. ������� ���������� �
����� ������� ������� ���������� ������� �����. ������ ���������
$\sim$ �������� �������� ���� ������ ���� ������������ ������,
������ ��������� $=$ �������� �������� ���� ������ ���������.
��������� $\mathcal{P}$ ��������� ������� $p=p(N)$, ��� �������
�������� ����� ���� ��� ������� ��� ������ ������� �������
�������. ����� ������� ������� ������� ��������� $\mathcal{L}.$ �
1969 ���� �.�.~��������, �.�.~�����, �.�.~���������� �
�.�.~�������  (��. \cite{Kogan}) � ���������� � 1976 ���� �.~�����
(��. \cite{Fagin}) ��������, ��� ����
$$
 \forall \alpha>0 \,\,\,\, N^{\alpha}\min\{p,1-p\}\rightarrow\infty,
 \,\, N\rightarrow\infty,
$$
�� $p\in\mathcal{P}$. ����� ����, � 1988 ���� ��. ������� � �.
���� (��. \cite{Shelah}, \cite{Strange}) ����������, ��� ���
������� $p=N^{-\alpha}$, $\alpha\in\mathbb{R}\setminus\mathbb{Q}$,
$\alpha\in(0,1)$, ����� ����������� $\mathcal{P}$. ����������,
$p=1-N^{-\alpha}\in\mathcal{P}$, ����
$\alpha\in\mathbb{R}\setminus\mathbb{Q}$, $\alpha\in(0,1)$.

�������, ��� ���� $\alpha$
--- ������������, $0<\alpha\leq 1$ � $p=N^{-\alpha}$, �� ��������
��������, ��� ��������� ���� $G(N,p)$ �� ����������� ������ ����
��� ������� (��. \cite{Alon}).

������ ������ $\mathcal{L}$ ��������������� ����� �������
$\mathcal{L}^{\infty}\supset\mathcal{L}$, ���������� ���������,
������� ����� ��������� ����������� ���������� ���������� ���
���������� (����������� � ����� �����, ������ ������, ����������,
� ������� �� �����������, ���������� �������� �� ������
$\mathcal{L}$). � 1997 ���� �.~���\-����� (��. \cite{McArtur})
���� ����������� ��������� ������ ���� ��� ������� ��� ������
������� $\mathcal{L}^{\infty}_k\subset \mathcal{L}^{\infty}$,
���������� ��������� � ���������� ��������, ������������ ������
$k$. � ������, ���� �������� ������ ��� ���������� ����� $G(N,p)$
��� $p=N^{-\alpha}$ � ��������� ������������ $\alpha$ �� $(0,1]$.
���������� ������ ����� $\mathcal{L}_k\subset \mathcal{L}$
�������, ���������� ��������� � ���������� ��������, ������������
������ $k$ (����������� �������, � ������� �� �����������,
�������� �������� �� ������ $\mathcal{L}_k^{\infty}$). � 2012 ����
�� ��������, ��� ��� $k\geq 3$ � $\alpha\in(0,1/(k-2))$ (��.
\cite{Zhuk2}, \cite{zhuk_dan}) ��������� ���� $G(N,N^{-\alpha})$
����������� ������ ���� ��� ������� ��� ������ $\mathcal{L}_k$
(���� ��������� ���� ����������� ������ ���� ��� ������� ���
������ $\mathcal{L}_k$, �� �� �������, ��� �� {\it �����������
$k$-������ ���� ��� �������}). ����� ����, � ���������� ������ ��
��������, ��� ��� $\alpha=1/(k-2)$ ��������� ����
$G(N,N^{-\alpha})$ �� ����������� $k$-������ ���� ��� �������. �
\cite{zhuk_MJC} �����������, ��� ���������� ������� ������������
${\sf P}_{N,N^{-1/(k-2)}}$ ���������� ���� �������, ����������
���������
� ���������� ��������, ������������ ������ $k$.\\


������������ �������� ���������� ������ ������. ����� ��
������������� ������ ������ $k>3$, ��� ��� ��� $k=3$ (�,
�������������, � ��� $k<3$) ��������� ���� $G(N,N^{-\alpha})$
����������� $k$-������ ���� ��� ������� ��� ���� $\alpha\in(0,1)$
(��. \cite{zhuk_MJC}).

\begin{theorem}

����� $k>3$ --- ������������ ����������� �����. �����, ����� ����,
$\mathcal{Q}$ --- ��������� ������������� ������ � ����������, ��
������������� ����� $2^{k-1}$. ��������� ���� $G(N,N^{-{\alpha}})$
����������� $k$-������ ���� ��� �������, ����
$\alpha=1-\frac{1}{2^{k-1}+\beta}$, $\beta\in(0,\infty)\setminus
\mathcal{Q}$.

\label{positive}
\end{theorem}


����, �� ����������� �������� $(1-2^{1-k},1)$ � �������� ���������
������������ ����� $\alpha$ �� ����� ���������, ��� �������
$k$-����� ����������. ��� ��� ����� ����� �� $(1-2^{1-k},1)$
�������������� � ���� $1-\frac{1}{2^{k-1}+\beta}$, ����� �����
�������� ��� ����� $\alpha$ ��
$$
 \left(1-\frac{1}{2^k},1\right)
 \bigcup\left(1-\frac{1}{2^k-1},1-\frac{1}{2^k}\right)
 \bigcup\ldots\bigcup\left(1-\frac{1}{2^{k-1}+
 2^{k-2}},1-\frac{1}{2^{k-1}+2^{k-2}+1}\right)
 \bigcup
$$
$$
 \left(1-\frac{1}{2^{k-1}+\frac{2^{k-1}-1}{2}},1-\frac{1}{2^{k-1}+2^{k-2}}\right)
 \bigcup\ldots
 \bigcup
$$
$$
 \left(1-\frac{1}{2^{k-1}+\frac{2^{k-1}}{3}},1-\frac{1}{2^{k-1}+\frac{2^{k-1}-\left[\frac{2^{k-1}}{3}\right]}{2}}\right)\bigcup\ldots.
$$
����� ���������� ����������� ��� ���������� ������ � $1-2^{1-k}$.
%�� ����� ����, ��� ������� �� ������� \ref{denominator}, �����
%���������� �������� ����������.
����� ����, ��� ��������� �� ��� �� ��������, ��� �� ������
���������� $k$-����� �� �������� (��.
������� \ref{negative}).\\

�������������� ������� ����� ��������� �� ��������� �����: �
������� \ref{game} �� ������������ ������� ����������, �����������
������ ���� ��� ������� � ������������� ���������� ���������
������� ������ � ���� ����������. � ��� �� ������� �� ���������
��������� ������� ������, ������� � ������������, ����������� � 1,
�������� ��� � ������, ��� �� ������� � ������� \ref{proof1}.
������ \ref{constructions} �������� ���������� �����������,
�������� ������� ��������� ��� ��������, ��� ������ ����� "�����
������"$\,\,$������ ������ � ������������ �
������������ ���� ����������.\\

������������ ��������� � ��������� ������ ���
$\alpha=1-\frac{1}{2^{k-1}+\beta}$ ��� ��������� $\beta$ ��
��������� $\mathcal{Q}$, ������������� �  ������� \ref{positive}.

\begin{theorem} ����� $k>3$ --- ������������ ����������� �����. �����, ����� ����,
$\tilde{\mathcal{Q}}$ --- ��������� ����������� �����, ��
������������� $2^{k-1}$. ��������� ���� $G(N,N^{-{\alpha}})$ ��
����������� $k$-������ ���� ��� �������, ����
$\alpha=1-\frac{1}{2^{k-1}+\beta}$, $\beta\in
\tilde{\mathcal{Q}}$.

\label{negative}
\end{theorem}

�������������� ������� �� �������� � ������� \ref{proof2}.
�������� ����������� �� ����� ��������� � ��� ��������� �������
$\beta$, �� ������ ���������� ��� ����� �� ����, ������� � ������
������ ��������������� ������ ����� $\beta$.

%��� ������ ��������� ����������, ��� ���������� ���� ��������
%����� ������������ $\alpha$, ��� ������� ��������� ����
%$G(N,N^{-\alpha})$ �� ����������� $k$-������.

%\begin{theorem}

%����� $k>3$ --- ������������ ����������� �����. ���������� �����
%����� $d(k)$, ��� ��� ����� ������������ ����� $\alpha$ �� $(0,1)$
%�� ������������, ������� $d(k)$, ��������� ����
%$G(N,N^{-{\alpha}})$ ����������� $k$-������ ���� ��� �������.

%\label{denominator}
%\end{theorem}

%������� �������� � ������� \ref{proof3}.


\section{�����������}
\label{constructions}


������ ������ �� ������ � �������� ��������� ����������� �
������������� ����� ��������� � ��������� ����� ������--�����. ���
�������� ��������� �� �������� � ���� ������� ��� �����������,
������� ����� ������������ ��� �������������� �������� �����������
������. � ��������� \ref{cicles} ����� �������������� � ��������
�����, �������� �������� ���� ��� �������������� �������
\ref{positive}.


\subsection{����� �������� � ����������}
\label{subgraphs}

��� ������������� ����� $G$ ��������� $v(G)$ ����� ��� ������,
$e(G)$ --- ����� ��� �����, $a(G)$ --- ����� ��� �������������.
��������� ����� $\frac{e(G)}{v(G)}$ ��������� $\rho(G)$. ���� $G$
���������� \emph{����������������}, ���� ��� ������� ��� ��������
$H$ ��������� ����������� $\rho(H)\leq \rho(G).$ ���� $G$
\emph{������ ����������������}, ���� ��� ������ $H\subset G$
����������� ������� ����������� $\rho(H)<\rho(G).$ ������������
������� (��. \cite{Erdos}--\cite{Bol}, \cite{Alon}) � ����������
����� ������ ����������������� �����. ����� $N_G$ --- ����������
����� $G$ � ��������� ����� $G(N,p)$. �������
$\rho^{\max}(G)=\max\{\rho(H):\,
H\subseteq G\}.$\\



\begin{theorem} [\cite{Erdos}] ����� $G$ --- ������������ ����. ���� $p=o\left(N^{-1/\rho^{\max}(G)}\right)$,
��
$$
 \lim_{N\rightarrow\infty}{\sf P}_{N,p}(N_G>0)=0.
$$
���� ��
$N^{-1/\rho^{\max}(G)}=o(p)$, ��
$$
 \lim_{N\rightarrow\infty}{\sf P}_{N,p}(N_G>0)=1.
$$
����� ������ $G$
--- ������ ���������������� ����. ���� $N^{-1/\rho(G)}=o(p),$ ��
��� ������ $\varepsilon>0$ ����������� ���������
$$
\lim\limits_{N\rightarrow\infty}{\sf P}_{N,p}(\left|N_G- {\sf
E}_{N,p}N_G\right|\leq \varepsilon {\sf E}_{N,p}N_G)=1,
$$
��� ${\sf E}_{N,p}$ --- ��� �������������� �������� �� ���� ${\sf
P}_{N,p}$ (����� � ����� � �������� ��������� �� ����� ��������,
��� � ��������������� ������������ $1$ ��������� $N_G\sim {\sf
E}_{N,p}N_G$). ���� �� $p=N^{-1/\rho(G)},$ ��
$$
\lim\limits_{N\rightarrow\infty}{\sf P}_{N,p}(N_G=0)=e^{-1/a(G)}.
$$
\label{erdos}
\end{theorem}

��������� � ������, ������������ ��.~��������� � 1990 ���� (��.
\cite{Alon}, \cite{Spencer}). ���������� ����� �����
$H,G,\widetilde{H},\widetilde{G}$, ��� $V(H)=\{x_1,...,x_k\}$,
$V(G)=\{x_1,...,x_l\}$,
$V(\widetilde{H})=\{\widetilde{x}_1,...,\widetilde{x}_k\}$,
$V(\widetilde{G})=\{\widetilde{x}_1,...,\widetilde{x}_l\}$, ������
$H\subset G$, $\widetilde{H}\subset\widetilde{G}$ (��� �����,
$k<l$). ���� $\widetilde{G}$ ���������� $(G,H)$--\emph{�����������
����� $\widetilde{H}$}, �����
$$
 \{x_{i_1},x_{i_2}\}\in E(G)\setminus E(H) \Rightarrow
 \{\widetilde{x}_{i_1},\widetilde{x}_{i_2}\}\in
 E(\widetilde{G})\setminus E(\widetilde{H}).
$$
���� ����������� �����������
$$
 \{x_{i_1},x_{i_1}\}\in
 E(G)\setminus E(H) \Leftrightarrow
 \{\widetilde{x}_{i_1},\widetilde{x}_{i_2}\}\in
 E(\widetilde{G})\setminus E(\widetilde{H}),
$$
�� $\widetilde{G}$ ������� \emph{������ �����������}, � ����
$(G,H)$ � $(\widetilde G,\widetilde H)$ --- �����������.
����������� ����� $\alpha>0$. �������
$$
 v(G,H)=|V(G)\setminus V(H)|, \,\,
 e(G,H)=|E(G)\setminus E(H)|,
$$
$$
 f_{\alpha}(G,H)=v(G,H)-\alpha e(G,H).
$$
���� ��� ������ ������ ����� $S,$ ��� $H\subset S\subseteq G,$
��������� ����������� $f_{\alpha}(S,H)>0,$ �� ���� $(G,H)$
���������� \emph{$\alpha$--��������} (��. \cite{Janson},
\cite{Alon}, \cite{Spencer}). ���� �� ��� ������ ������ $S,$ ���
$H\subseteq S\subset G,$ ��������� �����������
$f_{\alpha}(G,S)<0,$ �� ���� $(G,H)$ ���������� {\it
$\alpha$--�������} (��. \cite{Janson}, \cite{Alon}). ���� �����
������� ����� $H$ ��������� � ��������� �������� �� $V(G)\setminus
V(H)$ � ��� ������ ������ ����� $S$, ��� $H\subset S\subset G,$
����������� ����������� $f_{\alpha}(S,H)>0$, ��
$f_{\alpha}(G,H)=0$, �� ���� $(G,H)$ �������
\emph{$\alpha$-�����������}. ������, �������, ������� ������������
����. ����� $\widetilde{H}\subset\widetilde{G}\subset\Gamma$ �
$T\subset K$, ������ $|V(T)|\leq|V(\widetilde{G})|.$ ����
$(\widetilde{G},\widetilde{H})$ �������
\emph{$(K,T)$--������������ � $\Gamma$}, ���� � ������ ������
�������� $\widetilde{T}$ ����� $\widetilde{G},$ ���
$|V(\widetilde{T})|=|V(T)|$ �
$\widetilde{T}\cap\widetilde{H}\neq\widetilde{T},$ �� ����������
������ ������� $(K,T)$-���������� $\widetilde{K}$ �
$\Gamma\setminus(\widetilde{G}\setminus\widetilde{T})$, ��� ������
������� �� $V(\widetilde{K})\setminus V(\widetilde{T})$ ��
��������� ������ �� � ����� �������� �� $V(\widetilde{G})\setminus
V(\widetilde{T})$. ���� $\widetilde{G}$ �������
\emph{$(K,T)$--������������ � $\Gamma$}, ���� � ������ ������
�������� $\widetilde{T}$ ����� $\widetilde{G},$ ���
$|V(\widetilde{T})|=|V(T)|$, �� ���������� ������ �������
$(K,T)$-���������� $\widetilde{K}$ �
$\Gamma\setminus(\widetilde{G}\setminus\widetilde{T})$, ��� ������
������� �� $V(\widetilde{K})\setminus V(\widetilde{T})$ ��
��������� ������ �� � ����� �������� �� $V(\widetilde{G})\setminus
V(\widetilde{T})$.


��������� ������ � ���������� ����� $G(N,p)$. �����
$\alpha\in(0,1]$, $p=N^{-\alpha}$. �����, ����� ����, ���� $(G,H)$
�������� $\alpha$--�������� � $V(H)=\{x_1,...,x_k\},$
$V(G)=\{x_1,...,x_l\}$. ���������� ������������ �������
$\widetilde{x}_1,...,\widetilde{x}_k\in V_N$ � ��������� ��������
$N_{(G,H)}(\widetilde{x}_1,...,\widetilde{x}_k)$ �� �������������
������������ $(\Omega_N,\mathcal{F}_N,{\sf P}_{N,p})$, �������
������� ����� $\mathcal{G}$ �� $\Omega_N$ ������ � ������������
���������� $(G,H)$-���������� �������� � $\mathcal{G}$,
��������������� �� $\{\widetilde{x}_1,...,\widetilde{x}_k\}$ (����
$X$ �������� \emph{��������� ����� $Y$, �������������� ��
��������� $S\subset V(Y)$}, ���� $V(X)=S$ � ��� ����� ������
$x,y\in S$ ����������� $\{x,y\}\in E(X)\Leftrightarrow\{x,y\}\in
E(Y)$). ����� �������, ����� $W\subset V_N
\setminus\{\widetilde{x}_1,...,\widetilde{x}_k\}$
--- ���������, �������� $|W|$ �������� ����� $l-k.$ ���� ����� ���
������������ �������� ��������� $W$ ������� $k+1,k+2,...,l,$ ���
���� $\mathcal{G}|_{\{\widetilde{x}_1,...,\widetilde{x}_l\}}$
�������� $(G,H)$--����������� �����
$\mathcal{G}|_{\{\widetilde{x}_1,...,\widetilde{x}_k\}},$ ��
������� $I_W(\mathcal{G})=1.$ � ��������� ������
$I_W(\mathcal{G})=0.$ ��������� ��������
$N_{(G,H)}(\widetilde{x}_1,...,\widetilde{x}_k)$ ������������
��������� ����������:
$$
N_{(G,H)}(\widetilde{x}_1,...,\widetilde{x}_k)=
\sum\limits_{W\subset V_N
\setminus\{\widetilde{x}_1,...,\widetilde{x}_k\},\, |W|=l-k}I_W.
$$

\begin{theorem} [\cite{Spencer}]
� ��������������� ������������ $1$ ��� ����� ������
$\widetilde{x}_1,...,\widetilde{x}_k$ ����������� �����������
$N_{(G,H)}(\widetilde{x}_1,...,\widetilde{x}_k)\sim {\sf E}_{N,p}
N_{(G,H)}(\widetilde{x}_1,...,\widetilde{x}_k).$ ��� ����
$$
 {\sf
 E}_{N,p}N_{(G,H)}(\widetilde{x}_1,...,\widetilde{x}_k))=\Theta(N^{f_{\alpha}(G,H)}).
$$
\label{safe_extensions}
\end{theorem}

������ ���� ������� ��.~������� � �.~���� (��. \cite{Alon},
\cite{Shelah}) ��� ������������ ������� ���� ��� ������� ��������
������� � ���������� ������������ ���������� ��������� � ���������
����� (��� ������ "�����������"$\,$������� ���). � 2010 ���� ��
��������� �� ���������, ���������� "�����������"$\,$�����������
���� (��. \cite{zhuk_extensions}).

����� ���������, ����� ��������� ��������
$N^{(K,T)}_{(G,H)}(\widetilde{x}_1,...,\widetilde{x}_k)$ ������ �
������������ ������� ����� $\mathcal{G}$ �� $\Omega_N$ ����������
����� ������ $(G,H)$-���������� $\widetilde{G}$ �����
$\widetilde{H}=\mathcal{G}|_{\{\widetilde{x}_1,...,\widetilde{x}_k\}}$,
��� ���� $(\widetilde{G},\widetilde{H})$ ��������
$(K,T)$--������������ � $\mathcal{G}$. ������������ �������,
���������� � ������ ��.~�������� � �.~���� (��. \cite{Shelah}),
�� ��������������� ��������� ���� ��������� ��������.\\

\begin{theorem} [\cite{Shelah}]
����� ���� $(K,T)$ �������� $\alpha$--�������. ����� �
��������������� ������������ $1$ ��� ����� ������
$\widetilde{x}_1,...,\widetilde{x}_k$ ���������
$$
 N^{(K,T)}_{(G,H)}(\widetilde{x}_1,...,\widetilde{x}_k)\sim
 N_{(G,H)}(\widetilde{x}_1,...,\widetilde{x}_k) \sim
 {\sf
 E}_{N,p}
 N^{(K,T)}_{(G,H)}(\widetilde{x}_1,...,\widetilde{x}_k)
 =\Theta\left(N^{f_{\alpha}(G,H)}\right).
$$
\label{maximal_extensions_rigid}
\end{theorem}

%���������, �������, � ������ ����������, ����������������� �
%����������� � \cite{zhuk_extensions}. ����� ��������� ��������
%$\widehat{N}^{\mbox{\small{neutral}}}_{(G,H),r}(\widetilde{x}_1,...,\widetilde{x}_k)$
%������ � ������������ ������� ����� $\mathcal{G}$ �� $\Omega_N$
%���������� ����� ������ $(G,H)$-���������� $\widetilde{G}$ �����
%$\widetilde{H}=\mathcal{G}|_{\{\widetilde{x}_1,...,\widetilde{x}_k\}}$,
%��� ��� ������ ����
%$(K_i,T_i)\in\Sigma^{\mbox{\small{neutral}}}(r)$ ����
%$(\widetilde{G},\widetilde{H})$ �������� $(K_i,T_i)$-������������
%� $\mathcal{G}$.\\

%\begin{theorem} [\cite{zhuk_extensions}]
%� ��������������� ������������ $1$ ��� ����� ������
%$\widetilde{x}_1,...,\widetilde{x}_k$ ���������
%$$
% \widehat{N}^{\mbox{\small{neutral}}}_{(G,H),r}(\widetilde{x}_1,...,\widetilde{x}_k)\sim
% {\sf
% E}_{N,p}
% \widehat{N}^{\mbox{\small{neutral}}}_{(G,H),r}(\widetilde{x}_1,...,\widetilde{x}_k)
% =\Theta\left(N^{f(G,H)}\right).
%$$
%\label{maximal_extensions_neutral}
%\end{theorem}



\subsection{������������� �����}
\label{cicles}



����� $m\in\mathbb{N}$ --- ������������ ����������� �����.
���������� ����� ���� ������ $(G,H)$, ��� $G\supset H$. �����
��������, ��� ���� $G$ �������� {\it $m$--����������� ����� $H$
������� ����}, ���� $m\geq 3$ � ��������� ��������� �������.
���������� ����� ������� $x_1$ ����� $G$, ���
$$
 V(G)\setminus V(H)=\{y_1^1,...,y_{t_1}^1,y_1^2,...,y_{t_2}^2\},
$$
$$
 E(G)\setminus E(H)=\{\{x_1,y_1^1\},\{y_1^1,y_2^1\},...,\{y_{t_1-1}^1,y_{t_1}^1\},
 \{y_{t_1}^1,y_{1}^2\},\{y_1^2,y_2^2\},...,\{y_{t_2-1}^2,y_{t_2}^2\},\{y_{t_2}^2,y_{t_1}^1\}\},
$$
��� $t_1+t_2\leq m-1$, $t_1\geq 0$, $t_2\geq 2$  �
$\rho^{\max}(G)<\frac{m}{m-1}$ (��� $t_1=0$ ������� $x_1$ ��������
������� � ��������� $y^2_1,y^2_{t_2}$). ���� $G$ �� �������� {\it
$m$--����������� ����� $H$ ������� ����}, ���� $m\geq 2$ �
��������� ��������� �������. ���������� ��� ����� ���������
������� $x_1,x_2$ ����� $G$, ���
$$
 G=(V(H)\sqcup\{y_1,...,y_t\},E(H)\sqcup\{\{x_1,y_1\},\{y_1,y_2\},...,\{y_{t-1},y_t\},\{y_t,x_2\}\}),
$$
��� $t\leq m-1$ � $\rho^{\max}(G)<\frac{m}{m-1}$. ���� $G$
�������� {\it $m$--����������� ����� $H$ �������� ����}, ����
$m\geq 2$, $V(H)=V(G)$, $E(H)\subset E(G)$ �
$\rho^{\max}(G)<\frac{m}{m-1}$.


��� ������������� ������������ ����� $m\geq 3$ ��������� ���������
������ $\mathcal{H}_m$. ����� $x$ --- �������. ���� ��� ����� ��
��������� ������ $\{x\}$, ����������� $\mathcal{H}_m$. ����� �����
$G\in\mathcal{H}_m$. ��������� $\mathcal{H}_m$ �������� ���
������� ������������ $m$--���������� �������, ������� � ��������
����� ����� $G$.

�������, ��� ����� ���� $G$ �� $\mathcal{H}_m$, �������� ��
$(\{x\},\varnothing)$, �������� � ���� �������� ����� �����
��������� ������ $G_1,...,G_t$, $G_0=(\{x\},\varnothing)\subset
G_1\subset...\subset G_t\subseteq G$, ��� ��������� ���������
��������:

\begin{itemize}


\item[---] $G_i\neq G_{i+1}$ ��� ���� $i\in\{0,1,...,t-1\}$,



\item[---] ���� $G$ ���� ��������� � $G_t$, ���� ��������
$m$--����������� �������� ���� ����� $G_t$, � ����� $G_i$ ��������
$m$--������������ ������� ��� ������� ���� ������ $G_{i-1}$ ���
$i\in\{0,1,...,t\}$.

\end{itemize}

����� ������������������ ������ $G_0,G_1,...,G_t,G$ ����� ��������
{\it $m$--�����������} ����� $G$.



������������ ����������� � ��������� ��������� $\mathcal{H}_m$.

\begin{lemma} ��������� ��������� ��������.

\begin{itemize}

\item[1.] ����� $G\in\mathcal{H}_m$ � $G_0,G_1,...,G_t,G$ --- ���
$m$--����������, ������ ���� $t=1$ � $G_t\neq G$, ���� $t\geq 2$.
����� �������� ����� ����������� ����� $a,b$, ��� $b\leq m$ �
$\rho^{\max}(G)=1+\frac{1}{m-1+b/a}$.

%����� $\alpha\in(1-m^{-1},1)$, $G\in\mathcal{H}_m(x)$,
%$H$
%--- ����� ������� � $G$, ��� $\rho(H)=\rho^{\max}(G)$. ����� ����
%$H=G$, ���� ���� $(G,H)$ �������� $\alpha$-�������, ���� � �����
%$G$ �������� ����� ������� $S$, $H\subset S\subset G$, ��� ����
%$(S,H)$ �������� $\alpha$-��������, � ���� $(G,S)$ ��������
%$\alpha$-�������, ���� � ����� $G$ �������� �����  ��������
%$S_1,S_2$, $H\subset S_1\subset S_2\subset G$, ��� ���� $(S_1,H)$
%�������� $\alpha$-��������, ���� $(S_2,S_1)$ ��������
%$\alpha$-����������� �����, � ���� $(G,S_2)$ ��������
%$\alpha$-�������.


\item[2.] ����� $m\geq 2$ � $\rho\in(1,m/(m-1))$ --- ������������
�����. ����� ���������� ����� ����� $\eta\in\mathbb{N}$, ��� ���
������ ������������ $v>\eta$ � � ������ ����� $G\in\mathcal{H}_m$
�� $v$ �������� �������� ������� �� �� ����� ��� $\eta$ �������� �
����������, ������������� $\rho$.

\end{itemize}

\label{H-properties}
\end{lemma}

{\bf ��������������} ������ �� �������� 1. ���� $t=1$, ��
$\rho(G_1)=1,$ $v(G_1)\leq m$. �������������,
$\rho(G)=\frac{v(G_1)+e}{v(G_1)}$, ��� $e\in\mathbb{N}$. �������
$\rho(G)=1+\frac{1}{1+\frac{v(G_1)-e}{e}}$. ��� ��� $v(G_1)-e<m$,
�� �������� 1 ��� �������������� ������ ��������.

����� $t\geq 2$. ������� $v^{i+1}=v(G_{i+1})-v(G_i)$,
$i\in\{0,1,...,t-1\}$. �������, ���
$\rho(G_t)=1+\frac{1}{m-1+b_1/(t-1)}$ ��� ��������� $b_1\leq m$.
����������� �����������
$$
 \rho(G_t)=\frac{v^1+...+v^{t}+t}{1+v^1+...+v^{t}}=1+\frac{t-1}{1+v^1+...+v^{t}}<1+\frac{1}{m-1}.
$$

��� ��� $v^i\leq m-1$, $i\in\{1,...,t\}$, ��
$$
 m-1<\frac{1+v^1+...+v^{t}}{t-1}\leq\frac{1+t(m-1)}{t-1}=m-1+\frac{m}{t-1}.
$$
����� �������,
$$
 1+\frac{1}{m-1+\frac{m}{t-1}}\leq \rho(G)<1+\frac{1}{m-1},
$$
��� ����
$$
 \rho(G)=1+\frac{1}{m-1+\frac{b_1}{t-1}},
$$
��� $b_1=1+v^1+...+v^t-(m-1)(t-1)$. ������� ����� $b_1$ ��
����������� $m$.

������� ������, ��� $\rho(G)=1+\frac{1}{m-1+b_2 / (t+e_0-1)},$ ���
$b_2\leq m, e_0=e(G)-e(G_t)$. �����
$$
 \rho(G)=\frac{m(t-1)+b_1+e_0}{(m-1)(t-1)+b_1}=
 1+\frac{1}{m-1+\frac{b_1-(m-1)e_0}{t-1+e_0}}.
$$
��� ��� $\rho(G)<1+\frac{1}{m-1},$ �� $0<b_2\leq b_1\leq m,$ ���
$b_2=b_1-(m-1)e_0$.


% �����������
%���������, ��� ��������� $\rho(\tilde G)$ �������������� � ����
%$1+\frac{1}{m-1 + \tilde b / \tilde a},$ ��� $\tilde b> m$,
%$\tilde b/ \tilde a$ --- ������������ �����. �������������, �����
%������������ �����, ������������� ��������� $(1,m/(m-1))$
%����������� � ���������� ����, ��� $\tilde a,\tilde b$ ---
%��������� �����, �� ��������������� �����-���� ������������. �����
%\begin{equation}
% \frac{am+b+e}{am+b-a}=\frac{\tilde a m + \tilde b}{\tilde a m + \tilde b - \tilde
% a}.
%\label{fractions}
%\end{equation}
%�������, ��� ����� ������ ������������, ��� ��� ����� $a$ � $b$
%������� ������. �������
%\begin{equation}
 %\tilde a m + \tilde b\leq am+b+e.
%\label{less_numerator}
%\end{equation}
%������� $\tilde b$ �� ��������� (\ref{fractions}):
%\begin{equation}
% \tilde b =\frac{\tilde a(b-em+e)}{e+a}>m.
%\label{b_expression}
%\end{equation}
%�������������, $b-em+e>0$. ��� ��� $b\leq m,$ �� $e=1,$ $b=m$. ���
%�����, ����������� (\ref{b_expression}) �������� � $\tilde
%a>m(a+1)$. ������� $\tilde a>a$. ����� � ���� �����������
%(\ref{less_numerator}) $\tilde b<b+1=m+1$, ��� ������������ ������ �������������.\\



�����, ������� $H\subset G,$ $\rho(G)<\rho(H)<\frac{m}{m-1}$.
�����
$$
 \rho(H)=\frac{m(t-1)+b_1+e_0-y}{(m-1)(t-1)+b_1-x}
$$
��� ��������� ����������� ����� $x,y$. ����������� �����������
$y\geq x,$ ��� ��� ���� $G$
--- ���������. �������, ��� $\rho(H)=1+\frac{1}{m-1+b /
(t+e_0-1+x-y)},$ ��� $b\leq m$. �����
$$
 \rho(H)=1+\frac{1}{m-1+\frac{b_1+y(m-1)-mx-(m-1)e_0}{t-1+e_0+x-y}}.
$$

��� ��� $\rho(H)>\rho(G),$ ��
$$
 \frac{b_1+y(m-1)-mx-(m-1)e_0}{t-1+e_0+x-y}<\frac{b_1-(m-1)e_0}{t-1+e_0}.
$$
�� ����������� ������ ����� �� ������, ��� ����������� ������.
�������������, $b=b_1+y(m-1)-mx-(m-1)e_0<b_1-(m-1)e_0\leq m,$ ���
� ����������� ��������.\\


�������� � �������������� �������� 2. � ���� �����������
$m$--���������� ������� � ������� ����, ���� $G_0,G_1,...,G_t,G$
--- $m$--���������� ���������� ����� $G\in\mathcal{H}_m$, ��
$v(G_{i+1})-v(G_i)\leq m-1,$ $e(G_{i+1})-e(G_i)=v+1$ ��� ����
$i\in\{0,...,t-1\}$. �������������, ��� ������� $n\in\mathbb{N}$ �
��� ������ ����� $G\in\mathcal{H}_m$, ���������� ������ ��������
�� ������, ��� $(m-1)n+1$, ����������� �����������
$\rho(G)\geq\frac{mn}{(m-1)n+1}$. �������������, ��������� ������
����� �� ��������� $\mathcal{H}_m$ ������, ��� $\frac{m}{m-1}$,
������� ��� ���������� � ���� ��� $m$--���������� ������� ���
������� ���� ��� ��������� �������������. ����� ����, ��� ������
$\rho\in(1,\frac{m}{m-1})$ �������� ����� �����
$n_0\in\mathbb{N}$, ��� ��� ���� ����������� $n\geq n_0$ ���������
����������� $\frac{mn}{(m-1)n+1}>\rho.$ �������, �������, ��� �
����� ����� �� $\mathcal{H}_m$ �� ����� ��� $(m-1)(n+1)+1$
�������� �������� ������� �� $\mathcal{H}_m$, ���������� ������
�������� ��������� � ������� $[(m-1)n+1,(m-1)(n+1)+1]$. �������,
��������, ��� $\eta=(m-1)(n_0+1)+1$ ����������� ����� ���������.



%����� ���� $H$ �������� ������� $x$. �������, ��� � ���� ������
%��� ����� ���� 1) ����������� ����� $H$. ����� �������, �����
%������� $y_1^1,...,y_{t_1}^1,y_1^2,...,y_{t_2}^2$ � �����
%$\{x,y_1^1\},\{y_1^1,y_2^1\},...,\{y_{t_1-1}^1,y_{t_1}^1\},$ $
%\{y_{t_1}^1,y_{1}^2\},\{y_1^2,y_2^2\},...,\{y_{t_2-1}^2,y_{t_2}^2\},\{y_{t_2}^2,y_{t_1}^1\}$
%����������� $G$. ����� ��� ��� ������� � ����� ���������� � �
%����� $H$. �������������, �����������, ��� ��� �� ���, � � ����
%$H$ ������ ���� ����� ������
%$y_1,...,y_t\in\{y_1^1,...,y_{t_1}^1,y_1^2,...,y_{t_2}^2\}$. ��
%����� �������� ����� ����� ������
%$y_{t+1},...,y_r\in\{y_1^1,...,y_{t_1}^1,y_1^2,...,y_{t_2}^2\}$,
%�� �������� � ���� $H$, ��� �����
%$\{y_i,y_{t+1}\},\{y_{t+1},y_{t+2}\},...,\{,y_j\}$ ��� ���������
%$i,j\in\{1,...,t\}$ ���������� � $E(G)$. �� � ���� ������
%$\rho(G|_{V(H)\cup\{y_{t+1},...,y_r\}})\geq\frac{e(H)+(r-t+1)}{v(H)+(r-t)}\geq
%\frac{e(H)+m}{v(H)+m-1}>\rho(H),$ ��� ��� $\frac{m}{m-1}>\rho(H)$.
%�������� ������������.


%����� $G=(V,E)$, ������ $V=\{x\}\sqcup V_1\sqcup V_2$,
%$V_1=V_1^1\sqcup...\sqcup V_1^{i_1},$ $V_2=V_2^1\sqcup...\sqcup
%V_2^{i_2},$ $E=E_1\sqcup E_2\sqcup E_3$, $E_1=E_1^1\sqcup...\sqcup
%E_1^{i_1},$ $E_2=E_2^1\sqcup...\sqcup E_2^{i_2},$
%$E_3=E_3^1\sqcup...\sqcup E_3^{i_3}$. ����� �������, ���� $G$
%������� ���������������� ����������� $i_1$ �������� ���� 1) �
%����������� ��� $j$-�� �������� ��������� ������ $V_1^j$ �
%��������� ����� $E_1^j$, $i_2$ �������� ���� 2) � ����������� ���
%$j$-�� �������� ��������� ������ $V_2^j$ � ��������� ����� $E_2^j$
%�, �������, $i_3$ �������� ���� 3) � ����������� ��� $j$-��
%�������� ��������� ����� $E_3^j$. ����, ��� �� ��� ��������,
%$V_1\in V(H), E_1\in E(H).$ ������� �� ��������, ��� $V_2\in
%V(H)$, $E_2\in E(H).$ �����������, ��� $V_2\setminus(V_2^i\sqcup
%V_2^{i+1}...\sqcup V_2^{i_2})\in V(H),$ $E_2\setminus(E_2^i\sqcup
%E_2^{i+1}...\sqcup E_2^{i_2})\in E(H),$ ��� $i\in\{1,2,...,i_2\}$.
%����� ���� $H$ �������� ���� ��������� ������ �� $V_2^i$. ����
%$V_2^i=\{y_1,...,y_t\}$, �� � ����� $H$ �������� ����� �������
%$y_0,y_{t+1}$, ��� �����
%$\{y_0,y_1\},\{y_1,y_2\},...,\{y_{t-1},y_t\},\{y_t,y_{t+1}\}$
%�������� ���������� ��������� $E(G)$. ����� �������, �������
%$y_0,y_1,...,y_t,y_{t+1}$ ���������� �� ����� ������,
%��������������� ������ � ������������� ��������� $V(H)$, � ������,
%��������������� ������ � �� ������������� ��������� $V(H)$. ���
%���� ������ � ��������� ����� ����� �������� �� ������,
%������������� $H$. ������� $\rho(G|_{V(H)\cup
%V_2^i})\geq\frac{e(H)+m}{v(H)+m-1}>\rho(H),$ ��� ���
%$\frac{m}{m-1}>\rho(H)$. �������� ������������. �������������,
%$V_2^i\subset V(H),$ $E_2^i\subset E(H)$. �� �������� ��������,
%��� ��������� $V_2$ ���������� � $V(H),$ � ��������� $E_2$
%���������� � $E(H)$.

%�������, ��� ���������� ����� � ���� $H$ ��� ���������
%�������������. ������� $E_3\in E(H).$ ����� �������, $H=G$.\\

%����� $H$ �� �������� ������� $x$. ���� $H$ �������� ���� �� ����
%������� �������� ����� ����� �� ����� $m$, ����������� ����� $x$,
%�� $H$ �������� � ���� ���� ����, � ������ � ��� � ������� $x$, ��
%������������ ����������� ���, ������� �� ������� � ������ $x\in
%V(H)$. �������������, ���� $H$ �� �������� ������, �������������
%���������� ������. �����������, ��� ����� ������� $x$ ����� $G$
%�������� ���� �� ���� ������� ���� �����, �� ������������� �����
%$m$.



\section{���� ����������}
\label{game}


�������� ��������� � �������������� ������� ���� ��� ������� ���
������� ������� ������� ��������� ������, ��� �� �������� ����,
������ ������� �. ����������, ���������� � 1960 ���� (��.
\cite{Ehren}). � ������ ������� �� ������������ �� ������� ������
��� ������. ������ ����� ��������� ���� ���������� $\EHR(G,H,i)$
�� ���� ������ $G,H$ � ����������� �������, ������ $i$ (��.,
��������, \cite{Janson}, \cite{Alon}). �����
$V(G)=\{x_1,...,x_n\},$ $V(H)=\{y_1,...,y_m\}$. � $\nu\mbox{-}$��
������ ($1 \leq \nu \leq i$) ������� �������� ������� �� ������
����� (�� �������� ���� $x_{j_{\nu}}\in V(G)$, ����
$y_{j'_{\nu}}\in V(H)$). ����� ����������� �������� ������� ��
����������� �����. ���� ������� �������� � $\mu\mbox{-}$�� ������,
������, ������� $x_{j_{\mu}}\in V(G),$ $j_{\mu}=j_{\nu}$
($\nu<\mu$), �� ����������� ������ ������� $y_{j'_{\nu}}\in V(H)$.
���� �� � ���� ������ ������� ��������, ������, �������
$x_{j_{\mu}}\in V(G),$ $j_{\mu}\notin\{j_1,...,j_{\mu-1}\},$ �� �
����������� ������ ������� ����� ������� $y_{j'_{\mu}}\in V(H)$,
��� $j'_{\mu}\notin\{j'_1,...,j'_{\mu-1}\}.$ ���� �� �� �����
����� �������, �� ���� ���������� �������. � ����� ���� �������
������� $x_{j_1},...,x_{j_{i}}\in V(G)$, � ����� �������
$y_{j'_1},...,y_{j'_{i}}\in V(H)$. ��������� �� ���� ������ �����
���������. ������� �� ��� ������ ���������: $x_{h_1},...,x_{h_l};$
$y_{h'_1},...,y_{h'_l},$ $l \leq i.$ ����������� ��������� ����� �
������ �����, ����� ��������������� �������� ��������� � ���������
�� ������� ������:
$$
 G|_{\{x_{h_1},...,x_{h_l}\}}\cong
 H|_{\{y_{h'_1},...,y_{h'_l}\}}.
$$



\begin{theorem} [\cite{Ehren}]
��� ����� ���� ������ $G,H$ � ������ $i\in\mathbb{N}$ �����������
����� ���������� ��������� � ���� $\EHR(G,H,i)$ ����� � ������
�����, ����� ��� ������ �������� $L$ ������� �������, �����������
��������, ���������� ������� ������� �� ��������� $i$, ���� ���
����� �������� ���� ���������, ���� ��� �� ��������.
\end{theorem}

�������� ��������, ��� �� ���� ������� �������� ���������
��������� � ������� ���� ��� ������� (��., ��������,
\cite{Janson}, \cite{Alon}). ����� ${\sf P}_{N,p(N)}\times {\sf
P}_{M,p(M)}$
--- ������ ������������ ��� ${\sf P}_{N,p(N)}, {\sf P}_{M,p(M)}$.

\begin{theorem}
��������� ���� $G(N,p)$ ����������� $k$-������ ���� ��� �������
����� � ������ �����
$$
 \lim\limits_{N,M\rightarrow\infty}{\sf P}_{N,p(N)}\times {\sf
 P}_{M,p(M)}(\mbox{� ������������ ���� ���������� ��������� �
 ����}
$$
$$
 \EHR(G(N,p(N)),G(M,p(M)),k))=1.
$$


\label{ehren}
\end{theorem}

��������� � �������� ���������� ��������� ������������. �����
����� �� �������, ��� � ������ ������ ������ �������� �������
�������� �� ��� ���������. ����� ������������� �� ������������
�������� � ���� ����, ��� ������� ������ � ��������������� �������
� ����� �����������, ������������ � ������������, ���������
�������� �������, �������� �� ��� ���������. ������� �� ������
��������� �������� ������ $G,H$, ��������� ������� �����������
����������, ������������� ����� ���������. � ��������� ������� ��
�������, ��� ��������� ���� �������� ����� ���������� �
������������, ����������� � $1$.

����� $n_1,n_2,n_3,n_4$ --- ��������� ����������� �����, $n_2\leq
n_1$, $n_4\leq n_3$, $\rho$
--- ������������ ������������� �����. ����� ��������, ��� ���� $G$
�������� {\it $(n_1,n_2,n_3,n_4,\rho)$--�����������}, ���� ��
�������� ���������� ����������.

\begin{itemize}

\item[1)] ����� $K$ --- ����, ���������� ������ �������� ��
����������� $n_1$. ���� $\rho^{\max}(K)<\rho$, �� $G$ ��������
�������, ���������� $K$. ���� $\rho^{\max}(K)>\rho$, �� $G$ ��
�������� �������, ���������� $K$.



\item[2)] ����� $\mathcal{H}$ --- ��������� �����
$1/\rho$--�������� ��� $(H_1,H_2)$, ��� $v(H_1)\leq n_1$,
$v(H_2)\leq n_2.$ ����� $\mathcal{K}$ --- ��������� �����
$1/\rho$--������� ��� $(K_1,K_2)$, ��� $v(K_1)\leq n_3$,
$v(K_2)\leq n_4.$ ����� ��� ����� ��� $(H_1,H_2)\in\mathcal{H},$
$(K_1,K_2)\in\mathcal{K}$ � ��� ������ �������� $G_2\subset G$ ��
$v(H_2)$ �������� � ����� $G$ �������� ������� $G_1$, ����������
$(K_1,K_2)$--������������ � $G$ ������ $(H_1,H_2)$--�����������
����� $G_2$.



\end{itemize}

���������� ��������� ������������, ��������� ����, ���������
������ �� �������� $(n_1,n_2,n_3,n_4,\rho)$--������������� �����
������, �� ������� ������ ������� � ����������� (��� ���������
��������� $n_1,n_2,n_3,n_4,\rho$).


����� $\rho\in(1,\frac{2^{k-1}}{2^{k-1}-1})$,
$\rho\notin\{1+\frac{1}{2^{k-1}-1+b/a}, \, a,b\in\mathbb{N}, b\leq
2^{k-1}\}$. ��� �������������� ������ ���� ��� ������� � ���������
������� ����� ����� $\rho$ ����� �������� �� ����� $\alpha$, ���
�������� ������������ ����� ($\rho=1/\alpha$). ����� ����� $\rho$
�������� ������� ��� �������� ���������� ��������� � ����������
(�� ����� ���������� �� �������� � ����������� ������),
������������ � ��������� �����. ��������� ���� ��������� ���������
�� ����� ����� $\rho$. ����� �������, ��� �������������� ������
���� ��� ������� ��� ���������� ����� $G(N,N^{-\alpha})$ ��
������� ��������� �����
$\rho(\alpha)\in(1,\frac{2^{k-1}}{2^{k-1}-1})$, ����� ��������
����� $n_1,n_2,n_3,n_4,$ ��������� ������� ��������� �� $\rho$ �
$k$, ����������, ��� ��������� ���� � ������������, ����������� �
1, �������� $(n_1,n_2,n_3,n_4,\rho)$--�����������, ����� ����
���������� ����������, ��������� ����.

��������� $\eta(\rho)$ ����� �� ������������ ����� 1, �.�. �����
�����, ��� ��� ������ ������������ $v>\eta(\rho)$ � � ������ �����
$G\in\mathcal{H}_{2^{k-1}}$ �� $v$ �������� �������� ������� �� ��
����� ��� $\eta(\rho)$ �������� � ����������, �������������
$\rho$. �������
\begin{equation}
 n_1(\rho)=\eta(\rho)+(k-1)\left(\left[\frac{1}{\rho-1}\right]+1\right), \quad
 n_2(\rho)=\eta(\rho)+(k-2)\left(\left[\frac{1}{\rho-1}\right]+1\right),
\label{n1}
\end{equation}
\begin{equation}
 n_3=2^{k-2}+1, \quad n_4=2.
\label{n4}
\end{equation}
����� ����� $G,H$ ��������
$(n_1(\rho),n_2(\rho),n_3,n_4,\rho)$--������������. ������
��������� ������������ � ���� $\EHR(G,H,k)$. ����� ����������
$X_i$ ����, ��������� ��������� � $i$-�� ������. ���������� ����
����� ���������� $Y_i$. �������, ��������� � ����� $X_i$ � ������
$i$ ������� ��������� $x_i^1,...,x_i^i$, � ����� $Y_i$ ---
$y_i^1,...,y_i^i$. ����, ����� � ������ ������ ������� ������
������� $x_1^1$. � ���� ����� 1 � ��������
$(n_1(\rho),n_2(\rho),n_3,n_4,\rho)$--������������� ����� $X_1$ �
��� �� ���������� ��������, ����������� ���������� ����� ��
$\mathcal{H}_{m}$ � ����������� ������, �������������
$\eta(\rho).$ ��������� $\widetilde{X}_1^1$ ������� � $X_1$ ��
$v_1$ ��������, ���������� ���������� ����� ��
$\mathcal{H}_{2^{k-1}}$, ���������� ������� $x_1^1$ � ����������
��������� ���������. � $X_1$ �� ���������� ��������, �����������
������� $x_1^1$ � ����������� ���������� ����� ��
$\mathcal{H}_{2^{k-1}},$ ���������� ������ �������� �����������
$v_1$. ��������� ����������� $v_1\leq \eta(\rho)<n_1(\rho)$.
������� � ���� ����� 1 � ��������
$(n_1(\rho),n_2(\rho),n_3,n_4,\rho)$--������������� ����� $X_1$
��������� ����� $\widetilde{X}_1$ ������, ��� $\rho$.
�������������, �� ��������
$(n_1(\rho),n_2(\rho),n_3,n_4,\rho)$--������������� ����� $Y_1$ �
��� �������� ������� $\widetilde{Y}_1^1$, ����������
$\widetilde{X}_1$. ����� ��� ��������������� �����������
$\varphi_1:\widetilde{X}_1\rightarrow\widetilde{Y}_1^1$ �������
$x_1^1$ ��������� � ������� $y_1^1$, ������� � ������� �����������
� ������ ������.

����� ������� $i$ �������, $1\leq i < k$. ������ ���������
������������ � $i+1$-�� ������. ���� �� ��������� ��� �������
��������� � $G,H$ (��� ���������� (I), (II), (III)). �
������������ �� ��������� (I) ��������� �������
$x_1^i,...,x_i^i,y_1^i,...,y_i^i$ ������ ������������ �����������
���� ���������. �� �����������, ��� � $G$ � $H$ ����������
��������, ���������� ����� ����������. ����� �� �������, ���
���������� �� ������ ��������� ������� $x_{i+1}^{i+1}$ �����������
������ ����� ����� ������� $y_{i+1}^{i+1}$, ��� �������
$x_1^{i+1},...,x_{i+1}^{i+1},y_1^{i+1},...,y_{i+1}^{i+1}$ �����
����� ����������� � ���������, ���������� ���������� (I), (II) �
(III). ����� ����, �� �������, ��� ������� $x_1^1,y_1^1$
���������� � ���������, ���������� ����������� ����������, ������
�� �������� ��������� ����������� ����������� ��� ����������
������, �.�. ��� ������ $x_1^k,...,x_k^k,y_1^k,...,y_k^k$. �
���������, �� ���� ������� �� �������, ��� �����
$X_k|_{\{x_1^k,...,x_k^k\}}$ � $Y_k|_{\{y_1^k,...,y_k^k\}}$
���������.

������ �����������, ������� �� ����� ������������ � ���������� �
���� �������. ��� ������������� ����� $Q$, ��� �������� $W$ �
������� $x\in V(Q)\setminus V(W)$ ��������� $d_Q(x,W)$ ����� �����
�������� ���� �� $Q$ (���������� ����� � ���), ����������� �������
$x$ � ������������ �������� ����� $W$ (��������, ��� ������� �����
���� ����� ����� �� ����������� ����� $W$). ��� ���������
$W_1,W_2\subset Q$, �� ������� ����� ������, �������
$d_Q(W_1,W_2)=\min_{x\in V(W_1)}d_Q(x,W_2)$. ����� $r$
--- ������������ ����������� �����, �� ������������� $i$. �����,
����� ����, $W_1,...,W_r$ --- �������� � $Q$. ����� ��������, ���
$W_1,...,W_r$ �������� $(k,i,r)$--��������� � $Q$, ����

\begin{itemize}


\item[---] ����� ��� ����� �� $W_1,...,W_r$ �� ����� ����� ������;

\item[---] ��� ����� ��������� $j_1,j_2\in\{1,...,r\}$ �����������
����������� $d_{Q}(W_{j_1},W_{j_2})>2^{k-i}$;


%\item[---] ����� $\widetilde{X}^j_i$ � $\widetilde{Y}^j_i$
%��������� ��� $j\in\{1,...,r\}$;


\item[---] ��� ������ $j\in\{1,...,r\}$ � ����� $Q$ �� ����������
��������, ����������� $2^{k-i}$--����������� ������� ��� �������
���� ����� $W_j$;


% � ����� ������� ��
% $V(Q)\setminus V(W_j)$ �� ���������� ���� ��������� ����� � �����
% $Q$ �����, �� ������������� $2^{k-i-1}$, ����������� �� �
% (������������� ����������) ��������� ����� $W_j$;

\item[---] �������� ��������� $|V(W_1\cup...\cup W_r)|$ ��
�����������
$\eta(\rho)+(i-1)\left(\left[\frac{1}{\rho-1}\right]+1\right)$.


\end{itemize}


�����������, ��� ��� ���������� $r\in\{1,...,i\}$ ���� $X_i$
�������� �������� $\widetilde{X}_i^1,...,\widetilde{X}_i^r$, ����
$Y_i$ �������� �������� $\widetilde{Y}_i^1,...,\widetilde{Y}_i^r$,
������� �������� ���������� ����������.

\begin{itemize}

\item[(I)] ������� $x_i^1,...,x_i^i$ ����������� ���������
$V(\widetilde{X}_i^1\cup...\cup \widetilde{X}_i^r)$, �������
$y_i^1,...,y_i^i$ ����������� ���������
$V(\widetilde{Y}_i^1\cup...\cup \widetilde{Y}_i^r)$.


\item[(II)] ����� $\widetilde{X}^1_i,...,\widetilde{X}^r_i$
�������� $(k,i,r)$--��������� � $X_i$, �����
$\widetilde{Y}^1_i,...,\widetilde{Y}^r_i$ ��������
$(k,i,r)$--��������� � $Y_i$.


\item[(III)] ����� $\widetilde{X}^j_i$ � $\widetilde{Y}^j_i$
��������� ��� ������ $j\in\{1,...,r\}$ � ��� ���������
��������������� ����������� (����� ��� ���� ������, ��� ��� ��� ��
����� ����� ������) ������� $x_i^j$ ��������� � ������� $y_i^j,$
$j\in\{1,...,i\}$.


\end{itemize}


���� $X_{i+1}=X_i$, �� �������
$\widetilde{X}^j_{i+1}=\widetilde{X}^j_i$,
$\widetilde{Y}^j_{i+1}=\widetilde{Y}^j_i$, $j\in\{1,...,r\}$. �
��������� ������ �������
$\widetilde{X}^j_{i+1}=\widetilde{Y}^j_i$,
$\widetilde{Y}^j_{i+1}=\widetilde{X}^j_i$, $j\in\{1,...,r\}$.
����� $\varphi_{i+1}$ --- ���������� ��
$\widetilde{X}^1_{i+1}\cup...\cup\widetilde{X}^r_{i+1}$ �
$\widetilde{Y}^1_{i+1}\cup...\cup\widetilde{Y}^r_{i+1}$,
����������� ����� $\widetilde{X}^j_{i+1}$ �
$\widetilde{Y}^j_{i+1}$ ��� $j\in\{1,...,r\}$. �����, ����� ����,
$\varphi_{i+1}(x^j_{i+1})=y^j_{i+1}$ ��� $j\in\{1,...,i\}$.
���������� ����� ��� ��������� ��������.



\begin{enumerate}

\item �����������, ��� ������� � $i+1$-�� ������ ������ �������
$x_{i+1}^{i+1}$ �� ���������
$V(\widetilde{X}^1_{i+1}\cup...\cup\widetilde{X}^r_{i+1})$. �����
����������� ������� $y_{i+1}^{i+1}=\varphi(x_{i+1}^{i+1})$.
�������, ��� �� ���������� �����
$\widetilde{X}_{i+1}^1,...,\widetilde{X}_{i+1}^r,\widetilde{Y}_{i+1}^1,...,\widetilde{Y}_{i+1}^r$
������ ������������� �����
$\widetilde{X}_{i}^1,...,\widetilde{X}_{i}^r,\widetilde{Y}_{i}^1,...,\widetilde{Y}_{i}^r$
� �� ����� �� ���������. �������, ��� �������� ������, ��� $i<k-1$
����� $\widetilde{X}^1_{i+1},...,\widetilde{X}^r_{i+1}$ ��������
$(k,i+1,r)$--��������� � $X_{i+1}$, �����
$\widetilde{Y}^1_{i+1},...,\widetilde{Y}^r_{i+1}$ ��������
$(k,i+1,r)$--��������� � $Y_{i+1}$. ����� ����, �����
$\widetilde{X}^j_{i+1}$ � $\widetilde{Y}^j_{i+1}$ ��������� ���
������ $j\in\{1,...,r\}$ � ��� ��������������� �����������
$\varphi_{i+1}$ (����� � ��� �� ��� ���� ������) �������
$x_{i+1}^j$ ��������� � ������� $y_{i+1}^j,$ $j\in\{1,...,i+1\}$.
����� �������, ��� $i+1$-�� ������ �� ��������� �����
$\widetilde{X}^1_{i+1},...,\widetilde{X}^r_{i+1},\widetilde{Y}^1_{i+1},...,\widetilde{Y}^r_{i+1}$,
���������� ���������� (I), (II), (III).


\item ����������� ������, ��� ������� ������ �������
$x_{i+1}^{i+1}$, �� ������������� ���������
$V(\widetilde{X}^1_{i+1}\cup...\cup\widetilde{X}^r_{i+1})$, ���
����
$d_{X_{i+1}}(x_{i+1}^{i+1},\widetilde{X}_{i+1}^1\cup...\cup\widetilde{X}_{i+1}^r)\leq
2^{k-1-i}$. �������, ��� � ���� ����������� ������
$\widetilde{X}_{i+1}^1,...,\widetilde{X}_{i+1}^r$ � �����
$X_{i+1}$ �������� ����� ���� ����
$c_{X_{i+1}}$,%(x_{i+1}^{i+1},\widetilde{X}_{i+1}^1\sqcup...\sqcup\widetilde{X}_{i+1}^r)$,
���������� ������ ����� ������� �����
$X_{i+1}\setminus\left(\widetilde{X}_{i+1}^1\cup...\cup\widetilde{X}_{i+1}^r\right)$
(�� ������ ��������� �������), �����, �� �������������
$2^{k-1-i}$, ����������� $x_{i+1}^{i+1}$ � ��������� ��������
$\widetilde{x}_{i+1}^l$ �����
$\widetilde{X}_{i+1}^1\cup...\cup\widetilde{X}_{i+1}^r$, ���
$l\in\{1,...,r\}$, $\widetilde{x}_{i+1}^l\in
V(\widetilde{X}_{i+1}^l)$. �������������, ����
$(\widetilde{X}_{i+1}^1\cup...\cup\widetilde{X}_{i+1}^r\cup
 c_{X_{i+1}},%(x_{i+1}^{i+1},\widetilde{X}_{i+1}^1\sqcup...\sqcup\widetilde{X}_{i+1}^r),
 \widetilde{X}_{i+1}^1\cup...\cup\widetilde{X}_{i+1}^r)$ �������� $1/\rho$--��������. ����� ����,
$$
 |V(\widetilde{Y}_{i+1}^1\cup...\cup\widetilde{Y}_{i+1}^r)|<\eta(\rho)+(i-1)\left(\left[\frac{1}{\rho-1}\right]+1\right)\leq
 \eta(\rho)+(k-2)\left(\left[\frac{1}{\rho-1}\right]+1\right).
$$
������� � ���� ��������
$(n_1(\rho),n_2(\rho),n_3,n_4,\rho)$--������������� �����
$Y_{i+1}$ � ��� �������� ������ $(K_1,K_2)$--������������
$(\widetilde{X}_{i+1}^1\cup...\cup\widetilde{X}_{i+1}^r\cup
c_{X_{i+1}},%(x_{i+1}^{i+1},\widetilde{X}_{i+1}^1\sqcup...\sqcup\widetilde{X}_{i+1}^r),
\widetilde{X}_{i+1}^1\cup...\cup\widetilde{X}_{i+1}^r)$--����������
����� $\widetilde{Y}_{i+1}^1\cup...\cup\widetilde{Y}_{i+1}^r$ ���
���� ����� $1/\rho$--������� ��� $(K_1,K_2)$, ��� $v(K_2)=2$,
$v(K_1)\leq 2^{k-1-i}$. �������������,
$$
 |V(\widetilde{X}_{i+1}^1\cup...\cup\widetilde{X}_{i+1}^r\cup
 c_{X_{i+1}})|\leq%(x_{i+1}^{i+1},\widetilde{X}_{i+1}^1\sqcup...\sqcup\widetilde{X}_{i+1}^r))|\leq
 \eta(\rho)+(k-2)\left(\left[\frac{1}{\rho-1}\right]+1\right)+2^{k-1-i}<
$$
$$
 <\eta(\rho)+(k-2)\left(\left[\frac{1}{\rho-1}\right]+1\right)+\frac{1}{\rho-1}\leq
 \eta(\rho)+(k-1)\left(\left[\frac{1}{\rho-1}\right]+1\right)=n_1(\rho).
$$
����� �������, ���������� ����� ������� $y_{i+1}^{i+1}\in
V(Y_{i+1})$, ���
$$
 d_{Y_{i+1}}(y_{i+1}^{i+1},\widetilde{Y}_{i+1}^l)=
 d_{X_{i+1}}(x_{i+1}^{i+1},\widetilde{X}_{i+1}^l),
$$
� ������������ ���� $c_{Y_{i+1}}$ %(y_{i+1}^{i+1},\widetilde{Y}_{i+1}^1\sqcup...\sqcup\widetilde{Y}_{i+1}^r)$
�����, �� ������������� $2^{k-1-i}$, ����������� $y_{i+1}^{i+1}$ �
��������� �������� $\widetilde{y}_{i+1}^l$ �����
$\widetilde{Y}_{i+1}^1\cup...\cup\widetilde{Y}_{i+1}^r$,
$\widetilde{y}_{i+1}^l\in V(\widetilde{Y}_{i+1}^l)$. �������������
����� $\widetilde{X}_{i+1}^l,\widetilde{Y}_{i+1}^l:$
$$
 \widetilde{X}_{i+1}^l:=\widetilde{X}_{i+1}^l\cup
 c_{X_{i+1}},\,\,\,\,
 \widetilde{Y}_{i+1}^l:=\widetilde{Y}_{i+1}^l\cup c_{Y_{i+1}}.
$$
��������� �����
$\widetilde{X}_{i+1}^1,...,\widetilde{X}_{i+1}^{l-1},\widetilde{X}_{i+1}^{l+1},...,\widetilde{X}_{i+1}^{r}$,
$\widetilde{Y}_{i+1}^1,...,\widetilde{Y}_{i+1}^{l-1},\widetilde{Y}_{i+1}^{l+1},...,\widetilde{Y}_{i+1}^{r}$
������� ��� ���������. ��������� ���������� ������ $\varphi_{i+1}$
�� ������� �� ��������� $V(\widetilde{X}_{i+1}^l)$: ��� �������
$v$ ����
$c_{X_{i+1}}$ %(x_{i+1}^{i+1},\widetilde{X}_{i+1}^1\sqcup...\sqcup\widetilde{X}_{i+1}^r)$
� ������� $h$, ������ �� $\widetilde{x}_{i+1}^l$, ������ �������
$u$ ����
$c_{Y_{i+1}}$%(y_{i+1}^{i+1},\widetilde{Y}_{i+1}^1\sqcup...\sqcup\widetilde{Y}_{i+1}^r)$
� ��� �� ������� $h$, ������ �� $\widetilde{y}_{i+1}^l$, �
��������� $\varphi_{i+1}(v)=u$. �����
$\varphi_{i+1}|_{\widetilde{X}^j_{i+1}}:\widetilde{X}^j_{i+1}\rightarrow\widetilde{Y}^j_{i+1}$
--- ���������� ��� ������ $j\in\{1,...,r\}$ �
$\varphi_{i+1}(x_{i+1}^j)=y_{i+1}^j$ ��� ���� $j\in\{1,...,i+1\}$,
�.�. �����
$\widetilde{X}_{i+1}^1,...,\widetilde{X}_{i+1}^r,\widetilde{Y}_{i+1}^1,...,\widetilde{Y}_{i+1}^r$
�������� ���������� (I) � (III). �������, ��� ��� $i<k-1$
��������� �������� (II) (�����
$\widetilde{X}^1_{i+1},...,\widetilde{X}^r_{i+1}$ ��������
$(k,i+1,r)$--��������� � $X_{i+1}$, � �����
$\widetilde{Y}^1_{i+1},...,\widetilde{Y}^r_{i+1}$ ��������
$(k,i+1,r)$--��������� � $Y_{i+1}$). ��� ����� ���������� ��������
��������� �����������:

\begin{itemize}

\item[---] ��� ������ $j\in\{1,...,r\}\setminus\{l\}$
$$
 d_{X_{i+1}}(\widetilde{X}^{j}_{i+1},\widetilde{X}^{l}_{i+1})>2^{k-i-1},\,\,\,\,\,
 d_{Y_{i+1}}(\widetilde{Y}^{j}_{i+1},\widetilde{Y}^{l}_{i+1})>2^{k-i-1};
$$


\item[---] � ����� $X_{i+1}$ (� ����� $Y_{i+1}$) �� ��������
��������, ����������� $2^{k-i-1}$--����������� �����
$\widetilde{X}_{i+1}^l$ (����� $\widetilde{Y}_{i+1}^l$) �������
��� ������� ����;

%��� ����� ������� �� $V(X_{i+1})\setminus
%V(\widetilde{X}^l_{i+1})$ (������� �� $V(Y_{i+1})\setminus
%V(\widetilde{Y}^l_{i+1})$) �� ���������� ���� ��������� ����� �
%����� $X_{i+1}$ (� ����� $Y_{i+1}$) �����, �� �������������
%$2^{k-i-2}$, ����������� �� � (������������� ����������) ���������
%����� $\widetilde{X}^l_{i+1}$ (����� $\widetilde{Y}^l_{i+1}$);

\item[---] �������� ��������
$|V(\widetilde{X}^1_{i+1}\cup...\cup\widetilde{X}^r_{i+1})|,\,|V(\widetilde{Y}^1_{i+1}\cup...\cup\widetilde{Y}^r_{i+1})|$
�� �����������
$\eta(\rho)+i\left(\left[\frac{1}{\rho-1}\right]+1\right)$.


\end{itemize}


�����������, ��� �������� $j\in\{1,...,r\}\setminus\{l\}$ � ����
�����, �� ������������� $2^{k-1-i}$, ����������� ��������� �������
$u$ ����� $\widetilde{X}^l_{i+1}$ � ��������� �������� $v$ �����
$\widetilde{X}^j_{i+1}$. ��� ��� $2^{k-1-i}<2^{k-i}$, �� $u\in
V(c_{X_{i+1}})$. %(x_{i+1}^{i+1},\widetilde{X}_{i+1}^1\sqcup...\sqcup\widetilde{X}_{i+1}^r))$.
�� ����� ����
$c_{X_{i+1}}$%(x_{i+1}^{i+1},\widetilde{X}_{i+1}^1\sqcup...\sqcup\widetilde{X}_{i+1}^r)$
�� ����������� $2^{k-1-i}$. �������������,
$d_{X_{i+1}}(\widetilde{X}^j_{i+1},\widetilde{X}^l_{i+1}\setminus
(c_{X_{i+1}}%(x_{i+1}^{i+1},\widetilde{X}_{i+1}^1\sqcup...\sqcup\widetilde{X}_{i+1}^r)
\setminus\{\widetilde{x}_{i+1}^l\}))\leq
2^{k-1-i}+2^{k-1-i}=2^{k-i}$. �� �������� � ����� �����
����������� ����� ����
$d_{X_i}(\widetilde{X}^l_i,\widetilde{X}^j_i)$, ����
$d_{Y_i}(\widetilde{Y}^l_i,\widetilde{Y}^j_i)$. ��������
������������ ���� � $(k,i,r)$--��������� ������
$\widetilde{X}_i^1,...,\widetilde{X}_i^r$, ���� �
$(k,i,r)$--��������� ������
$\widetilde{Y}_i^1,...,\widetilde{Y}_i^r$. ����� �������,
$d_{X_{i+1}}(\widetilde{X}^{j}_{i+1},\widetilde{X}^{l}_{i+1})>2^{k-i-1}$.
���������� ������������ �����������
$d_{Y_{i+1}}(\widetilde{Y}^{j}_{i+1},\widetilde{Y}^{l}_{i+1})>2^{k-i-1}$.

�������������� ������� ����������� �� ���� �������� ������ ���
����� $X_{i+1}$, ��� ��� ��� � �������� ��������� ��������������
��� ����� $Y_{i+1}$. ����, ����� � ����� $X_{i+1}$ ����������
������� $W$, ���������� $2^{k-1-i}$--����������� ������� ���
������� ���� ����� $\widetilde{X}_{i+1}^l$. ���������� ���������
����� $E=E(W)\setminus (E(\widetilde{X}_{i+1}^l)\cup E(W\setminus
\widetilde{X}_{i+1}^l))$. ������, ������������� ���������
$V(\widetilde{X}_{i+1}^l)$ � ���������� ������� ����� �� $E$, ��
����� ����. ��������� �� $v_1$ � $v_2$ (������ ������, ��� �������
����� ���������). ���� $v_1,v_2\in
V(\widetilde{X}_{i+1}^{l})\setminus
(V(c_{X_{i+1}})\setminus\{\widetilde{x}_{i+1}^l\})$, �� ��
�������� � ������������ ���� � $(k,i,r)$--��������� ������
$\widetilde{X}_i^1,...,\widetilde{X}_i^r$, ���� �
$(k,i,r)$--��������� ������
$\widetilde{Y}_i^1,...,\widetilde{Y}_i^r$. ���� �� ���� �� ���� ��
������ $v_1,v_2$ �� ����������� ���������
$V(\widetilde{X}_{i+1}^{l})\setminus
(V(c_{X_{i+1}})\setminus\{\widetilde{x}_{i+1}^l\})$, �� � �����
$W$ �������� ������� $W_1$, ��������� ������ �������� ��������
$V(\widetilde{X}_{i+1}^{l})\setminus
(V(c_{X_{i+1}})\setminus\{\widetilde{x}_{i+1}^l\})$, ����������
$2^{k-i}$--����������� ������� ��� ������� ���� �����
$W|_{V(\widetilde{X}_{i+1}^{l})\setminus
(V(c_{X_{i+1}})\setminus\{\widetilde{x}_{i+1}^l\})}$. �� �����
�������� � ������������ ���� � $(k,i,r)$--��������� ������
$\widetilde{X}_i^1,...,\widetilde{X}_i^r$, ���� �
$(k,i,r)$--��������� ������
$\widetilde{Y}_i^1,...,\widetilde{Y}_i^r$. ��������� �����������
���������, ��� ��� ���������� ����������� ������ �� �����������
$2^{k-1-i}\leq \left[\frac{1}{\rho-1}\right]+1$.


\end{enumerate}


���� $i=k-1$, �� � ����� ������� ��� ��� $\varphi_k:
\widetilde{X}_k^1\cup...\cup\widetilde{X}_k^r\rightarrow
\widetilde{Y}_k^1\cup...\cup\widetilde{Y}_k^r$ --- ���������� �
$\varphi_k(x_k^j)=y_k^j$ ��� ���� $j\in\{1,...,k\}$, �� �����
$X_k|_{\{x_k^1,...,x_k^k\}}$, $Y_k|_{\{y_k^1,...,y_k^k\}}$ �����
��������� � ����������� ���������.


\begin{enumerate}

\item[3.] �����, �������,
$d_{X_{i+1}}(x_{i+1}^{i+1},\widetilde{X}_{i+1}^1\cup...\cup\widetilde{X}_{i+1}^r)>
2^{k-1-i}$. ������ ������� � $X_{i+1}$, ���������� ����������
���������� ������, ���� �� ������� ��������� � $x_{i+1}^{i+1}$, �
���������� ���������� ����� �� ���������
$\mathcal{H}_{2^{k-1-i}}$. ��������� ���������� ����
$\widetilde{X}_{i+1}^{r+1}$. � ���� ��������
$(n_1(\rho),n_2(\rho),n_3,n_4,\rho)$--������������� �����
$X_{i+1}$ �� �������� �� ����� ������ �������� �����.


���������� ���� $(H_1,H_2)$, ��� ���� $H_1$ �������� ����� �����
$\left[\frac{1}{\rho-1}\right]+1$, ������������ � ������,
���������� $\widetilde{X}_{i+1}^{r+1}$ (������� $x_{i+1}^{i+1}$
��� ��������������� ����������� ��������� � ��������� �������
$h$). ���� $H_2$ �������� ���� ���� �������, ������� ��������
�������� �������� ������������� ����, �������� �� $h$. ����������,
����� ����, ��������� $\mathcal{K}$ ���� ��������� ���
$(K_1,K_2)$, ��� ������ �� ������� �������� ����� ���� $K$, ���
$K\cap K_1=K_2$, ���� $K\cup K_1$ ��������
$2^{k-1-i}$--����������� ������� ��� ������� ���� ����� $K$. �
���� $(n_1(\rho),n_2(\rho),n_3,n_4,\rho)$--������������� �����
$Y_{i+1}$ �������� ����� ������� $y_{i+1}^{i+1}\in
V(Y_{i+1})\setminus
V(\widetilde{Y}_{i+1}^1\cup...\cup\widetilde{Y}_{i+1}^r)$,
$\widetilde{y}_{i+1}^l\in V(\widetilde{Y}_{i+1}^l)$ ��� ����������
$l\in\{1,...,r\}$, ���� $c_{Y_{i+1}}\subset Y_{i+1}$ �����
$\left[\frac{1}{\rho-1}\right]+1$, ����������� �������
$\widetilde{y}_{i+1}^l$ � $y_{i+1}^{i+1}$, � ����� ����
$\widetilde{Y}_{i+1}^{r+1}\subset Y_{i+1}$, ����������
$\widetilde{X}_{i+1}^{r+1}$, ���
$d_{Y_{i+1}}(y_{i+1}^{i+1},\widetilde{Y}_{i+1}^1\cup...\cup\widetilde{Y}_{i+1}^r)=
\left[\frac{1}{\rho-1}\right]+1$, $V(c_{Y_{i+1}})\cap
V(\widetilde{Y}_{i+1}^{r+1})=\{y_{i+1}^{i+1}\}$ � ����
$(c_{Y_{i+1}}\cup
\widetilde{Y}_{i+1}^{r+1},(\{\widetilde{y}_{i+1}^l\},\varnothing))$
�������� $(K_1,K_2)$--������������ � $Y_{i+1}$ ������
$(H_1,H_2)$--����������� �����
$(\{\widetilde{y}_{i+1}^l\},\varnothing)$ ��� ����
$(K_1,K_2)\in\mathcal{K}$.\\


��������� ���������� ������ $\varphi_{i+1}$ �� ������� ��
��������� $V(\widetilde{X}_{i+1}^{r+1})$:
$\varphi_{i+1}|_{\widetilde{X}_{i+1}^{r+1}}:
\widetilde{X}_{i+1}^{r+1}\rightarrow \widetilde{Y}_{i+1}^{r+1}$,
������ $\varphi_{i+1}(x_{i+1}^{i+1})=y_{i+1}^{i+1}$.\\


�������, ��� �����
$\widetilde{X}_{i+1}^1,...,\widetilde{X}_{i+1}^{r+1},\widetilde{Y}_{i+1}^1,...,\widetilde{Y}_{i+1}^{r+1}$
�������� ���������� (I), (II) � (III) ��� $i<k-1$. �������� (I)
���������, ��� ��� $x_{i+1}^{i+1}\in
V(\widetilde{X}_{i+1}^{r+1})$, $y_{i+1}^{i+1}\in
V(\widetilde{Y}_{i+1}^{r+1})$. �� ������������ ���
$(c_{Y_{i+1}}\cup
\widetilde{Y}_{i+1}^{r+1},(\{\widetilde{y}_{i+1}^l\},\varnothing))$,
$(H_1,H_2)$ ������� ������������ ���
$(\widetilde{X}^1_{i+1}\cup...\cup
\widetilde{X}^{r+1}_{i+1},\widetilde{X}^1_{i+1}\cup...\cup
\widetilde{X}^{r}_{i+1})$, $(\widetilde{Y}^1_{i+1}\cup...\cup
\widetilde{Y}^{r+1}_{i+1},\widetilde{Y}^1_{i+1}\cup...\cup
\widetilde{Y}^{r}_{i+1})$ � �������������� �������� (III).
�������� ��������, ��� �����
$\widetilde{X}^1_{i+1},...,\widetilde{X}^{r+1}_{i+1}$ ��������
$(k,i+1,r+1)$--��������� � $X_{i+1}$, � �����
$\widetilde{Y}^1_{i+1},...,\widetilde{Y}^{r+1}_{i+1}$ ��������
$(k,i+1,r+1)$--��������� � $Y_{i+1}$. ����� $j\in\{1,...,r\}$.
�����������, ��� ���������� ����� ������� $v\in
V(\widetilde{X}_{i+1}^{r+1})$, �������� �� $x_{i+1}^{i+1}$, ���
$d_{X_{i+1}}(v,\widetilde{X}_{i+1}^j)<2^{k-1-i}$. ����� � �����
$X_{i+1}$ ���������� �������, ���������� $2^{k-i}$--�����������
������� ���� ����� $\widetilde{X}_{i+1}^j$. �������� ������������
� $(k,i,r)$--��������� ������
$\widetilde{X}^1_{i+1},...,\widetilde{X}^{r}_{i+1}$ � $X_{i+1}$.
�������������,
$d_{X_{i+1}}(\widetilde{X}^j_{i+1},\widetilde{X}^{r+1}_{i+1})\geq
2^{k-1-i}$. ����� ����,
$$
 d_{Y_{i+1}}(\widetilde{Y}^j_{i+1},\widetilde{Y}^{r+1}_{i+1})>
 d_{Y_{i+1}}(\widetilde{Y}^j_{i+1},y_{i+1}^{i+1})-|V(\widetilde{Y}_{i+1}^{r+1})|\geq
$$
$$
 \geq\left[\frac{1}{\rho-1}\right]+1-2^{k-1-i}>2^{k-1}-2^{k-1-i}\geq 2^{k-2}\geq 2^{k-1-i}.
$$
���� $\widetilde{X}^{r+1}_{i+1}$ (����
$\widetilde{Y}_{i+1}^{r+1}$) �� ����� ����� ������ � ������
$\widetilde{X}_{i+1}^1\cup...\cup\widetilde{X}_{i+1}^r$ (������
$\widetilde{Y}_{i+1}^1\cup...\cup\widetilde{Y}_{i+1}^r$) ��
����������. ����������� �����������
$$
 |W_1\cup...\cup W_{r+1}|=
 |V(W_1\cup...\cup W_{r})|+|V(W_{r+1})|\leq
$$
$$
 \leq\eta(\rho)+(i-1)\left(\left[\frac{1}{\rho-1}\right]+1\right)+2^{k-1-i}<
 \eta(\rho)+i\left(\left[\frac{1}{\rho-1}\right]+1\right),
$$
��� ���� $W_j=\widetilde{X}^j_{i+1}$ ��� ���� $j\in\{1,...,r+1\}$,
���� $W_j=\widetilde{Y}^j_{i+1}$ ��� ���� $j\in\{1,...,r+1\}$.
�������, �������, ��� � ����� $X_{i+1}$ (� ����� $Y_{i+1}$) ��
�������� ��������, ����������� $2^{k-1-i}$--����������� �����
$\widetilde{X}_{i+1}^{r+1}$ (����� $\widetilde{Y}_{i+1}^{r+1}$). �
������ ����� $\widetilde{X}_{i+1}^{r+1}$ ���������� ���������, ���
�� �������� ���������� ���������� ������ ����� ���� ������,
���������� ������-���� ����� �� $\mathcal{H}_{2^{k-1-i}}$ �
���������� ������� $x_{i+1}^{i+1}$. ���� $Y_{i+1}$ �� ��������
������, ���������� $2^{k-1-i}$--������������ ������� ��� �������
���� ����� $\widetilde{Y}_{i+1}^{r+1}$, ��� ��� ����
$\widetilde{Y}_{i+1}^{r+1}$ �������� $(K_1,K_2)$--������������ �
$Y_{i+1}$ ��� ���� $(K_1,K_2)\in\mathcal{K}$.\\

���� $i=k-1$, �� ��� ��� $\varphi_k:
\widetilde{X}_k^1\cup...\cup\widetilde{X}_k^{r+1}\rightarrow
\widetilde{Y}_k^1\cup...\cup\widetilde{Y}_k^{r+1}$ --- ����������
� $\varphi_k(x_k^j)=y_k^j$ ��� ���� $j\in\{1,...,k\}$, �� �����
$X_k|_{\{x_k^1,...,x_k^k\}}$, $Y_k|_{\{y_k^1,...,y_k^k\}}$ �����
��������� � ����������� ���������.


\end{enumerate}


\section{�������������� ������� 1}
\label{proof1}

����� $\beta\in(0,\infty)\setminus \mathcal{Q}$ --- ������������
�����, $\alpha=1-\frac{1}{2^{k-1}+\beta}$, $\rho=1/\alpha$. ���
����, ����� � ������������, ����������� � 1, ����������� ������� �
���� $\EHR(G(N,N^{-\alpha}),G(M,M^{-\alpha}),k)$, ���������
����������, ��������� � ���������� �������, ���������� ��������,
��� � ������������, ����������� � 1, ��������� ����
$G(N,N^{-\alpha})$ �������� $(n_1,n_2,n_3,n_4,\rho)$--�����������,
��� ����� $n_1,n_2,n_3,n_4$ ���������� ����������� (\ref{n1}),
(\ref{n4}). ��������� ������� � ������� �������� � �����������
$(n_1,n_2,n_3,n_4,\rho)$--������������ �����. ���������� �����
��������� $\mathcal{G}$ ������� ������������ ������, ����������
������ ������� �� ����������� $n_1$, � ��������� ������� ��
$\rho$, ��� ����� ���� $G$ � $v(G)\leq n_1$ � $\rho(G)\neq\rho$
��������� ���������� ����� �� $\mathcal{G}$. ����� $\mathcal{G}_1$
--- ����� ��������� ������� ������������ ������, ���������� ������ ������� �� �����������
$n_1$, � ������������ ��������� ������, ��� $\rho$, ��� �����
����, ��������������� �������� ��������, ��������� ����������
����� �� $\mathcal{G}_1$. ��������, $|\mathcal{G}_1|\leq
|\mathcal{G}|<\infty$. ������� � ������������ � ��������
\ref{erdos} ����������� ���������
$$
 \lim_{N\rightarrow\infty}{\sf P}_{N,p}(\forall G\in\mathcal{G}_1 \,\,
 N_G>0)=1,
$$
$$
 \lim_{N\rightarrow\infty}{\sf P}_{N,p}(\exists G\in\mathcal{G}\setminus\mathcal{G}_1 \,\,
 N_G>0)=0.
$$
�������� 1) ��������.

����� $\mathcal{H}$ --- ��������� ����� ������� ������������
$1/\rho$--�������� ��� $(H_1,H_2)$, ��� $v(H_1)\leq n_1$,
$v(H_2)\leq n_2$ � �������� $\mathcal{H}$ �����������. �����
$\mathcal{K}$
--- ��������� ����� ������� ������������ $1/\rho$--������� ��� $(K_1,K_2)$, ���
$v(K_1)\leq n_3$, $v(K_2)\leq n_4$ � �������� $\mathcal{K}$
�����������. � ���� ������� \ref{maximal_extensions_rigid} ���
����� ������ $\widetilde{x}_1,...,\widetilde{x}_{v(H_2)}\in V_N$
��������� ���������
$$
 \lim_{N\rightarrow\infty}{\sf P}_{N,p}(\forall (H_1,H_2)\in\mathcal{H} \, \forall (K_1,K_2)\in\mathcal{K}
 \,\,\,
 N_{(H_1,H_2)}^{(K_1,K_2)}(\widetilde{x}_1,...,\widetilde{x}_{v(H_2)})>0)=1.
$$
��� �����, �������� 2) �, �������������, � ������� \ref{positive}
��������.





\section{�������������� ������� 2}
\label{proof2}


� ���� ������� ��� ������� $\alpha=1-\frac{1}{2^{k-1}+\beta},$
$\beta\in\widetilde{Q}$, �� ���������� ��� ����� $G$ � $H$, �
����� �������� $L_1$, ������� �������� ���� $G$, � �������� $L_2$,
������� �������� ���� $H$. �� �������, ��� � �������� ����
���������� ��������� � ���� $\EHR(G,H,k)$, � ����� ���������, ���
��������� ���� $G(N,p)$ � ������������, ����������� � ����������
�������������� �����, �������� ���������� $L_1$ � $L_2$. ��� �����
����������� ������� ����� ��������.

����, ����� $k>3$ --- ��������� ����������� �����,
$\beta\in\widetilde{Q}$, $\alpha=1-\frac{1}{2^{k-1}+\beta}$.
�������
$\rho=\frac{1}{\alpha}=\frac{2^{k-1}+\beta}{2^{k-1}+\beta-1}.$
���������� ���� $X$, ������ ����������� ���� ������� ������
$C_1,C_2$, ������� ����� ���� ����� �������, ������
$v(C_1)+v(C_2)=2^{k-1}+\beta-1$, $v(C_1)\leq 2^{k-1}$, $v(C_2)\leq
2^{k-1}-1$, $v(C_1)>v(C_2)$. ����� ����� $C_1$ � $C_2$ �� �����
����� �����. ��������� $L_1$ �������� ����� ��������� �������,
���������� $X$. ���������� �������� ��������� ����� ������� $x$,
��� � ����� ���������� $v(C_1)$--���������� ������� ���� ��������
$\{\{x\},\varnothing\}$ � $v(C_2)$--���������� ������� ���� ����
�� ��������. ��������� ��������� ����� �������� $L_2$. ����� ����
$G$ �������� ��������� $L_1$, � ���� $H$ �������� ��������� $L_2$.
������ ���������� ��������� �������� � ���� $\EHR(G,H,k)$. �
������ ������ ������� �������� ����� ������� $x_1$ ����� $G$, ���
$x_1$ �������� �������� ���������� �������� $G_1\cup G_2$ � $G$,
����������� $X$, ������ $G_1\cong C_1$, $G_2\cong C_2$,
$V(G_1)\cap V(G_2)=\{x\}$. ����������� �������� ��������� �������
$y_1\in V(H)$. �� ����������� ��������, ����� �������, ��� � �����
$H$ �� �������� $v(C_1)$--���������� ������� ���� �����
$\{\{y_1\},\varnothing\}$. ������� �� ������ ������ ��������
������� $x_2$ ����� $G_1$, �������� ��������� �� ������� $x_1$.
����� $A$, $B$ --- ��� ��������� ����, ���������� ���������� $G_1$
� ����������� $x_1$ � $x_2$. ����������� �� ������ ������ ��������
��������� ������� $y_2\in V(H)$. �������, ��� � ����� $H$ ��
�������� ���� ��������� �����, ����� ����� �� ������� ��
����������� $v(A)-1$, � ������
--- $v(B)-1$, � ����������� $y_1$ � $y_2$. �����, ��������, ��
������� ���� ����� $v(A)-1$. ������� $T_{1}^2=A$. ����� �������
$i$ �������, $i\geq 2$. �����, ����� ����, ������� �������
$x_1,...,x_i\in V(G)$, $y_1,...,y_i\in V(H)$, � ����� ����� ����
$T_{i-1}^i$ ����������� ������� $x_{i-1}$ � $x_i$ � ����� $G$, ���
� ����� $H$ �� �������� ���� ����� �� �����, ����������� �������
$y_{i-1}$ � $y_i$. ������� � $i+1$-�� ������ �������� �����
������� $x_{i+1}$, ������������� ���� $T_{i-1}^i$, ���
$|d_{T_{i-1}^i}(x_i,x_{i+1})-d_{T_{i-1}^i}(x_{i-1},x_{i+1})|$ ---
����������. ����������� �� ������ ������ �������� ���������
������� $y_{i+1}\in V(H)$. �������, ��� � ����� $H$ �� ��������
���� �����, ���� �� ������� ����� �����
$d_{T_{i-1}^i}(x_{i-1},x_{i+1})$ � ��������� $y_{i-1}$ �
$y_{i+1}$, ������ ����� ����� $d_{T_{i-1}^i}(x_{i},x_{i+1})$ �
��������� $y_{i}$ � $y_{i+1}$ (�� ���������� $d_W(x,y)$ �����
���������� ���� � ����� $W$, ����������� ������� $x$ � ��������
$y$). �����, ��������, �� ������� ����, ����������� $y_{i-1}$ �
$y_{i+1}$. ��������� ����, ���������� ��������� � $T_{i-1}^i$ �
����������� $x_{i-1}$ � $x_{i+1}$, $T_i^{i+1}$. ��� ���
$\max\{v(C_1),v(C_2)\}\leq 2^{k-1}$, �� � ����� �� ������� �
������� $r\in\{3,...,k\}$ ������� ������� ����� ������� $x_r$, ���
��� ����� ��������� ������� ��� � �������� $x_{r-1},$ ��� � �
�������� $x_{r-2}$. � ����� $H$ �������, ����������� � �
$y_{r-1}$, � � $y_{r-2}$, �� ��������. ������� ������� �������.

������� ������, ��� ��������� ���� $G(N,p)$ � ������������,
����������� � ���������� �������������� �����, �������� ����������
$L_1$ � $L_2$. ���� $X$ ������ ����������������, � ��� ���������
����� $\rho$. ������� � ���� ������� \ref{erdos} ����������� ����,
��� ��������� ���� �������� ��������� $L_1$ ��������� �
$1-e^{-1/a(X)}$. ��� ���������� �������������� �������� ����������
�������������� ���������� �����������:
$\lim_{N\rightarrow\infty}{\sf P}_{N,p}(\overline{L}_2)\in(0,1)$.
����� ��������, ��� �������� $\overline{L}_2$ ��������� ����� �
������ �����, ����� ���� �������� �������, ��������� �� ����������
��������� ���������, ������ ��������� ������ �� ����� ��������� ��
������, ��� $\rho$. � ������������ � �������� � ����������
������������� ����� ��������� � ��������� ����� (��.
\cite{Janson}, Chapter III, Remark 3.20) � ������������,
����������� � ���������� ����� �� ��������� $(0,1)$, ���������
���� $G(N,p)$ �������� ���� �� ���� ������� �� �����������
���������. ��� ����� ������� ��������.






\begin{thebibliography}{99}


\bibitem{Zhuk2} M.E. Zhukovskii, \emph{Zero-one $k$-law},
Discrete Mathematics, 2012, 312: 1670--1688.


\bibitem{Erdos} P. Erd\H{o}s, A. R\'{e}nyi, \emph{On the evolution
of random graphs}, Magyar Tud. Akad. Mat. Kutat\'{o} Int.
K\"{o}zl. \textbf{5}: 17--61, 1960.


\bibitem{Janson} S. Janson, T. \L uczak, A. Rucinski, \emph{Random Graphs},
New York, Wiley, 2000.

\bibitem{Bol} B. Bollob\'{a}s, \emph{Random Graphs}, 2nd Edition, Cambridge University Press, 2001.

\bibitem{Kolchin} �.�. ������, \emph{��������� �����}, 2-� �������, ���������, ������, 2004.

\bibitem{Alon} �. ����, ��. �������, \emph{������������� �����}, ������,
�����. ����������� ������, 2007.

\bibitem{Veresh} �.�. ���������, �. ����, \emph{����� � ����������}, ������, �����, 2000.

\bibitem{Usp} �.�. ���������, �.�. ���������, �.�. ������, \emph{������� ���� ��������������
������}, ���, ���������, ������, 1997.


\bibitem{Kogan} �.�. ��������, �.�. �����, �.�. ����������, �.�.
�������, \emph{����� � ���� ������������ ������ ������ ����������
����������}, ����������� 2, 1969, �. 17--26.

\bibitem{Fagin} R. Fagin, \emph{Probabilities in finite models}, J. Symbolic
Logic \textbf{41}: 50--58, 1976.

\bibitem{Shelah} S. Shelah, J.H. Spencer, \emph{Zero-one laws
for sparse random graphs}, J. Amer. Math. Soc. \textbf{1}:
97--115, 1988.

\bibitem{Strange} J. H. Spencer, \emph{The Strange Logic of Random Graphs}, Number 22 in
Algorithms and Combinatorics, Springer-Verlag, Berlin, 2001.


\bibitem{McArtur} M. McArthur, \emph{The asymptotic behavior of
$L^k_{\infty,\omega}$ on sparse random graphs}, Logic and Random
Structures, \textbf{33}: 53-63, 1997.


\bibitem{zhuk_dan} �.�. ���������, \emph{������ ���� ��� ������� ��� ������ �������
������� � ������������ ���������� ��������}, ������� �������� ����
\textbf{436(1)}: 14--18, 2011.


\bibitem{zhuk_MJC} M.E. Zhukovskii, \emph{On the convergence of probabilities of the random
graphs' properties expressed by first-order formulae with a
bounded quantifier depth}, Moscow Journal of Combinatorics, under
review, 2012.


\bibitem{Spencer} J.H. Spencer, \emph{Counting extensions},
J. Comb. Th., Ser. A \textbf{55}: 247--255, 1990.

\bibitem{zhuk_extensions} �.�. ���������, \emph{������ ���������� ������������ ����������
� ��������� �����}, ���������� ����������, 2012, 24(1): 79--107.



\bibitem{Ehren} A. Ehrenfeucht, \emph{An application of
games to the completness problem for formalized theories},
Warszawa, Fund. Math. \textbf{49}: 121--149, 1960.

\bibitem{Zhuk1} �.�. ���������, \emph{����������� ����� ���� ��� ������� ��� ��������� ������������� ������},
������ ������������ � �� ���������� \textbf{55}: 344--350, 2010.










\end{thebibliography}


\end{document}

1304.0900.extracted_bib
\begin{thebibliography}{99}


\bibitem{Zhuk2} M.E. Zhukovskii, \emph{Zero-one $k$-law},
Discrete Mathematics, 2012, 312: 1670--1688.


\bibitem{Erdos} P. Erd\H{o}s, A. R\'{e}nyi, \emph{On the evolution
of random graphs}, Magyar Tud. Akad. Mat. Kutat\'{o} Int.
K\"{o}zl. \textbf{5}: 17--61, 1960.


\bibitem{Janson} S. Janson, T. \L uczak, A. Rucinski, \emph{Random Graphs},
New York, Wiley, 2000.

\bibitem{Bol} B. Bollob\'{a}s, \emph{Random Graphs}, 2nd Edition, Cambridge University Press, 2001.

\bibitem{Kolchin} �.�. ������, \emph{��������� �����}, 2-� �������, ���������, ������, 2004.

\bibitem{Alon} �. ����, ��. �������, \emph{������������� �����}, ������,
�����. ����������� ������, 2007.

\bibitem{Veresh} �.�. ���������, �. ����, \emph{����� � ����������}, ������, �����, 2000.

\bibitem{Usp} �.�. ���������, �.�. ���������, �.�. ������, \emph{������� ���� ��������������
������}, ���, ���������, ������, 1997.


\bibitem{Kogan} �.�. ��������, �.�. �����, �.�. ����������, �.�.
�������, \emph{����� � ���� ������������ ������ ������ ����������
����������}, ����������� 2, 1969, �. 17--26.

\bibitem{Fagin} R. Fagin, \emph{Probabilities in finite models}, J. Symbolic
Logic \textbf{41}: 50--58, 1976.

\bibitem{Shelah} S. Shelah, J.H. Spencer, \emph{Zero-one laws
for sparse random graphs}, J. Amer. Math. Soc. \textbf{1}:
97--115, 1988.

\bibitem{Strange} J. H. Spencer, \emph{The Strange Logic of Random Graphs}, Number 22 in
Algorithms and Combinatorics, Springer-Verlag, Berlin, 2001.


\bibitem{McArtur} M. McArthur, \emph{The asymptotic behavior of
$L^k_{\infty,\omega}$ on sparse random graphs}, Logic and Random
Structures, \textbf{33}: 53-63, 1997.


\bibitem{zhuk_dan} �.�. ���������, \emph{������ ���� ��� ������� ��� ������ �������
������� � ������������ ���������� ��������}, ������� �������� ����
\textbf{436(1)}: 14--18, 2011.


\bibitem{zhuk_MJC} M.E. Zhukovskii, \emph{On the convergence of probabilities of the random
graphs' properties expressed by first-order formulae with a
bounded quantifier depth}, Moscow Journal of Combinatorics, under
review, 2012.


\bibitem{Spencer} J.H. Spencer, \emph{Counting extensions},
J. Comb. Th., Ser. A \textbf{55}: 247--255, 1990.

\bibitem{zhuk_extensions} �.�. ���������, \emph{������ ���������� ������������ ����������
� ��������� �����}, ���������� ����������, 2012, 24(1): 79--107.



\bibitem{Ehren} A. Ehrenfeucht, \emph{An application of
games to the completness problem for formalized theories},
Warszawa, Fund. Math. \textbf{49}: 121--149, 1960.

\bibitem{Zhuk1} �.�. ���������, \emph{����������� ����� ���� ��� ������� ��� ��������� ������������� ������},
������ ������������ � �� ���������� \textbf{55}: 344--350, 2010.










\end{thebibliography}