\documentclass[a4paper]{article} \usepackage{e-jc} \specs{}{}{} % Please remove all commands that change parameters such as % margins or page sizes. % Packages amssymb and amsthm are already loaded. % We recommend these AMS packages: %\usepackage{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} % Theorem-like environments that are declared in the style file are: % theorem, lemma, corollary, proposition, fact, observation, claim, % definition, example, conjecture, open, problem, question, remark, note %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % If needed, include a line break (\\) at an appropriate place in the title. %\title{An elementary proof\\ of the reconstruction conjecture} % Input author, affiliation, address and support information as follows; % The address should include the country, but does not have to include % the street address. Give at least one email address. %\author{First Author\thanks{Supported by NASA grant ABC123.}\\ %\small Department of Inconsequential Studies\\[-0.8ex] %\small Solatido College\\[-0.8ex] %\small North Kentucky, U.S.A.\\ %\small\tt first.author@dis.solatido.edu\\ %\and %Some Second Author \qquad Some Third Author\\ %\small School of Hard Knocks\\[-0.8ex] %\small University of Western Nowhere\\[-0.8ex] %\small Somewhere, Australia\\ %\small\tt \{ssa,sta\}@uwn.edu.au} \usepackage{amsthm,amsmath,amssymb,enumerate,graphicx,psfrag,color} %\usepackage[notref,notcite]{showkeys} % comment for final version \theoremstyle{plain} \newtheorem*{claim*}{Claim} \newcommand{\kreis}[1]{\mathaccent"7017\relax #1} \newcommand{\charf}[1]{\raisebox{\depth}{\(\chi\)}_{#1}} \newcommand{\1}{{\rm 1\hspace*{-0.4ex}% \rule{0.1ex}{1.52ex}\hspace*{0.2ex}}} \newcommand{\bigO}{\ensuremath{O}} \newcommand{\comment}[1]{} %\newcommand{\comment}[1]{\footnote{{\bf Comment:} #1}} \newcommand{\N}{\mathbb N} \newcommand{\R}{\mathbb R} \newcommand{\Z}{\mathbb Z} \newcommand{\es}{\emptyset} \newcommand{\cP}{\mathcal{P}} \newcommand{\cQ}{\mathcal{Q}} \newcommand{\cK}{\mathcal{K}} \newcommand{\cL}{\mathcal{L}} \newcommand{\cA}{\mathcal{A}} \newcommand{\cB}{\mathcal{B}} \newcommand{\cC}{\mathcal{C}} \newcommand{\cG}{\mathcal{G}} \newcommand{\cS}{\mathcal{S}} \newcommand{\bP}{\mathbb{P}} \newcommand{\bE}{\mathbb{E}} \newcommand{\DGm}{\vec{G}_m} \newcommand{\UGm}{G_{\vec{m}}} \newcommand{\DGp}{\vec{G}_{p_0}} \newcommand{\UGp}{G_{\vec{p_0}}} \DeclareMathOperator{\ex}{ex} \DeclareMathOperator{\bin}{Bin} \DeclareMathOperator{\geo}{Geo} \DeclareMathOperator{\dist}{dist} \newcommand{\sm}{\setminus} \newcommand{\selfcite}[1]{$\!\!${\bf\cite{#1}}} \definecolor{red}{RGB}{255,0,0} \newcommand{\new}[1]{\textcolor{black}{#1}} \title{\new{Paths and cycles in random subgraphs\\ of graphs with large minimum degree}} \author{Stefan Ehard\\ \small Institut f\"ur Optimierung und Operations Reserach\\[-0.8ex] \small Universit\"at Ulm\\[-0.8ex] \small Ulm, Germany\\ \small\tt stefan.ehard@uni-ulm.de\\ \and Felix Joos\\ \small School of Mathematics\\[-0.8ex] \small University of Birmingham\\[-0.8ex] \small Birmingham, United Kingdom\\ \small\tt f.joos@bham.ac.uk} \date{} \begin{document} %%%%%%%%%%%%%METADATA%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Give the submission and acceptance dates in the format shown. % The editors will insert the publication date in the third argument. \dateline{Jan 20, 2017}{May 9, 2018}{XXX} % Give one or more subject codes separated by commas. % Codes are available from http://www.ams.org/mathscinet/freeTools.html \MSC{05C38, 05C80} % Uncomment exactly one of the following copyright statements. Alternatively, % you can write your own copyright statement subject to the approval of the journal. % See https://creativecommons.org/licenses/ for a full explanation of the % Creative Commons licenses. % % We strongly recommend CC BY-ND or CC BY. Both these licenses allow others % to freely distribute your work while giving credit to you. The difference between % them is that CC BY-ND only allows distribution unchanged and in whole, while % CC BY also allows remixing, tweaking and building upon your work. % % One author: %\Copyright{The author.} %\Copyright{The author. Released under the CC BY license (International 4.0).} %\Copyright{The author. Released under the CC BY-ND license (International 4.0).} % More than one author: %\Copyright{The authors.} %\Copyright{The authors. Released under the CC BY license (International 4.0).} \Copyright{The authors. Released under the CC BY-ND license (International 4.0).} \maketitle \begin{abstract} \noindent For a graph $G$ and $p\in [0,1]$, let $G_p$ arise from $G$ by deleting every edge mutually independently with probability $1-p$. The random graph model $(K_n)_p$ is certainly the most investigated random graph model and also known as the $G(n,p)$-model. We show that several results concerning the length of the longest path/cycle naturally translate to $G_p$ if $G$ is an arbitrary graph of minimum degree at least $n-1$. For a constant $c>0$ and $p=\frac{c}{n}$, we show that asymptotically almost surely the length of the longest path in $G_p$ is at least $(1-(1+\epsilon(c))ce^{-c})n$ for some function $\epsilon(c)\to 0$ as $c\to \infty$, and the length of the longest cycle is a least $(1-O(c^{- \frac{1}{5}}))n$. The first result is asymptotically best-possible. This \new{extends} several known results on the length of the longest path/cycle of a random graph in the $G(n,p)$-model \new{to the random graph model $G_p$ where $G$ is a graph of minimum degree at least $n-1$}. \end{abstract} \section{Introduction} Around 1960 Erd\H{o}s and Renyi proved the first results about random graphs -- especially about graphs on $n$ vertices where every possible edge is present independently with probability $p$, which is nowadays known as the $G(n,p)$-model. It is not an overstatement saying that this field has grown enormously since then and for numerous graph parameters the typical value is (precisely) known for large $n$. In particular, the lengths of paths and cycles are investigated. As for any $\epsilon>0$ and $p \geq \frac{(1+ \epsilon) \log n}{n}$ a.a.s.\footnote{\new{For a sequence of graphs $(G_i)_{i\in \N}$ and numbers $(p_i)_{i\in \N}$ in $[0,1]$, we say that the graph sequence has property ${\cal P}$ asymptotically almost surely (a.a.s.) if $\bP[(G_i)_{p_i}\in {\cal P}]\to 1$ as $i\to \infty$.}}~a graph in $G(n,p)$ is hamiltonian, we consider the length of a longest path/cycle if $p= \frac{c}{n}$ for some constant $c>1$. A~series of papers~\cite{AKS81,Bol82,BFF84,Veg79,Fri86} finally led to the following theorem, where $$\alpha(c)= \sup_{\alpha\geq 0}\Big\{G\in G(n,cn^{-1}) \text{ contains a path of length \new{at least} }\alpha n \text{ a.a.s.}\Big\}$$ and $\beta(c)$ analogously for the length of cycles. \begin{theorem}\label{thm:oldcycle} There exists a function $\epsilon(c) \rightarrow 0$ as $c \rightarrow \infty$ such that \begin{align*} \alpha(c),\beta(c)= 1-(1+\epsilon(c))ce^{-c}. \end{align*} \end{theorem} Let us consider a more general random graph model. For a graph $G$, we denote by $G_p$ the random subgraph obtained by deleting every edge independently with probability $1-p$ from the edge set of $G$. Thus $(K_{n})_p$ has the same distribution as $G(n,p)$. In this paper we consider the typical asymptotic behavior of $(G_k)_p$ instead of $(K_n)_p$ where $G_k$ is a simple graph of minimum degree at least $k$. In our setting $p$ depends on $k$ instead of the order of $G_k$. To be precise, we consider $p=\frac{c}{k}$ where $c>0$ and $k$ is large enough in terms of $c$. We denote by $\cG$ the set of all graph sequences $G_1,G_2,\ldots$ such that $G_k$ has minimum degree at least $k$. We define \begin{align*} \alpha'(c)= \inf_{(G_k)_{k\geq 1}\in \cG} \ \sup_{\alpha\geq 0}\Big\{(G_k)_{\frac{c}{k}}\text{ contains a path of length \new{at least} }\alpha k \text{ a.a.s.}\Big\} \end{align*} and $\beta'(c)$ analogously for cycles. It is clear that $\alpha'(c)\leq \alpha(c)$ and $\beta'(c)\leq \beta(c)$. We prove that there is essentially no difference between $\alpha'(c)$ and $\alpha(c)$ and our second contribution is a lower bound on $\beta'(c)$. \begin{theorem}\label{thm: path} There exists a function $\epsilon(c) \rightarrow 0$ as $c \rightarrow \infty$ such that \begin{align*} \alpha'(c)= 1-(1+\epsilon(c))ce^{-c}. \end{align*} \end{theorem} \begin{theorem}\label{thm: cycle} We have \new{$\beta'(c)=1-O(c^{- \frac{1}{5}})$ as $c\to\infty$.} %\begin{align*} % \beta'(c)=1-O\left(c^{- \frac{1}{5}}\right). %\end{align*} \end{theorem} Thus Theorem~\ref{thm: path} describes precisely the asymptotic behavior of $\alpha'(c)$ as $c \rightarrow \infty$ improving a result due to Krivelevich, Lee and Sudakov~\cite{KLS15} who showed that $\alpha'(c)=1-O(c^{- \frac{1}{2}})$. In addition, it \new{generalizes} the statement about paths in Theorem~\ref{thm:oldcycle}. %results concerning the length of the longest path in the $G(n,p)$-model due to %Ajtai, Koml{\'o}s and Szemer{\'e}di~\cite{AKS81}, %Fernandez de la Vega~\cite{Veg79}, %Bollob\'as~\cite{Bol82}, %Bollob\'as, Fenner and Frieze~\cite{BFF84}, and Frieze~\cite{Fri86}. Theorem~\ref{thm: cycle} improves a result of Krivelevich, Lee and Sudakov~\cite{KLS15} and Riordan~\cite{Rio14} implying $\beta'(c)=1-o(1)$. It also generalizes early results of the length of the longest cycle in the $G(n,p)$-model~\cite{AKS81,Veg79}. Note that the questions of hamiltonicity in the $G(n,p)$ setting naturally translates to the question whether $G_k$ has a cycle of length at least $k+1$. These extensions are successfully settled by Krivelevich, Lee and Sudakov~\cite{KLS15}, and by Glebov, Naves and Sudakov~\cite{GNS14}. We do not believe that the bound in Theorem~\ref{thm: cycle} is tight and conjecture that $\alpha'(c)=\beta'(c)$ holds. However, due to the different setting as in the $G(n,p)$-model, the construction of cycles is much more complicated as a graph of minimum degree at least $k$ can clearly have arbitrarily large girth. Thus any cycle in $G_p$ might be much larger than $k$ and is therefore difficult to detect. This may be one reason why the approach of Glebov, Naves and Sudakov in~\cite{GNS14} needs so much more effort and additional tools in comparison to a proof that shows the same threshold behavior in the $G(n,p)$-model. We think that a proof that describes the behavior of $\beta'(c)$ may be similarly complicated. In comparison to the approach in~\cite{GNS14}, the proof of Theorem~\ref{thm: cycle} is rather short. \section{Preliminaries}\label{sec:pre} We use standard notation. In particular, we denote the vertex set of a graph $G$ by $V(G)$. For a path $P$ and two vertices $u,v\in V(P)$, we denote by $uPv$ the subpath of $P$ with endvertices $u,v$. \bigskip We will frequently need to show that a binomial random variable is very close to its expected value and use for these purposes Chernoff's inequality. \begin{theorem}[Chernoff's inequality \cite{AS04}]\label{thm: cher} If X is a binomial distributed random variable with \mbox{$X\sim \bin\left(n,p\right)$} and $0<\lambda \leq np= \bE X$, then \begin{align*} \bP\left[|X-np|\geq\lambda\right]\leq 2e^{-\frac{\lambda^2}{3np}}. \end{align*} \end{theorem} Several results in this paper are based on the depth-first-search algorithm (DFS-algorithm) which is a frequently used exploration method of graphs. We briefly describe this algorithm and introduce some notation along the way. To the best of our knowledge, Krivelevich and Sudakov were the first who used this method in connection with random graphs~\cite{KS13}. This paper and~\cite{Rio14} present very nice and short proofs of previously known and new results. The DFS-algorithm is an algorithm traversing a graph such that all vertices of a given graph $G$ are finally visited and outputs a rooted spanning forest $T$ of $G$. It proceeds in the following way. At any step, there is a partition of the vertex set $V(G)$ into three sets $R$, $S$ and $U$. The set $U$ contains the vertices that have not yet been visited during the exploration, $R$ denotes the set of vertices whose exploration is complete, and all the remaining vertices that are currently under exploration are contained in~$S$. The vertices of $S$ are kept in a stack, which is a last-in-first-out data structure. The algorithm starts with $U=V(G)$ and $R=S=\emptyset$ and executes the following rounds (one round is the execution of (a) or (b)) until every vertex is explored, i.e. $R=V(G)$ and $S=U=\emptyset$. \begin{enumerate}[(a)] \item If $S=\emptyset$, then some unreached vertex $v$ in $U$ is moved to $S$. This vertex $v$ will be the root of a new component of our rooted spanning forest $T$. \item Otherwise, let $v$ be the top element of the stack $S$ (the \emph{last-in} vertex). The algorithm queries whether $v$ has some neighbor $w$ in $U$. If so, $w$ is placed on top of the stack $S$. If $v$ has no neighbor in $U$, it is completely explored and is moved to $R$. %\item As long as $U\neq \es$, the algorithm moves to the next round. \end{enumerate} In each round of the algorithm there is exactly one vertex moved either from $U$ to $S$ or from $S$ to $R$. So indeed, after $2|V(G)|$ rounds every vertex has been moved from $U$ to $R$ through $S$ and the algorithm terminates with a rooted spanning forest $T$. The following properties of the DFS-algorithm are important to us: \begin{enumerate}[(I)] \item\label{DFS1}Every positively answered query about a neighbor in $U$ increases the size of $R\cup S$ by exactly one. \item\label{DFS2}The set $S$ always spans a path in $T$. \item\label{DFS3}At any round of the algorithm, all possible edges between the set $R$ and $U$ have been queried and answered negatively. \item\label{DFS4}Every edge $e=uv$ of the graph $G$ which is not tested during the exploration of $G$ joins two vertices on some vertical path in the rooted spanning forest $T$ (because otherwise the algorithm would have queried the edge $uv$ during the exploration). %As a consequence, $u$ is either an ancestor or a descendant of $v$ in $T$. \end{enumerate} We will use the DFS-algorithm to explore the random graph $G_p$. Therefore, we assume that the algorithm already knows the underlying graph $G$ and all the edges of $G$. The DFS-algorithm only queries about these edges of $G$ during the exploration of $G_p$. That is, if the DFS-algorithm looks for neighbors of some vertex $v$, it only considers the neighbors $w$ of $v$ in $G$, and queries whether this vertex is also a neighbor of $v$ in $G_p$. We receive a positive answer of each such query independently with probability $p$. In this way, following this algorithm, we explore a rooted spanning forest of our random graph $G_p$. Note that by definition the answer of a query does not depend on the answers of the previous queries. We say an edge of $G$ is \emph{tested} if the DFS-algorithm queried whether this edge is in $G_p$ and otherwise we say it is \emph{untested}. Throughout the paper we consider graphs $G_k$ of minimum degree at least $k$. %Almost all our results include asymptotic statements %and an event occurs asymptotically almost surely (a.a.s.) if the probability that this event occurs tends to $1$ as \mbox{$k\to\infty$}. Several inequalities in our computations are only correct if $k$ is large enough. \new{For the purpose of readability we often drop the index $k$ and simple write $G$. Additionally, we leave out necessary roundings where it does not affect the argument.} \section{Long Cycles} In this section we prove Theorem~\ref{thm: cycle}. Let $G$ be a graph of minimum degree at least $k$ on $n$ vertices and let $p=\frac{c}{k}$ for $c$ sufficiently large and $k$ sufficiently large in terms of $c$. We consider a rooted forest $T$ which is an output of the DFS-algorithm described in Section~\ref{sec:pre}. We emphasize that every untested edge of $G$ is present in $G_p$ independently of $T$. This proof is based on ideas of Riordan~\cite{Rio14} and follows its strategy. In particular, the first two short lemmas naturally transfer to our setting. Note that he considers $p=\omega(k^{-1})$; that is, in our case $p$ is significantly smaller. As a consequence, in our case many smaller error quantities do not vanish as $k\to \infty$. Therefore, we carefully introduced a suitable hierarchy of these small quantities. Beside that a few new ideas are need to deal with a smaller edge probability $p$. The strategy of the proof is as follows. At first we show that for most of the vertices in $G$ almost all incident edges are not queried by the DFS-algorithm (Lemma~\ref{lem: tested edges} and~\ref{lem: all free}). By \eqref{DFS4}, all untested edges connect two vertices in the same component of $T$. Thus we may assume that there are not too many untested edges joining two vertices in distance at least $(1-5c^{-1/5})k$ in $T$. %\mymargin{Das mit dem $\epsilon$ ist mir hier auch aufgefallen. Eigentlich sogar: \emph{vertices in distance at least $(1-\new{5}c^{-1/5})k$ in $T$}. Vielleicht w\"urde ich diesen Satz mit dem danach vertauschen, denn die distance bezieht sich ja auf die distance im Pfad $P$.} Using this we show that $T$ contains a long root-to-leaf path $P$ with certain properties (Lemma~\ref{lem: heighthk} and~\ref{lem: longpath}). Finally, we use $P$ and all the untested edges that join two vertices on $P$ to find a long cycle in $G_p$. \begin{lemma}\label{lem: tested edges} During the DFS-algorithm on $G_p$ a.a.s.\ at most $\frac{2n}{p}=\frac{2nk}{c}$ many edges are tested. \end{lemma} \begin{proof} We run the DFS-algorithm on $G_p$. Note that the rooted spanning forest $T$ of $G_p$ has at most $n-1$ edges and that every positively answered query contributes an edge to our exploration of this forest. Let $X$ be the number of tested edges. \new{For a positive integer $\ell$, let $A_{\ell}$ be the event that out of $\ell$ queries at most $n-1$ are answered positively. %Let $X'$ be the number of positively answered queries of the first \new{$2n/p$} tested edges. %Thus, $X'$ is a binomial distributed random variable with $X'\sim \bin\left(\frac{2n}{p},p\right)$ %and $\bE X'=\frac{2n}{p}\cdot p=2n$. %By Chernoff's inequality, we obtain By comparison with a binomial distribution and using Chernoff's inequality, we obtain} \begin{align*} \bP\left[X>2n/p\right] \leq \bP\left[A_{2n/p}\right]\leq 2e^{-\frac{n}{3}}=o(1), \end{align*} which completes the proof. \end{proof} \bigskip \noindent From now on, let $\epsilon=c^{-1/5}$. \new{In view of the statement, we assume from now always that $\epsilon<10^{-4}$.} Let $E_u$ be the set of untested edges of $G$ during the DFS-algorithm. We call a vertex \emph{free} if it is incident with at least $(1-\epsilon)k$ untested edges in $E_u$. \begin{lemma}\label{lem: all free} A.a.s., at most $4\epsilon^4n$ vertices of the rooted forest $T$ \new{produced by the DFS-algorithm} are not free. \end{lemma} \begin{proof} Let $v\in V(T)$ be a vertex that is not free. Since the minimum degree of $G$ is at least $k$, the vertex $v$ is incident with at least $\epsilon k$ tested edges. Assume that there are more than $4\epsilon^4n$ vertices that are not free. Hence, we have more than $\frac{1}{2}4\epsilon^4n \cdot\epsilon k=\frac{2nk}{c}$ many tested edges in total. By Lemma~\ref{lem: tested edges}, the probability of this is $o(1)$, which implies the statement. \end{proof} Following the proof of Riordan~\cite{Rio14}, for a rooted forest $T$ and a vertex $v\in V(T)$, we introduce the following notation. \begin{itemize}%[(i)] \item Let $A(v)$ be the set of ancestors of $v$ in $T$ excluding $v$ and let $D(v)$ be the set of descendants of $v$ in $T$ excluding $v$. \item Let $A_i(v)$ and $D_i(v)$ be the sets of ancestors and descendants of $v$ at distance exactly $i$, respectively, and let $A_{\leq i}(v)$ and $D_{\leq i}(v)$ be the sets of ancestors and descendants of $v$ at distance at most $i$. \item The height of the vertex $v$ is defined as $\max\{i:D_i(v)\neq\emptyset\}$. \item For two vertices $u,v$, let $d(u,v)$ be the number of edges on a shortest $u,v$-path in $T$ if such a path exists, otherwise set $d(u,v)=\infty$. \item We say the vertex $v$ is \emph{up} if $|D(v)|\geq \epsilon k$. If this is not the case, then $v$ is \emph{down}. \item\label{heavy} We call the vertex $v$ \emph{skinny} if $|D_{\leq(1-5\epsilon)k}(v)|\leq (1-4\epsilon)k$. Let $Y$ denote the set of vertices in $T$ which are not skinny. \end{itemize} \begin{lemma}\label{lem: heighthk} If \new{a} rooted forest $T$ contains at most $5\epsilon^4n$ down vertices, then, for any constant $h\geq 1$, at most $6h\epsilon^3n$ vertices of $T$ are at height less than $hk$. \end{lemma} \begin{proof} We define the set $$\cS_1=\{ (v,w) : v\text{ is up, $v$ is at height at most $hk$, and }w\in D(v)\text{ is down}\}.$$ \new{As $A(w)$ forms a path,} every vertex $w$ which is down is contained in at most $hk$ pairs $(v,w)\in \cS_1$. Since there are at most $5\epsilon^4n$ down vertices, we conclude $|\cS_1|\leq 5hk\epsilon^4n$. As a vertex $v$ which is up and at height at most $hk$ is contained in at least $\epsilon k$ pairs $(v,w)\in \cS_1$, there are at most $5h\epsilon^3n$ such vertices. That is, at most $5h\epsilon^3n+ 5\epsilon^4n\leq 6h\epsilon^3n$ vertices in $T$ are at height less than $hk$. \end{proof} %For each up vertex $v\in V(T)$, %let $P(v)$ be a set of $\epsilon k$ descendants of $v$, %obtained by choosing vertices of $D(v)$ one-by-one starting with those with largest distance to $v$ in $T$. %For every $w\in P(v)$, we have $|D(w)|<|P(v)|=\epsilon k$, %because $D(w)\subsetneq P(v)$. %This implies that every vertex $w\in P(v)$ is down. %We define the set $\cS_1=\{ (v,w) : v\text{ is up and }w\in P(v)\}$. %Each up vertex $v$ appears in exactly $\epsilon k$ pairs $(v,w)\in \mathcal{S}_1$ and by the assumption of the lemma, %we have at least $(1-5\epsilon^4)n$ up vertices. %Hence, we obtain %\begin{align*} %|\mathcal{S}_1|\geq \left(1-5\epsilon^4\right)\epsilon kn. %\end{align*} %We consider the pairs $(v,w)\in \mathcal{S}_1$ that satisfy $d(v,w)\leq hk$. %For pairs $(v,w)\in \mathcal{S}_1$, %we conclude that $v\in A(w)$ and $w$ is down. %Note that each vertex has at most one ancestor at each distance, hence $|A_{\leq hk}(w)| \leq hk$. %Since we have at most $5\epsilon^4n$ down vertices, %this implies that there are at most $hk\cdot5\epsilon^4n$ pairs $(v,w)\in \mathcal{S}_1$ satisfying $d(v,w)\leq hk$. %Hence, if we consider the set \mbox{$\mathcal{S}_1^{'}=\left\{ (v,w) \in \mathcal{S}_1: d(v,w)>hk \right\}$}, then %\begin{align*} % |\mathcal{S}_1^{'}|&\geq |\mathcal{S}_1| -5h\epsilon^4kn\\ % &\geq \left(1-5\epsilon^4\right)\epsilon kn-5h\epsilon^4kn\\ % &\geq \left(1-6h\epsilon^3\right)\epsilon kn. %\end{align*} %Recall that each up vertex $v$ appears in exactly $\epsilon k$ pairs $(v,w)\in \mathcal{S}_1$, and since $\mathcal{S}_1^{'}\subset\mathcal{S}_1$, each such $v$ appears also %in at most $\epsilon k$ pairs $(v,w)\in\mathcal{S}_1^{'}$. %Hence, at least %\begin{align*} % \frac{\left(1-6h\epsilon^3\right)\epsilon kn}{\epsilon k}= % \left(1-6h\epsilon^3\right)n %\end{align*} %distinct up vertices $v$ appear in pairs $(v,w)\in\mathcal{S}_1^{'}$. %By the definition of $\mathcal{S}_1'$, each such vertex $v$ is at height at least $hk$, which completes the proof. %\end{proof} \begin{lemma}\label{lem: longpath} If \new{a} rooted forest $T$ contains at most $5\epsilon^4n$ down vertices and $X\subseteq V(T)$ such that $\vert X\vert\leq 5\epsilon^4n$, then, $T$ contains a vertical path $P$ of length at least $4k$ containing at most $\frac{1}{4}\epsilon k$ vertices in $X\cup Y$. \end{lemma} \begin{proof} Let $X$ be a subset of $V(T)$ of size at most $5\epsilon^4n$. First we show that the set $Y\subseteq V(T)$ is small enough for our purposes. (Recall that $Y$ denotes the set of vertices which are not skinny.) We define the set \begin{align*} \mathcal{S}_2=\{(v,w) : v\in A(w),~ d(v,w)\leq (1-5\epsilon)k \}. \end{align*} Since a vertex has at most one ancestor at any given distance, we conclude \begin{align*} |\mathcal{S}_2|\leq (1-5\epsilon)kn. \end{align*} By Lemma~\ref{lem: heighthk}, all but at most $6\epsilon^3n$ vertices $v$ are at height at least $k$ and thus, each such $v$ appears in at least $(1-5\epsilon)k$ pairs $(v,w)\in\mathcal{S}_2$. This contributes at least \begin{align}\label{eq:S2} (1-5\epsilon)(1-6\epsilon^3)kn \geq (1-5\epsilon)kn - 6\epsilon^3kn \end{align} pairs to the set $\mathcal{S}_2$. Any vertex which is not skinny contributes another $\epsilon k$ pairs to the lower bound \eqref{eq:S2}. As $|\mathcal{S}_2|\leq (1-5\epsilon)kn$, we conclude $|Y|\leq \frac{6\epsilon^3kn}{\epsilon k}= 6\epsilon^2n$. %Since $|\mathcal{S}_2|\leq (1-5\epsilon)kn$, %the number of vertices $v$ that appear in more than $(1-4\epsilon)k$ pairs $(v,w)\in \cS_2$ is at most $\left(1-5\epsilon\right) 6\epsilon^2n$, %as (if a vertex $v$ has appears in at least $(1-4\epsilon)k$ pairs $(v,w)$, then it contributes $\epsilon k$ more pairs to the lower bound given before) %\begin{align*} % \left(1-5\epsilon\right)\left(1-6\epsilon^3\right)kn+ % \left(1-5\epsilon\right) 6\epsilon^2n\cdot \epsilon k=\left(1-5\epsilon\right)kn, %\end{align*} %is an upper bound for $|\mathcal{S}_2|$. %By the definition of $\mathcal{S}_2$ %all vertices $v$ appearing in at most $(1-4\epsilon)k$ pairs $(v,w)\in \cS_2$ are skinny. %Hence, %\begin{align*} % |Y|\leq \left(1-5\epsilon\right) 6\epsilon^2n\leq 6\epsilon^2n. %\end{align*} \medskip Next we want to find the desired path $P$. We define the set \begin{align*} \mathcal{S}_3=\left\{(v,w)\colon w\in X\cup Y,~ v\in A(w),~d(v,w)\leq 4 k\right\}. \end{align*} Since a vertex has at most one ancestor at each distance, for a pair $(v,w)\in\mathcal{S}_3$, the vertex $w$ can appear in at most $4 k$ different pairs in $\mathcal{S}_3$. We obtain \begin{align*} |\mathcal{S}_3|&\leq 4k \cdot|X\cup Y|\\ &\leq 4k\cdot \left(5\epsilon^4n+ 6\epsilon^2n \right)\\ &\leq 25\epsilon^2kn. \end{align*} This implies that the number of vertices $v$ that can appear in more than $\frac{1}{4}\epsilon k$ pairs $(v,w)\in\mathcal{S}_3$, is bounded from above by \begin{align*} \frac{25\epsilon^2kn}{\frac{1}{4}\epsilon k}=100\epsilon n. \end{align*} By Lemma~\ref{lem: heighthk}, all but at most $24\epsilon^3n$ vertices of $T$ are at height at least $4k$ and from above follows that all but at most $100\epsilon n$ vertices $v$ appear in at most $\frac{1}{4}\epsilon k$ pairs $(v,w)\in\mathcal{S}_3$. Hence, for $c$ sufficiently large such that $\epsilon$ is small enough, there exists a vertex $v$ at height at least $4k$ that appears in at most $\frac{1}{4}\epsilon k$ pairs $(v,w)\in\mathcal{S}_3$. Let $P$ be the vertical path from $v$ to some vertex in $D_{4 k}(v)$. Then $P$ has length $4 k$ and by the choice of $v$, the path $P$ contains at most $\frac{1}{4}\epsilon k$ vertices in $X\cup Y$. \end{proof} \begin{proof}[Proof of Theorem~\ref{thm: cycle}] Recall, $G$ is a graph of minimum degree at least $k$ and $p=\frac{c}{k}$ for $c$ sufficiently large. We run the DFS-algorithm on $G_p$. Let $T$ be the spanning forest and let $E_u$ be the set of untested edges of $G$ that we obtain from this algorithm. By Lemma~\ref{lem: all free}, we may assume that all but at most $4\epsilon^4n$ vertices of $T$ are free, that is, incident with at least $(1-\epsilon)k$ untested edges. Due to property~(\ref{DFS4}) of the DFS-algorithm, for every untested edge $uv\in E_u$, either $u\in A(v)$ or $u\in D(v)$. Suppose we have \begin{align}\label{case1} \Big|\left\{u:uv\in E_u,~ d(u,v)\geq(1-5\epsilon)k\right\}\Big| \geq \epsilon k \end{align} for more than $\log k$ vertices $v$. This means, we can find at least $\epsilon k\log k$ untested edges $uv\in E_u$ in $G$ with $d(u,v)\geq(1-5\epsilon)k$. With probability $$1- (1- p)^{\epsilon k\log k}\leq 1- e^{-c^{4/5} \log k}= 1-o(1)$$ at least one of these edges present in $G_p$. Such an edge $uv$ forms together with the $u,v$-path in $T$ the desired cycle of length at least $(1-5\epsilon)k$ in $G_p$. Hence we may assume that for all vertices $v$ except for at most $\log k$, we have \begin{align}\label{case2} \Big|\left\{u:uv\in E_u,~d(u,v)\geq(1-5\epsilon)k\right\}\Big| < \epsilon k. \end{align} Let $V_0$ be the set of vertices $v$ that do not satisfy (\ref{case2}); that is, $|V_0|\leq \log k$. \begin{claim*} A.a.s., there are at most $5\epsilon^4n$ down vertices. \end{claim*} \begin{proof}[Proof of the claim:] \renewcommand{\qedsymbol}{$\blacksquare$} Assume that some vertex $v\in V(T)\setminus V_0$ is free and down. Since $|D(v)|<\epsilon k$ and $v$ is free, there are at least $(1-\epsilon)k-\epsilon k= (1-2\epsilon)k$ untested edges $uv\in E_u$ with $u\in A(v)$. Since each vertex has at most one ancestor at each distance, $v$ has at least $(1-2\epsilon)k-(1-5\epsilon)k=3\epsilon k$ ancestors $u$ with $uv\in E_u$ and $d(u,v)\geq(1-5\epsilon)k$, which is a contradiction as $v\notin V_0$. Therefore, no down vertex in $V(T)\setminus V_0$ is free. By Lemma~\ref{lem: all free}, a.a.s.\ all but $4\epsilon^4n$ vertices are free. Hence, at most \begin{align*} 4\epsilon^4n+|V_0|\leq 4\epsilon^4n+\log k\leq 5\epsilon^4n \end{align*} vertices are down\new{, where the last inequality holds for sufficiently large $k$ since $n\geq k$}. \end{proof} Thus we may apply Lemma~\ref{lem: longpath}, where $X$ is the union of $V_0$ and the set of vertices that are not free, that is, $|X|\leq 4\epsilon^4n+\log k\leq 5\epsilon^4n$ (Lemma~\ref{lem: all free}). Recall that $Y$ is the set of vertices that are not skinny. Let $P$ be the path of length $4k$ that is given by the Lemma~\ref{lem: longpath} and let $Z$ be the set of vertices of $V(P)\sm V_0$ that are free and skinny. By Lemma~\ref{lem: longpath}, we obtain \begin{align*} \big|V(P)\setminus Z\big| = \big|(X\cup Y)\cap V(P)\big| \leq \frac{1}{4}\epsilon k. \end{align*} For any vertex $v\in Z$, there are at least $(1-\epsilon)k$ untested edges $uv\in E_u$ with $u\in A(v)\cup D(v)$. We want to show that there are sufficiently many of these vertices $u$ in $A(v)$. Since $v\in Z$ implies $v\notin V_0$, at least $(1-2\epsilon)k$ of these vertices $u$ with $uv\in E_u$ satisfy $d(u,v)\leq(1-5\epsilon)k$. Moreover, as $v$ is skinny, at least $(1-2\epsilon)k-(1-4\epsilon)k=2\epsilon k$ vertices $u$ must be ancestors of $v$ with $d(u,v)\leq(1-5\epsilon)k$. We define a set of ancestors of $v$ within a certain distance, namely \begin{align*} B(v)=\{u\in A(v): uv\in E_u,~ \epsilon k\leq d(u,v)\leq(1-5\epsilon)k\}. \end{align*} Again, since $v$ has only one ancestor at each distance, we obtain $|B(v)|\geq \epsilon k$. Let $u_1\in V(P)$ be the vertex on the path $P$, which is at height $k$ in $P$. Let $V_1$ be the set of the first descendants of $u_1$ on $P$, such that $\big|V_1\cap Z\big|\geq \log k$. Since $|V(P)\setminus Z| \leq \frac{1}{4}\epsilon k$, we have \begin{align*} V_1\subseteq D_{\leq\frac{1}{4}\epsilon k+\log k}(u_1) \cap V(P). \end{align*} For each of these vertices $v\in V_1\cap Z$, we have $|B(v)|\geq \epsilon k$. Hence, there are at least $\epsilon k\log k$ untested edges $uv\in E_u$ such that $v\in V_1\cap Z$ and $u\in B(v)$. With probability at least $1- (1- p)^{\epsilon k\log k} = 1-o(k^{-1})$ one of these edges is present. Let $v_1u_2$ be one of it such that $v_1 \in V_1$, $u_2\in B(v_1)$. Assume for some $i\geq 2$ we have defined vertices $v_1,u_1,v_2,u_2,\ldots,u_{i-1},u_i$ that appear in this bottom-to-top order on $P$ such that \begin{itemize} \item $v_ju_{j+1}\in E(G_p)$, \item $u_{j+1}\in B(v_j)$, \item $v_j\in D_{\leq\frac{1}{4}\epsilon k+\log k}(u_j)$ and $|V(u_jPv_j)\cap Z|\leq 1+ \log k$ for all $1\leq j\leq i-1$, and \item $d(u_1,u_i)\leq 2k$ \new{where $d(u,v)$ denotes the distance between two vertices $u,v$ in $T$.} \end{itemize} Next we show how to define $v_i$ and $u_{i+1}$. Let $V_i$ be the set of the first descendants of $u_i$ on $P$ such that $|V_i\cap Z|\geq \log k$. Thus for every vertex $w\in V_i$, we have $d(w,u_{i-1})\geq \epsilon k -\frac{1}{4}\epsilon k - 2\log k > \frac{\epsilon}{2}k$. Again, as $\big|V_i\cap Z\big|\geq \log k$, there is an edge $v_iu_{i+1}$ present in $G_p$ with $v_i\in V_i$ and $u_{i+1}\in B(v_i)\subseteq V(P)$ with probability $1-o(k^{-1})$. %Let $V_2$ be the set of the first descendants of $u_2$ on $P$ %such that $|V_2\cap Z|\geq \log k$. %Thus for every vertex $w\in V_2$, %we have $d(w,u_1)\geq \epsilon k -\frac{1}{4}\epsilon k - 2\log k > \frac{\epsilon}{2}k$. %Again, as $\big|V_2\cap Z\big|\geq \log k$, %and there is an edge $v_2u_3$ present in $G_p$ with $v_2\in V_2$ and $u_3\in B(v_2)$ with probability $1-o(k^{-1})$. %Next, let $V_3$ be the set of the first descendants of $u_3$ on $P$ such that $\big|V_3\cap Z\big|\geq \log k$. We may continue this iterative procedure to find such edges $v_ju_{j+1}$ until we reach a vertex $u_{i+1}$ with $d(u_1,u_{i+1})>2k$. Since $d(u_j,u_{j+1})>\frac{1}{2}\epsilon k$, this implies $i\leq 4\epsilon^{-1}$. Thus the procedure does not fail with probability $1-o(\epsilon^{-1} k^{-1})=1-o(1)$. %Note that we also remain within the path $P$, since $P$ has length at least $4k$ and we start at most at height $k$ and with each step we go up at most $(1-5\epsilon)k$. Suppose $i$ is even. Consider the following cycle $C$ obtained by the concatenation of the following paths: \begin{align*} &v_1u_2, u_2Pv_3, v_3u_4, u_4Pv_5,v_5u_6,u_6Pv_7 \ldots \\ &v_{i-1}u_{i},u_{i}Pu_{i+1}, u_{i+1}v_{i}, v_{i}Pu_{i-1}, u_{i-1}v_{i-2}, v_{i-2}Pu_{i-3}, \ldots \\ &u_3v_2, \new{v}_2Pv_1. \end{align*} %Note that every vertex in $V(P)\sm V(v_1Pu_{i+1})$ is contained in some $V_j$. \new{Note that the number of vertices of $V_1\cup\ldots\cup V_i$ that are not contained in $C$ is at most $|V(P)\setminus Z|+i\log k\leq \frac{1}{4}\epsilon k +4\epsilon^{-1}k$. Since $d(u_1,u_{i+1})>2k$, the length of $C$ is at least \begin{align*} 2k - \frac{1}{4}\epsilon k- 4\epsilon^{-1}\log k>k. \end{align*} } A similar argument applies if $i$ is odd. \end{proof} \section{Long Paths and the DFS-algorithm} Before we prove Theorem~\ref{thm: path}, in we cite and prove some results for later use. The first one uses a nice and direct analysis of the DFS-algorithm. \begin{lemma}[Krivelevich, Lee, Sudakov~\cite{KLS15}]\label{lem: bippath} Let $p=\frac{c}{k}$ for $c$ sufficiently large, and let $G$ be a graph of minimum degree at least $k$. If $G$ is bipartite, then $G_p$ a.a.s.\ contains a path of length $\left(2-6c^{-1/2}\right)k$. \end{lemma} The next lemma is of a similar flavor as the last one. We suitably modify a result of~\cite{KLS15} for our purposes. \begin{lemma} \label{lem: logk-starting-path} Let $p=\frac{c}{k}$ for $c$ sufficiently large, and let $G$ be a graph of minimum degree at least $k$. If $V_0\subseteq V(G)$ with $|V_0|\geq \log k$, then $G_p$ $a.a.s.$ contains a path of length $\left(1-2c^{-1/2}\right)k$ which starts at a vertex in $V_0$. \end{lemma} \begin{proof} Let $\epsilon=c^{-1/2}$. Let $V_0\subseteq V(G)$, and we may assume that $|V_0|=\left\lceil\log k\right\rceil$. We modify the DFS-algorithm as follows. Recall that the stack $S$ denotes the vertices that are currently under exploration. If $S=\es$ in some step of the algorithm, then as long as possible we select a vertex of $V_0\cap U$ as the new root of a component and put it onto the stack $S$. %Moreover, if we are currently exploring the component of with root $v\in V_0$, %then we forbid the use of edges incident to the set $V_0\setminus\left\{v\right\}$. Hence, by this modified DFS-algorithm, at least up to the point when we explored $\log k$ vertices, the root of the current component is in $V_0$. We stop this modified DFS-algorithm when we reach $|R\cup S|=(1-\epsilon)k$. Let $\cA$ be the event that $S=\emptyset$ at some moment after $\frac{1}{2}\log k$ steps of the algorithm and let $\cB$ be the event that there are less than $(1-\epsilon)k$ positive answers among the first $\frac{k}{p}=\epsilon^2k^2$ tested edges. \begin{claim*}\label{cla: all fine} $\bP[\cA\cup \cB]=o(1).$ \end{claim*} Assuming this claim we can a.a.s.\ find a path of length $(1-\epsilon)k$ starting in a vertex of $V_0$ as follows. Suppose neither $\cA$ nor $\cB$ holds. Consider the step of the DFS-algorithm at which we reach $|R\cup S|=(1-\epsilon)k$. Thus the root of the current component is contained in $V_0$, as $\cA$ does not hold. Due to property (\ref{DFS1}) such a step exists. Recall that the vertices in $S$ form a path (property (\ref{DFS2})). If $|S|\geq(1-2\epsilon)k$, then the statement of the lemma follows directly. Thus, we may assume that \begin{align}\label{S small} |S|<(1-2\epsilon)k \end{align} which implies $|R|>\epsilon k$. Moreover, each vertex in $R$ has at least $k-|R\cup S|\geq \epsilon k$ neighbors in $G$ in the set of unreached vertices $U$. Due to property (\ref{DFS3}), all these edges between $R$ and $U$ have been queried and answered negatively. Hence at least $|R|\cdot \epsilon k>\epsilon^2 k^2$ queries are answered negatively and less than $(1-\epsilon)k$ are answered positively. Thus $\cB$ holds, which is a contradiction. We complete the proof of the lemma by the proof of claim. For a positive integer $i$, let $\cA_i$ be the event that we complete exploring a component when $|R|=i$. Since every vertex has degree at least $k$, in this moment of the algorithm every vertex in $R$ has at least $k-i\geq \epsilon k$ neighbors in $U$ (for $i\leq (1- \epsilon) k$) and all these edges are queried negatively. Thus we queried at least $i \epsilon k$ edges in total, and had at most $i$ positive answers. The probability that this occurs is at most the probability that a binomial distributed random variable $X_i$ with $X_i\sim\bin( i\epsilon k, p)$ is at most $i$. Hence $\bE X_i = i\epsilon c=ic^{1/2}$. By Chernoff's inequality, we obtain \begin{align*} \bP[\cA_i] \leq\bP[X_i\leq i] \leq \bP\left[\Big|X_i- ic^{1/2}\Big|\geq \frac{ic^{1/2}}{2}\right] \leq 2e^{-\frac{ic^{1/2}}{12}} \leq \frac{1}{2^i}. \end{align*} Using the union bound leads to the desired result \begin{align*} \bP[\cA] \leq\bP\left[\bigcup\limits_{i=\frac{1}{2}\ln k}^{(1-\epsilon)k}\cA_i\right] \leq \sum_{i=\frac{1}{2}\ln k}^{(1-\epsilon)k} \bP[\cA_i] \leq \sum_{i=\frac{1}{2}\ln k}^{(1-\epsilon)k}\frac{1}{2^i} =o(1). \end{align*} An upper bound for the event $\cB$ follows by a direct applications of Chernoff's inequality. Let $Y$ be a binomial distributed random variable with $Y\sim\bin\left(\frac{k}{p},p\right)$. Then, \begin{align*} \bP[\cB] \leq\bP[Y\leq (1-\epsilon)k] \leq 2\exp\left(-\frac{\epsilon^2 k}{3}\right)=o(1). \end{align*} This implies $\bP[\cA\cup \cB]=o(1)$, which completes the proof of the claim and thus the proof of the lemma. \end{proof} \section{Long Cycles in Pseudo-Cliques}\label{sec:pseudo-clique} Consider the well-known $G(n,p)$-model and with our notation $(K_n)_p$. It is very natural and intuitive that $(K_n)_p$ and $H_p$ typically have the same properties if $H$ is a graph on $n$ vertices which is almost a clique. In this section we indicate that a result of Frieze~\cite{Fri86} can be suitably modified. Let $\gamma>0$ be a constant sufficiently small, \new{say $\gamma<10^{-5}$}. We call a graph $G$ on $n$ vertices a \emph{$k$-pseudo-clique} (or simply pseudo-clique) if its minimum degree is at least $k$ and $n\leq (1+ \gamma)k$. We say a vertex $v$ has \emph{small} degree if \new{$d_G(v)\leq \frac{c}{10}$} and otherwise its degree is \emph{large}. Let $S$ and $L$ be the set of all vertices of small and large degree in $G_p$, respectively. For $1\leq i\leq 4$, let $W_i$ be the set of all vertices $v$ of small degree such that there is a vertex $w$ of small degree and a $v,w$-path of length $i$ or $v$ is contained in a cycle of length $i$. We set $W=W_1 \cup \ldots \cup W_4$. The following lemmas are extensions of the results of Frieze~\cite{Fri86}, who prove the analogous results for $G=K_{k+1}$. Lemma~\ref{lem:basicprop} summarizes a several properties of $G_p$. The proof is very similar as the original proof of Frieze. The extra factor $(1+\gamma)$ for the larger order disappears quickly in all the calculations. The same applies for the proofs of Lemma~\ref{lem:X_i} and \ref{lem:core}. Theorem~\ref{thm: pseudo-clique} needs even fewer changes as it uses the properties provided by Lemma~\ref{lem:basicprop}--\ref{lem:core}. Thus we decided to omit the proofs. We denote by $e(G)$ the number of edges of $G$ and for two disjoint sets $X,Y\subseteq V(G)$, we denote by $G[X,Y]$ the bipartite subgraph of graph $G$ spanned by the vertices $X$ and $Y$. \begin{lemma}\label{lem:basicprop} Let $G$ be a $k$-pseudo-clique on $n$ vertices, $p=\frac{c}{k}$ and let $\ell\geq 7$ be a fixed integer. Then a.a.s.\ $G_p$ has the following properties, \begin{enumerate}[(a)] \item $|\{v\in V(G): d_{G_p}(v)\leq \frac{c}{10}+1\}|\leq (1+ \gamma)ke^{-\frac{2}{3}c}$, \item for all sets $Z\subseteq V(G)$ with $|Z|\geq ke^{-c}$, we have $|\{e\in E(G_p): e\cap Z\not= \es\}|\leq 4c|Z|$, \item $\Delta(G_p)\leq 4\log k$, \item $|W|\leq c^4 e^{- \frac{4c}{3}}k$, \item $\es \not= Z \subseteq L$ and $|Z|\leq \frac{k}{2\ell}$ implies $|N_{G_p}(Z)|\geq \ell |Z|$, and \item $ Z\subseteq V(G)$ and $ \frac{k}{2\ell}\leq |Z|\leq \frac{1}{2}k$ implies $e(G_p[Z,V(G)\sm Z])\geq \frac{c|Z|}{3\ell}$. \end{enumerate} \end{lemma} \new{Let us comment on the changes that need to be done to the calculations due to the original Lemma 2.1 due to Frieze. The statements (a)-(f) refer to (2.1)-(2.6) in Lemma 2.1. As (a) follows directly by a standard application of Chernoff's inequality and the `linearity of expectations' no further changes are needed. For (b) a factor of $(1+\gamma)^{4+1/c}<11/10$ has to be added. Since $\sum_{i\geq ke^{-c}}( \frac{11e^{5+1/c}}{2560})^{ci}$ still vanishes as $k\to \infty$, this proves (b). The calculation for (c) is easy to modify and would even work for $\gamma=1$. For (d), observe that $e^{-2/3}$ is once estimated by $e^{-0.669}$, so we have here some room to spare to add another factor of $(1+\gamma)$. For (e), observe that in the proof of (2.5) the factor $e^{-\frac{3\cdot20}{7}}$ is once estimated by $e^{-8}$, again giving enough room to add the corresponding factors of $1+\gamma$. For (f), the same estimation as in the proof of (2.6) holds for $c$ and $k$ large enough as $(1+\gamma)/c\to0$ for $c\to\infty$ and hence, it still holds $$2\sum\limits_{i=\lfloor k/(2\ell)\rfloor}^{\lceil k/2\rceil} \left(\frac{(1+\gamma)ke}{i} \right)^i \left(\frac{3\ell i\big((1+\gamma)k-i\big)e}{ci}\right)^{ci/(3\ell)} \left(\frac{c}{k}\right)^{ci/(3\ell)} e^{-ci/3}=o(1).$$ } \begin{lemma}\label{lem:X_i} Let $G$ be a $k$-pseudo-clique on $n$ vertices, $p=\frac{c}{k}$, and let $X_1,X_2,\ldots $ be a sequence obtained by the following rule \begin{align*} X_i = \left\{ v\in V(G): \left|N_{G_p}(v) \cap \left(S\cup \bigcup_{\smash{j}=1}^{i-1}X_j\right)\right|\geq 2\right\}. \end{align*} If $X=\bigcup_{j\geq 1}X_j$, then $|X|\leq 500c^4e^{- \frac{4c}{3}}k$ a.a.s. \end{lemma} \new{Again, let us comment on the original Lemma 2.2 due to Frieze. It originally states that $|X|\leq 2e^4c^4e^{-4c/3}n$ a.a.s. By observing that $2e^4(1+\gamma)\leq 500$, it can be easily seen that the proof of Lemma~\ref{lem:X_i} works analogously as the original proof of Frieze. This also explains why the additional factor of $1+\gamma$ vanishes in our statement. } Let $V_2$ be vertex set of the largest subgraph of $G_p$ with minimum degree $2$ ($G_p[V_2]$ is also known as the $2$-core). Moreover, let $Y$ be the set of all vertices $v$ in $G_p$ which have degree $2$ and have a neighbor in $X$. Let $A=V_2\sm (W \cup X \cup Y)$. \begin{lemma}\label{lem:core} Let $G$ be a $k$-pseudo-clique on $n$ vertices and $p=\frac{c}{k}$. Then, a.a.s. \begin{align*} |A|\geq \left(1- (1+\epsilon(c))ce^{-c}\right)k, \end{align*} where $\epsilon(c) \rightarrow 0$ as $c \rightarrow\infty$. \end{lemma} \new{The above lemma refers to Lemma 2.4 of Frieze. Note that there is a little typo in Frieze's version and the corrected statement (2.27) should be $$|A_{k'}|\geq \left(1- (1+\epsilon(c))\frac{c^{\smash{k'}-1}}{(k'-1)!}e^{-c}\right)n.$$ In our case, we have $k'=2$. As $n\geq k$ for the minimum degree $k$, no further changes are needed. } Having proved these three lemmas for pseudo-cliques, one can go once again along the lines of the result of Frieze to obtain the following. \begin{theorem}\label{thm: pseudo-clique} \new{Let} $G$ be a $k$-pseudo-clique on $n$ vertices and $p=\frac{c}{k}$. Then, a.a.s.\ $G_p$ contains a cycle of length at least \[%begin{align*} \left(1- (1+\epsilon(c))ce^{-c}\right)k, \]%end{align*} where $\epsilon(c)\rightarrow 0$ as $c \rightarrow\infty$. \end{theorem} \new{As the proof of Theorem~\ref{thm: pseudo-clique} only exploits the statements of the lemmas before, no alterations are necessary.} \section{Long Paths} This section is devoted to the proof of Theorem~\ref{thm: path}. This proof is inspired by a result in \cite{KLS15} which states that a.a.s.\ the random subgraph $G_p$ of a graph $G$ of minimum degree at least $k$ contains a path of length $k$ if $p=\frac{(1+ \epsilon)\log k}{k}$ for any fixed $\epsilon>0$. Our strategy for the proof is as follows. If $G$ contains a pseudo-clique, then Theorem~\ref{thm: pseudo-clique} gives rise to the desired path. Otherwise, we use Theorem~\ref{thm: cycle} that guarantees a cycle $C$ of length $(1- O(c^{-1/5}))k$. Next we either dry to extend $C$ by a path that leads away from it or we use a set of vertices, which is small, but large enough for our purposes, that forms together with $C$ a larger cycle. \begin{proof}[Proof of Theorem~\ref{thm: path}] Let $c$ be sufficiently large, $k$ be sufficiently large in terms of $c$, and let $\epsilon=5\left(\frac{c}{3}\right)^{-1/5}$. If $G$ contains a set $V'\subseteq V(G)$ such that \begin{align}\label{eq: dense set} \left(1- \frac{1}{\log k}\right)k \leq |V'| \leq (1+ 10\epsilon)k \end{align} and the minimum degree of the graph $G[V']$ is at least $(1- \frac{2}{\log k})k$ , then by Theorem~\ref{thm: pseudo-clique}, $G_p$ a.a.s.\ contains a cycle of length at least \begin{align*} \left(1- (1+ \delta(c))ce^{-c}\right)k, \end{align*} for some function $\delta(c) \rightarrow 0$ as $c \rightarrow \infty$, which implies the statement. Hence, we may assume that $G$ does not contain such a set $V'$. In the following, we use a technique which is known as \emph{sprinkling}. In our case, we expose the edges of $G_p$ in three rounds and in each round we suppose an edge to be present independently with probability $\frac{c}{3k}$. Thus we consider the union of three graphs $G_{p_1}\cup G_{p_2}\cup G_{p_3}$, where $p_i=\frac{c}{3k}$. As \begin{align*} 1-(1-p_1)(1-p_2)(1-p_3)=\left(1-\frac{c}{3k}+\frac{c^2}{27k^2}\right)\frac{c}{k}\leq p, \end{align*} the union of these three graphs underestimates the model $G_p$. Therefore, if we can show that $G_{p_1}\cup G_{p_2}\cup G_{p_3}$ a.a.s.\ contains a path of the desired length, then also $G_p$ a.a.s.\ contains such a path. By Theorem \ref{thm: cycle}, we know that $G_{p_1}$ a.a.s.\ contains a cycle $C$ of length at least $(1-\epsilon)k$ (in the proof we use explicitly this constant). Moreover, we may assume that $|C|<\left(1- (1+\delta(c))ce^{-c}\right)k$. Let $A\subseteq V(G)\setminus V(C)$ be the set of vertices having at least $(1-20\epsilon)k$ neighbors in $V(C)$ and let $B= V(G)\sm (V(C)\cup A)$. We divide the proof into two parts. First, we suppose that $|A|\leq 10\epsilon k$. Hence, if $B\not=\es$, then $G[B]$ has minimum degree at least $10\epsilon k$. Suppose first that at least $4k\log k$ edges join $B$ and $C$ in $G$ and denote this set by $E$. Consider an ordering $b_1,b_2,\ldots$ of the vertices in $B$ and consider an ordering $e_1,e_2,\ldots$ of the edges in $E$ which respects the ordering on $B$, that is, if $i}\\ %Universit\"at Ulm, Ulm\\ %Germany\\ % %\noindent %Felix Joos %{\tt }\\ %School of Mathematics, University of Birmingham, Birmingham\\ %United Kingdom \end{document} %%%%%%%%%%%%%%%%% end of doc %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % %\begin{figure}[ht] %\centering %\includegraphics[scale=1]{} %\caption{}\label{} %\end{figure} % %\begin{equation}\label{somelabel} %\begin{minipage}[c]{0.8\textwidth}\em %text goes in here %\end{minipage}\ignorespacesafterend %\end{equation}