% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P23}{20(2)}{2013}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\newcommand\LL{{\mathcal{L}}}
\newcommand\veps{\varepsilon}
\newcommand\E{\mathbb E}
\newcommand\Prob{\mathbb P}
\newcommand\Var{{\mathbb V}{\rm ar}}
\newcommand\Cov{{\mathbb C}{\rm ov}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins

% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Random lifts of graphs\\ are highly connected}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Marcin Witkowski\\
\small Faculty of Mathmematics and Computer Science\\[-0.8ex]
\small Adam Mickiewicz University\\[-0.8ex] 
\small ul. Umultowska 87, 61-614 Poznan, Poland\\
\small\tt mw@amu.edu.pl\\
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Oct 8, 2012}{Apr 22, 2013}{Apr 30, 2013}\\
\small Mathematics Subject Classifications: 05C80, 05C40}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
In this note we study asymptotic properties of random lifts of graphs introduced by Amit and Linial as a new model of random graphs. Given a base graph $G$ and an integer $n$, a random lift of $G$ is obtained by replacing each vertex of $G$ by a set of $n$ vertices, and joining these sets by random matchings whenever the corresponding vertices
of $G$ are adjacent. In this paper we study connectivity properties of random lifts. We show that the size of the largest topological clique in typical random lifts, with $G$ fixed and $n$ $\rightarrow$ $\infty$, is equal to the maximum degree of the core of $G$ plus one. 
A similar idea can be used to prove that for any graph $G$ with $\delta(G)\geq2k-1$ almost every random lift of $G$ is $k$-linked.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} random graphs; random lifts; connectivity 
\end{abstract}

\section{Introduction}

The concept of covering maps of graphs is essentially a restriction to the case of graphs the general topological notion of covering maps. Let $G$, $\tilde{G}$ be finite graphs. A map $f$ from $V(\tilde{G})$ to $V(G)$ is called a \textit{covering map} if for every vertex $x \in \tilde{G}$, the mapping $f$ maps the neighbors of $x$ one-to-one onto the neighbors of $f(x)$. Note that every covering map is also a homomorphism of graphs, but the converse is not true.

Whenever there is a covering map $f$ from $\tilde{G}$ to $G$, we say that $\tilde{G}$ is a \textit{lift} of $G$ and
$G$ is the \textit{base graph}.
The set of vertices which are mapped in $f$ to a given vertex $v \in G$ is called the \textit{fiber} related to $v$ and denoted by $\tilde{G}_v$.
One can view $\tilde{G}_v$ as a vertical stack of vertices above $v$. 
It is easy to see that fibers of all vertices in a connected graph $G$ have the same cardinality. This common value is denoted by $n$ and called the \textit{degree of covering}. A lift for which all fibers have size $n$ is called a $n$-lift. The edge set of an $n$-lift $\tilde{G}$ consists, for each edge $(u,v) \in E(G)$, of  perfect matchings between fibers $\tilde{G}_u$ and $\tilde{G}_v$. The set of all $n$-lifts of a fixed graph $G$ is denoted $L_n(G)$.

A simple model for a random lift $R(n,G)$ of $G$ was proposed by Amit and Linial \cite{pierwsza}. The idea is to choose
uniformly at random some graph from the set $L_n(G)$. Equivalently, $R(n,G)$ can be obtained in the following way: for each edge $\{u,v\}$ of $G$ we join sets $\tilde{G}_u$ and $\tilde{G}_v$ by a random matching, i.e., a matching chosen uniformly at random from all possible matchings between $\tilde{G}_u$ and~$\tilde{G}_v$. Yet another way to construct $R(n,G)$ is, for any two adjacent vertices $u$ and $v$, choose uniformly at random one of the $n!$ permutations  $\sigma_{uv}:[n]\to [n]$ and connect $u_i$ with $v_{\sigma_{uv}(i)}$.

As typical in random graph theory we are interested in properties of lifts of graphs when $n$ is large. In particular, we say that some property of a random lift of graph $G$ holds for \textit{almost every} lift of $G$ if a graph $H$ drawn at random from $L_n(G)$ has this property with probability $1 - \epsilon_n$, where $\epsilon_n \rightarrow 0$ as $n \rightarrow \infty$.
%We use a short term random lift of $G$ for
%a random $n$-lift of $G$ as $n \rightarrow \infty$.
We say that a sequence of random events $X_n$ occurs with high probability (w.h.p.) if $\lim_{n \rightarrow \infty} \Pr[ X_n]=1$.

There are only a handful of papers concerning this model of random graphs. Amit and Linial \cite{pierwsza} proved that if $G$ is a simple connected graph with minimum degree $\delta \geq 3$, then almost every random lift of $G$ is $\delta$-connected. They continued this study in \cite{druga} proving that random lifts have good expanding properties. The third
article in this series of papers on random lifts, written jointly with Matousek \cite{trzecia}, deals with the independence and chromatic numbers of random lifts.

We say that a theorem is a \textit{zero-one law} if it specifies that each event of a certain type either w.h.p. happens or w.h.p. does not happen.
That is, the probability that such an event occurs tends either  to zero, or to one. Another part of research in the area of random lifts is connected with such theorems. Linial and Rozenman \cite{czwarta} showed that for any graph $G$ its random lift either w.h.p. has a perfect matching or w.h.p. does not have such matching. A similar question has been raised for
hamiltonicity, but only partial results have been obtained (see \cite{frieze} and \cite{fr2}).

\textit{Subdividing} an edge $uv$ in a graph means replacing the edge $uv$ by a path $uwv$ containing  a new vertex $w$. Graph $H$ is  a \textit{topological clique} if it can be obtained from a complete graph by series of edge subdivisions. The vertices of the original complete graph are called \textit{branch vertices}. 

Drier and Linial \cite{drier} proved the following theorems concerning topological cliques.

\begin{theorem} %[\cite{drier}]
For almost every $H \in L_n(K_\ell)$, a maximum topological clique in $H$ is smaller than $O(\sqrt{n\ell})$.
\end{theorem}

\begin{theorem} %[\cite{drier}]
If $\ell = \Omega(n) $, then for almost every $H \in L_n(K_\ell)$, the size of a maximum topological clique in $H$ is greater than
$\Omega(n)$.
\end{theorem}

In those cases the degree of covering depends on the size of the complete graph.  Our main result, Theorem~\ref{thm:main},
deals with the case when the size of the base graph is fixed
and does not depend on $n$. In order to state it we need one more notion.
For a graph $G = (V,E)$, the \textit{core} of $G$, denoted as $core(G)$, is the maximal subgraph of $G$ with minimum degree at least two. It is easy to see that the core of the lift of a graph $G$
is the same as the lift of the core of $G$. Thus, the maximum size of the
topological clique contained in the lift of the graph is bounded
from above by $\Delta(core(G))+1$, where
$\Delta({core}(G))$ stands for the maximum degree
in the core of $G$.
We  show  that in a random lift of  a given graph $G$
with high probability we can find a topological clique of the maximum possible size.

\begin{theorem}
For a given graph $G$ almost every  $H\in L_n(G)$ contains a topological clique of size $\Delta(core(G))+1$.
\label{thm:main}
\end{theorem}

Let us recall that a graph with at least $2k$ vertices is said to be \textit{$k$-linked} if for every $2k$ distinct vertices $s_1,s_2,\dots,s_k,t_1,t_2,\dots,t_k$ it contains $k$ vertex-disjoint paths $P_1,P_2,\dots,P_k$ such that $P_i$ connects $s_i$ to $t_i$, $1\leq i \leq k$. Obviously, from  Menger's theorem it follows that each $k$-linked graph is $k$-connected. The converse is far from being true. Using basically the same argument as in the proof of Theorem \ref{thm:main} one can prove the following result.

\begin{theorem}\label{thm:conn}
For a given graph $G$, with $\delta(G)\geq2k-1$ almost every  $H\in L_n(G)$ is $k$-linked.
\end{theorem}

\section{Proof of the Main Result}

The idea of the proof is the following. Let $G$ be a base graph and let $H$ denote the core of $G$. We want to find a set of vertices which form a topological clique of size $\Delta_H+1$ in $\tilde{H}$. Therefore the vertices of such a clique must have degree at least $\Delta_H$ in $\tilde{H}$. Let $v$ be a vertex of the maximum degree $\Delta_H$ in $H$. Since vertex $v$ could be the only one having the required degree in $H$ we focus on vertices from the fiber $\tilde{H}_v$. We choose first $\Delta_H+1$ vertices $U=\{u_1,u_2,\dots, u_{\Delta_H+1}\}\subset \tilde{H}_v$ of $\tilde{H}_v$. Our aim will be to generate large sets of vertices which can be reached from each $u_i$. We will be using a family $\mathcal{W}$ of different closed walks in $H$ which contain vertex $v$ to perform a bfs-type procedure. Starting from one vertex of the fiber $\tilde{H}_v$ we follow each cover of walk from $\mathcal{W}$ to get to more vertices from this fiber. We continue this procedure until our set is large enough. Let $R_\ell(u_i)$ denote the set of vertices of $\tilde{H}_v$ which can be reached from vertex $u_i$ in $\ell$ steps of such a procedure. 

Note, however, that in the topological clique the paths which connect branch vertices should be vertex disjoint. Moreover we want the $R_\ell(u_i)$'s to be generated ``nearly'' independently of each other. These are the main technical obstacles we should deal with in our argument. Thus, roughly speaking, in the process of generating the set $R_\ell(u_j)$, we have to omit the vertices which had been added to the sets $R_\ell(u_i)$ generated in earlier stages of the algorithm. Hence, whenever we reach an ``already visited'' vertex we do not continue expansion from it. Clearly, the modified set $\hat R_\ell(u_j)$ generated in this way will be slightly smaller than $R_\ell(u_j)$, but we argue that w.h.p. this difference is not substantial and does not much affect the probability that the random sets $\hat R_\ell(u_j)$ and $\hat R_\ell(u_i)$ have a non-empty intersection. Using properties of random lifts we will show that for $\rho \leq \log \log^4 n$, when $|R_\rho(u_i)| = O(\log^4 n)$ it is easy to get all $R_\rho(u_i)$'s disjoint. In the next step we expand those sets to sizes of $\sqrt{n}\log n$ using walks from the family $\mathcal{W}$. We show that w.h.p. we can avoid $R_\ell(u_l)$'s with which we do not want to have an intersection, simultaneously obtaining connection between $\hat R_\ell(u_i)$ and $\hat R_\ell(u_j)$. Once we find a common vertex $w$ for these two sets, we establish a path connecting $u_j$ and $u_i$ in $\tilde{H}$. We repeat the argument above for each pair of vertices.

When we connect branch vertices by paths it is important that these paths do not cross at any place. 
Thus, although two cycles $C_i$ and $C_j$ from  $\mathcal{W}$  can intersect at vertices other than $v$, we want to avoid such intersections likewise intersections on $R_\ell(u_j)$. 
Note that for each common point, every cover $\tilde{C}^p_i$ of $C_i$ intersect with at most one of  $\tilde{C}^k_j$. Assume that there is an intersection between some walks $C_i$ and $C_j$ apart from fiber $\tilde{H}_v$. Then if we use a cycle $C_i$ to expand the $R_\ell(u_j)$ we do not want to use a cycle $C_j$ anytime in the future. 
Thus, in this case, in order to prevent $C_j$ from being a part of $\hat R_\ell(u_j)$, for any prospective vertex, we add the ends of the second walk to the set of already visited vertices of $\tilde{H}_v$. Let $c$ denote the total number of intersections between walks $C_1,C_2,\dots,C_{\Delta_H}$ apart from at vertex $v$. Note that $c$ is bounded from above by the square of the number of vertices of $G$. Thus, let us recall, is a constant which does not depend on $n$.

We start our argument with a fact about some asymptotic properties of random lifts.  

\begin{lemma}\label{odl}
Let $G$ be a simple graph with $\delta(G)\geq 2$, v be a vertex of $H$ such that $deg(v)=\Delta(H)$. Then, for almost every $H\in L_n(G)$ the $\Delta(H)+1$ first lexicographically first vertices of the fiber $\tilde{H}_v$ lie at distance at least $11\log\log n$ from each other. Moreover almost surely all those vertices are at the distance at least $6\log\log n$ from any cycle shorter than $12\log\log n$. 
\end{lemma}

\begin{proof}
Let $r$ denote an order of a graph $G$. Let $S$ be the set of 
the  $\Delta(G)+1$ lexicographically first vertices of $\tilde{H}_v$
and let  $Z_{a,b}$ count the number of paths shorter than $11\log\log n$ 
connecting the vertices $a,b \in S$. Then we get
\begin{align*}
\E Z_{a,b} & \leq \sum_{m=1}^{11\log\log n} \binom{rn}{m} (m)! \Big(\frac{1}{n-m}\Big)^{m+1}\\
&\le \sum_{m=1}^{11\log\log n} \frac{(rn)^{m}}{m!} \frac{ m! }{(n-m)^{m+1}}\\
&\le \sum_{m=1}^{11\log\log n} \frac{(rn)^{m} }{(n-m)^{m+1}} \stackrel{(1)}{\leq} \sum_{m=1}^{11\log\log n} \frac{(10r)^{m}}{n - m} \\
&\leq \frac{ (10r)^{11\log \log n}11\log \log n}{n - 11\log\log n}\leq  \frac{\exp((\log\log n)^2)}{n - 11\log\log n}.
\end{align*}

(1) For sufficiently large $n$.

Let $Z$ counts the expected number of paths shorter than $11\log\log n$ connecting any pair of vertices from $S$. Then using union bound we get
\begin{align*}
\E Z = \binom{\Delta(G)+1}{2} \E Z_{a,b} & 
\stackrel{n \rightarrow \infty}{\leq}  \binom{\Delta(G)+1}{2} \frac{\exp((\log\log n)^2}{n - 11\log\log n} \stackrel{n \rightarrow \infty}{\longrightarrow} 0.
\end{align*}

\noindent Thus, from Markov's inequality,
$$\Prob(Z>0)\le \E Z=o(1)\,,$$
and the first assertion follows.

Now we would like to count the expected number of cycles shorter than $12\log\log n$ which are closer than $6\log\log n$ to some vertex in $S$. Let $X$ count the number of paths starting at a vertex in $S$ which are shorter than $25\log\log n$ and for which the last vertex has an edge to any vertex from this path. Then
\begin{align*}
\E X & \leq \sum_{m=1}^{25\log\log n} (\Delta(H)+1) \binom{rn}{m} (m)! m \Big(\frac{1}{n-m}\Big)^{m+1}\\
&\le \sum_{m=1}^{25\log\log n} (\Delta(H)+1) \frac{(rn)^{m} m }{(n-m)^{m+1}}  \stackrel{(1)}{\leq} \sum_{m=1}^{25\log\log n} (\Delta(H)+1)\frac{(10r)^m m}{n-m} \\
&\stackrel{(1)}{\leq} (\Delta(H)+1) \frac{ (10r)^{25\log \log n} 25(\log\log n)}{n - 25\log\log n} \stackrel{n \rightarrow \infty}{\longrightarrow} 0.
\end{align*}

(1) For sufficiently large $n$.

\noindent Again, from Markov's inequality,
$$\Prob(X>0)\le \E X=o(1)\,,$$
and the second part of the assertion follows.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:main}]
Let $G$ be a base graph and let $H$ denote the core of $G$.
By $\Delta_H$ we denote the maximum degree of vertices in $H$
and let $v\in V(H)$ be a vertex with degree equal to $\Delta_H$. We show that with probability tending to $1$ the $\Delta_H+1$ 
lexicographically first vertices of the fiber $\tilde{H}_v$ 
are branch vertices of some  topological clique.

If $\Delta_H = 2$, then $H$ is collection of cycles. The lift of a cycle is a sum of cycles, so the lift of $G$ contains a topological clique of size $3$. Therefore we may assume $\Delta_H>2$ and, since we are considering the core of $G$, $\delta_H \geq 2$. For the remainder of this section, we condition on the event that a graph  $\tilde{H}$ satisfy conditions of Lemma~\ref{odl} (i.e. The $\Delta(H) + 1$ lexicographically first vertices of the fiber $H_v$ are at distance $11\log\log n$ from each other and at distance at least $6\log \log n$ from all short cycles in $H$).

In our argument we use a family $\mathcal{W}=\{C_1,C_2,\dots,C_{\Delta_H}\} $ of directed closed walks
which start and end in $v$ and are such that each edge incident with $v$ is
traversed from $v$ to its neighbor by precisely one walk
from $\mathcal{W}$ (for which it is, of course, the starting edge). Each walk from $\mathcal{W}$ forms either a cycle, or a cycle connected by a path to $v$, so for every lift $\tilde{C}_i$ the probability that it starts and ends at the same vertex equals $\frac{1}{n}$. It is easy to see that, because the minimum degree of $H$ is at least two, such a family exists.

Note that for every walk from $C_i\in \mathcal{W}$ its lift $\tilde{C}_i$ is a set of disjoint walks which start and end at vertices of the fiber  $\tilde{H}_v$. In our argument, for a given $u\in \tilde{H}_v$, we recursively build sets of vertices of the graph $\tilde{H}$ which can be reached from $u$; we do it in the following way. Let $T_0(u)=R_0(u)=u$.
%Choose $i\in [\Delta_H]=\{1,2,\dots,\Delta_H\}$.
By $T_1(u)$ we denote the set of vertices of the walks in $\tilde{H}$ which start at $u$ and are lifts of paths from the set $\mathcal{W}$ - namely $C_i$, for $i \in \{1,2,\dots,\Delta_H\}$. Let $R_1(u) = T_1(u) \cap \tilde{H}_v$ denote the set of all vertices of the fiber above $v$ in which those walks end. Next, $T_2(u)$ would be the set which consists of $T_1(u)$ and $T_1(u')$, for all $u' \in R_1(u) \backslash u $. Thus, let us recall, we start with a vertex $u$, use the lifts of each $C_i$, for $i \in \{1,2,\dots,\Delta_H\}$, to travel from $u$ to the fiber $\tilde{H}_v$ and then use all the walks from $\mathcal{W}$ again to reach next vertices. Notice that this time there is no point in using edges by which we arrived to the points of $R_1(u)$, because they take us back to $u$ using vertices which were already visited. In general we set $R_\ell(u)=T_\ell(u)\cap \tilde{H}_v$ and call it the \textit{$\ell$-vicinity }of $u$. The set of vertices $T_\ell(u)$ is defined recursively, we take all vertices of $T_{\ell-1}(u)$ and add to them vertices which cover walks from $\mathcal{W}$ and start at vertices from $R_{\ell-1}(u) \backslash R_{\ell-2}(u)$. Again, whenever we branch from any one of them one direction points us to a previously used path, so it does not add any new vertex to $T_\ell(u)$.

Note that the set $R_\ell(u)$ has a structure of a tree $T$ rooted at $u$, which has all leaves placed on the
fiber $\tilde{H}_v$; we can think of ordering the vertices of this tree from the root to the leaves. We a call vertex a \textit{successor} if it has a directed edge pointing towards it, i.e. each successor of $w$ follows $w$ in the lift of one of the walks from $\mathcal{W}$. Note that because $\delta(T)\geq 3$ the sizes of $R_\ell(u)$ are expected to grow exponentially with $\ell$, at least for small~$\ell$. 

Let us consider vertices from sets $R_\ell(u')$ and their successors on the tree rooted at $u'$. Notice that for a given closed walk $C_i \in \mathcal{W}$ the mapping assigning in $\tilde{G}$ to each vertex of $\tilde{G}_v$ its closest successor on $\tilde{G}_v$ is a random matching, which can be viewed as a random permutation.

%Whenever we have in $\mathcal{W}$ two closed walks which 
%are reverse of each other the corresponding permutations are inverse. In the other case the assumption about edge-distinctness of %closed walks let us treat any two permutations related to adequate walks as independent. We will not draw whole permutations at once %but generate them in steps by choosing successively successors for selected vertex.

Now let us restate the above ideas in a rigorous way. By $N(u_i)$ we will denote the set of $\log^5 n$ vertices which are at shortest distance to $u_i$ in $\tilde{H}$ and called it a neighborhood of $u_i$. By Lemma~\ref{odl} the first $\Delta_H+1$ vertices of the fiber above $v$, namely $U=\{u_1,u_2,\dots, u_{\Delta_H+1}\}\subseteq \tilde{H}_v $ are almost surely at distance at least $11\log\log n$ from each other. Moreover, since they are at distance at least $6\log \log n$ from any 
cycle of length at most $12\log\log n$, for all $i$ we can choose neighborhood $N(u_i)$
which form a tree and is disjoint from other neighborhoods. Notice that in these neighborhoods the distance between two vertices from the fiber $\tilde{H}_v$ is bounded by the size of $G$, which is constant and does not grow with $n$.

 
 For all trees $N(u_i)$ we will restrict our attention only to vertices from $\tilde{H}_v$. For each $i$ we define a new tree $M_{u_i}$, the set of vertices for those trees is the set $\tilde{H}_v$ and two of them are connected by an edge if they are closest neighbors in the neighborhood $N(u_i)$. Notice that $M_{u_i}$ is a topological minor of $N(u_i)$ and the number of vertices of each $M_{u_i}$ is of order $\Theta(\log^4 n)$. Next we will perform further subdivision on those trees. For each $u_i$, we choose a subset of vertices $U_i = \{u_i^1,\dots,u_i^{\Delta_H}\}\in M_{u_i}$ and divide $M_{u_i}$ into disjoint connected subtrees $M_{u^1_i} \cup \dots \cup  M_{u_i^{\Delta_H}}$ rooted at $u_i^j$'s of sizes $\Theta(\log^4n)$. We will connect those vertices by paths such that the $u_i$'s would create a topological clique. Therefore we will take pairs of vertices $\{u_i^j,u_j^i\}$ for $i\neq j$ and $\{u_i^j,u_{\Delta_H+1}^i\}$ for $i=j$ and try to build a set of disjoint paths between them.

  In each step of the expansion we would have to avoid vertices visited earlier. The first reason is that we do not want to intersect some path chosen earlier and the second is that we want neighborhoods to be generated nearly independently of previously generated ones. Let us denote by $S$ the set of vertices which we have already visited, meaning vertices for which we have already generated their vicinities (we generated at least one edge coming out from it). After choosing the $u_i$'s and generating the $M_{u_i}$'s our set $S$ equals $\{u_1,u_2,\dots, u_{\Delta_H+1}\}$ together with vertices of $M_{u_i}$'s and endings of cycles which cross those neighborhoods. Let $S_v= S \cap \tilde{H}_v$ and $S_{C_k}= S_v \cup \{\tilde{C}_k : |\tilde{C}_k \cap S_v| \geq 1\}$ be the set of unvisited ends of the cycles from the set of all covers of cycle $C_k$. 

Consider the first pair of vertices $\{u_1^2,u_2^1\}$. Our goal is to further expand the neighborhood of $u_1^2$ chosen earlier. We take all leaves of $M_{u^2_1}$ and expand their vicinities in the following manner. Let $w \in M_{u^2_1}$ be currently processed vertex. We generate consecutively $R_1(w),R_2(w),\dots,R_j(w)$. This is equivalent to choosing, for each of the vertices $w' \in R_{j-1}(w) \backslash (R_{j-2}(w) \cup S_v)$,  and for all walks $C_k, k\in \{1,2,\dots,\Delta_H\}$, an element from corresponding set $\tilde{H}_v - S_{C_k}$  at random with uniform distribution. The selected vertex $w'$ is added to the vicinity and to the sets $S$ and $S_{C_k}$. Furthermore if a walk $C_k$ crosses any other walk $C_q$ the we add end vertices from the walk $\tilde{C_q}$ to the sets $S$ and $S_{C_q}$. We continue expanding until for some $\ell$ we obtain $|R_\ell(w)| = \Theta ({\sqrt n}/{\log^3 n})$. 

The probability of the event $\mathcal{C}$, that at some point of this process we choose a vertex which has already been visited, is bounded by 

$$ \Pr(\mathcal{C}) \leq c\frac{\sqrt{n}}{\log^3 n} \cdot \frac{|S|}{n - |S|}  \leq c\frac{\sqrt{n}}{\log^3 n} \cdot \frac{\sqrt{n}}{n - \sqrt{n}} \leq  \frac{c}{\log^2 n} \stackrel{n \rightarrow \infty}{\longrightarrow} 0.$$

Thus, for a vertex $u_1^2$, there are $c\log^4 n$ vertices whose vicinities we want to expand and the probability of failure in each equals $\frac{c}{\log^2 n}$. The probability of the event $\mathcal{D}$, that we fail to expand one half of the vertices from $M_{u^2_1}$, is bounded by 
\begin{equation}\label{eq1}
\Pr(\mathcal{D}) \leq 2^{c\log^4 n}\left(\frac{c}{\log^2 n}\right)^{c\log^4 n} =
o(n^{-3\Delta_H}).
\end{equation}

This means that w.h.p. we expand the vicinities of vertices of $M_{u^2_1}$ to the size of $\sqrt{n} / \log^3 n$, avoiding previously visited vertices. In total we expand the vicinity of $u^2_1$ to size $\sqrt{n}\log n$. The same analysis can be done with respect to the vertex $u_2^1$. Again, during the expansion of the vicinity, we have to exclude all vertices from $S$ (which now also contains vertices used in previous step, so $|S| = \Theta(\sqrt{n} \log n$)). Thus, the probability of the event $\mathcal{C'}$, that at some point of this process we choose an already visited vertex, is bounded by 

$$ \Pr(\mathcal{C'}) \leq c \frac{\sqrt{n}}{\log^3 n} \cdot  \frac{|S|}{n - |S|} \leq c \frac{\sqrt{n}}{\log^3 n} \cdot  \frac{\sqrt{n} \log n}{n - \sqrt{n} \log n} = \frac{c}{\log^2 n} \stackrel{n \rightarrow \infty}{\longrightarrow} 0.$$

As before, for $u_2^1$, there are at least $c\log^4 n$ vertices whose vicinities we want to expand. The probability of the event $\mathcal{D'}$, that we fail to expand one half of these vertices, is bounded by 
\begin{equation}\label{eq2}
\Pr(\mathcal{D'}) \leq 2^{c\log^4 n}\left(\frac{c}{\log^2 n}\right)^{c\log^4 n} = o(n^{-3\Delta_H}).
\end{equation}

Denote the sets obtained for both of the vertices by $R(u^2_1)$ and $R(u^2_1)$. Both of these sets have size $\Theta (\sqrt{n}\log n)$. In order to connect vertices $u_1^2$ and $u_2^1$ by a path we need to find some vertex $w \in R(u^2_1) \cap R(u^2_1)$, then the path $u_1^2-\dots-w-\dots-u_2^1$ would connect $u_1$ with $u_2$. The probability that such a vertex does not exist can be bounded by the probability that we can choose a random set $R(u^1_2)$ of size $\sqrt{n}\log n$ which avoids $R(u^2_1)$. Thus
\begin{align}
\frac{\binom{n - |S| - \sqrt{n}\log n}{\sqrt{n}\log n}}{\binom{n - |S|}{\sqrt{n}\log n}} &\leq \frac{(n-|S|-\sqrt{n}\log n)!}{(\sqrt{n}\log n)!(n-|S|-2\sqrt{n}\log n)!} \cdot  \frac{(\sqrt{n}\log n)!(n-|S|-\sqrt{n}\log n)!}{(n-|S|)!} \nonumber \\
&= \frac{(n-|S| - 2\sqrt{n}\log n)\cdot\dots\cdot (n-|S| -\sqrt{n}\log n)}{(n-|S| - \sqrt{n}\log n)(n-|S| -\sqrt{n}\log n+1)\cdot\dots\cdot (n - |S|)} \nonumber \\
&\leq \left(1 - \frac{\log n}{\sqrt{n} - O(\log n)}\right)^{\sqrt{n}\log n} \stackrel{}{=} o(n^{-3\Delta(H)}) \longrightarrow 0.
\label{eq:5}
\end{align}

The argument for other pairs of vertices is similar to the one above
but after each phase we must take into account the fact
that the size of the set $S$ increases. Therefore the probability of success in connecting the last pair is smaller than the probability of success in connecting each of the previous pairs. Since there are only $(\Delta_H+1)^2$ pairs, if we show that the probability of failure in connecting the last pair tends to zero as $n$ goes to infinity, then we prove that w.h.p. we get success for all the events.

When we are connecting the last pair the size of $S$ is less than $m=(\Delta_H+1)^2\sqrt{n}\log{n}+\Delta_H+1$. Now the probability of choosing some previously visited vertex while expanding vicinities of both vertices to the size of ${\sqrt{n}}/{\log^3 n}$, is bounded by
$$\frac{c\sqrt{n}}{\log^3 n} \cdot \frac{m}{n - m} \stackrel{(1)}{\leq} \frac{c(\Delta_H+1)^2}{\log^2 n} \stackrel{n \rightarrow \infty}{\longrightarrow} 0.$$
 

(1) For sufficiently large $n$. 

 Hence, $\Pr(\mathcal{D})=o(n^{-3\Delta_H})$ and we would be able to expand vicinities of more than half of the vertices from the neighborhood of the considered pair to size $\frac{\sqrt{n}}{\log^3 n}$. This implies that in $O(\log n)$ stages we expand the vicinities of vertices from our pair to the sizes of $\sqrt{n}{\log n}$. Finally,
 as in (\ref{eq1}), the probability that we do not find a vertex which connects these two vicinities can be bounded from above by 
\begin{equation}\label{eq4}
\frac{\binom{n-p-\sqrt{n}\log n}{\sqrt{n}\log n}}{\binom{n-p}{\sqrt{n}\log n}} = o(n^{-3\Delta_H}),
\end{equation}
where $p = (\Delta_H+1)^2\sqrt{n}\log{n}+\Delta_H+1. $

 
Thus, we have showed that the probability of failure in connecting any pair is smaller than $o(1)$. Moreover we show that besides choosing the first $\Delta_H+1$ vertices the probability that we fail in any step is $o(n^{-3\Delta_H})$. Since there are a finite number of pairs, the probability that we do not find a topological clique of size $\Delta_H+1$ can be also bounded by $o(1)$.
\end{proof}

\section{Links}

Connectivity properties of random lifts were first considered by Amit and Linial \cite{pierwsza}. They proved the following theorem.

\begin{theorem}[\cite{pierwsza}]
If $G$ is a connected simple graph with minimum degree $\delta\geq 3$, then almost every $H\in L_n(G)$  is $\delta$-connected.
\end{theorem}

 Jung \cite{jung} and, independently, Larman and Mani \cite{mani} proved that every $2k$-connected graph that contains a $K_{3k}$ as a topological minor is $k$-linked. Combining their result with Theorem 3 and Theorem 7 we get the following corollary.

\begin{corollary}
If $G$ is a connected graph with minimum degree $\delta$, then almost every $H\in L_n(G)$  is $\min\{{\Delta(\text{core}(G))}/{3},{\delta}/{2}\}$-linked.
\end{corollary}

A slight modification of the argument used in the proof of Theorem~\ref{thm:main} will give us a sharp result. To be able to apply it we will also need one additional fact concerning lifts of graphs.

\begin{lemma}\label{odl2}
Let $G$ be a simple graph. Then,  for almost every $H\in L_n(G)$ no two cycles of length smaller than $(\log\log n)^2$ in $H$ lie within distance $(\log\log n)^2$ from each other.
\end{lemma}

\begin{proof}
Let $G$ be a graph on $r$ vertices. Let $Z$ count the number of pairs of cycles which are shorter than $(\log\log n)^2$ and are connected by path of length at most $(\log\log n)^2$ in $H\in L_n(G)$. It is easy to see that $Z$ is bounded from above by the number of paths of length smaller than $3(\log\log n)^2$ such that both ends of the path $P$ has neighbors among internal vertices of $P$. Thus
\begin{align*}
\E Z & \leq \sum_{m=1}^{3(\log\log n)^2} \binom{rn}{m} m! m^2 \Big(\frac{1}{n-m}\Big)^{m+1}\\
&\le \sum_{m=1}^{3(\log\log n)^2} \frac{(rn)^{m}}{m!} \frac{ m!m^2 }{(n-m)^{m+1}}\\
&\le \sum_{m=1}^{3(\log\log n)^2} \frac{(rn)^{m}m^2 }{(n-m)^{m+1}} \stackrel{(1)}{\leq} \sum_{m=1}^{3(\log\log n)^2} \frac{(10r)^{m}m^2}{n - m} \\
&\leq \frac{ 9(10r)^{3(\log \log n)^2}(\log\log n)^6}{n - 3(\log\log n)^2}\leq  \frac{exp(\log\log n)^2}{n - 3(\log\log n)^2}.
\end{align*}

(1) For sufficiently large $n$.

\noindent Thus, from Markov's inequality,
$$\Prob(Z>0)\le \E Z=o(1)\,,$$
and the assertion follows.
\end{proof}

\smallskip

\begin{theorem}[\ref{thm:conn}]
For a given $k\ge 2$ and a connected graph $G$ with $\delta(G)\geq2k-1$,
 almost every  $H\in L_n(G)$ is $k$-linked.
\end{theorem}

\begin{proof}
Let us first remark that this result is sharp. Assume that $\delta(G)= 2k-2$. If we choose a set of $2k$ vertices $S=\{s_1,s_2,\dots,s_k,t_1,t_2,\dots,t_k\}$ in such way that the first vertex $s_1$ is connected to $s_2,s_3,\dots,s_k,t_2,t_3,\dots,t_k$, then obviously we can not find a path connecting $s_1$ to $t_1$ which avoids $s_2,s_3,\dots,s_k,t_2,t_3,\dots,t_k$. Thus we assume $\delta(G)\geq2k-1$. 

In the proof we would consider only those lifts of $G$ which fulfill Lemma \ref{odl2}. In particular this means that if we take two vertices $a,b$ which are close (at a distance less than $6\log\log n$ from each other) and look at their neighborhoods $N(a)$ and $N(b)$ of radius $18\log\log n$, then we can always find a pair of vertices $a'\in N(a)$ and $b' \in N(b)$ which are at distance at least $6\log\log n$ from each other. Moreover paths connecting $a$ with $a'$ and $b$ with $b'$ are disjoint. 

By Lemma \ref{odl2} the neighborhoods of the vertices in $S$ of diameter $6\log\log n$ form trees with at most one cycle. Thus we either find for each pair a short path connecting particular $s_i$ with $t_i$ inside $N(s_i)\cup N(t_i)$ or we can find a set of disjoint paths connecting vertices $s_1,s_2,\dots,s_k,t_1,t_2,\dots,t_k$ with vertices $u_1,\dots,u_{2k}$ respectively, satisfying Lemma \ref{odl} (we want $u_i$'s to be on one fiber and far from each other in $H$). Now we proceed in the same way as in our proof of Theorem \ref{thm:main}. We can connect $u_1,\dots,u_{2k}$ in a topological clique avoiding initially chosen paths from each $s_i$ and $t_l$ to corresponding $u_j$'s. The probability that we fail in any step of the proof is less than $o(n^{-3\Delta_H})$ (see the  estimates in (\ref{eq1})-(\ref{eq4})).  Let $g$ denote the number of vertices in $G$. Since there are at most ${ng \choose 2k} \leq ({ng})^{2k}$ possibilities to choose $2k$ vertices out of $ng$ vertices the probability of failure in connecting any of them tends to $0$ as $n \rightarrow \infty$. 
\end{proof}

Let us remark that the above statement does not hold for $k=1$ even if $\delta(G)=2$,
since w.h.p.\ the random lift of a cycle is not connected.

\section{$k$-diameter}

Another parameter which is related to connectivity properties of graphs is the $k$-diameter of a graph. Let $G$ be a $k$-connected graph and $u,v,$ $u \neq v$, be any pair of vertices of $G$. Let $P_k(u,v)$ be a family of $k$ vertex disjoint paths between $u$ and $v$, i.e.

$$ P_k(u,v) = \{p_1,p_2,\dots,p_k\}, \text{ where } |p_1| \leq |p_2| \leq \dots \leq |p_k|  $$


\noindent and $|p_i|$ denotes the number of edges in path $p_i$. The \textit{$k$-distance} $d_k(u,v)$ between vertices $u$ and $v$ is the minimum $|p_k|$ among all $P_k(u,v)$ and the \textit{$k$-diameter} $d_k(G)$ of G is defined as the maximum $k$-distance $d_k(u,v)$ over all pairs $u,v$ of vertices of $G$. The concept of $k$-diameter comes from analysis of the performance of routing algorithms \cite{chung} but has also drawn some attention as a graph parameter \cite{hsu}. In the case of lifts of a given graph $G$, for all vertices $u,v \in V(G)$, by the proof of Theorem \ref{thm:main}, we know that for almost every random lift whenever we choose nearest neighbors of $u$ and $v$ we find a set of disjoint paths connecting vertices from these two sets. It is easy to see that by the same argument as we used in the proof of Theorem \ref{thm:main} it follows that each such a path is of order $O(\log n)$. Hence, we get following result

\begin{corollary}
If $G$ is a connected graph with minimum degree $\delta \geq 3$, then for all $k=1,2,\dots,\delta$, 
the $k$-diameter of almost every $H\in L_n(G)$ is $O(\log n)$.
\end{corollary}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}

I wish to thank Codrut Grosu for
introducing to me the problem of existence of large topological cliques in random lifts and pointing out its relation to the existence of large
links in $L_n(G)$. I also thank Tomasz \L{}uczak for his
help in preparation of this paper and many valuable comments and remarks.

% \bibliographystyle{plain} 
% \bibliography{myBibFile} 
% If you use BibTeX to create a bibliography

%\bibliography{bibliography}
\begin{thebibliography}{11}
%\small

\bibitem{pierwsza} A.~Amit and N.~Linial. \newblock {\em Random graph coverings \texttt{I}: General theory and graph connectivity}.  \newblock{Combinatorica 22:1--18, 2002}.

\bibitem{trzecia} A.~Amit, N.~Linial,  and J.~Matousek. \newblock {\em Random lifts of graphs: Independence and chromatic number}. \newblock {Random Structures and Algorithms 20:1--22, 2002}.

\bibitem{druga} A.~Amit and N.~Linial. \newblock {\em Random lifts of graphs: edge expansion}. \newblock {Combinatorics, Probability \& Computing 15:317-332, 2006}.

\bibitem{frieze} K.~Burgin, P.~Chebolu, C.~Cooper, and A.M.~Frieze. \newblock {\em Hamilton cycles in random lifts of graphs}. \newblock {European Journal of Combinatorics 27:1282-1293, 2006}.

\bibitem{fr2} P.~Chebolu,  and A.~Frieze. \newblock {\em Hamilton cycles in random lifts of directed graphs}. \newblock {SIAM Journal on Discrete Mathematics 22:520-540, 2008}.

\bibitem{chung} F.R.K.~Chung. \newblock {\em Diameter of graphs: Old problems and new results}. \newblock {18th Southeastern Conference on Combinatorics, Graph Theory and Computing, 1987}.

\bibitem{drier} Y. Drier and N. Linial. \newblock {\em Minors in lifts of graphs}. \newblock {Random Structures and Algorithms}. \newblock {29:208-225, 2006}.

\bibitem{hsu} D. Frank Hsu and T. \L uczak. \newblock {\em On the k-diameter of k-regular k-connected graphs}. \newblock {Discrete Mathematics 133:291-296, 1994}.

\bibitem{jung} H. A. Jung. \newblock {\em Eine Verallgemeinerung des n-fachen Zusammenhangs f\"{u}r Graphen}. \newblock {Mathematische Annalen 187:95-103, 1970}.

\bibitem{mani} D. G. Larman and P. Mani. \newblock {\em On the existence of certain configurations within graphs and the 1-skeletons of polytopes}. \newblock {Proceedings of the London Mathematical Society 20:144--160, 1970}.

\bibitem{czwarta} N.~Linial and E.~Rozenman. \newblock {\em Random lifts of graphs: perfect matchings}. \newblock {Combinatorica 25:407-424, 2005}.

\end{thebibliography}

\end{document}