%\newcommand{\dieter}[1]{{\bf [~Dieter:\ } {\em #1}{\bf~]}} %\newcommand{\pawel}[1]{{\bf [~Pawel:\ } {\em #1}{\bf~]}} \documentclass[12pt]{article} \usepackage{e-jc} % 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}}} % 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} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\documentclass[11pt,reqno]{amsart} %%\documentclass[a4wide,10pt]{article} %\usepackage{amsmath} %\usepackage{amssymb} %\usepackage[left=3cm,top=3cm,right=3cm,bottom=3cm]{geometry} %\usepackage{epsfig} %\usepackage{todonotes} % \usepackage{caption} %\usepackage{subcaption} %\newtheorem{theorem}{Theorem}[section] %\newtheorem{lemma}[theorem]{Lemma} %\newtheorem{definition}[theorem]{Definition} %\newtheorem{conjecture}[theorem]{Conjecture} %\newtheorem{proposition}[theorem]{Proposition} %\newtheorem{algorithm}[theorem]{Algorithm} %\newtheorem{corollary}[theorem]{Corollary} %\newtheorem{observation}[theorem]{Observation} %\newtheorem{claim}[theorem]{Claim} %\newtheorem{problem}[theorem]{Open Problem} %\newtheorem{remark}[theorem]{Remark} \newcommand{\noin}{\noindent} \newcommand{\ind}{\indent} \newcommand{\om}{\omega} \newcommand{\I}{\mathcal I} \newcommand{\pp}{\mathcal P} \newcommand{\ppp}{\mathfrak P} \newcommand{\N}{{\mathbb N}} \newcommand{\LL}{\mathbb{L}} \newcommand{\R}{{\mathbb R}} \newcommand{\E}[1]{\mathbb{E}\left[#1 \right]} \newcommand{\V}{\mathbb Var} \newcommand{\Prob}{\mathbb{P}} \newcommand{\eps}{\varepsilon} \newcommand{\Tv}{P} \newcommand{\mT}{\mathcal{T}} \newcommand{\mS}{\mathcal{S}} \newcommand{\mA}{\mathcal{A}} \newcommand{\mB}{\mathcal{B}} \newcommand{\Cyc}[1]{\mathrm{Cyc}\left(#1\right)} \newcommand{\Seq}[1]{\mathrm{Seq}\left(#1\right)} \newcommand{\Mul}[1]{\mathrm{Mul}\left(#1\right)} \newcommand{\Mulo}[1]{\mathrm{Mul}_{>0}\left(#1\right)} \newcommand{\Set}[1]{\mathrm{Set}\left(#1\right)} \newcommand{\Setd}[1]{\mathrm{Set}_{d}\left(#1\right)} \title{\bf On the hyperbolicity of random graphs} % 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{Dieter Mitsche\\ \small Laboratoire J-A Dieudonn\'{e}\\[-0.8ex] \small Universit\'{e} Nice Sophia Antipolis\\[-0.8ex] \small Parc Valrose, 06108 Nice cedex 02\\ \small\tt dmitsche@unice.fr\\ \and Pawe\l{} Pra\l{}at\thanks{The second author gratefully acknowledges support from NSERC and Ryerson University.}\\ \small Department of Mathematics\\[-0.8ex] \small Ryerson University\\[-0.8ex] \small Toronto, ON, Canada\\ \small\tt pralat@ryerson.ca } % \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{Jan 23, 2014}{April 25, 2014}\\ \small Mathematics Subject Classifications: 05C12, 05C35, 05C80} \begin{document} \maketitle %\subjclass{05C80} \begin{abstract} Let $G=(V,E)$ be a connected graph with the usual (graph) distance metric $d:V \times V \to \N \cup \{0 \}$. Introduced by Gromov, $G$ is $\delta$-hyperbolic if for every four vertices $u,v,x,y \in V$, the two largest values of the three sums $d(u,v)+d(x,y), d(u,x)+d(v,y), d(u,y)+d(v,x)$ differ by at most $2\delta$. In this paper, we determine precisely the value of this hyperbolicity for most binomial random graphs. \bigskip\noindent \textbf{Keywords:} random graphs; hyperbolicity; diameter \end{abstract} \maketitle \section{Introduction}\label{sec:intro} Hyperbolicity is a property of metric spaces that generalizes the idea of negatively curved spaces like the classical hyperbolic space or Riemannian manifolds of negative sectional curvature (see, for example,~\cite{book1, book2}). Moreover, this concept can be applied to discrete structures such as trees and Cayley graphs of many finitely generated groups. The study of properties of Gromov's hyperbolic spaces from a theoretical point of view is a topic of recent and increasing interest in graph theory and computer science. Informally, in graph theory hyperbolicity measures how similar a given graph is to a tree---trees have hyperbolicity zero and graphs that are ``tree-like'' have ``small'' hyperbolicity. Formally, a connected graph $G=(V,E)$ is \textbf{$\delta$-hyperbolic}, if for every four vertices $u,v,x,y \in V$, the two largest values in the set $$ \{d(u,v)+d(x,y), d(u,x)+d(v,y), d(u,y)+d(v,x) \} $$ differ by at most $2\delta$. The \textbf{hyperbolicity} of $G$, denoted by $\delta_H(G)$, is the smallest $\delta$ for which this property holds. Our results below show a close relation between the diameter and hyperbolicity. This relation was also studied in~\cite{Benj2}: the authors show that for vertex transitive graphs, the hyperbolicity is within a constant factor of the diameter. The author of~\cite{Benj1} bounds the number of vertices in terms of the Cheeger constant and the hyperbolicity, showing that the family of expanders is not uniformly $\delta$-hyperbolic for $\delta$ constant. In~\cite{Bandelt1} several equivalent conditions for a graph to be $0$-hyperbolic are given, and in~\cite{Bandelt2} the authors characterize $1/2$-hyperbolic graphs in terms of forbidden subgraphs. On the algorithmic side, by the conditions investigated in~\cite{Bandelt1}, $0$-hyperbolic graphs can be recognized in linear time, and in~\cite{Coudert2} it is shown that recognizing $1/2$-hyperbolic graphs is equivalent to finding an induced cycle of length $4$ in a graph. Fast algorithms for computing the hyperbolicity of large-scale graphs are given in~\cite{Coudert}. \\ %\dieter{perhaps indeed we cite too many algorithms papers. Maybe 2 is enough here instead of 4, so I propose this new version. It is more or less the same authors, so maybe it is ok this way} In~\cite{Chepoi2} fast algorithms for computing properties related to the diameter of graphs with small hyperbolicity are given, and in~\cite{Chepoi1} it is shown that all cop-win graphs in which the cop and the robber move at different speeds have small hyperbolicity. \dieter{start old version with 4 references} The study of this parameter is motivated by the following observations: on the algorithmic side, in~\cite{Chepoi2} fast algorithms for computing properties related to the diameter of graphs with small hyperbolicity are given. In~\cite{Chepoi3} the authors give a simple construction showing that distances in graphs with small hyperbolicity can be approximated within small error by corresponding trees. In~\cite{Chepoi1a} the authors give a polynomial algorithm which computes for such graphs an augmented graph of at most a given diameter, and whose number of added edges is within a constant factor of the minimum number of added edges that are needed such that the augmented graph has at most such a diameter. Finally, in~\cite{Chepoi1} it is shown that all cop-win graphs in which the cop and the robber move at different speeds have small hyperbolicity, and also a constant-factor approximation of $\delta_H$ in time $O(n^2 \log \delta)$ is given. %\dieter{end old version. If you decide to remove, then also references chepoi1a and chepoi3 have to be removed. From here on as before} Moreover, the concept of hyperbolicity turns out to be useful for many applied problems such as visualization of the Internet, the Web graph, and other complex networks~\cite{Munzner1, Munzner2}, routing, navigation, and decentralized search in these networks~\cite{boguna, kleinberg}. In particular, hyperbolicity plays an important role when investigating the spread of viruses through a network~\cite{jonckheere}. \bigskip Let us recall a classic model of random graphs that we study in this paper. The \textbf{binomial random graph} $\mathcal{G}(n,p)$ is defined as a random graph with vertex set $[n]=\{1,2,\dots, n\}$ in which a pair of vertices appears as an edge with probability $p$, independently for each such a pair. As typical in random graph theory, we shall consider only asymptotic properties of $\mathcal{G}(n,p)$ as $n\rightarrow \infty$, where $p=p(n)$ may and usually does depend on $n$. We say that an event in a probability space holds \textbf{asymptotically almost surely} (\textbf{a.a.s.}) if its probability tends to one as $n$ goes to infinity. We say that $f(n) = O(g(n))$ if there exists an integer $n_0$ and a constant $c > 0$ such that $|f(n)| \leq c |g(n)|$ for all $n \geq n_0$, and $f(n) =\Omega(g(n))$, if $g(n) = O(f(n))$. Also, $f(n) = \omega(g(n))$, or $f(n) \gg g(n)$, if $\lim_{n \to \infty} |f(n)|/|g(n)| = \infty$, and $f(n) = o(g(n))$ or $f(n) \ll g(n)$, if $g(n) = \omega(f(n))$. Throughout this paper, $\log n$ always denotes the natural logarithm of $n$. \bigskip In this paper, we investigate the hyperbolicity for binomial random graphs. Surprisingly, this important graph parameter is not well investigated for random graphs which is an important and active research area with numerous applications. In~\cite{sparse_graphs}, sparse random graphs ($p=p(n)=c/n$ for some real number $c>1$) are analyzed. It was shown that $\mathcal{G}(n,p)$ is, with positive probability, not $\delta$-hyperbolic for any positive $\delta$. Nothing seems to be known for $p \gg n^{-1}$. On the other hand, it is known that for a random $d$-regular graph $G$, for $d \ge 3$, we have that a.a.s. $$ \frac 12 \log_{d-1} n - \omega(n) \le \delta_H(G) \le \frac 12 \log_{d-1} n + O(\log \log n), $$ where $\omega(n)$ is any function tending to infinity together with $n$. (In fact, almost geodesic cycles are investigated in~\cite{d-reg}, and this is an easy consequence of this result.) The hyperbolicity of the class of Kleinberg's small-world random graphs is investigated in~\cite{small-world}. \bigskip Our contribution is the following result. \begin{theorem}~\label{thm:main} Let $G \in \mathcal{G}(n,p)$. \\ Suppose first that $$ d=d(n)=p(n-1) \gg \frac {\log^5 n}{(\log \log n)^2} \textrm{ \ \ \ and \ \ \ } p = 1 - \omega(1/n^2). $$ Let $j \geq 2$ be the smallest integer such that $d^j/n - 2\log n \to \infty$. Then, the following properties hold a.a.s. \begin{itemize} \item[(i)] If $j$ is even and $d^{j-1} \leq \frac{1}{16} n \log n$, then $\delta_H(G) =j/2$. \item[(ii)] If $j$ is even and $d^{j-1} > \frac{1}{16} n \log n$ (but still $d^{j-1} \leq (2+o(1)) n \log n$), then $$j/2-1 \le \delta_H(G) \le j/2.$$ \item[(iii)] If $j$ is odd, then $\delta_H(G)=(j-1)/2$. \end{itemize} Furthermore, the following complementary results hold. \begin{itemize} \item[(iv)] For $p=1-2c/n^2$ for some constant $c > 0$, a.a.s.\ $\delta_H(G) \in \{0,1/2,1\}$. More precisely, \begin{eqnarray*} \Prob{(\delta_H(G)=0)} &=& (1+o(1))e^{-c}, \\ \Prob{(\delta_H(G)=1/2)}&=&(1+o(1))ce^{-c}, \textrm{ and } \\ \Prob{(\delta_H(G)=1)}&=&(1+o(1))\left(1-(c+1)e^{-c}\right). \end{eqnarray*} \item[(v)] For $p =1-o(1/n^2)$, a.a.s.\ $\delta_H(G)=0$. \end{itemize} \end{theorem} \bigskip \textbf{Remark.} It seems that with quite a bit more work, we could slightly push the lower bound required for $d$ and require only that $d \gg \log^3 n$ or perhaps even only $d \gg \log^2 n$. Unfortunately, it seems that it is more difficult to investigate sparser graphs (that is, assuming only $d \gg \log n$ or even closer to the connectivity threshold). Therefore, we aim for an easier (and cleaner) argument in this paper, leaving the investigation of sparser graphs as an open problem. Let us also mention that the hyperbolicity is not determined precisely for dense graphs right before the diameter decreases from even $j$ to $j-1$ (case (ii) in Theorem~\ref{thm:main}). Again, the constant $\frac {1}{16}$ could be slightly improved with a more delicate argument but the gap cannot be closed with the current approach. This is also worth investigating and (unfortunately) left open at the moment. \section{Preliminaries} \label{sec:prel} In this section, we introduce a few useful lemmas. The following result is well-known but we include the proof for completeness. \begin{lemma}\label{lem:upperbound} Let $G$ be any connected graph with diameter at most $D$. Then $\delta_H(G) \leq D/2$. \end{lemma} \begin{proof} Consider any four vertices $u,v,x,y$ with their three sums of distances $d_1=d(u,v)+d(x,y) \geq d_2=d(u,x)+d(v,y) \geq d_3=d(u,y)+d(v,x)$. We need to show that $d_1-d_2 \leq D$. Clearly, $d_1 \leq 2D.$ First observe that by applying the triangle inequality four times, \begin{eqnarray*} 2d_1 &=& 2\left( d(u,v) + d(x,y) \right) \\ & \leq& d(u,y)+d(y,v) + d(u,x)+d(x,v)+d(x,u)+ d(u,y)+d(x,v)+d(v,y) \\ &=&2(d_2+d_3), \end{eqnarray*} and thus $d_1 \leq d_2+d_3$ or equivalently $d_1-d_2 \leq d_3$. Hence, if $d_3 \leq D$, the required condition holds and we are done. Otherwise, $d_3 > D$ and so also $d_2 > D$. As a consequence, $d_1 - d_2 < 2D - D=D$, and we are done as well. \end{proof} We can slightly improve the upper bound for graphs with odd diameter. \begin{lemma}\label{lem:upperbound2} Let $G$ be any graph with diameter at most $D=2k+1$ for some integer $k$. Then $\delta_H(G) \leq (D-1)/2=k.$ \end{lemma} \begin{proof} As in the previous proof, we consider four vertices $u,v,x,y$ with their three sums of distances $d_1=d(u,v)+d(x,y) \geq d_2=d(u,x)+d(v,y) \geq d_3=d(u,y)+d(v,x)$. Our goal is to show that $d_1-d_2 \leq D-1$. Arguing as in the previous proof, we get that $d_1 - d_2 \le d_3$. Hence, if $d_3 < D$, then $d_1 - d_2 \le D-1$ and we are done. Also, if $d_2 \geq D+1$, then $d_1 - d_2 \leq 2D - (D+1) \leq D-1$. So the only case to analyze is when $d_2=d_3=D$. For a contradiction, suppose that $d_1-d_2=D$, that is, %Otherwise, let $d_2=s \leq D$. If $d_3 < s$, then $d_1 \leq d_2+d_3 < 2s$, and hence $d_1 - d_2 < s \leq D$, and thus also $d_1-d_2 \leq D-1$. Therefore, suppose $d_2=d_3=s \leq D$. Then $d_1 \leq d_2+d_3 =2s$, and $d_1-d_2 \leq s$. If $s \leq D-1$, then the result follows. Hence, in order to have $d_1-d_2=D$, we must have $d(u,x)+d(v,y)=d_2=d(u,y)+d(v,x)=d_3=D$, and thus $d_1=d(u,v)+d(x,y)=2D$. In particular, $d(u,v)=D$ and $d(x,y)=D$. Since $D=d_3=d(u,y)+d(v,x)$ and $D$ is odd, we may assume (without loss of generality) that $d(u,y) < D/2$. Then, since $$ D=d(u,v) \leq d(u,y)+d(y,v) $$ and $$ D=d(x,y) \leq d(x,u)+d(u,y), $$ we have $d(y,v) > D/2$, $d(x,u) > D/2$, and we have that $d_2 =d(u,x)+d(v,y) > D$, contradicting our assumption on $d_2$. Therefore, $d_1-d_2 \leq D-1$, and the lemma follows. \end{proof} \bigskip In order to bound the hyperbolicity from above, we will make use of the following result for random graphs, see~\cite[Corollary~10.12]{bol}. \begin{lemma}[\cite{bol}, Corollary 10.12]\label{lem:diameter} Suppose that $d = p(n-1) \gg \log n$ and \[ d^i/n - 2 \log n \to \infty \text{ \ \ \ \ and \ \ \ \ } d^{i-1}/n - 2 \log n \to -\infty. \] Then the diameter of $G \in \mathcal{G}(n,p)$ is equal to $i$ a.a.s. \end{lemma} From the proof of this result, we have the following corollary. \begin{corollary}\label{cor:diameter} Suppose that $d = p(n-1) \gg \log n$ and that $$d^i/n - 2 \log n \to \infty.$$ Then the diameter of $G \in \mathcal{G}(n,p)$ is at most $i$ a.a.s. \end{corollary} \bigskip In order to obtain a lower bound on the hyperbolicity, we will need the following expansion lemma investigating the shape of typical neighbourhoods of vertices. Before we state the lemma we need a few definitions. For any $j \geq 0$, let us denote by $N(v,j)$ the set of vertices at distance at most $j$ from $v$, and by $S(v,j)$ the set of vertices at distance exactly $j$ from $v$. %We also simplify the notation and write $N(x)$ instead of $N(x,1)$. \dieter{we use this only once below in statement (i) of the lemma and once in proof, where it needs to be changed, I think. And in the proof of (iii) we use anyway the old notation with $N(v,1)$. It would be okay, but it is nonstandard definition of neighborhood, as it includes $x$, right? So I don't know whether we need this simplified notation? up to you.} Also, for a set of vertices $F \subseteq V$, and $x \in V \setminus F$, denote by $N_{V \setminus F}(x,j)$ the set of vertices in $V \setminus F$ at distance at most $j$ from $x$ in the graph induced by $V \setminus F$, and similarly let $S_{V \setminus F}(x,j)$ be the set of vertices in $V \setminus F$ at distance exactly $j$ from $x$ in the graph induced by $V \setminus F$. \begin{lemma}\label{lem:expansion} Suppose that $d=p(n-1)$ is such that $$ \frac {\log^5 n}{(\log \log n)^2} \ll d \le \left(\frac{1}{16}n\log n\right)^{1/3}. $$ Let $G = (V,E) \in \mathcal{G}(n,p)$ and let $i \geq 4$ be the largest even integer such that $d^{i-1} \leq \frac{1}{16} n \log n.$ Fix any set $F \subseteq V$ such that $|F| = O(d^{i/2-1}) = O(\sqrt{n \log n/d})$ and fix any vertex $v \in V \setminus F$. Then, \begin{itemize} \item [(i)] with probability $1-o(n^{-1})$ we have $$ |N_{V \setminus F}(v,1)| = d \left( 1 + o \left( \frac {\log \log n}{\log^2 n} \right) \right), $$ \item [(ii)] with probability $$ 1-O(d^{i/2}/n) = 1-O(\sqrt{d \log n / n})=1-O((\log n)^{2/3} n^{-1/3}) $$ there is no edge from $v$ to $F$. \end{itemize} \bigskip \noindent In particular, it follows that a.a.s.\ the following properties hold: \begin{itemize} \item[(iii)] for all $j=1,2,\ldots,i/2 - 1$, $$ |N_{V \setminus F}(v,j)| = |S_{V \setminus F}(v,j)| (1+O(1/d)) = d^j(1+o(\log^{-1} n)), $$ \item [(iv)] for all $j=1,2,\ldots,i/2 - 2$, every vertex of $S_{V \setminus F}(v,j)$ has $d(1+o(\log \log n / \log^{2} n))$ neighbours in $S_{V \setminus F}(v, j+1)$, \item [(v)] the graph induced by $N_{V \setminus F}(v, i/2 -2)$ forms a tree, \item [(vi)] all vertices of $S_{V \setminus F}(v,i/2-1)$ have exactly one neighbour in $S_{V \setminus F}(v,i/2-2)$, \item [(vii)] for any fixed partition of the neighbours of $v$ into two sets, $V_L$ and $V_R$, such that $||V_L| - |V_R|| \le 1$, let $S_L$ denote the set of vertices of $S(v,i/2-1)$ that are at distance $i/2-2$ from $V_L$, and let $S_R=S(v,i/2-1) \setminus S_L$; then, $$ |S_L| = |S_R| (1+o(\log^{-1} n)) = \frac {d^{i/2-1}}{2} (1+o(\log^{-1} n)). $$ \end{itemize} \end{lemma} \begin{proof} Let $F \subseteq V$, $f=|F| = O(d^{i/2-1})$, and $v \in V \setminus F$. Consider the random variable $X = X(F,v) = |S_{V \setminus F}(v,1)|$. We will bound $X$ in a stochastic sense. There are two things that need to be estimated: the expected value of $X$, and the concentration of $X$ around its expectation. Since $X \in \textrm{Bin}(n-f-1,p)$, it is clear that $$ \E{X} = \frac {d}{n-1} (n-f-1) = d \left( 1 + O(f/n) \right) = d (1+O(n^{-1/2})). $$ A consequence of Chernoff's bound (see e.g.~\cite[Corollary~2.3]{JLR}) is that \begin{equation}\label{eq:chern} \Prob \Big( |X-\E X| \ge \eps \E X \Big) \le 2\exp \left( - \frac {\eps^2 \E X}{3} \right) \end{equation} for $0 < \eps < 3/2$. Hence, after taking $\eps = 2 \sqrt{\log n / d}$, we get that with probability $1+o(n^{-1})$ we have $$ X = \E{X} (1+O(\eps)) = d (1+O(n^{-1/2})) (1+O(\eps)) = d \left( 1 + o \left( \frac {\log \log n}{\log^2 n} \right) \right). $$ This proves part (i) of the lemma. Part (ii) is straightforward since the probability that there is no edge from $v$ to $F$ is equal to $$ (1-p)^f = \exp(-(1+o(1))p f) = \exp \left( - O \left( \frac {d^{i/2}}{n} \right) \right) = 1 - O \left( \frac {d^{i/2}}{n} \right). $$ Part (iii) is a straightforward implication of (i). In order to have good bounds on the ratios of the cardinalities of $N(v,1)$, $N(v,2)$, and so on, we consider the Breadth First Search (BFS) algorithm that explores vertices one by one (instead of the whole $j$-th neighbourhood). Formally, the process is initiated by putting $v$ into the queue $Q$. In each step of the algorithm, one vertex $w$ is taken from $Q$ and edges from $w$ to all vertices that are not in $F$ and have not yet been discovered are examined. All new neighbours of $w$ that are found are put into the queue $Q$. The process continues until the queue $Q$ is empty or vertices of $N_{V \setminus F}(v,i/2-1)$ are discovered. (Note that if the process stops because $N_{V \setminus F}(v,i/2-1)$ is discovered, vertices of $S_{V \setminus F}(v,i/2-1)$ are in the queue $Q$; that is, no vertex from this sphere is processed and, in particular, edges in the graph induced by $S_{V \setminus F}(v,i/2-1)$ are not exposed yet.) Suppose that $N_{V \setminus F}(v,j-1)$ is discovered and we continue investigating vertices of the sphere $S_{V \setminus F}(v,j-1)$, one by one, that are in the queue $Q$. Provided $O(d^{i/2-1})$ vertices have been discovered so far, it follows from part (i) that we may assume that when each vertex of $S_{V \setminus F}(v,j-1)$ is processed, we discover $d (1+o(\log \log n / \log^2 n))$ new neighbours that belong to $S_{V \setminus F}(v,j)$. After that we update $F$ by adding all newly discovered vertices to it, adding the vertex processed at this step, and removing the next vertex to be processed---see Figure~\ref{PictureF2}. \begin{figure} \includegraphics[width=0.4\textwidth]{PictureF1-Pawel.eps}%\label{fig:sub1} \includegraphics[width=0.4\textwidth]{PictureF2-Pawel.eps}%\label{fig:sub2} \caption{Two consecutive steeps of BFS started from vertex $v$. The black vertex is the vertex currently exposed. Grey vertices form the set $F$ that is updated each time. White vertices are newly discovered ones.}\label{PictureF2} \end{figure} We continue until $N_{V \setminus F}(v,j)$ is discovered to get that $$ |S_{V \setminus F}(v,j)| = |S_{V \setminus F}(v,j-1)| d (1+o(\log \log n / \log^2 n)). $$ We consider this up to the $j$'th iterated neighbourhood, where $j=i/2-1$ and $d^{i-1} \le n \log n / 16$ and thus $j = O(\log n /\log \log n)$. Then the cumulative multiplicative error term is $$ \left( 1 + o \left( \frac {\log \log n}{\log^2 n} \right) \right)^j = (1 + o(\log^{-1} n)), $$ and thus $|S(v,j)|=d^j(1 + o(\log^{-1} n))$, and $$ |N(v,j)|=\sum_{i=1}^j |S(v,i)|=|S(v,j)|(1+O(1/d)). $$ This establishes (iii). For parts (iv), (v), and (vi) we note that in each step of the BFS algorithm the probability that there is no edge from $w$ (the vertex that is processed at this point) to vertices that have been already discovered is, by part (ii), $1-O(d^{i/2}/n)$. % \dieter{Similarly, for part (vi), since the size of $N_{V \setminus F}(v,i/2-2)$ is at most $O(d^{i/2-2})$, by inspection of the proof of (ii), part (ii) holds with probability at least $1-O(d^{i/2-1}/n)$, and by a union bound over all $O(d^{i/2-1})$ vertices in $S(v,i/2-1)$ we see that the probability that for all vertices there is no additional edge to already exposed vertices, is at least %$1-O(d^{i/2-1}d^{i/2-1}/n)=1-O(\log n/d)=1+o(1)$} Hence, by the union bound, a.a.s.\ this never happens since the number of vertices processed is \begin{eqnarray*} |N_{V \setminus F}(v,i/2-2)| &=& (1+o(1)) d^{(i-1)/2-3/2} = O(d^{-3/2} \sqrt{n \log n}) \\ &=& O(d^{-3/2} (n \log n) / d^{(i-1)/2}) = O(d^{-1} (n \log n) / d^{i/2}) \\ &=& o(n/d^{i/2}). \end{eqnarray*} The claim follows. Part (vii) follows immediately (and deterministically) from (iv), (v), and (vi). The proof of the lemma is finished. \end{proof} \bigskip We first give the proof of the result for very dense graphs. \begin{proof}[Proof of Theorem~\ref{thm:main}(iv)-(v).] For $p =1-o(1/n^2)$, note that the expected number of edges in the complement of $G$ is ${n \choose 2} (1-p) = o(1)$, and thus by Markov's inequality, a.a.s., $G$ is the complete graph on $n$ vertices. If this is the case, then $d(u,v)=1$ for any pair of vertices $u$ and $v$, and thus for any four vertices $u,v,x,y$, clearly, $d(u,v)+d(x,y)-(d(u,x)+d(v,y))=0$, and hence $\delta_H(G)=0$. Part (v) is proved. For $p=1-2c/n^2$ and $c > 0$, note that a.a.s.\ there is no component of size $3$ or more in the complement of $G$. Thus, a.a.s., for all four-tuples of vertices in the original graph, either all edges are present, only one edge is missing, or two disjoint edges are missing. In all of these cases, the non-adjacent vertices are at distance $2$, and thus a.a.s.\ $\delta_H(G) \leq 1$. The expected number of edges in the complement of $G$ equals ${n \choose 2}(1-p) = (1+o(1)) c$. Also, for any fixed $r$, the $r$-th moment of the number of edges in the complement of $G$ equals $c^r(1+o(1))$, and thus, by the method of moments (see, for example, Theorem~1.22 of~\cite{bol}) the number of edges converges to a random variable with a Poisson distribution with parameter $c$. In particular, with probability $(1+o(1))e^{-c}$, the complement of $G$ is empty, and by the argument in the first case, we have $\delta_H(G)=0$. Also, with probability $(1+o(1))ce^{-c}$, the complement of $G$ contains exactly one edge, say $\{u,v\}$. For the four-tuples not containing both $u$ and $v$, the analysis is as before. For a four-tuple $u,v,x,y$ we now have for the distances in the original graph $d(u,v)+d(x,y)=3$, $d(u,x)+d(v,y)=d(u,y)+d(v,x)=2$, and thus $\delta_H(G)=1/2$. Finally, with probability $(1+o(1))\left(1-(c+1)e^{-c}\right)$ the complement of $G$ has at least two disjoint edges, say $\{u,v\}$ and $\{x,y\}$. In this case, in the original graph we have $d(u,v)+d(x,y)=4$, $d(u,x)+d(v,y)=d(u,y)+d(v,x)=2$, and thus $\delta_H(G) \geq 1$, and part (iv) follows. \end{proof} The main challenge of this paper is to prove the following result and the whole next section is dedicated to it. Here, we show how Theorem~\ref{thm:main}(i)-(iii) can be derived from it. \begin{theorem}\label{thm:main2} Suppose that $$ d=d(n)=p(n-1) \gg \frac {\log^5 n}{(\log \log n)^2} \textrm{ \ \ \ and \ \ \ } p = 1 - \omega(1/n^2). $$ Let $i \geq 2$ be the largest even integer such that $d^{i-1} \leq \frac{1}{16} n \log n.$ Let $G \in \mathcal{G}(n,p)$. Then, a.a.s., $\delta_H(G) \geq i/2$. \end{theorem} \begin{proof}[Proof of Theorem~\ref{thm:main}(i)-(iii)] Fix $j$ to be the smallest integer such that $d^j/n- 2\log n \to \infty$. In particular, $d^{j+1}/n = \omega(\log n)$. Moreover, it follows from Corollary~\ref{cor:diameter} that the diameter of $G$ is at most $j$ a.a.s. Hence, by Lemma~\ref{lem:upperbound}, a.a.s.\ $\delta_H(G) \leq j/2$. This establishes upper bounds in parts (i) and (ii). Suppose first that $j$ is even and that $d^{j-1} \leq \frac{1}{16} n \log n$. Then $j$ is the largest even integer such that $d^{j-1} \leq \frac{1}{16} n \log n.$ By Theorem~\ref{thm:main2}, a.a.s.\ $\delta_H(G) \geq j/2$ and part (i) holds. %On the other hand, $d^{i-1}/n - 2\log n \to -\infty$, and thus by Lemma~\ref{lem:diameter}, the diameter of $G$ is $i$ a.a.s. By Lemma~\ref{lem:upperbound}, in this case $\delta_H \leq i/2$, and Part(i) of Theorem~\ref{thm:main} follows. Suppose next that $j$ is even and that $d^{j-1} > \frac{1}{16} n \log n$ (note that it follows from the definition of $j$ that $d^{j-1} \leq (2+o(1))n \log n$). Then $j-2$ is the largest even integer such that $d^{j-3} \leq \frac{1}{16} n \log n$, and by Theorem~\ref{thm:main2}, a.a.s.\ $\delta_H(G) \geq j/2 -1$. This finishes part (ii). %On the other hand, by Corollary~\ref{cor:diameter}, the diameter of $G$ is at most $i$ a.a.s., and thus by Lemma~\ref{lem:upperbound}, a.a.s. $\delta_H(G) \leq i/2$, and thus Part(ii) of Theorem~\ref{thm:main} follows. Finally, suppose that $j$ is odd. Since $d^{j-1}/n = O(\log n)$, $d^{j-2}/n = o(\log n)$, and thus $j-1$ is the largest even integer such that $d^{j-2}\leq \frac{1}{16}n \log n.$ By Theorem~\ref{thm:main2}, a.a.s., $\delta_H(G) \geq (j-1)/2$. Since a.a.s.\ the diameter of $G$ is at most $j$, and $j$ is odd, by Lemma~\ref{lem:upperbound2} we have that a.a.s.\ $\delta_H(G) \leq (j-1)/2$. Part (iii) and so the whole proof is finished. \end{proof} \section{Proof of Theorem~\ref{thm:main2}} Let $G = (V, E) \in \mathcal{G}(n,p)$ and suppose that $d=p(n-1) \gg \frac {\log^5 n}{(\log \log n)^2}$ and $p = 1 - \omega(1/n^2)$. Let $i \geq 2$ be the largest even integer such that $d^{i-1} \leq \frac{1}{16} n \log n.$ Assume first that $d > (\frac{1}{16}n\log n)^{1/3}$ which implies that $i=2$. In this case, we have to prove that a.a.s.\ $\delta_H(G) \geq 1$. It therefore suffices to find four vertices $u,v,x,y$ such that the subgraph induced by them is a $4$-cycle. Since $p > n^{-2/3}(\frac{1}{16}\log n)^{1/3}$ and $1-p = \omega(n^{-2})$, the expected number of induced cycles of length 4 is ${n \choose 4} p^4 (1-p)^2 \to \infty$. It is a straightforward application of the second moment method to show that a.a.s.\ there is at least one induced cycle in $G$ and the statement follows in this case. % Since $p > n^{-2/3}(\frac{1}{96}\log n)^{1/3}$, we are clearly above the threshold of having cycles of length $4$. For $p =o(1)$, a.a.s. almost all of them are induced, and the statement follows. For $p=\Theta(1)$ and $p < 1$, four given vertices form an induced $4$-cycle with constant probability, and since there are $n/4$ independent choices of $4$-tuples, a.a.s. there will be one such $4$-tuple. Finally, for $p=1-o(1)$, note that the complement of $G$ a.a.s. has $o(n^2)$ edges. Since $p \leq 1 - \omega(1/n^2)$, there are a.a.s. at least $\omega$ edges in the complement of $G$. As the complement of $G$ is sparse, a.a.s., most of these pairs of edges share no vertex. Moreover, for a given pair of disjoint edges in the complement of $G$, a.a.s. the induced graph on the four vertices in the complement of $G$ contains no other edge, thus yielding an induced $4$-cycle in the original graph. Thus, in this case the statement follows. Hence, from now on we may assume that \begin{equation}\label{eq:deg_bound} d \leq \left(\frac{1}{16}n\log n\right)^{1/3}, \end{equation} which implies that $i \geq 4$. We need one more definition: for a given $u \in V$, $k \geq 1$, and $A \subseteq V$, we say that $N_{V \setminus A} (u,k)$ \textbf{expands well} if for all $j=1,2,\ldots, k$, $$|N_{V \setminus A} (u,j)| =|S_{V \setminus A}(u,j)|(1+O(1/d))=d^{j}(1+o(\log^{-1} n))$$ and for all $j=1,2,\ldots, k-1$, every vertex of $S_{V \setminus A}(u,j)$ has $d(1+o(\log \log n / \log^{2} n))$ neighbours in $S_{V \setminus A}(u, j+1)$. Finally, fix a four-tuple of different vertices $u,v,x,y$ and consider the following process (see Figure~\ref{FigHyp1}): \\ \begin{figure} \includegraphics[width=.4\textwidth]{Figure1Hyp-Pawel.eps} \includegraphics[width=.4\textwidth]{Figure2Hyp-Pawel.eps} \caption{ left: \textsc{Hyperbolicity($u,v,x,y$)}, the big picture; right: the neighbourhood exposure around $a$ in more detail}\label{FigHyp1} \end{figure} \textsc{Hyperbolicity($u,v,x,y$)} \begin{enumerate} \item Let $B:=\{v,x,y\}$. Perform Breadth-First Search (BFS) from $u$ in the graph induced by $V \setminus B$ to expose $N_{V \setminus B}(u,i/2 - 1)$. Make sure that the following properties hold (otherwise stop the process): \begin{description} \item [(a)] $N_{V \setminus B}(u,i/2 - 1)$ expands well. %For all $j=1,2,\ldots,i/2-1$, $$|N_{V \setminus B} (u,j)| =|S_{V \setminus B}(u,j)|(1+O(1/d))=d^{j}(1+o(\log^{-1} n))$$ and for all $j=1,2,\ldots,i/2 - 2$, every vertex of $S_{V \setminus B}(u,j)$ has $d(1+o(\log \log n / \log^{2} n))$ neighbours in $S_{V \setminus B}(u, j+1)$. \item [(b)] The graph induced by $N_{V \setminus B}(u,i/2-1)$ is a tree. \item [(c)] There is no edge from $N_{V \setminus B}(u,i/2-2)$ to $\{v,x,y\}$. \end{description} (As a result, $N(u,i/2-1)=N_{V \setminus B}(u,i/2-1)$ and so $N(u,i/2-1)$ expands well, $N(u,i/2-1)$ is a tree, and $\{v,x,y\} \cap N(u,i/2-1) = \emptyset$.) \item Let $D:=N(u,i/2 - 1) \cup \{x,y\}$. Perform BFS from $v$ in the graph induced by $V \setminus D$ to expose $N_{V \setminus D}(v,i/2-1)$. (The reason that here we restrict ourselves to the induced graph is to make sure no edge in this graph is already exposed and so, as typical, we perform BFS by exposing edges one by one, as required.) Make sure that the following properties hold (otherwise stop): \begin{description} \item [(d)] $N_{V \setminus D}(v,i/2-1)$ expands well. %For all $j=1,2,\ldots,i/2-1$, $$|N_{V \setminus D}(v,j)| =|S_{V \setminus D}(v,j)|(1+O(1/d))=d^{j}(1+o(\log^{-1} n))$$ and for all $j=1,2,\ldots,i/2 - 2$, every vertex of $S_{V \setminus D}(v,j)$ has $d(1+o(\log \log n / \log^{2} n))$ neighbours in $S_{V \setminus D}(v, j+1)$. \item [(e)] There is no edge from $N_{V \setminus D}(v,i/2-1)$ to $S(u,i/2-1)$ (note that edges from vertices of $N(u,i/2-2)$ are already exposed, so that the only chance for the intersection of $N_{V \setminus D}(v,i/2-1)$ and $N(u,i/2-1)$ to be non-empty is when we reach vertices of $S(u,i/2-1)$). \item [(f)] The graph induced by $N_{V \setminus D}(v,i/2-1)$ is a tree. \item [(g)] There is no edge from $N_{V \setminus D}(v, i/2-2)$ to $\{x,y\}$. \end{description} (As a result, $N(v,i/2-1) = N_{V \setminus D}(v,i/2-1)$ and $N(v,i/2-1)$ so expands well, $N(v,i/2-1) \cap N(u,i/2-1) = \emptyset$, $N(v,i/2-1)$ is a tree, and $\{x,y\} \cap N(v,i/2-1) = \emptyset$.) \item Let us partition (arbitrarily) the neighbours of $u$ into two sets, $U_L$ and $U_R$, such that $||U_L| - |U_R|| \le 1$. Let us partition the vertices of $S(u,i/2-1)$ and call vertices that are at distance $i/2-2$ from $U_L$ to be `$u$-left'; otherwise, they are called `$u$-right'. Similarly, the vertices of $S(v,i/2-1)$ are partitioned into $v$-left and $v$-right ones. Expose the edges between $x$ and $S(u,i/2-1) \cup S(v,i/2-1)$ and similarly also between $y$ and $S(u,i/2-1) \cup S(v,i/2-1)$. Make sure that the following properties hold (otherwise stop): \begin{description} \item[(h)] The number of $u$-left vertices is $\frac {d^{i/2-1}}{2} (1+o(\log^{-1} n))$, and the number of $u$-right vertices is also $\frac {d^{i/2-1}}{2} (1+o(\log^{-1} n))$. \item[(i)] The number of $v$-left vertices is $\frac {d^{i/2-1}}{2} (1+o(\log^{-1} n))$, and the number of $v$-right vertices is also $\frac {d^{i/2-1}}{2} (1+o(\log^{-1} n))$. \item[(j)] There is exactly one edge between $x$ and the $u$-left vertices; call the corresponding neighbour of $x$ to be $a$. There is no edge between $x$ and the $u$-right vertices. \item[(k)] There is exactly one edge between $x$ and the $v$-left vertices; call the corresponding neighbour of $x$ to be $b$. There is no edge between $x$ and the $v$-right vertices. \item[(l)] There is exactly one edge between $y$ and the $u$-right vertices; call the corresponding neighbour of $y$ to be $c$. There is no edge between $y$ and the $u$-left vertices. \item[(m)] There is exactly one edge between $y$ and the $v$-right vertices; call the corresponding neighbour of $y$ to be $d$. There is no edge between $y$ and the $v$-left vertices. \end{description} \item In this step, the neighbourhood of $a$ is investigated. Unfortunately, this is slightly more complicated since some part of the neighbourhood of $a$ is already ``buried'' in $N(u,i/2-1)$. In order to accomplish our goal, we need to perform BFS not only from $a$ (up to level $i/2-2$), but also from some other vertices of $S(u,i/2-1)$ (this time going not as deep as $i/2-2$; the level until which the neighborhood is explored depends on the distance from $a$)---see Figure~\ref{FigHyp1} (right side). % \begin{figure} % \includegraphics[width=0.6\textwidth]{Figure2Hyp.pdf} % \vspace{-2cm} % \caption{The neighbourhood exposure around $a$}\label{Fig2Hyp} %\end{figure} Formally, for $1 \le k \le i/2-2$, let $S_k$ be the set of vertices of $S(u,i/2-1)$ that are at distance $k$ from $a$ in the tree induced by $N(u,i/2-1)$. (In fact, $k$ has to be even in order for $S_k$ to be non-empty, but we consider all values of $k$ for simplicity.) Let $$ F:= \left( N(u,i/2-1) \setminus \left( \{a\} \cup \bigcup_{k=1}^{i/2-2} S_k \right) \right) \cup N(v,i/2-1) \cup \{x\} \cup \{y\}. $$ We perform BFS from $a$ and from vertices of $\bigcup_{k=1}^{i/2-2} S_k$ in the graph induced by $V \setminus F$; we reach vertices at distance $i/2-2$ from $a$ and at distance $i/2-2-k$ from $S_k$. Make sure that the following properties hold (otherwise stop). \begin{description} \item[(n)] $N_{V \setminus F}(a,i/2-2)$ expands well. Moreover, for all $1 \le k \le i/2-2$ and all $\ell \in S_k$ we have that $N(\ell, i/2-2-k)$ expands well. In particular, %For all $j=1,2,\ldots,i/2-2$, $$|N_{V \setminus F}(a,j)| =|S_{V \setminus F}(a,j)|(1+O(1/d))=d^{j}(1+o(\log^{-1} n))$$ and for all $j=1,2,\ldots,i/2 - 3$, every vertex of $S_{V \setminus F}(a,j)$ has $d(1+o(\log \log n / \log^{2} n))$ neighbours in $S_{V \setminus F}(a, j+1)$. \begin{eqnarray*} |N_{V \setminus F}(a,i/2-2)| &=& d^{i/2-2} (1+o(\log^{-1} n))\\ \sum_{k=1}^{i/2-2} \sum_{\ell \in S_k} |N_{V \setminus F}(\ell,i/2-2-k)| &=& o(d^{i/2-2} \log^{-1} n). \end{eqnarray*} %\dieter{I agree with your suggestion, for $d \gg \log^2 n$ it seems to work. So maybe let us leave it for the moment in this way and go first to second moment? We can see there whether there is some chance to go down to $d \gg \log n$} %\dieter{The following comment should be erased, I guess...}(Note that the size of the neighbourhood of $a$ in the whole graph is estimated, which includes vertices reached from vertices of $S_k$.) \dieter{Since you didn't like re-exposing edges, now to me it is strange to have the whole graph when performing BFS in a subgraph. I suggest the following: % For all $j \in \{1,2,\ldots,i/2 - 2\}$, we have $|N_{V \setminus F}(a,j)| =d^j(1+o(\log^{-1} n))$ and for every $k \in \{1, 2, \ldots,i/2-2\}$, every vertex $\ell \in S_k$ and every $j \in \{1,\ldots,i/2-2-k\}$, $|N_{V \setminus F}(\ell,j)| =d^j(1+o(\log^{-1} n))$.} %\pawel{Again, I think there are two things that might prevent us to go to $\gg \log n$, and they are independent. So perhaps we should try to squeeze as much as possible. At this point I think we need to control the error term for the second moment, which means we have to go for $\gg \log^2 n$. We need to check it. The other thing is how many vertices do we have to test. Here I think we should be fine but do much more work. I do not think we can re-expose anything (I am not sure what it means). I guess we can apply union bound but we do not know which $a$ we have in mind, and then we need to move inside the tree, and make sure that when we grow from there (till distance $i/2-2-1$) we accumulate negligible number of vertices. I guess we will have $d^{i/2-2} (1+o(\log^{-1} n))$ vertices from $a$. We go back one level and then we need to go up to distance $i/2-3$ from there; we expect $d^{i/2-3}$ vertices there and we need only $o(d^{i/2-2} \log^{-1} n = o(d^{i/2-3} \log n)$. or something. So we should be fine, since this should be true for all vertices. If we move 2 steps, we can afford more but this also requires a bit of work. Anyway, this looks doable but only when $d \gg \log^2 n$. For smaller $d$, we would have a problem. If you want to fight for this, we have to change the condition you have (since what you say is checking a lot of vertices). If we leave it as you suggest, then $d$ has to go up. We could put exactly what we want} \item[(o)] There is no edge from $N_{V \setminus F}(a,i/2-2) \setminus \{a\}$ to $F$ and for every $k=1, 2, \ldots,i/2-2$ and every vertex $\ell \in S_k$, there is no edge from $N_{V \setminus F}(\ell, i/2-2-k) \setminus \{\ell\}$ to $F$. \item[(p)] All graphs exposed in this step are disjoint trees. Note that this implies that $N(a,i/2-2)$ is a tree. %\dieter{If you say so, let's put it this way then, I can live with this. We are hiding some details, but for $d \gg \log^2 n$ it should be fine. Anyway, if we hide details here, I don't want to give more details in the first moment proof below... My old suggestion is still commented, in case you want to change back...} % \dieter{I would be more precise here and say: $N_{V \setminus F}(a,i/2-2)$ is a tree, and there is no edge between a vertex in $N(a, i/2-2)$ and a vertex in $\bigcup_{k=1}^{i/2-2} S_k$. Moreover, for every $k \in \{1, 2, \ldots,i/2-2\}$, and every vertex $\ell \in S_k$, $N(\ell,i/2-2-k)$ is a tree, and for every such $\ell$, there is no edge between a vertex in $N(\ell,i/2-2-k)$ and a vertex in $\left( \bigcup_{k=1}^{i/2-2} S_k \right)\setminus \{\ell\} \cup \{a\}$. Note that this implies that $N(a,i/2-2)$ is a tree, and it also implies that for all $j \in \{1,2,\ldots,i/2 - 2\}$, we have $|N(a,j)| =d^j(1+o(\log^{-1} n))$. } % \pawel{This is all a bit confusing. Perhaps we can define $F$ and then say that we perform BFS from $a$ in the graph induced by $V \setminus F$ (define $V$ at the very beginning). Then we can use $N_{V\setminus F}()$ instead of $N()$ to make it less confusing. We can call the three properties (h), (i), (j) or something, as usual. Then for $b$ we just define different $F$ (with neighbourhood of $a$ included, and say that the three conditions hold for this modified $F$ and $b$ instead of $a$. Finally, do the same with $c$ and $d$?} Let $F=N(u,i/2-1) \cup N(v,i/2-1) \cup \{x\} \cup \{y\}$. Expose $N(a,i/2-2)$ without exposing $N(x)$ and without re-exposing vertices in $N(u,i/2-2)$ \dieter{writing explicitly this simplifies the conditions in the following sentences}. Since we do not consider other neighborhoods of $a$ ($b$,$c$,$d$, respectively), let us here and in the following by slight abuse of notation still call the corresponding neighborhoods by $N(a,j)$ ($N(b,j)$, $N(c,j)$, $N(d,j)$, respectively). \dieter{Maybe there is a better notation for this? I am not sure, it appears later always like this when adding it to $F$. One choice would be to add those forbidden vertices somehow into the definition of neighborhood} Stop if there exists some $j \in \{1,\ldots,i/2 - 2\}$ such that \pawel{Use $N_{V \setminus F}$ and then do not remove $F$?} $|N(a,j) \setminus F| =d^j(1+o(\log^{-1} n))$ does not hold. \pawel{Use $N_{V \setminus F}$? Again, it is not the whole neighbourhood, since we did not grow from $x$} Stop if $N(a,i/2-2)$ is not a tree. \item[(q)] For $1 \leq k \leq i/2-2$, let $S'_k$ be the set of vertices of $S(v,i/2-1)$ that are at distance $k$ from $b$ in the tree induced by $N(v,i/2-1)$ and let \begin{eqnarray*} F' &:=& \left( N(v,i/2-1) \setminus \left( \{b\} \cup \bigcup_{k=1}^{i/2-2} S'_k \right) \right) \cup N(u,i/2-1) \cup \{x\} \cup \{y\} \\ && \cup N(a,i/2-2). \end{eqnarray*} Perform BFS from $b$ and from vertices of $\bigcup_{k=1}^{i/2-2} S'_k$ in the graph induced by $V \setminus F'$; Properties \textbf{(n)}, \textbf{(o)}, and \textbf{(p)} hold when $a$ is replaced by $b$, $F$ is replaced by $F'$, and the sets $S_k$ are replaced by $S_k'$. \item[(r)] For $1 \leq k \leq i/2-2$, let $S''_k$ be the set of vertices of $S(u,i/2-1)$ that are at distance $k$ from $c$ in the tree induced by $N(u,i/2-1)$ and let \begin{eqnarray*} F'' &:=& \left( N(u,i/2-1) \setminus \left( \{c\} \cup \bigcup_{k=1}^{i/2-2} S''_k \right) \right) \cup N(v,i/2-1) \cup \{x\} \cup \{y\} \\ && \cup N(a,i/2-2) \cup N(b,i/2-2). \end{eqnarray*} Perform BFS from $c$ and from vertices of $\bigcup_{k=1}^{i/2-2} S''_k$ in the graph induced by $V \setminus F''$; Properties \textbf{(n)}, \textbf{(o)}, and \textbf{(p)} hold when $a$ is replaced by $c$, $F$ is replaced by $F''$, and the sets $S_k$ are replaced by $S''_k$. \item[(s)] For $1 \leq k \leq i/2-2$, let $S'''_k$ be the set of vertices of $S(v,i/2-1)$ that are at distance $k$ from $d$ in the tree induced by $N(v,i/2-1)$ and let \begin{eqnarray*} F''' &:=& \left( N(v,i/2-1) \setminus \left( \{d\} \cup \bigcup_{k=1}^{i/2-2} S'''_k \right) \right) \cup N(u,i/2-1) \cup \{x\} \cup \{y\} \\ && \cup N(a,i/2-2) \cup N(b,i/2-2) \cup N(c,i/2-2). \end{eqnarray*} Perform BFS from $d$ and from vertices of $\bigcup_{k=1}^{i/2-2} S'''_k$ in the graph induced by $V \setminus F'''$; Properties \textbf{(n)}, \textbf{(o)}, and \textbf{(p)} hold when $a$ is replaced by $d$, $F$ is replaced by $F'''$, and the sets $S_k$ are replaced by $S'''_k$. \end{description} \item Let \begin{eqnarray*} Q &:=& N(u,i/2-1) \cup N(v,i/2-1) \cup \{y\} \\ && \cup N(a,i/2-2) \cup N(b,i/2-2) \cup N(c,i/2-2) \cup N(d,i/2-2). \end{eqnarray*} We perform BFS from $x$ in the graph induced by $V \setminus Q$ to expose $N_{V \setminus Q}(x,i/2-1)$. Make sure that the following properties hold (otherwise stop): \begin{description} \item[(t)] $N_{V \setminus Q}(x,i/2-1)$ expands well. %For all $j=1,2,\ldots,i/2-1$, $$|N_{V \setminus Q}(x,j)| =|S_{V \setminus Q}(x,j)|(1+O(1/d))=d^{j}(1+o(\log^{-1} n))$$ and for all $j=1,2,\ldots,i/2 - 2$, every vertex of $S_{V \setminus Q}(x,j)$ has $d(1+o(\log \log n / \log^{2} n))$ neighbours in $S_{V \setminus Q}(x, j+1)$. \item[(u)] There is no edge from $N_{V \setminus Q}(x,i/2-1) \setminus \{x\}$ to $Q$. \item[(v)] $N_{V \setminus Q}(x,i/2-1)$ is a tree. Note that since the remaining branches accessed by the edge $xa$ and the edge $xb$ are already guaranteed to be trees and there are no edges between different parts, this implies that $N(x,i/2-1)$ is a tree. \item[(w)] There is no edge between $x$ and $y$. \item[(x)] Let $R:=Q \cup N(x,i/2-1) \setminus \{y\}$. Properties \textbf{(t)}, \textbf{(u)}, and \textbf{(v)} hold when $x$ is replaced by $y$ and $Q$ is replaced by $R$. \end{description} \item It is the end of this tedious process so it is time for a short break---perform a fireworks show (fireworks are explosive pyrotechnic devices typically used for aesthetic, cultural, and religious purposes; here the main purpose is to celebrate finding an object with the desired properties). \end{enumerate} \bigskip We say that the process \textsc{Hyperbolicity}(u,v,x,y) \textbf{terminates successfully} if all the required conditions are satisfied, that is, the process does not stop prematurely before reaching the end. \begin{claim}\label{claim:correctness} If \textsc{Hyperbolicity}(u,v,x,y) terminates successfully for some four-tuple $u,v,x,y$, then $\delta_H(G) \geq i/2$. \end{claim} \begin{proof} By Property \textbf{(e)}, $N(u,i/2-1) \cup N(v,i/2-1) = \emptyset$, and there is no edge between $S(u,i/2-1)$ and $S(v,i/2-1)$. Hence, we have $d(u,v) \geq i$. In fact, the distance between $u$ and $v$ is exactly $i$, since by Properties $\textbf{(j)}$ and $\textbf{(k)}$ there is a path of length $i$ going through $x$. Next, by Properties $\textbf{(c)}$, $\textbf{(g)}$, $\textbf{(j)}$, $\textbf{(k)}$, $\textbf{(l)}$ and $\textbf{(m)}$, we have $d(u,x)=d(v,x)=d(u,y)=d(v,y)=i/2$. For the distance between $x$ and $y$ observe the following: first, by Properties $\textbf{(j)}$ and $\textbf{(l)}$ there is an $x-y$ path of length $i$ going from $x$ to $a$, then through $u$ to $c$, and then to $y$. We will show that $N(x,i/2-1) \cap N(y,i/2-1) = \emptyset$ and that there is no edge between $S(x,i/2-1)$ and $S(y,i/2-1)$. Indeed, if a shortest $x-y$-path first goes from $x$ to $a$, by Properties $\textbf{(o)}$, $\textbf{(r)}$, $\textbf{(s)}$ and $\textbf{(x)}$, it has to go until $S(a,i/2-2)$, and then it has to pass through at least two more edges before entering $S(y,i/2-1)$, including $S(c,i/2-2)$ and $S(d,i/2-2)$, and in each case the length is at least $i$. By properties $\textbf{(q)}$, $\textbf{(r)}$, $\textbf{(s)}$ and $\textbf{(x)}$, the same holds if the path starts from $x$ to $b$. If the path from $x$ neither goes through $a$ nor through $b$, it has to go through $N_{V \setminus Q}(x,i/2-1)$. By Properties $\textbf{(u)}$ and $\textbf{(x)}$, it has to arrive at $S(x,i/2-1)$, and then it has to go through at least two edges before entering $S(y,i/2-1)$, including $S(c,i/2-2)$ and $S(d,i/2-2)$, and in each case the length is also at least $i$. % a path from $x$ to $y$ not going through any of $\{a,b,c,d\}$ is of length at least $i$, since $y \notin N(x,i/2-1)$, $x \notin N(y,i/2-1)$ and there is no edge going between $S(x,i/2-1)$ and $S(y,i/2-1)$. Otherwise, % if the path goes through two vertices of say $N(u,i/2-1)$, $a$ and $c$, then, since $N(a,i/2-2)$ does not contain any edge to $S(u,i/2-1)$ or $S(v,i/2-1)$ unless it was already present, the path either has to go through $u$ (in which case its length is $i$), or it has to go from $x$ to $a$, then through $N(a,i/2-2)$, then through at least two more edges, then through $N(c,i/2-2)$, and then back to $y$, and hence its length is at least $i$. % If this path goes through exactly one of the vertices in the set $\{a,b,c,d\}$, say $a$, or it goes through two vertices, one in $N(u,i/2-1)$ and one in $N(v,i/2-1)$, say $a$ and $d$, then, any path going from $x$ to $a$, going then back to $y$ either goes through $u$ (in which case its length is more than $i$), or it goes from $a$ through $N(a,i/2-2)$, then it takes at least two more edges to enter $N(y,i/2-1)$ or $N(d,i/2-2)$, and then it either goes through $N(y,i/2-1)$ or it goes through $N(d,i/2-2)$ and then back to $y$ (in both cases its length is at least $i$). Hence, $d(u,v)+d(x,y)\geq 2i$, $d(u,x)+d(v,y)=d(u,y)+d(v,x)=i$, and thus, $\delta_H(G) \geq i/2$. The proof of the claim is finished. \end{proof} Thus, by Claim~\ref{claim:correctness}, in order to show that a.a.s.\ $\delta_H(G) \geq i/2$, it suffices to show that a.a.s. \textsc{Hyperbolicity}($u,v,x,y$) succeeds for at least one four-tuple of vertices $u,v,x,y$. Let $X_{u,v,x,y}$ be the indicator random variable defined as follows: $$ X_{u,v,x,y}=\begin{cases} 1, & \mbox{ if \textsc{Hyperbolicity}}(u,v,x,y) \mbox{ terminates successfully,}\\ 0, & \mbox{ otherwise. } \end{cases} $$ %Fix a partition (arbitrarily) of the $n$ vertices into $\lfloor n/2 \rfloor$ disjoint pairs (in the case of $n$ being odd the last vertex is discarded) and let $\mathcal{P}$ denote the set of the chosen pairs. Let $$ X=\sum_{u,v,x,y} X_{u,v,x,y}, $$ where the sum is taken over all $\binom{n}{4}$ $4$-tuples of all disjoint vertices. In order to prove that a.a.s. $\delta_H(G) \geq i/2$, we will apply the second moment method to $X$. Define $q=\exp(-d^{i-1}/(2n))$ and note that from the assumption that $d^{i-1} \leq \frac{1}{16}n \log n$ we have $q \geq n^{-1/32}$. \begin{lemma}\label{lem:firstmoment} For a fixed four-tuple of vertices $u,v,x,y$, $$\Prob{(X_{u,v,x,y}=1)} = \left( \frac {d^{i/2}}{2n} \right)^4q^{16} (1+o(1)). $$ Moreover, $$\E{X} = \frac{d^{2i}}{384}q^{16}(1+o(1)) = \Omega(n^{5/6}(\log n)^{4/3}).$$ \end{lemma} \begin{proof} Fix a four-tuple of vertices $u,v,x,y$. First, we will calculate $\Pr{(X_{u,v,x,y}=1)}$. We will estimate for each of the five steps of \textsc{Hyperbolicity}(u,v,x,y) the probability that it fails at that step. For $z \in \{a,b,\ldots,x\}$, let $P_z$ be the indicator random variable for the event that Property \textbf{(z)} succeeds provided that all previous properties have succeeded as well. Similarly, for step $z \in \{1,2,\ldots,5\}$, let $T_z$ be the indicator random variable for the event that step $z$ succeeds provided that all previous steps have succeeded as well. By Lemma~\ref{lem:expansion}(iii) and (iv), $$ \Prob{(P_a=1)}=1+o(1). $$ Let $E$ be the event that there is no edge within the last sphere $S_{V \setminus B}(u,i/2-1)$. By Lemma~\ref{lem:expansion}(v) and (vi), in order to calculate the probability that Property \textbf{(b)} holds, it remains to estimate the probability that $E$ holds. We have \begin{eqnarray} \Prob{(E)}&=&(1-p)^{\binom{|S_{V \setminus B}(u,i/2-1)|}{2}} \label{propE} \\ &=& \exp \left(-p(1+O(p)) \binom{|S_{V \setminus B}(u,i/2-1)|}{2} \right) \nonumber \\ &=&\exp\left(-p(1+O(p)) \left( \frac {(d^{i/2-1})^2}{2} (1+o(\log^{-1}n)) \right) \right) \nonumber, \end{eqnarray} where the last equality follows from Property \textbf{(a)} that is assumed to hold deterministically now. %$$ %|S_{V \setminus B}(u,i/2-1)|=d^{i/2-1} (1+o(\log^{-1}n)). %$$ %\begin{eqnarray} %|S_{V \setminus B}(u,i/2-1)| &=& |N_{V \setminus B}(u,i/2-1)| - |N_{V \setminus B}(u,i/2-2)| \nonumber \\ %&=& |N_{V \setminus B}(u,i/2-1)|(1+O(1/d)) \label{eq:SNcompare} \\ %&=&d^{i/2-1} (1+o(\log^{-1}n)). \label{eq:SNcompare2} %\end{eqnarray} Hence, % \pawel{I agree that the error term should be $(1+o(\log^{-1}n))$ to make sure that at the end we get $(1+o(1))$. However, if we only have $(1+o(1))$ in the exponent, it does not hurt us to much. We get $n^{-(1+o(1))/96}$ instead of $n^{-1/96}$ but this is not a big deal, right? We can just say at least $q$ and define $q$ to be $n^{-1/100}$. If we go for weaker concentration, then I think we can go down to $d \gg \log n$ which would be nice since it matches the result of Bela for the diameter. If you agree, then I would suggest to use weaker version for the lemma (provided that we do not need stronger somewhere else. Oh, I remember this now! We do need a concentration for the second moment method, right? We cannot afford to have o(1) in the exponent. OK. Let's leave it as is but keep in mind that for this part we still do not need to have concentration. I will try to remember it. } \begin{eqnarray*}\label{eq:EventE} \Prob{(E)}&=& \exp\left(-\frac{pd^{i-2}}{2} (1+o(\log^{-1} n)) \right) \\ &=& \exp\left( - \frac{d^{i-1}}{2n}(1+o(\log^{-1} n))\right) \\ &=& \exp\left (-\frac{d^{i-1}}{2n}\right) (1+o(1)) = q(1+o(1)), \end{eqnarray*} where the last line follows from the assumption that $d^{i-1} \leq \frac{1}{16}n \log n$. %\pawel{If you agree with the lemma, then it is not needed.} Let $E'$ be the event that no vertex in $S_{V \setminus B}(u,i/2-1)$ is adjacent to two vertices in $S_{V \setminus B}(u,i/2-2)$. We have %\begin{eqnarray*} %\Prob{(E')}&\geq&(1-p)^{|S_{V \setminus B}(u,i/2-2)||S_{V \setminus B}(u,i/2-1)|}\\ %&=&\omega \left( (1-p)^{\binom{|S_{V \setminus B}(u,i/2-1)|}{2}} \right)\\ % &=&\omega \left( \Prob{(E)} \right). %\end{eqnarray*} % All other events are clearly more likely. \pawel{keep from here?} Hence, the probability that $N_{V \setminus B}(u,i/2-1)$ is a tree is asymptotically equal to the probability that the event $E$ holds, and thus $$ \Prob{(P_b=1)}=q(1+o(1)). \\ $$ Now, let us move to Property \textbf{(c)}. By Lemma~\ref{lem:expansion}(ii) together with a union bound over all vertices in $N_{V \setminus B}(u,i/2-2)$, we see that with probability $$ 1-O(d^{i/2-2}d^{i/2}/n)=1-O(d^{i-2}/n)=1+o(1) $$ there is no edge from $N_{V \setminus B}(u,i/2-2)$ to $B$, and thus $$\Prob{(P_c=1)}=1+o(1).$$ Hence, $$ \Prob{(T_1=1)}=q(1+o(1)). $$ Next, for Property \textbf{(d)}, by Lemma~\ref{lem:expansion}(iii) and (iv), we obtain $$ \Prob{(P_d=1)}=1+o(1). $$ For Property \textbf{(e)}, since Property \textbf{(d)} is assumed to hold deterministically at this point, we have \begin{eqnarray*} \Prob{(P_e=1)}&=&(1-p)^{|S(u,i/2-1)||N_{V \setminus D}(v,i/2-1)|} \\ &=&(1-p)^{|S(u,i/2-1)||S_{V \setminus D}(v,i/2-1)|(1+O(1/d))} \\ &=&(1-p)^{(d^{i/2-1})^2 (1+o(\log^{-1} n))} \\ &=&\left(\exp\left( -p(1+O(p))\left( \frac{(d^{i/2-1})^2}{2}(1+o(\log^{-1} n)) \right) \right)\right)^2 \end{eqnarray*} and hence, by the same calculations following~\eqref{propE} we obtain $$ \Prob{(P_e=1)}=q^2(1+o(1)). $$ The probability of having Property \textbf{(f)} is calculated as before for Property \textbf{(b)}, and of having Property \textbf{(g)} as before for Property \textbf{(c)}. Thus, $$ \Prob{(T_2=1)} = q^3 (1+o(1)). $$ For Property \textbf{(h)} we immediately have by Lemma~\ref{lem:expansion}(vii) that $$ \Prob{(P_h=1)} = 1+o(1), $$ and the same applies to Property \textbf{(i)}. For Property \textbf{(j)}, since Property \textbf{(h)} is assumed to hold deterministically, we have \begin{eqnarray*} \Prob{(P_j=1)} &=& (1+o(1)) \frac {d^{i/2-1}}{2} p(1-p)^{(1+o(1))d^{i/2-1}} \\ &=& (1+o(1))\frac{d^{i/2}}{2n}\exp\left(-p(1+O(p))(1+o(1))d^{i/2-1}\right) \\ &=& (1+o(1))\frac{d^{i/2}}{2n}\exp\left(-(1+o(1))d^{i/2}/n\right) \\ &=& (1+o(1))\frac{d^{i/2}}{2n}\exp\left(-(1+o(1))(d^{i-1})^{1/2}\sqrt{d}/n\right) \\ &=& (1+o(1))\frac{d^{i/2}}{2n}, \end{eqnarray*} where the last line follows from the fact that $(d^{i-1})^{1/2} = O(\sqrt{n \log n})$ (by definition of $i$), and by~\eqref{eq:deg_bound}, which implies that $(d^{i-1})^{1/2}\sqrt{d}/n =O(\sqrt{d \log n/n})=o(1)$. Note then that Properties \textbf{(j)}, \textbf{(k)}, \textbf{(l)} and \textbf{(m)} are symmetric and mutually independent, and thus they are calculated in the same way. Therefore $$ \Prob{(T_3=1)} = \left(\frac{d^{i/2}}{2n}\right)^4(1+o(1)). $$ Let us move to investigating Properties \textbf{(n)}, \textbf{(o)}, and \textbf{(p)}. First, we perform BFS from $a$ in $V \setminus F$. It follows immediately from Lemma~\ref{lem:expansion}(iii) that $N_{V \setminus F}(a,i/2-2)$ expands well and so the bound on $|N_{V \setminus F}(a,i/2-2)|$ in Property \textbf{(n)} holds a.a.s. For the vertices in $S_k$, since Properties \textbf{(a)} and \textbf{(b)} are assumed to hold deterministically, for every even value of $k$ such that $2 \le k \le i/2-2$, the number of vertices in $S_k$ is $(1+o(1))d^{k/2}$. In order to deal with the second bound of Property \textbf{(n)} (and to investigate Properties \textbf{(o)} and \textbf{(p)} at the same time), we mimic the proof of Lemma~\ref{lem:expansion}(iii). We perform BFS from some other vertex in some $S_k$ in $V \setminus F$, updating the set $F$ every time a vertex is processed. As shown in Figure~\ref{PictureF2}, the vertex that was processed before, together with all its neighbours, will be added to $F$, and the next vertex in the queue to be processed will be taken out of $F$. Once we are done, we take the next vertex in some $S_k$ and continue in this way until all neighbourhoods under consideration are discovered. Arguing as in the proof of Lemma~\ref{lem:expansion}(iii), by Lemma~\ref{lem:expansion}(i) together with a union bound over all vertices processed, we obtain the desired bounds for the sizes of neighbourhoods. Moreover, by Lemma~\ref{lem:expansion}(ii) together with a union bound over all vertices that are discovered during this step (at most $O(d^{i/2-2})$ vertices), we get that a.a.s.\ at the time when a given vertex was processed there was no edge to already discovered vertices (neither within the same tree where we started BFS from, nor to other trees, nor to the initial set $F$). This deals with Properties \textbf{(o)} and \textbf{(p)}. Finally, it follows that a.a.s. $$%\label{eq:Sk} \sum_{k=1}^{i/2-2} \sum_{\ell \in S_k} |N_{V \setminus F}(\ell,i/2-2-k)| \leq \sum_{k=1}^{i/2-2} (1+o(1))d^{i/2-2-k/2} = o(d^{i/2-2} \log^{-1} n), $$ where the last equality follows from the fact that $d \gg \log^5 n/(\log \log n)^2$. Thus, $$ \Prob{(P_{n}=1 \textrm{ and } P_{o}=1 \textrm{ and } P_{p}=1)}=1+o(1). $$ The probabilities for Properties \textbf{(q)}, \textbf{(r)} and \textbf{(s)} to hold are calculated in exactly the same way as for Properties \textbf{(n)}, \textbf{(o)} and \textbf{(p)}, and hence $$\Prob{(T_4=1)}=1+o(1).$$ Finally, for $T_5$, when exposing $x$, Property \textbf{(t)} is investigated as before. Also, by analogous calculations as for $T_1$, the probability of having no edge to $Q$ (Property \textbf{(u)}) and the one of being a tree (Property \textbf{(v)}), altogether yield $q^5(1+o(1))$; note that the exponent of $5$ comes from the fact that $N_{V \setminus Q}(x,i/2-1)$ is a tree (giving one $q$), that there is no edge to $S(u,i/2-1)$ (giving $2$ additional factors of $q$), and no edge to $S(v,i/2-1)$ (giving another $2$ additional factors of $q$). Property \textbf{(w)} clearly also holds with probability $1+o(1)$. Similarly, when exposing $y$, we also have to consider the condition of having no edge to $N_{V \setminus R}(x,i/2-1)$ (Property \textbf{(x)}), giving us another factor of $q^2$, and thus yielding a probability of $q^7(1+o(1))$. Thus, \begin{eqnarray*} \Prob{(T_5=1)} &=& q^{12} (1+o(1)). \end{eqnarray*} Combining the events $T_1, T_2, \ldots,T_5$, we obtain \begin{eqnarray*} \Prob{(X_{u,v,x,y}=1)} &=& (d^{i/2}/(2n))^4q^{16} (1+o(1)), \end{eqnarray*} yielding the first part of the lemma. Observing that $i$ is such that $d^{i+1} > \frac{1}{16} n \log n$, and therefore $d^i > \frac{1}{16}n \log n/d$, and also using~\eqref{eq:deg_bound}, we obtain \begin{eqnarray*} \E{X}&= & \binom{n}{4}\left(\frac{d^{i/2}}{2n}\right)^4q^{16} (1+o(1)) \\ &=& \frac{d^{2i}}{384}q^{16}(1+o(1)) \\ &>& \frac{(\frac{1}{16}n\log n)^2}{384d^2}q^{16}(1+o(1)) \\ &=& \Omega(n^{3/2}(\log n/d)^2) \\ &=& \Omega(n^{5/6}(\log n)^{4/3}), \end{eqnarray*} which finishes the proof of the lemma. \end{proof} \bigskip We now move to the second moment method. \begin{lemma}\label{lem:secondmoment} $\E{X^2}=(1+o(1))(\E{X})^2$. \end{lemma} \begin{proof} In order to analyze the expected value of $X^2$ we will consider $8$ different cases. Note that $$ \E{X^2} = \sum_{u,v,x,y} \sum_{u',v',x',y'} \Prob{(X_{u,v,x,y}=1 \wedge X_{u',v',x',y'}=1)}, $$ where both sums range over all $4$-tuples of different vertices. For a fixed $4$-tuple of vertices $u,v,x,y$, it follows from the first part of Lemma~\ref{lem:firstmoment} that $$ \Prob{(X_{u,v,x,y}=1)} = (d^{i/2}/(2n))^4q^{16} (1+o(1)). $$ Conditioning on $X_{u,v,x,y}=1$, our goal is to investigate $\Prob{(X_{u',v',x',y'}=1 | X_{u,v,x,y}=1)}$. Note that the lower bound for $\E{X^2}$ trivially holds and so we aim for an upper bound. Therefore, we focus on properties that hold with probability $o(1)$ in the unconditional case (such as Property \textbf{(b)} that holds with probability asymptotic to $q$). We ignore properties that hold with probability $1+o(1)$ in the unconditional case (such as Property \textbf{(a)}) although it might happen that the probability that they hold in the conditional space is smaller (which clearly helps). Assume that $X_{u,v,x,y}=1$, and let $U$ be the set of vertices exposed to certify this, that is, \begin{eqnarray*} U &:=&N(u,i/2-1) \cup N(v,i/2-1) \cup N(x,i/2-1) \cup N(y,i/2-1) \\ && \cup N(a,i/2-2) \cup N(b,i/2-2) \cup N(c,i/2-2) \cup N(d,i/2-2). \end{eqnarray*} Since $X_{u,v,x,y}=1$, $|U|=O(d^{i/2-1})$. %We will make a case analysis below depending on whether $\{u,v,x,y\} \cap \{u',v',x',y'\} = \emptyset$ and whether $U$ intersects the $(i/2-1)th$-neighbourhoods of the second $4$-tuple $u',v',x',y'$. For $z \in \{u,v,x,y,a,b,c,d\}$, we always denote by $z'$ the vertex in \textsc{Hyperbolicity}$(u',v',x',y')$ corresponding to vertex $z$ in \textsc{Hyperbolicity}$(u,v,x,y)$. %We will show that Subcase a) of the first case below, \dieter{} \pawel{I do not think we actually show it. We say above that the lower bound holds trivially (you told me that ;-)) and so we just focus on the upper bound. It is true what you say but we actually do not show it. Well, I guess we show that all other cases are negligible so it implies (although implicitly) that the first subcase is the main contribution (not just part of this). Anyway, I would move it after Subcase b) and say that btw the main contribution is when `pictures are completely disjoint' (so technically it is a sub sub case of this sub case). Or maybe just say that we will show that all remaining cases are negligible and so this was the one that carries the main contribution.} \dieter{Yes, you are right, i will put this below} when $\{u',v',x',y'\} \cap U = \emptyset$ and moreover %\begin{eqnarray*} (N(u',i/2-1) \cup N(v',i/2-1) \cup N(x',i/2-1) \cup N(y',i/2-1) \\ %\cup N(a',i/2-2) \cup N(b',i/2-2) \cup N(c',i/2-2) \cup N(d',i/2-2)) \cap U =\emptyset, %\end{eqnarray*} %gives the dominant contribution to $X^2$. \smallskip Before we move to investigating cases, let us note that we may assume the following useful properties that will hold for all $4$-tuples of vertices $u,v,x,y$ with corresponding set $U$ a.a.s. \smallskip \textbf{Claim 1}: For a vertex $z' \notin U$, the number of edges between $N(z',i/2-1) \setminus U$ and $U$ is $O(\log n)$. \begin{proof} Indeed, we may assume that $|N(z',i/2-1) \setminus U| = O(d^{i/2-1})$ and so the expected number of edges between $N(z',i/2-1) \setminus U$ and $U$ is $O(pd^{i-2})=O(d^{i-1}/n)=O(\log n)$. It follows from Chernoff's bound that there exists some constant $C > 0$ such that the probability to have at least $C \log n$ edges of this type is $o(n^{-4})$. %It follows from Chernoff's bound that with probability $o(n^{-4})$there are at least $C \log n$ edges of this type, where $C$ is a large enough constant. The contribution of all such four-tuples $u',v',x',y'$ to $X^2$ is $o(1)$ and so can be safely ignored. \end{proof} \smallskip \textbf{Claim 2}: For a vertex $z' \notin U$, $|N(z',i/2-1) \cap U| = O(d^{i/4-1} \log n)$. \begin{proof} Indeed, suppose that there is an edge from $N(z',i/2-1) \setminus U$ to $U$. In fact, since $U$ is exposed during the BFS process, this edge has to be adjacent to a leaf $\ell$ of the graph induced by $U$. We need to estimate the size of $N(\ell, i/2-2) \cap U$, since vertices in $N(z',i/2-1) \cap U$ due to the existence of this edge form a subset of $N(\ell, i/2-2) \cap U$. From the fact that $U$ induces an almost regular tree, it follows that $|N(\ell, i/2-2) \cap U| = O(d^{i/4-1})$.The claim follows from the same Chernoff bound as in Claim~1. \end{proof} %\smallskip \textbf{Claim 3}: \pawel{Not clear if this is needed} For a vertex $z' \in U$, $z' \notin \{u,v,x,y\}$, $|N(z',i/2-1) \setminus U|=d^{i/2-1}(1+o(\log^{-1} n))$. %\begin{proof} %Since $U$ induces an almost regular tree and $z' \notin \{u,v,x,y\}$, we have that $|N(z',i/2-1) \cap U| = O(d^{i/2-2})$. The claim follows immediately, since we may assume that $|N(z',i/2-1)| = d^{i/2-1}(1+o(\log^{-1} n))$. %\end{proof} %\pawel{Now, this part can be removed, right?} First note that in order to have $X_{u',v',x',y'}=1$, in particular Properties \textbf{(a)}, \textbf{(d)}, \textbf{(t)} and \textbf{(x)} have to hold in the whole graph. Observe the following: whenever the $(i/2-1)$th neighbourhood of a vertex $z' \in \{u',v',x',y'\}$ that is not in $U$ is expanded, part of $N(z',i/2-1)$ might already be exposed in $U$. However, since $X_{u,v,x,y}=1$, the properties that hold for $U$ imply that the neighbourhoods of $u,v,x,y$ inside $U$ form trees with degrees around $d$. We will show then that for every vertex $z'$, the part of $S(z',i/2-1)$ that is already exposed is small. Indeed, if $z' \notin U$, then in order to touch $U$, $z'$ would have to be connected by an edge to a leaf of the graph induced by $U$. Note that, by Lemma~\ref{lem:expansion}(ii), the probability of having such an edge is $O(d^{i/2}/n)=o(n^{-1/4})$, and hence the probability of having more than $16$ edges \dieter{If you say $16$ edges is not correct, maybe we could say more than $16$ different leaves of $S(z',i/2-1)$?} is $o(1/n^4)$, so that the contribution of all such $4$-tuples $u',v',x',y'$ to $X^2$ can be safely ignored. Next, if one such edge is present, the part of $S(z',i/2-1)$ that is already exposed in the \pawel{why not referring to the graph induced by $U$?} \dieter{I want only $a$,$b$,$c$,$d$ here. rest is later} \pawel{Is there a reason to do it independently? If not, then we should do it in one shot. I do not see a difference whether you touch sphere of $a$ or $v$. Is there any?} \dieter{Well, the reason is that $a,b,c,d$ are smaller, and so a simple argument just taking into account total size of their neighborhoods is enough for them. However, feel free to modify if you want to have them below with the same argument}\pawel{I think this is all very confusing, and probably not 100\% correct. First I would observe that when there is an edge from $S(z',k)$ to $U$, then the part of $N(z',i/2-1)$ in $U$ is $O(d^{(i/2-1-k)/2})$, since the main contribution would be if we go up half steps and then go down (of course, use different language). Now it seems that you only care about $k=0$, that is, when there is an edge from $z'$ directly to $U$. I agree that we get the largest neighbourhood and we can assume that there are at most 16 edges of this type. But for, say, $k=1$ (edges from $S(z',1)$ to $U$), we get smaller contribution but we might have more edges, right? I guess we still expect $o(1)$ edges from `left' to `right' so perhaps we should just observe this and by Chernoff we might assume that it is at most $O(\log n)$ of them. Then we we could just focus on the main contribution which is for $k=0$. Anyway, I guess we get that in any case the part in $U$ is at most $O(d^{i/4-1} \log n)$ or something, which should be negligible. Even if everything is sitting as $u$-left then it is negligible so what is the point of doing this independently?}\dieter{Feel free to modify } neighbourhood of $N(a,i/2-2) \cup N(b,i/2-2) \cup N(c,i/2-2) \cup N(d,i/2-2)$ is, by the bound on their sizes, at most $O(1/d)$. Finally, for the part that is already exposed in say $N(u,i/2-1)$, after connecting by an edge to $S(u,i/2-1)$, an already exposed part has to come from going up $k$ layers in $N(u,i/2-1)$, and then going down at most $k$ layers, for $k=1,\ldots,i/4-2$. Thus, the number of vertices exposed is at most $O(d^{i/4})=|S(u,i/2-1)|O(1/d)$. For a fixed partition of the neighbours of $u'$ and $v'$, as needed in step 3 of \textsc{Hyperbolicity}$(u',v',x',y')$, the same argument (instead of applying it to $S(z',i/2-1)$ it is applied separately to both partitions of it) can be used to show that at most a $O(1/d)$-fraction of $u'$-left, $u'$-right, $v'$-left and $v'$-right vertices is already exposed in $U$. Therefore, all but a $O(1/d)$-fraction of $u'$-left, $u'$-right, $v'$-left and $v'$-right vertices are not yet exposed. In particular, since in order for $X_{u',v',x',y'}=1$ it is necessary that Properties \textbf{(b)}, \textbf{(e)}, \textbf{(f)}, \textbf{(u)}, \textbf{(v)} and \textbf{(x)} hold after having expanded the corresponding neighbourhoods in the subgraph excluding $U$. Since they are asymptotically equivalent of having no edges inside the last layer (between two last layers, respectively), these probabilities hold up to a $1+o(1)$ factor as before, and the same holds for Properties \textbf{(j)}, \textbf{(k)}, \textbf{(l)} and \textbf{(m)}. Now, we are ready for a case analysis. \bigskip \noindent \textbf{Case 1:} $\{u',v',x',y'\} \cap U = \emptyset.$ It follows from Claim 2 above that the part of the graph that needs to be exposed in order to check whether $X_{u',v',x',y'}=1$ intersects with $U$ only in a negligible way. It is straightforward to show that Properties \textbf{(b)}, \textbf{(e)}, \textbf{(f)}, \textbf{(u)}, \textbf{(v)} and \textbf{(x)}, as well as Properties \textbf{(j)}, \textbf{(k)}, \textbf{(l)} and \textbf{(m)} are up to a $1+o(1)$ factor independent of conditioning on $X_{u,v,x,y}=1$, and their calculations are as in Lemma~\ref{lem:firstmoment}. We obtain $$ \Prob{(X_{u',v',x',y'}=1 | X_{u,v,x,y}=1)} \leq (d^{i/2}/(2n))^4q^{16} (1+o(1))=\Prob{(X_{u,v,x,y}=1)}(1+o(1)). $$ Clearly, the number of choices of four-tuples $u,v,x,y$ and $u',v',x',y'$ is at most the square of the number of choices for $u,v,x,y$, so the contribution of this case is at most $(1+o(1))\E{X^2}$. (We will show that the contribution of all other cases is $o(\E{X^2})$ and so the contribution of this case is indeed $(1+o(1))\E{X^2}$.) %In this case first observe that by Lemma~\ref{lem:expansion} \dieter{I think it refers to the whole lemma, so no part needed} \textsc{Hyperbolicity}$(u',v',x',y')$ has in the graph excluding the vertex set $U$ up to a $(1+o(1))$ factor the same desired expansion properties as in the unconditional case. %\dieter{put this sentence earlier now}Since $X_{u,v,x,y}=1$, we know that $|U| \leq O(d^{i/2-1})$, and thus, by Lemma~\ref{lem:expansion}(iii), the sizes of the neighbourhoods of $u'$, $v'$, $x'$ and $y'$ in the graph whose vertex set is the whole vertex set excluding $U$ are asymptotically not affected. Observe that in order for $X_{u',v',x',y'}$ to be $1$, in particular \dieter{} it is necessary that Properties \textbf{(b)}, \textbf{(e)}, \textbf{(f)}, \textbf{(u)}, \textbf{(v)} and \textbf{(x)} hold after having expanded the corresponding neighbourhoods in the subgraph excluding $U$. All other properties have to hold as well, but since we aim for an upper bound only, we may focus on those properties that hold with probability $o(1)$ only. \pawel{I agree with (b) and probably also (e) but to get probability of (e) ($q$) we actually need to say something about the size of this sphere so it seems that we also need (a). So this is already a bit tricky (if we want to be perfect). Let me think for a sec... I guess it is not a big problem. There might be some edges to old part but still (a) has to hold and (e). So we may assume that (a) holds (we do not try to estimate the probability of (a), just prevent that we know it holds). Then we just want to estimate the probability that (e) holds. Some of the two sets we investigate might be `buried' inside the old part but only $O(d^{i/2-2})$ are inside, the rest is brand new or perhaps in the sphere of the old part) Hence, when we test (e) we still need to check exactly the same number of edges as before, right? We get the same probability as before ($q$ or so). Also, I am not sure why we need to look at (b). It holds a.a.s.\ so it is negligible for us. Perhaps we should concentrate on properties that hold with probability $o(1)$ only? It would make more sense to me (of course, other properties are assumed to hold).}\dieter{I want to concentrate on those that hold with probability $o(1)$ only, right. $b$ is one of these properties. } . Therefore, the probabilities of these properties to hold are up to a $(1+o(1))$ factor as in the unconditional case. Furthermore, since $x',y' \notin U$, Properties \textbf{(j)}, \textbf{(k)}, \textbf{(l)} and \textbf{(m)} are also up to a $(1+o(1))$ factor independent of conditioning on $X_{u,v,x,y}=1$, and their calculations are as in Lemma~\ref{lem:firstmoment}. The calculations of other properties to hold might change (in fact, as for example vertices $a$,$b$, $c$ or $d$ might be reused, the corresponding probabilities might change), but since they already hold with probability $1+o(1)$ in the unconditional case, and we only aim for an upper bound on $\E{X^2}$, we may safely ignore them. We obtain %$$ % \Prob{(X_{u',v',x',y'}=1 | X_{u,v,x,y}=1)} \leq (d^{i/2}/(2n))^4q^{16} (1+o(1))=\Prob{(X_{u,v,x,y}=1)}(1+o(1)), %$$ %and since clearly the number of choices of four-tuples $u,v,x,y$ and $u',v',x',y'$ is at most the square of the number of choices for $u,v,x,y$, the contribution of this case is at most $(1+o(1))\E{X^2}$.\\ \bigskip \noindent \textbf{Case 2:} $\{u',v'\} \cap U \neq \emptyset$ and $\{x',y'\} \cap U = \emptyset.$ Since $\{x',y'\} \cap U = \emptyset$, edges emanating from $x'$ and $y'$ are not exposed yet. Hence, the probabilities that Properties \textbf{(j)}, \textbf{(k)}, \textbf{(l)} and \textbf{(m)} hold are as in the unconditional case. Ignoring all other properties we get $$ \Prob{(X_{u',v',x',y'}=1 | X_{u,v,x,y}=1)} \le (d^{i/2}/(2n))^4 (1+o(1)) = O \left( \Prob{(X_{u,v,x,y}=1)} q^{-16} \right). $$ On the other hand, since at least one of $u',v'$ is in $U$, only a $$ O(|U|/n) = O(d^{i/2-1}/n) = O \left( \sqrt{\log n / (dn)} \right) = O(n^{-1/2} (\log^{-2} n) (\log \log n) ) = o(q^{16}) $$ fraction of four-tuples is considered here. Hence, the contribution of this case to $X^2$ is negligible. %Hence, all subcases where only a $O(d^{i/2-1}/n \log^5 n)$ \dieter{some log needed below, we see which} fraction of four-tuples is considered, can therefore safely be ignored, as by our choice of $q$, $O(\log^5 n (d^{i/2-1}/n) q^{-16})=o(1)$. This holds in particular for $u' \in U$ or $v' \in U$, no matter whether $\{u',v'\}=\{u,v\}$ or not. %Moreover, for $u' \notin U$, if $N(u',i/2-1) \cap U = \emptyset$, Properties \textbf{(j)} and \textbf{(l)} hold up to a $1+o(1)$ factor as in the unconditional case. Similarly, if $v' \notin U$, if $N(v',i/2-1) \cap U = \emptyset$, Properties \textbf{(k)} and \textbf{(m)} hold up to a $1+o(1)$ factor as in the unconditional case. Therefore, if both $N(u',i/2-1) \cap U = \emptyset$ and $N(v',i/2-1) \cap U = \emptyset$ hold, we may also ignore subcases where $x' \in U$ or $y' \in U$, no matter whether or not $x=x'$ or $y=y'$. \bigskip From now on we may assume that at least one of $x',y'$ has to be in $U$. \bigskip \noindent \textbf{Case 3:} $\{u', v'\} \cap U = \emptyset$, and $|\{x',y'\} \cap U|=1$. By symmetry, we may assume that $x' \in U$ and $y' \notin U$. Since $y' \notin U$, arguing as in the previous case, we get that Properties \textbf{(l)} and \textbf{(m)} hold with probability up to a $1+o(1)$ factor as in the unconditional case. However, it might happen that, say, $N(u',i/2-1) \cap U \neq \emptyset$ and Property \textbf{(j)} holds ``for free''. Intuitively, for this to happen, an edge joining $N_{V \setminus U}(u',i/2-1)$ and $U$ must occur at the right place, which happens with small probability. Moreover, only a small fraction of four-tuples satisfies $x' \in U$. %\dieter{remove following sentence? Otherwise I am afraid reader could think for a moment we are done with this case, just giving intuition}These observations are enough to show that the contribution from this case is negligible. More precisely, for Property \textbf{(j)} to hold ``for free'', we must have that $d(u',x')=i/2$, and so there must be an edge between $S_U(x',k)$ and $S_{V \setminus U}(u',i/2-1-k)$ for some $k = 0, 1, \ldots, i/2-1$. By the union bound, this happens with probability $$ O(i d^k d^{i/2-1-k} p) = O \left( \frac {d^{i/2}}{n} \cdot \frac {\log n}{\log \log n} \right), $$ since $i = O(\log n /\log \log n)$. (In fact, with a slightly more delicate argument one can remove the $\log n / \log \log n$ factor but this is not needed.) The same argument applies to Property \textbf{(k)}. (Recall, that we may assume that $N(u',i/2-1)$ and $N(v',i/2-1)$ are disjoint.) Hence, by considering only these four properties we get that \begin{eqnarray*} \Prob{(X_{u',v',x',y'}=1 | X_{u,v,x,y}=1)} &=& O \left( \left( \frac {d^{i/2}}{n} \right)^4 \left( \frac {\log n}{\log \log n} \right)^2 \right)\\ &=& O \left( \Prob{(X_{u,v,x,y}=1)} q^{-16} \left( \frac {\log n}{\log \log n} \right)^2 \right). \end{eqnarray*} On the other hand, since $x' \in U$, only a $$ O(|U|/n) = O(n^{-1/2} (\log^{-2} n) (\log \log n) ) = o(q^{16} (\log n / \log \log n)^{-2}) $$ fraction of four-tuples is considered here. Hence, the contribution of this case to $X^2$ is negligible. \bigskip \noindent \textbf{Case 4:} $\{u', v'\} \cap U = \emptyset$, and $|\{x',y'\} \cap U|=2$. Note that if $X_{u',v',x',y'}=1$ then, in particular, $d(x',y')=i$ and so the distance between $x'$ and $y'$ in the graph induced by $U$ is at least $i$. It follows that, for example, an edge between $s \in S_U(x',k)$ and $t \in S_{V \setminus U}(u',i/2-1-k)$ (for some $k = 0, 1, \ldots, i/2-1$) cannot make both Property \textbf{(j)} and Property \textbf{(l)} to hold, since that would imply that $d(x',y') \le d(x',s) + d(s,y') \le i-2$. %\pawel{remove? ``Note that Property \textbf{(j)} is concerned with a vertex at distance $i/2$ from $x'$, and Property \textbf{(l)} with a vertex at distance $i/2$ from $y'$. Hence, the sets of vertices explored for the two properties are except for possibly the vertices at distance $i/2$ of either of them disjoint, and no edge can be used for both properties at the same time.''} Hence the calculations dealing with $y'$ (related to Properties \textbf{(l)} and \textbf{(m)}) are independent of the calculations dealing with $x'$ (related to Properties \textbf{(j)} and \textbf{(k)}). Arguing as in the previous case, we get that $$ \Prob{(X_{u',v',x',y'}=1 | X_{u,v,x,y}=1)}= O \left( \Prob{(X_{u,v,x,y}=1)} q^{-16}(\log n / \log \log n)^4 \right). $$ Finally, note that only a $$ O( (|U|/n)^2 ) = o(1/n) = o(q^{16} (\log \log n / \log n)^4) $$ fraction of four-tuples is considered here, making the contribution of this case negligible. \bigskip From now on we may assume that at least one of $u',v'$ has to be in $U$ (and still at least one of $x',y'$). \bigskip \noindent \textbf{Case 5:} $|\{u', v'\} \cap U| = 1$, and $|\{x',y'\} \cap U|=1$. By symmetry, suppose that $u' \in U$, $v' \notin U$, $x' \in U$, $y' \notin U$. Since $y' \notin U$, as before, we get that Properties \textbf{(l)} and \textbf{(m)} hold with probability up to a $1+o(1)$ factor as in the unconditional case. Now, since $v' \notin U$, by the same calculations as in Case 3, the probability that Property \textbf{(k)} holds is at most $O \left( (d^{i/2}/n) \log n / \log \log n \right)$. Property \textbf{(j)}, however, might hold deterministically now, so we lose an additional factor of $O(d^{i/2}/n)$. By considering only Properties \textbf{(k)}, \textbf{(l)} and \textbf{(m)}, we get that \begin{eqnarray*} \Prob{(X_{u',v',x',y'}=1 | X_{u,v,x,y}=1)} &=& O \left( \left ( \frac{d^{i/2}}{n} \right)^3 \frac {\log n}{\log \log n} \right) \\ &=& O \left( \Prob{(X_{u,v,x,y}=1)} q^{-16} \frac{n}{d^{i/2}} \frac {\log n} {\log \log n} \right). \end{eqnarray*} On the other hand, since $u',x' \in U$, only a $$ O((|U|/n)^2) = O( (d^{i/2-1}/n) n^{-1/2} (\log^{-2} n) (\log \log n) ) = o( (d^{i/2}/n) q^{16} (\log \log n / \log n) ) $$ fraction of four-tuples is considered here, and so the contribution of this case to $X^2$ is negligible. \bigskip \noindent \textbf{Case 6:} $|\{u', v'\} \cap U| = 1$, and $|\{x',y'\} \cap U|=2$. By symmetry, suppose that $u' \in U$ and $v' \notin U$. By the same argument as in Case 4, the calculations involving Properties related to $x'$ are independent of those related to $y'$. Since $v' \notin U$, by the same calculations as in Case 3, the probability that Properties \textbf{(k)} and \textbf{(m)} both hold is at most $O \left( (d^{i/2}/n)^2 (\log n/\log \log n)^2 \right)$. This time, Properties \textbf{(j)} and \textbf{(l)} might hold deterministically, so we lose an additional factor of $O((d^{i/2}/n)^2).$ By considering only Properties \textbf{(k)} and \textbf{(m)} we get that $$ \Prob{(X_{u',v',x',y'}=1 | X_{u,v,x,y}=1)} = O \left( \Prob{(X_{u,v,x,y}=1)} q^{-16} \left( \frac{n}{d^{i/2}} \right)^2 \left( \frac {\log n} {\log \log n} \right)^2 \right). $$ On the other hand, since $u',x',y' \in U$, only a $$ O((|U|/n)^3) = O( (d^{i/2-1}/n)^2 n^{-1/2} (\log^{-2} n) (\log \log n) ) = o( (d^{i/2}/n)^2 q^{16} (\log \log n / \log n)^2 ) $$ fraction of four-tuples is considered here, and the contribution of this case to $X^2$ is negligible. \bigskip \noindent \textbf{Case 7:} $|\{u', v'\} \cap U| = 2$, and $|\{x',y'\} \cap U|=1$. By symmetry, suppose that $x' \in U$ and $y' \notin U$. Since $y' \notin U$, as before, we get that Properties \textbf{(l)} and \textbf{(m)} hold with probability up to a $1+o(1)$ factor as in the unconditional case. By considering only these two properties we get that $$ \Prob{(X_{u',v',x',y'}=1 | X_{u,v,x,y}=1)} = O \left( \Prob{(X_{u,v,x,y}=1)} q^{-16} \left( \frac{n}{d^{i/2}} \right)^2 \right). $$ %Properties \textbf{(j)} and \textbf{(k)}, however, might hold deterministically now, so we lose a factor of $\Theta((d^{i/2}/n)^2).$ On the other hand, since $u',v',x' \in U$, only a $$ O((|U|/n)^3) = O( (d^{i/2-1}/n)^2 n^{-1/2} (\log^{-2} n) (\log \log n) ) = o( (d^{i/2}/n)^2 q^{16} ) $$ fraction of four-tuples is considered here, and the contribution of this case to $X^2$ is negligible. \bigskip \noindent \textbf{Case 8:} $|\{u', v'\} \cap U| = 2$, and $|\{x',y'\} \cap U|=2$. %If $X_{u',v',x',y'} = 1$, then vertices $u',v',x',y'$ lie on an induced cycle of length $i$. This is a necessary condition only, of course, but this should be enough for us in this case. In the graph induced by $U$ there is only one such cycle. So we have $\Theta(\log n / \log \log n)$ four-tuples that satisfy this necessary condition. But this is less than expectation so we should be fine even with trivial bound of 1 for the probability. For any other four-tuple we need to make sure the cycles closes outside of $U$. Let's say there is a missing path connecting $u'$ and $x'$. To estimate probability of this event to happen, we expose $N(u',k)$ and $N(x',i/2-1-k)$ (for some $k$) and make sure there is at least one edge connecting neighbourhoods. We should get $O( (d^{i/2}/n) (\log n / \log \log n))$. I hope it is enough. \\ First, let us observe that in order to have $X_{u',v',x',y'} = 1$ the vertices $u',v',x',y'$ have to lie on an induced cycle of length $2i$ (of course, this is a necessary condition only). Moreover, note that there is only one such cycle in the graph induced by $U$ (namely, the one going through $u,v,x,y$). Hence, in order for this necessary condition to hold ``for free,'' all four vertices of $u',v',x',y'$ have to be on this cycle. Thus, there are only $(2i)^4=O( (\log n / \log \log n)^4 )=o(\E{X})$ such $4$-tuples of vertices, and this contribution is negligible. Otherwise, we observe that at least one edge of the cycle $u',v',x',y'$ is not yet present in the graph induced by $U$, say an edge on the path between $u'$ and $x'$. For this to happen, there must be an edge between $S(u',k)$ and $S(x',i/2-1-k)$ for some $k \in \{0,1, \ldots,i/2-1\}$ that is not yet exposed. By the same calculations as in Case 3, this happens with probability at most $$ O \left( \frac {d^{i/2}}{n} \cdot \frac {\log n}{\log \log n} \right). $$ Thus, $$ \Prob{(X_{u',v',x',y'}=1 | X_{u,v,x,y}=1)} = O \left( \Prob{(X_{u,v,x,y}=1)} q^{-16} \left( \frac{n}{d^{i/2}} \right)^3 (\log n / \log \log n) \right). $$ %Properties \textbf{(j)} and \textbf{(k)}, however, might hold deterministically now, so we lose a factor of $\Theta((d^{i/2}/n)^2).$ On the other hand, since $u',v',x',y' \in U$, only a $$ O((|U|/n)^4) = O( (d^{i/2-1}/n)^3 n^{-1/2} (\log^{-2} n) (\log \log n) ) = o( (d^{i/2}/n)^3 q^{16} (\log \log n/\log n)) $$ fraction of four-tuples is considered here, and the contribution of this case to $X^2$ is negligible. \end{proof} Using Lemma~\ref{lem:firstmoment} and Lemma~\ref{lem:secondmoment}, Theorem~\ref{thm:main2} follows now easily by Chebyshev's inequality. \section{Concluding remarks and open questions} We have shown that in $\mathcal{G}(n,p)$, for $p \gg \frac{\log^5 n}{n (\log \log n)^2}$ the hyperbolicity is (up to a possible difference of $1$) a monotone decreasing graph parameter. In general, since trees as well as cliques have hyperbolicity $0$, the hyperbolicity is not monotone, but we conjecture that in $\mathcal{G}(n,p)$ with $p$ above the threshold of connectivity, the same behavior holds. Intuitively, if $p$ is close to the threshold of connectivity, then $\mathcal{G}(n,p)$ a.a.s.\ contains a lot of long cycles, and there will not be many shortcuts, making the hyperbolicity of the graph large. After extending the definition of hyperbolicity to non-connected graphs by defining it as the maximum over all connected components, the situation is quite different. For $p < (1-\eps)/n$ for some $\eps > 0$, the hyperbolicity is $0$ a.a.s., but for $p > (1+\eps)/n$ for some $\eps>0$, the appearance of the giant component makes the hyperbolicity to tend to infinity a.a.s.\ (see also~\cite{sparse_graphs}). It would be interesting to investigate for which values of $p$ the hyperbolicity of $\mathcal{G}(n,p)$ is maximized, and what this value is. We also would like to know whether the hyperbolicity is monotone increasing up to its maximal value and then decreasing, or whether there are several ``peaks.'' \subsection*{Acknowledgements} The first author would like to thank David Coudert and Guillaume Ducoffe for helpful discussions. \begin{thebibliography}{10} \bibitem{book1} J.~Alonso, T.~Brady, D.~Cooper, T.~Delzant, V.~Ferlini, M.~Lustig, M.~Mihalik, M.~Shapiro, G.~Short. \newblock Notes on word hyperbolic groups. \newblock In: {\em E.~Ghys, A.~Haefliger, A.~Verjovsky (Eds.), Group Theory from a Geometrical Viewpoint}, World Scientific, Singapore, 1992. \bibitem{Bandelt1} H. J.~Bandelt, V.~Chepoi. \newblock 1-Hyperbolic graphs. \newblock {\em SIAM Journal on Discrete Mathematics}, 16(2) (2003), 323--334. \bibitem{Bandelt2} H.J.~Bandelt, H.M.~Mulder. \newblock Distance-hereditary graphs. \newblock {\em Journal of Comb. Th. Series B}, 41(2) (1986), 182--208. \bibitem{Benj1} I.~Benjamini. \newblock Expanders are not hyperbolic. \newblock {\em Israel J. Math}. 108 (1998), 33-36. \bibitem{d-reg} I.~Benjamini, C.~Hoppen, E.~Ofek, P.~Pra\l{}at, N.~Wormald. \newblock Geodesics and almost geodesic cycles in random regular graphs. \newblock {\em Journal of Graph Theory} 66 (2011), 115--136. \bibitem{Benj2} I.~Benjamini, O.~Schramm. \newblock Finite transitive graph embeddings into a hyperbolic metric space must stretch or squeeze. \newblock {\em Geometric aspects of functional analysis}, 123-136, Lecture Notes in Math., 2050, Springer, Heidelberg, 2012. \bibitem{boguna} M.~Boguna, D.~Krioukov, K.~Claffy. \newblock Navigability of complex networks. \newblock {\em Nature Physics}, 5:74--80, 2009. \bibitem{bol} B.\ Bollob\'{a}s. \newblock {\em Random Graphs}. \newblock {\em Cambridge University Press}, Cambridge, 2001. \bibitem{small-world} W.~Chen, W.~Fang, G.~Hu, M.W.~Mahoney. \newblock On the Hyperbolicity of Small-World and Treelike Random Graphs. \newblock {\em Internet Mathematics} 9(4): 434--491 (2013). \bibitem{book2} M.~Gromov. \newblock Hyperbolic groups. \newblock In: {\em ``Essays in group theory''. Edited by S. M. Gersten}, M. S. R. I. Publ. 8, Springer, 1987, 75--263. %\bibitem{bridson} M.R.~Bridson, A.~Haefliger, Metric Spaces of Non-Positive Curvature, Grundlehren der Mathematischen Wissenschaften vol. 319, Springer-Verlag, Berlin, 1999. \bibitem{Chepoi1} J.~Chalopin, V.~Chepoi, P.~Papasoglu, T.~Pecatte. \newblock Cop and Robber Game and Hyperbolicity. \newblock {\em Submitted}. Preprint available at http://arxiv.org/pdf/1308.3987v1.pdf. \bibitem{Chepoi1a} V.~Chepoi, B.~Estellon. \newblock Packing and covering delta-hyperbolic spaces by balls, \newblock {\em APPROX-RANDOM'07}, August 20-22, 2007, Princeton, USA. \bibitem{Chepoi2} V.~Chepoi, F.~Dragan, B.~Estellon, M.~Habib, Y.~Vaxes. \newblock Diameters, centers, and approximating trees of delta-hyperbolic geodesic spaces and graphs. \newblock {\em Symposium on Computational Geometry}, SoCG'2008, 59--68. \bibitem{Chepoi3} V.~Chepoi, F.~Dragan, B.~Estellon, M.~Habib, Y.~Vaxes, Y.~Xiang. \newblock Additive spanners and distance and routing labeling schemes for delta-hyperbolic graphs. \newblock {\em Algorithmica} 62 (2012), 713--732. \bibitem{Coudert} N.~Cohen, D.~Coudert, A.~Lancin. \newblock Exact and approximate algorithms for computing the hyperbolicity of large-scale graphs. \newblock {\em Submitted.} Preprint available at http://hal.inria.fr/hal-00735481. Also in: {\em Algorithme exact et approch{\'e} pour le calcul de l'hyperbolicit{\'e} d'un graphe, 15\`{e}mes Rencontres Francophones sur les Aspects Algorithmiques des T{\'e}l{\'e}communications (AlgoTel)}, Pornic, 2013. \bibitem{Coudert2} D.~Coudert, G.~Ducoffe. \newblock On the recognition of $\frac12$-hyperbolic graphs. \newblock {\em Submitted}. Preprint available at http://hal.inria.fr/hal-00937935. \bibitem{JLR} S.~Janson, T.~{\L}uczak, A.~Ruci\'nski.\newblock {\em Random graphs}. \newblock {\em Wiley}, New York, 2000. \bibitem{jonckheere} E.A.~Jonckheere, P.~Lohsoonthorn. \newblock Geometry of network security. \newblock {\em Amer.\ Control Conf., ACC}, 111--151 (2004). \bibitem{kleinberg} R.~Kleinberg. \newblock Geographic routing using hyperbolic space. \newblock In: {\em Proceedings of the 26th IEEE International Conference on Computer Communications}, 1902--1909, 2007. \bibitem{Munzner1} T.~Munzner, P.~Burchard. \newblock Visualizing the structure of the World Wide Web in 3D hyperbolic space. \newblock In: {\em Proceedings of the First Symposium on Virtual Reality Modeling Language}, 33--38, 1995. \bibitem{Munzner2} T.~Munzner. \newblock Exploring large graphs in 3D hyperbolic space.\newblock {\em IEEE Computer Graphics and Applications}, 18(4):18--23, 1998. \bibitem{sparse_graphs} O.~Narayan, I.~Saniee, G.~Tucci. \newblock Lack of spectral gap and hyperbolicity in asymptotic Erd\"{o}s-R\'{e}nyi random graphs.\newblock In: {\em Proceedings of the 5th International Symposium on Communications Control and Signal Processing (ISCCSP)}, 1--4, 2012. %\bibitem{bol_diameter} B.\ Bollob\'{a}s, The diameter of random graphs, \emph{Transactions of the American Mathematical Society}\ \textbf{267} (1981), 41--52. \end{thebibliography} \end{document} \newpage \pawel{Your old subcase b} \bigskip \noindent \textit{Subcase b:} $u' \notin U$, $v' \notin U$, and for some $w \in \{x',y'\}$, $w \in U$.\\ First, by the remarks before Case 1, Properties \textbf{(b)}, \textbf{(e)} and \textbf{(f)} hold up to a $1+o(1)$ factor with the same probability as before. Next, observe that if we want to have $X_{u',v',x',y'}=1$, there cannot be a vertex $z$ such that both $x'$ and $y'$ are in $N(z,i/2-1)$, as otherwise $d(x',y') < i$, and then the contribution to $X^2$ is $0$. Hence, we may assume (without loss of generality) that $x' \in N(z,i/2-1)$ for some vertex $z \in \{u,v,x,y\}$ or $x' \in N(z,i/2-2)$ for some vertex $z \in \{a,b,c,d\}$, and $y' \notin N(z,i/2-1)$ ($N(z,i/2-2)$, respectively). Therefore, the calculations involving edges to $y'$ are independent from the calculations involving edges to $x'$, and we may consider the calculations separately. Suppose now that $x' \in S(z,i/2-1 -k)$ for some $0 \leq k \leq i/2-2$ in the case $z \in \{u,v,x,y\}$ (or $x' \in S(z,i/2-2-k)$ for some $0 \leq k \leq i/2-3$ in the case $z \in \{a,b,c,d\}$, respectively). For Property \textbf{(j)} to hold, in order to to have $d(x',u')=i/2$, for some $k' \geq k$, there must be some vertex $r$ at distance $k'$ from $x'$, with $r \in S(z,i/2-1)$ in the case $z \in \{u,v,x,y\}$ ($r \in S(z,i/2-2)$ in the case $z \in \{a,b,c,d\}$, respectively), that is connected by an edge to some vertex at distance ${i/2-1-k'}$ from $u'$ (see also Figure~\ref{variance}). \begin{figure} \includegraphics[width=0.4\textwidth]{Variance.pdf} \vspace{-2cm} \caption{Possibilities for Property \textbf{(j)} to hold}\label{variance} \end{figure} Note that $r \in U$, and therefore the corresponding pairs of vertices between all vertices at distance $k'$ from $x'$ in $S(z,i/2-1)$ (or $S(z,i/2-2)$, respectively), to all vertices at distance $k'$ from $u'$ have not been exposed. The probability to have such an edge is at most \begin{eqnarray*} \sum_{k' \geq k} \Theta\left(|S(x',k')||S(u',i/2-1-k')|p\right) &=& \sum_{k' \geq k} \Theta(d^{k'-(k'-k)/2}d^{i/2-1-k'}d/n) \\ &=&\Theta(d^{i/2}/n \sum_{k' \geq k}d^{-(k'-k)/2}) = \Theta(d^{i/2}/n). \end{eqnarray*} Properties \textbf{(k)}, \textbf{(l)} and \textbf{(m)} are independent of Property \textbf{(j)}, and they are investigated in the same way. Hence, the probability that Properties \textbf{(j)}, \textbf{(k)}, \textbf{(l)} and \textbf{(m)} hold is $\Theta\left((d^{i/2}/n)^4\right)$, and thus of the same order as in the unconditional case. Finally, since $x' \in S(z,i/2-1-k)$ ($S(z,i/2-2-k)$, respectively), the first $k$ neighborhoods of $x'$ are already exposed when conditioning under $X_{u,v,x,y}=1$. However, since $k \leq i/2-2$ ($k \leq i/2-3$, respectively), the edges emanating from vertices in $S(x',i/2-2)$ are not yet exposed. In step (5) of the algorithm, instead of performing BFS from $x'$, we do the following: let $T_k' $ \dieter{we cannot use S, i guess - or should we?} for $k' \geq k$ the set of vertices at distance exactly $k'$ from $x'$, and such that they are in $S(z,i/2-1)$ in the case $z \in \{u,v,x,y\}$ ($S(z,i/2-2)$ in the case $z \in \{a,b,c,d\}$). We perform BFS from the vertices in $T_k'$ until we reach depth $i/2-1-k'$ from them. By a similar argument as in the remarks before Case 1, we also have that the exposed part of $S(x',i/2-1)$ in $U$ accounts for at most a $O(1/d)$-fraction of $|S(x',i/2-1)|$: if one wants to use an already exposed part, one has to go up at least one layer in the tree $S(z,i/2-1)$ (or $S(z,i/2-2)$, thereby losing again a factor of at least $\Omega(1/d)$. Once having left this tree, by the same argument as in the case $z' \notin U$, only a constant number of edges exist to connect back, and as before, also a factor of at most $O(1/d)$ is exposed. Hence when exposing the vertices at distance exactly $(i/2-1)$ of $x'$ in the subgraph excluding $U$, the size of $|S(x',i/2-1)|$ when restricted to the graph excluding $U$ is up to a $1-O(1/d)$ factor as in the unconditional case. Thus, by the remarks before Case 1, Properties \textbf{(u)} and \textbf{(v)} are thus up to a $(1+o(1))$ factor as in the unconditional case, and the same argument holds for $y'$ and Property \textbf{(x)}. Hence, $$ \Prob{(X_{u',v',x',y'}=1 | X_{u,v,x,y}=1)}=\Theta \left( \Prob{(X_{u,v,x,y}=1)} \right). $$ Using~\eqref{eq:deg_bound} and the definition of $i$, there are only $\Theta(d^{i/2-1})=\Theta((d^{i-1})^{1/2}\sqrt{d})=O(n^{2/3} (\log n)^{2/3})$ choices for $x'$. The same argument holds for $y'$. Hence, if $y' \notin U$, the total contribution of this case to $X^2$ is at most\dieter{no bound on $q$ required here} $$ O\left(n^3 (d^{i/2}/n)^4q^{16} n^{2+2/3}(\log n)^{2/3}(d^{i/2}/n)^4q^{16}\right) =o(\left( \E{X})^2 \right), $$ and if $y' \in U$, the total contribution is at most \dieter{no bound on $q$ required} $$ O\left(n^3 (d^{i/2}/n)^4q^{16} n^{1+4/3}(\log n)^{4/3}(d^{i/2}/n)^4q^{16}\right) =o(\left( \E{X})^2 \right), $$ and thus, both for $y' \in U$ and for $y' \notin U$, the contribution of this case does not affect the first order term of $\E{X^2}$. \bigskip \noindent \textit{Subcase c:} $x' \notin U$, $y' \notin U$, and for some $w \in \{u',v'\}$, $w \in U$.\\ As in Subcase b, there cannot be a vertex $z$ such that both $x'$ and $y'$ are in $N(z,i/2-1)$, as otherwise $d(u',v') < i$, and hence we may treat the calculations involving $u'$ and $v'$ separately. We may thus assume that $u' \in S(z,i/2-1-k)$ for $z \in \{u,v,x,y\}$ and $k \in \{0,\ldots,i/2-2\}$ (or $u' \in S(z,i/2-2-k)$ for $z \in \{a,b,c,d\}$ and $k \in \{0,\ldots,i/2-3\}$), and $v' \notin S(z,i/2-1)$ ($S(z,i/2-2)$, respectively). As in Subcase b, in step (1) of the algorithm, instead of performing BFS from $u'$, we do the following: let $T_k' $ for $k' \geq k$ the set of vertices at distance exactly $k'$ from $u'$, and such that they are in $S(z,i/2-1)$ in the case $z \in \{u,v,x,y\}$ ($S(z,i/2-2)$ in the case $z \in \{a,b,c,d\}$). We perform BFS from the vertices in $T_k'$ until we reach depth $i/2-1-k'$ from them, and by the arguments given in Subcase b, Properties \textbf{(b)}, \textbf{(e)} and \textbf{(f)} hold still with the same probability. For Properties \textbf{(j)}, \textbf{(k)}, \textbf{(l)} and \textbf{(m)} observe that edges emanating from $x'$ and $y'$ were not exposed, so the probabilities are as in the unconditional case. Similarly, Properties \textbf{(u)}, \textbf{(v)} and \textbf{(x)} are calculated as before, and hence $$ \Prob{(X_{u',v',x',y'}=1 | X_{u,v,x,y}=1)}=\Prob{(X_{u,v,x,y}=1)}(1+o(1)). $$ As there are only $\Theta(d^{i/2-1})=\Theta((d^{i-1})^{1/2}\sqrt{d})=O(n^{2/3} (\log n)^{2/3})=o(n)$ choices for $u'$, there are at most that many choices for the pair $u',v'$, and hence the contribution of this case to $\E{X^2}$ is negligible. \dieter{again here no bound on $q$ needed} \bigskip \noindent \textit{Subcase d:} for some $w \in \{u',v'\}$, $w \in U$, and for some $w \in \{x',y'\}$, $w \in U$.\\ As in Subcases b and c, there cannot be a vertex $z$ such that both $x'$ and $y'$ are in $N(z,i/2-1)$, and also, there cannot be a vertex $z$ such that both $u'$ and $v'$ are in $N(z,i/2-1)$. If there is no vertex $z$ such that two vertices out of $\{u',v',x',y'\}$ are in $N(z,i/2-1)$ (or $N(z,i/2-2)$ in the case of $z \in \{a,b,c,d\}$), the calculations are as before, and the contribution is negligible. Suppose therefore that there exists some vertex $z$ such that both $v',x'$ are in $N(z,i/2-1)$ ($N(z,i/2-2)$, respectively). In this case we do not worry about Properties \textbf{(b)}, \textbf{(e)}, \textbf{(f)}, \textbf{(u)}, \textbf{(v)} and \textbf{(x)} (in fact some of these might hold with higher probability). Now, since $u' \notin N(z,i/2-1)$, by the calculations as in Subcase b, the probability that Property \textbf{(j)} holds is still of the same order as in the unconditional case. Property \textbf{(k)}, however, might hold deterministically now, so we lose a factor of $\Theta(d^{i/2}/n).$ If there exists no other vertex $z_2$ \dieter{use $z'$ would be nice, but not according to the labels} such that $u'$ and $y'$ are in $N(z_2,i/2-1)$, then Properties \textbf{(l)} and \textbf{(m)} are of the same order as in the unconditional case. As there are only $\Theta(d^{i/2-1})$ choices for both $v'$ and $x'$, the total contribution of this case to $X^2$ is at most \dieter{here the needed condition is $q \gg n^{-1/32}$} $$ O\left(n^3 (d^{i/2}/n)^4q^{16} n (d^{i/2-1})^2(d^{i/2}/n)^3 \right) =o(\left( \E{X})^2 \right),$$ since by the definition of $i$ we have $d^{5i/2}/(nd)^2 \ll q^{16}d^{2i}/n=\Theta(\E{X})$. Similarly, if there exists some other vertex $z_2$ such that both $u'$ and $y'$ are in $N(z_2,i/2-1)$ ($N(z_2,i/2-2)$, respectively), Property \textbf{(l)} might hold deterministically, but Property \textbf{(m)} is still of the same order as in the unconditional case. By the same argument as before the total contribution of this case to $X^2$ is at most \dieter{condition on $q$ as before} $$ O\left(n^3 (d^{i/2}/n)^4q^{16} (d^{i/2-1})^3 (d^{i/2}/n)^2 \right) =o(\left( \E{X})^2 \right). $$ \\ \textbf{Case 2: $\{u,v\}=\{u',v'\}$:} \\ \textit{Subcase a: $\{x,y\} \cap \{x',y'\} = \emptyset.$}\\ In this case note that by the remarks before Case 1 that the probabilities for Properties \textbf{(j)}, \textbf{(k)}, \textbf{(l)} and \textbf{(m)} to hold are still up to a $(1+o(1))$ factor in the unconditional case. Not caring about other properties, we see that the contribution of this case to $X^2$ is at most $$ O\left(n^3 (d^{i/2}/n)^4q^{16} n^2 (d^{i/2}/n)^4 \right) =o(\left( \E{X})^2 \right), $$ since $q^{16}/n \geq n^{-13/12} \gg 1/n^2.$ \dieter{here $q \gg n^{-1/16}$ needed} \\ \textit{Subcase b: $x=x'$, and $y \neq y'$.}\\ Independently whether or not $y \in U$, Properties \textbf{(l)} and \textbf{(m)} are still of the same order as in the unconditional case. Not caring about other properties, the contribution of this case to $X^2$ is at most $$ O\left(n^3 (d^{i/2}/n)^4q^{16} n (d^{i/2}/n)^2 \right) =o(\left( \E{X})^2 \right), $$ since by the definition of $q$, by the definition of $i$ and using~\eqref{eq:deg_bound}, \dieter{here $q \gg n^{-1/24}(\log n)^{-1/24}$ needed} $$d^i q^{16}/n \geq d^i n^{-13/12} \geq n^{-1/12}(\log n/d) \geq n^{-5/12}(\log n)^{2/3} \gg 1/n.$$ \\ \textbf{Case 3: $\{u,v\} \cap \{u',v'\} = \emptyset$, $x=x'$.}\\ \textit{Subcase a: $u' \notin U$, $v' \notin U$, and if $y \neq y'$, also $y' \notin U$.}\\ Perform BFS from $u'$ and then from $v'$ as in the unconditional case. If no vertex in $N(u',i/2-2)$ and also no vertex in $N(v',i/2-2)$ is adjacent to a vertex in $U$, then Properties \textbf{(j)}, \textbf{(k)}, \textbf{(l)} and \textbf{(m)} are calculated as in the unconditional case. Not caring about other properties, we see that in this case the contribution to $X^2$ is for $y' \neq y$ at most $$ O\left(n^3 (d^{i/2}/n)^4q^{16} n^2 (d^{i/2}/n)^4 \right) =o(\left( \E{X})^2 \right), $$ since $q^{16}/n \gg 1/n^2$,\dieter{here $q \gg n^{-1/16}$ needed} and for $y' =y$, at most $$ O\left(n^3 (d^{i/2}/n)^4q^{16} n (d^{i/2}/n)^4 \right) =o(\left( \E{X})^2 \right). $$ If on the other hand there is a vertex in say $N(u',i/2-2)$ that is adjacent to a vertex in $U$, say in $S(u,i/2-1)$, then note that Property \textbf{(j)} might hold deterministically. However, for this to happen, either a vertex in $S(u',i/2-2)$ would have to connect to $a$, or a vertex $r \in S(u',k)$ for some $0 \leq k \leq i/2-4$ would have to be connected by an edge with a vertex $t \in S(u,i/2-1)$ whose distance to $a$ in the tree $N(u,i/2-1)$ is exactly $i/2-1-(k+1)$. The probability for such an edge to be present is at most $O(d^{i/2-2}p)+\sum_{k=0}^{i/2-4} O(d^k d^{1/2(i/2-2-k)}p)=O(d^{i/2-2}p)=O(d^{i/2-1}/n)$. Note that $O(d^{i/2-1}/n)=O(d^{i/2}/n)$, which is the corresponding probability of Property \textbf{(j)} to hold in the unconditional case. Note also that the part of $S(u,i/2-1)$ containing vertex $c$ can never be reached from $t$ in less than $i/2$ steps using edges from $N(u,i/2-1)$ only, and hence the probability for Property \textbf{(l)} to hold remains up to a $(1+o(1))$ factor unchanged from such an edge. The same also holds for Properties \textbf{(k)} and \textbf{(m)}, and thus, if there were more edges connecting to different parts of $U$, we can always bound the probability of each of the Properties \textbf{(j)}, \textbf{(k)}, \textbf{(l)} and \textbf{(m)} to hold by $O(d^{i/2}/n)$. For $y' \neq y$, the contribution to $X^2$ is thus at most \dieter{here $q \gg n^{-1/16}$ needed} $$ O\left(n^3 (d^{i/2}/n)^4q^{16} n^2 (d^{i/2}/n)^4 \right) =o(\left( \E{X})^2 \right), $$ and for $y'=y$, the contribution is at most \dieter{here weaker bound on $q$ needed} $$ O\left(n^3 (d^{i/2}/n)^4q^{16} n (d^{i/2}/n)^4 \right) =o(\left( \E{X})^2 \right). $$ \\ \textit{Subcase b: $u' \in U$, and if $y \neq y'$, then also $y' \notin U$.}\\ If $u' \in U$ and $v' \notin U$, assume w.l.o.g. that $u' \in N(u,i/2-1)$. If $u'$ is in the subtree that contains the vertex $a$, then Property \textbf{(j)} might hold deterministically. However, the probability for Property \textbf{(l)} to hold is up to a $(1+o(1))$ factor as in the unconditional case, since the path from $u'$ to the part of $S(u,i/2-1)$ containing $c$ (which is the part where $y'$ looks for a vertex $c'$) in $N(u,i/2-1)$ would have to go through $u$, and the distance inside $N(u,i/2-1)$ between $u'$ and any vertex in the part of $S(u,i/2-1)$ containing $c$ would be strictly bigger than $i/2-1$. For $y' \neq y$, the total contribution to $X^2$ is thus at most \dieter{here $q \gg n^{-1/16}$ needed} $$ O\left(n^3 (d^{i/2}/n)^4q^{16} n d^{i/2-1} (d^{i/2}/n)^3 \right) =o(\left( \E{X})^2 \right), $$ and for $y'=y$ it is at most $$ O\left(n^3 (d^{i/2}/n)^4q^{16} d^{i/2-1} (d^{i/2}/n)^3 \right) =o(\left( \E{X})^2 \right). $$ If both $u' \in U$ and $v' \in U$, say $u' \in N(u,i/2-1)$ and $v' \in N(v,i/2-1)$, then two out of the Properties \textbf{(j)}, \textbf{(k)}, \textbf{(l)} and \textbf{(m)} might hold deterministically. The contribution in the case $y' \neq y$ to $X^2$ is thus at most \dieter{here $q \gg n^{-1/32}(\log n)^{1/32}$ needed} $$ O\left(n^3 (d^{i/2}/n)^4q^{16} n d^{i/2-1} (d^{i/2}/n)^2 \right) =o(\left( \E{X})^2 \right), $$ and in the case $y'=y$ it is at most $$ O\left(n^3 (d^{i/2}/n)^4q^{16} d^{i/2-1} (d^{i/2}/n)^2 \right) =o(\left( \E{X})^2 \right). $$ \textit{Subcase c: $u' \notin U$, $v' \notin U$, $y \neq y'$, $y' \in U$.}\\ If both $u'$ and $v'$ are such that from their corresponding neighborhoods $N(u',i/2-2)$ and $N(v',i/2-2)$ there is no edge to $U$, Properties \textbf{(j)}, \textbf{(k)}, \textbf{(l)} and \textbf{(m)} are up to a $(1+o(1))$ factor as in the unconditional case, and the contribution to $X^2$ is at most \dieter{here $q \gg n^{-3/32}(\log n)^{1/2}$ needed} $$ O\left(n^3 (d^{i/2}/n)^4q^{16} n d^{i/2-1} (d^{i/2}/n)^4 \right) =o(\left( \E{X})^2 \right). $$ Otherwise, as in Subcase a), if a vertex in say $N(u',i/2-2)$ is adjacent to one vertex in $U$, say in $S(u,i/2-1)$, but no vertex in $N(v',i/2-2)$ is adjacent to a vertex in $U$, then Property \textbf{(j)} might hold deterministically, and also Property \textbf{(l)} might be deterministically implied. By the calculations of Subcase a), the probability for this to happen is $O(d^{i/2-2}p)=O(d^{i/2-1}/n)$, and the contribution of this case to $X^2$ is at most \dieter{here $q \gg n^{-1/16}$ needed} $$ O\left(n^3 (d^{i/2}/n)^4q^{16} n d^{i/2-1}(d^{i/2-1}/n) (d^{i/2}/n)^2 \right) =o(\left( \E{X})^2 \right). $$ Finally, if a vertex in $N(u',i/2-2)$ is adjacent to vertices in both $S(u,i/2-1)$ and $S(v,i/2-1)$ or if say a vertex in $N(u',i/2-2)$ is adjacent to a vertex in $S(u,i/2-1)$, and a vertex in $N(v',i/2-2)$ is adjacent to a vertex in $S(v,i/2-1)$, then all four properties \textbf{(j)}, \textbf{(k)}, \textbf{(l)} and \textbf{(m)} might hold deterministically, and the contribution of this case to $X^2$ is at most \dieter{here $q \gg n^{-1/32}$ is needed} $$ O\left(n^3 (d^{i/2}/n)^4q^{16} n d^{i/2-1}(d^{i/2-1}/n)^2 \right) =o(\left( \E{X})^2 \right). $$ \\ \textit{Subcase d: $u' \in U$, $y \neq y'$, $y' \in U$.} \\ If $u' \in U$, $v' \notin U$, and there is no edge from $N(v',i/2-2)$ to $U$, Properties \textbf{(k)} and \textbf{(m)} are still as in the unconditional case, and the contribution to $X^2$ is at most \dieter{here $q \gg n^{-1/16}$ is needed} $$ O\left(n^3 (d^{i/2}/n)^4q^{16} (d^{i/2-1})^2 (d^{i/2}/n)^2 \right) =o(\left( \E{X})^2 \right). $$ If $v' \notin U$, and there is an edge from $N(v',i/2-2)$ to $U$, then, as in Subcase c), Properties \textbf{(k)} and \textbf{(m)} might hold deterministically. This happens, as seen, with probability $O(d^{i/2-1}/n)$, and therefore the contribution to $X^2$ is at most \dieter{here $q \gg n^{-1/32} (\log n)^{1/2}$ is needed} $$ O\left(n^3 (d^{i/2}/n)^4q^{16} (d^{i/2-1})^2 (d^{i/2-1}/n) \right) =o(\left( \E{X})^2 \right). $$ Finally, if both $u' \in U$, say in $N(u,i/2-1)$, and $v' \in U$, say in $N(v,i/2-1)$, then as they are in different subtrees, at least one of them, say $u'$, is in the subtree which does not contain $y'$. Thus, either only the part of $S(u,i/2-1)$ containing $a$ or only the part of $S(u,i/2-1)$ containing $c$ are such that $u'$ is at distance exactly $i/2-1$ from them inside $S(u,i/2-1)$, but not both. Hence, one of the two Properties \textbf{(j)} and \textbf{(l)} is of the same order as in the unconditional case. Thus, the contribution of this case is at most \dieter{here $q \gg n^{-1/32} (\log n)^{1/2}$ is needed} $$ O\left(n^3 (d^{i/2}/n)^4q^{16} (d^{i/2-1})^2 (d^{i/2}/n) \right) =o(\left( \E{X})^2 \right). $$