\documentclass[12pt]{article} \usepackage{e-jc} \specs{P4.8}{24(4)}{2017} %\usepackage[margin=1in]{geometry} % set the margins to 1in on all sides \usepackage{graphicx} % to include figures \usepackage{amsmath} % great math stuff \usepackage{amssymb} % great math stuff \usepackage{amsfonts} % for blackboard bold, etc \usepackage{amsthm} % better theorem environments \usepackage{mathtools} \usepackage{enumerate} \usepackage{xparse} %\usepackage{hyperref} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} %\hypersetup{hidelinks} \usepackage[utf8]{inputenc} \usepackage{color} %\usepackage{authblk} \usepackage{thm-restate} % various theorems, numbered by section \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{claim}[theorem]{Claim} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{definition}[theorem]{Definition} \newtheorem{property}[theorem]{Property} \renewcommand*{\sectionautorefname}{Section} \newcommand{\bd}[1]{\mathbf{#1}} % for bolding symbols \newcommand{\RR}{\mathbb{R}} % for Real numbers \newcommand{\ZZ}{\mathbb{Z}} % for Integers \newcommand{\N}{\mathbb{N}} % for Integers \DeclarePairedDelimiter\abs{\lvert}{\rvert} \DeclarePairedDelimiter\norm{\lVert}{\rVert} \DeclarePairedDelimiter\floor{\lfloor}{\rfloor} \DeclarePairedDelimiter\ceil{\lceil}{\rceil} %swap star and not star (make \abs resize) %\makeatletter %\let\oldabs\abs %\def\abs{\@ifstar{\oldabs}{\oldabs*}} %\makeatother \makeatletter \let\oldnorm\norm \def\norm{\@ifstar{\oldnorm}{\oldnorm*}} \makeatother \makeatletter \let\oldfloor\floor \def\floor{\@ifstar{\oldfloor}{\oldfloor*}} \makeatother \makeatletter \let\oldceil\ceil \def\ceil{\@ifstar{\oldceil}{\oldceil*}} \makeatother \renewcommand*{\Pr}[1]{\mathrm{Pr}\left[#1\right]} \newcommand*{\E}[1]{\mathrm{E}\left[#1\right]} \newcommand{\Var}[1]{ \mbox{Var} \left[ {#1} \right] } \NewDocumentCommand\G{gggg}{% \IfNoValueTF{#1}{\mathcal{G}}{% \IfNoValueTF{#2}{\mathcal{G}\left({#1}\right)}{% \IfNoValueTF{#3}{\mathcal{G}\left({#1}, {#2}\right)}{% \IfNoValueTF{#4}{\mathcal{G}\left({#1}, {#2}, {#3}\right)}{% \mathcal{G}\left({#1}, {#2}, {#3}, {#4}\right)}}}}% } \NewDocumentCommand\tildeG{gggg}{% \IfNoValueTF{#1}{\mathcal{\tilde G}}{% \IfNoValueTF{#2}{\mathcal{\tilde G}\left({#1}\right)}{% \IfNoValueTF{#3}{\mathcal{\tilde G}\left({#1}, {#2}\right)}{% \IfNoValueTF{#4}{\mathcal{\tilde G}\left({#1}, {#2}, {#3}\right)}{% \mathcal{\tilde G}\left({#1}, {#2}, {#3}, {#4}\right)}}}}% } %\reg -> (e)-regular %\reg{asd} -> (asd)-regular %\reg{e}{p} -> (e,p)-regular \NewDocumentCommand\reg{gg}{% \IfNoValueTF{#1}{\reg{\epsilon}}{% \IfNoValueTF{#2}{\(\left({#1}\right)\)-regular}{\(\left({#1}, {#2}\right)\)-regular}}% } \NewDocumentCommand\lreg{gg}{% \IfNoValueTF{#1}{\lreg{\epsilon}}{% \IfNoValueTF{#2}{\(\left({#1}\right)\)-lower-regular}{\(\left({#1}, {#2}\right)\)-lower-regular}}% } \newcommand{\ooint}[2] { \left( {#1},{#2} \right) } \newcommand{\ccint}[2] { \left[ {#1},{#2} \right] } \newcommand{\ocint}[2] { \left( {#1},{#2} \right] } \newcommand{\coint}[2] { \left[ {#1},{#2} \right) } \newcommand{\set}[1] { \left[ {#1} \right] } \newcommand*{\eps}{\epsilon} % comments \usepackage{color} \usepackage[usenames,dvipsnames]{xcolor} %\newcommand{\an}[1]{{\color{orange}\textbf{AN: }#1}} %\newcommand{\AS}[1]{{\color{red}{\bf AS:} #1}} \title{\bf Local resilience for squares of almost\\ spanning cycles in sparse random graphs} \author{ Andreas Noever\thanks{Author was supported by grant no.\ 200021 143338 of the Swiss National Science Foundation.}\qquad Angelika Steger\\ \small Department of Computer Science\\[-0.8ex] \small ETH Z\"urich\\[-0.8ex] \small 8092 Z\"urich, Switzerland\\ \small\tt \{anoever,asteger\}@inf.ethz.ch } \date{\dateline{Jul 5, 2016}{Sep 25, 2017}{Oct 6, 2017}\\ \small Mathematics Subject Classifications: 05C80, 05C38 } \begin{document} \maketitle \begin{abstract} In 1962, P\'{o}sa conjectured that a graph $G=(V, E)$ contains a square of a Hamiltonian cycle if $\delta(G)\ge 2n/3$. Only more than thirty years later Koml\'{o}s, S\'{a}rk\"{o}zy, and Szemer\'{e}di proved this conjecture using the so-called Blow-Up Lemma. Here we extend their result to a random graph setting. We show that for every $\eps > 0$ and $p=n^{-1/2+\eps}$ a.a.s.\ every subgraph of $G_{n,p}$ with minimum degree at least $(2/3+\eps)np$ contains the square of a cycle on $(1-o(1))n$ vertices. This is almost best possible in three ways: (1) for $p\ll n^{-1/2}$ the random graph will not contain any square of a long cycle (2) one cannot hope for a resilience version for the square of a {\em spanning} cycle (as deleting all edges in the neighborhood of single vertex destroys this property) and (3) for $c<2/3$ a.a.s.\ $G_{n,p}$ contains a subgraph with minimum degree at least $cnp$ which does not contain the square of a path on $(1/3+c)n$ vertices. \bigskip\noindent \textbf{Keywords:} random graphs, resilience, almost spanning subgraphs \end{abstract} \section{Introduction} A classical result of Dirac~\cite{dirac52} states that any graph $G$ on $n\ge 3$ vertices with minimum degree $\delta(G)\ge n/2$ contains a Hamilton cycle. This result is not difficult and a proof can be found in most text books on graph theory, see e.g.\ \cite{Bollobas1998modern,west}. One also easily checks that the constant $1/2$ is best possible: the complete bipartite graph on $(n-1)/2$ and $(n+1)/2$ vertices (assuming $n$ odd) has minimum degree $n/2-1/2$ but does not contain a Hamilton cycle. In 1962, P\'{o}sa conjectured that $G(V,E)$ contains a square of a Hamiltonian cycle if $\delta(G)\ge 2n/3$. A square of a cycle $C$ is the cycle $C$ together with all edges between vertices that have distance $2$ in $C$. Again it is not difficult to see that the constant $2/3$ is best possible, just consider the complete tripartite graph on $(n-1)/3$, $(n-1)/3$ and $(n+2)/3$ vertices (assuming $3$ divides $n-1$). However proving that minimum degree $2n/3$ actually suffices turned out to be a difficult problem. It required the development of powerful tools, most notably Szemer\'{e}di's Regularity Lemma \cite{Szemeredi75,Szemeredi78} and the so-called Blow-Up Lemma \cite{BlowUp97}, before P\'{o}sa's conjecture was proven, at least for all sufficiently large~$n$~\cite{KSS96}. \begin{theorem}[Koml\'{o}s, S\'{a}rk\"{o}zy, Szemer\'{e}di]\label{theorem:kss} There exists a natural number $n_0$ such that if $G$ has order $n$ with $n\geq n_0$ and \[ \delta(G)\geq \frac{2}{3}n, \] then $G$ contains the square of a Hamiltonian cycle. \end{theorem} The above results can also be stated as resilience statements. For a monotone increasing graph property ${\cal P}$ the (local) resilience of a graph $G=(V,E)$ with respect to ${\cal P}$ is the minimum $r \in \mathbb R$ such that by deleting at each vertex $v \in V$ at most an $r$-fraction of the edges incident to $v$ one can obtain a graph that does not have property ${\cal P}$. Dirac's theorem implies that the local resilience of the property `containing a Hamilton cycle' of the complete graph is $1/2$, while the proof of Posa's conjecture implies that the property `containing a square of a Hamilton cycle' of the complete graph is $1/3$. A natural extension for resilience results is to consider instead of the complete graph the random graph $G_{n,p}$ and ask for the resilience as a function of the edge probability~$p$. It is natural to expect that there exists a threshold $p_0$ so that for $p\gg p_0$ the local resilience of $G_{n,p}$ of a property ${\cal P}$ is w.h.p.\ equal to the local resilience of the complete graph, while for $p\ll p_0$ the random graph $G_{n,p}$ w.h.p.\ does not satisfy the property ${\cal P}$ at all. Indeed, such a result is known, up to constant factors, for the property `contains a Hamilton cycle'. The threshold for existence of a Hamilton cycle is $p=(\log n + \log \log n + \omega(1))/n$ \cite{KOMLOS198355,BOLLOBAS198397}, while Lee and Sudakov~\cite{LS12} showed that for every positive $\epsilon$, there exists a constant $C=C(\epsilon)$ such that for $p \ge C\log n/n$ w.h.p.\ the local resilience is $1/2-\eps$. The aim of this paper is to study the local resilience for the property `containing a square of a Hamilton cycle'. For this problem already the threshold for existence is a hard problem. Since a square of a Hamilton cycle contains many triangles, $p\ge c / \sqrt{n}$ is certainly necessary. Indeed improving on a series of previous bounds (\cite{doi:10.1137/120871729}\cite{Nenadov16}) Benett, Dudek and Frieze have recently determined the threshold to lie at $p=1/\sqrt{n}$ \cite{2016arXiv161106570B}. For the resilience problem one is thus tempted to speculate that at least for $p\ge \operatorname{poly}(\log n)/\sqrt{n}$, for an appropriate polylog-factor, we have that the resilience of $G_{n,p}$ with respect to the property 'containing a square of a Hamilton cycle' is $1/3-o(1)$. However, for this property it is easy to see that this is far too optimistic. By deleting all edges in the neighborhood of a vertex $v$ we can ensure that $v$ cannot be part of any square of a cycle. Thus for any $p=o(1)$ we have that the resilience for `containing a square of a Hamilton cycle' is $o(1)$. In order to obtain a non-trivial result we thus need to weaken the required property. One easily checks that for constant resilience the best one can hope for is to find a square of a cycle that covers all but $\Theta(1/p^2)$ vertices. Here we show an approximate version of such a best possible result. \begin{restatable}{theorem}{mainTheorem} For every $\gamma,\nu>0$ and $p=n^{-\frac{1}{2}+\gamma/2}$ a.a.s.\ every subgraph of $G_{n,p}$ with minimum degree at least $(2/3+\nu)np$ contains a square of a cycle on at least $(1-\nu)n$ vertices. \end{restatable} Our result should be compared to a recent result of Peter Allen, Julia B\"{o}ttcher, Julia Ehrenm\"{u}ller and Anusch Taraz \cite{sparseBandwidth}. The authors prove a sparse version of the bandwidth theorem, which in particular implies that $G_{n,p}$ has local resilience for the property `contains a square of a cycle on $n-C/p^2$ vertices' as long as $p\gg (\log n/n)^{1/4}$. Their proof technique as well as previous universality results hit a natural barrier around $p=n^{-1/\Delta}$ where $\Delta$ denotes the maximum degree of the embedded graph. Note that this density is required for any greedy / sequential type of embedding scheme, as for $p\ll n^{-1/\Delta}$ the typical neighbourhood of any $\Delta$ vertices is empty and one thus need to design more sophisticated look-ahead schemes. We achieve this by designing some pruning process that identifies edges that satisfy some good expansion properties. In this way we obtain the first nontrivial resilience result for almost spanning subgraphs that achieves, up to polylog factors, the optimal density. A natural question is whether a similar result holds for higher powers of a cycle. Applying the aforementioned bandwidth theorem gives a bound of $p\gg (\log n/ n)^{1/2k}$ for the $k$-th power of an almost spanning cycle. Similarly to the case $k=2$ this does not match the obvious lower bound of $p\geq n^{-1/k}$. Our approach does not generalize easily to this setting. This is mostly due to our reliance on sparse regularity techniques which yield very strong statements about the distribution of the edges, but not on larger structures like triangles or larger complete graphs. %Our proof technique relies heavily on the sparse regularity lemma and related tools. These techniques work well for triangles, but so far have not yielded tight counting statements for arbitrary graphs. \section{Proof} The proof makes heavy use of the sparse regularity lemma (see \cite{Kohayakawa1997216}) and related techniques. The definition of an \reg{\eps}{p} graph is briefly stated below. For a more in depth introduction to the topic see for example \cite{GerkeSteger05}. \begin{definition} A bipartite graph $B=\left(U\cup W,E\right)$ is called \reg{\epsilon}{p} if for all $U'\subseteq U$ and $W'\subseteq W$ with $\abs{U'}\geq\eps\abs{U}$ and $\abs{W'}\geq\eps\abs{W}$, \begin{displaymath} \abs*{\frac{\abs{E\left(U',W'\right)}}{\abs{U'}\abs{W'}}-\frac{\abs E}{\abs{U}\abs{W}}}\leq\epsilon p. \end{displaymath} We write \reg{\epsilon} in case $p$ equals the density $\abs E/\left(\abs{U}\abs{W}\right)$. $B$ is called \lreg{\eps}{p} if for all $U'\subseteq U$ and $W'\subseteq W$ with $\abs{U'}\geq\eps\abs{U}$ and $\abs{W'}\geq\eps\abs{W}$, \[\frac{\abs{E(U',W')}}{\abs{U'}\abs{W'}}\geq(1-\eps)p.\] \end{definition} The next two lemmas follow immediately from the above definition. \begin{lemma}\label{l:degreeok} Let $B=\left(U\cup W,E\right)$ be an \lreg{\epsilon}{p} bipartite graph. Then for every $W'\subseteq W$ of size at least $\eps \abs{W}$ all but at most $\eps|U|$ vertices in $U$ have at least $(1-\eps)|W'|p$ neighbours in $W'$. If $B$ is \reg{\eps} with density $p$, then all but at most $2\eps|U|$ vertices in $U$ have at least $(1-\eps)|W'|p$ and at most $(1+\eps)|W'|p$ neighbours in $W'$. \qed \end{lemma} \begin{lemma}\label{l:subgraphok} Let $B=\left(U\cup W,E\right)$ be an \reg{\epsilon} bipartite graph for some $\eps< 1/3$. Then every subgraph $\left(U\cup W,E'\right)$ of $B$ such that $|E\setminus E'| \le \eps^4|E|$ is \reg{2\epsilon}. \qed \end{lemma} The so-called sparse regularity lemma allows us to partition every subgraph of a random graph $G_{n,p}$ in \reg{\eps} parts. To make this more precise we need one more definition. \begin{definition} We say that a partition $(V_i)_0^k$ of a set $V$ is $(\eps,k)$-equitable if $\abs{V_0}\leq \eps \abs{V}$ and $\abs{V_1}=\dots=\abs{V_k}$. We call a partition $(V_i)_0^k$ $(\eps,p)$-regular if at most $\eps\binom{k}{2}$ pairs $(V_i,V_j)$ with $1\leq i < j \leq k$ are not \reg{\eps}{p}. \end{definition} %\begin{definition}A graph $G=(V,E)$ is called $\eta$-upper-uniform with density $p$ if for all disjoint vertex sets $U,W\subseteq V$ of size at least $\eta \abs{V}$, we have %\[ %\abs{E(U,W)}\leq (1+\eta)p\abs{U}\abs{W}. %\] %\end{definition} The original Sparse regularity lemma~\cite{Kohayakawa1997216} required the graph to fulfill a certain density condition. We use a more recent version of Scott~\cite{scott_2011} that does require such a condition. \begin{theorem}[Sparse regularity lemma,~\cite{scott_2011}]\label{sparseregularity} For any $\eps > 0$ and $m \geq 1$, there exists a constant $M(\eps, m) \geq m$ such that for any $p \in [0, 1]$, any graph $G$ admits an $(\eps, p)$-regular partition $(V_i)_{i = 0}^{k}$ with exceptional class $V_0$ such that $m \leq k \leq M$. \end{theorem} % %\begin{theorem}[Sparse Regularity Lemma, Theorem 2 in \cite{Kohayakawa1997216}]\label{sparseregularity} %For any given $\eps>0$ and $k_{\min}\geq 0$ there are constants $\eta>0$ and $k_{\max}\geq k_{\min}$ such that any $\eta$-upper-uniform graph with density $00$ and every positive integer $r_{\min}$ there exists $\alpha(\nu)>0$ and $r_{\max}(\nu,\eps, r_{\min})$ such that for $p\gg 1/n$ a.a.s.\ every spanning subgraph $\tilde G\subseteq G_{n,p}$ with minimum degree at least $(\mu+\nu)np$ contains a partition of the vertices $V=V_0\cup V_1\cup\dots\cup V_r$, where $r\in[r_{\min}, r_{\max}] $, such that $\abs{V_0}\leq \eps n$, $\abs{V_1}=\dots=\abs{V_r}$ and such that for every $i$ there exist at least $\mu r$ indices $j\in\set{r}\setminus\{i\}$ such that $\tilde G[V_i, V_j]$ contains a spanning \reg{\eps} subgraph with $\floor{\abs{V_i}\abs{V_j}\alpha p}$ edges. \end{corollary} \begin{proof} We choose $\alpha(\nu)$, $m(r_{\min})$ and $\eps_0(\mu, \nu, \eps)$ such that inequality $(*)$ from below and the following inequalities are satisfied simultaneously: $$ \sqrt{\eps_0} \leq \frac{\nu}{2}, \qquad 2\eps_0/\alpha < \eps, \qquad (1-\sqrt{\eps_0})m\geq r_{\min},\qquad\eps_0 + 2\sqrt{\eps_0} \leq \eps. $$ Suppose that $\tilde G$ is a spanning subgraph of $G_{n,p}$ with $\delta(\tilde G)\geq (\mu+\nu)np$. For every $\eta>0$ a.a.s.\ every subgraph of the random graph $G_{n,p}$ is $\eta$-upper-uniform with density $p$ and thus the sparse regularity lemma can be applied to every subgraph of $G_{n,p}$. The sparse regularity lemma (\autoref{sparseregularity}) gives us a constant $M(\eps_0, m)$ such that we find an \reg{\eps_0}{p} $(\eps_0,k)$-equitable partition $(V_i)_{0}^{k}$ of $\tilde G$ for some $k\in [m,M]$. Denote with $\tilde n\in\ccint{(1-\eps_0)n/k}{n/k}$ the size of the partition classes. For $i\in\set{k}$ define \[ d_i\coloneqq \{j\in \set{k}\setminus \{i\}\mid \text{$V_i$, $V_j$ has density at least $\alpha p$ in $\tilde G$}\}. \] Note that a.a.s.\ in $G_{n,p}$ we have that $\abs{E(V_i,V_j)} \leq (1+\eps_0) \tilde n^2p$ for all $i,j\in\set{k}$ and, with room to spare, $\abs{E(V_i, V_0\cup V_i)}\leq 2(\eps_0n+\tilde n) \tilde n p$ for all $i\in\set{k}$. The minimum degree condition of $\tilde G$ thus implies that for all $i\in\set{k}$ \[ \tilde n\left(\mu+\nu\right)np \leq E(V_i,V_0\cup V_i) + \sum_{\mathclap{j\in\set{k}\setminus i}} E(V_i, V_j) \leq 2(\eps_0 n+\tilde n)\tilde n p + k \alpha p \tilde n^2 + d_i (1+\eps_0) \tilde n^2 p \] and thus \[ d_i \geq \frac{\left(\mu+\nu\right)n - 2(\eps_0 n +\tilde n) - k\alpha \tilde n}{(1+\eps_0)\tilde n} \geq \frac{\left(\mu+\nu\right) k - 2(\frac{\eps_0}{1-\eps_0}k + 1) - k\alpha}{(1+\eps_0)} \stackrel{(*)}\geq \left(\mu+\frac{\nu}{2}\right) k. \] %for $m$, $n$ large enough and $\eps_0$, $\alpha$ small enough depending on $\nu$. Observe that the fact that at most $\eps_0\binom{k}2$ pairs $(V_i,V_j)$ are not \reg{\eps_0}{p} implies that there are at most $\sqrt{\eps_0} k$ indices in $\set{k}$ for which the set \[ \{j\in \set{k}\setminus \{i\}\mid \text{$(V_i, V_j)$ is not an \reg{\eps_0}{p} graph}\} \] has size at least $\sqrt{\eps_0}k$. Every \reg{\eps_0}{p} graph with density at least $\alpha p$ is \reg{\eps_0/\alpha} and thus contains a \reg{2\eps_0/\alpha} subgraph with $\floor{\tilde n^2 \alpha p}$ edges (see for example Lemma 4.3 in \cite{GerkeSteger05}). As $\sqrt{\eps_0} \leq \frac{\nu}{2}$, we can thus find a subset $R\subseteq \set{k}$ of at least $(1-\sqrt{\eps_0})k$ indices such that for every $i\in R$ the set \[ \{j\in R\setminus \{i\}\mid \text{$V_i$, $V_j$ contain an \reg{2\eps_0/\alpha} graph with $\floor{\tilde n^2\alpha p}$ edges}\} \] is of size at least $\mu k$. Without loss of generality we may assume that $R=\left\{1,\dots,r\right\}$, where $r\geq (1-\sqrt{\eps_0})k\geq r_{\min}$. By choice of $\eps_0$ we know that the cardinality of $V_0\cup \bigcup_{i> r} V_i$ is at most $\eps_0 n + \sqrt{\eps_0}k \tilde n \leq \eps n$. Thus $V_0\cup\bigcup_{i>r} V_i,V_1,\dots,V_r$ is the desired partition and the corollary thus holds for $r_{\max}=M$. \end{proof} With \autoref{l:standard} at hand, an alert reader will certainly be able to guess our proof strategy: apply the Koml\'{o}s, S\'{a}rk\"{o}zy, Szemer\'{e}di Theorem to the partition guaranteed by \autoref{l:standard} in order to find a square of a cycle for this partition and then find a long square of a cycle within this structure. The next definitions provide the notations to make this idea precise. %To add additional structure to the \reg{\eps}{p} pairs provided by the sparse regularity lemma First we define the notion of a regular blow-up of a graph. \begin{definition} Denote with $\G{F}{n}{p}{\eps}$ the class of graphs that consist of $\abs{V(F)}$ pairwise disjoint vertex sets of size $n$. Each vertex set represents a vertex of $F$, and two vertex sets span an \reg{\eps} graph with density $(1\pm\eps)p$ whenever the corresponding vertices are adjacent in $F$. \end{definition} With $P_k$ we denote a path of length~$k$, with vertex set $\{1,\ldots,k+1\}$ and edges $\{i,i+1\}$ for $1\le i\le k$. The cycle $C_k$ is obtained from $P_k$ by identifying the vertices $1$ and $k+1$. The square of a path is denoted with $P_k^2$ and the square of a cycle with $C^2_k$. For a graph $F\in\left\{P^2_k,C^2_k\right\}$ and its blow-up $G\in\G{F}{n}{p}{\eps}$ we denote the vertex sets of $G$ by $V_1,\dots,V_{\abs {F}}$ and assume that the vertex set $V_i$ represents the $i$-th vertex along the path (or cycle). We collect some additional properties of $\G{P^2_k}{n}{p}{\eps}$ in the following definition: \begin{definition}\label{def:gtilde} Denote with $\mathcal{\tilde G}(P^2_{k}, n, p, \eps)\subseteq \G{P^2_{k}}{n}{p}{\eps}$ the class of graphs in which for $i\in\{1,\dots,k-1\}$ \begin{list}{}{} \item[$(i)$] every edge spanned by $V_i, V_{i+1}$ closes a triangle with at least $(1-\eps)np^2$ vertices in $V_{i+2}$, and \item[$(ii)$] all but $\eps n$ vertices $v\in V_{i+1}$ have neighborhoods into $V_i$ and $V_{i+2}$ which induce an \lreg{\eps}{p} subgraph. \end{list} \end{definition} We also need two auxiliary lemmas related to the above definition. Their proofs are deferred to \autoref{sec:gtilde} and \autoref{sec:pathExpansion}. The first lemma states that in the random graph the restrictions imposed by \autoref{def:gtilde} are easy to satisfy: \begin{restatable}{lemma}{gtilde}\label{lemma:gtilde} For every $\alpha,\eps,\gamma,k_{\max}>0$ there exists $\eps'>0$ such that for every $\eta>0$ a.a.s.\ in $G_{n,p}$ with $p=n^{-1/2+\gamma/2}$ every subgraph $G\subseteq G_{n,p}$, where $G\in\G{P^2_k}{n_0}{\alpha p}{\eps'}$, $n_0\geq \eta n$, $k\leq k_{\max}$ contains a spanning subgraph from $\tildeG{P^2_k}{n_0}{\alpha p}{\eps}$. \end{restatable} For $G\in\tildeG{P^2_k}{n}{p}{\eps}$ with vertex partitions $V_1,\dots,V_k$ we say that an edge $e\in E(V_1, V_2)$ \emph{expands} to a set of edges $E'\subseteq E(V_{i},V_{i+1})$ if there exists a square of a path of length $i$ in $G$ between $e$ and every edge of $E'$. The next lemma asserts that in the random graph every edge in $E(V_1,V_2)$ expands to a majority of the edges in $E(V_ {k},V_{k+1})$, whenever $k$ is sufficiently large. Property (1) of \autoref{def:gtilde} already guarantees that every edge spanned by $V_1, V_2$ is contained in many squares of a path ending in $E(V_ {k},V_{k+1})$. But since these paths may overlap this alone does not imply that every edge expands to a large portion of $E(V_ {k},V_{k+1})$. \begin{restatable}{lemma}{pathExpansion}\label{pathExpansion} Let $\eta,\alpha,\gamma>0$ and $k\geq \frac{3}{\gamma}$ be fixed and let $p=n^{-1/2+\gamma/2}$. For $\eps$ small enough depending on $\alpha$ a.a.s.\ every subgraph $G\subseteq G_{n,p}$ which is from $G\in\tildeG{P^2_{k+4}}{n_0}{\alpha p}{\eps}$ for some $n_0\geq \eta n$ satisfies the following: all edges in $G[V_1\cup V_2]$ expand to at least a $0.52$-fraction of the edges in $G[V_{k+4}\cup V_{k+5}]$. \end{restatable} With these two lemmas at hand we can prove our main result. \mainTheorem* \begin{proof} Suppose that $\tilde G$ is a spanning subgraph of $G_{n,p}$ with $\delta(\tilde G)\geq(\frac{2}{3}+\nu)np$. We will the fix constants $\alpha(\nu), \eps(\nu,\alpha), \eps'(\nu, \alpha, \eps, \gamma)>0$ throughout the proof. Set $k_0=\lceil\frac{3}{\gamma}\rceil+4$ and let $r_{\min}=\max\{3k_0, n_0\}$ where $n_0$ denotes the constant from \autoref{theorem:kss}. For $\alpha(\nu)$ small enough we may invoke \autoref{l:standard} with $\mu\leftarrow 2/3$, $\nu\leftarrow \nu$, $\eps\leftarrow\eps'$ to obtain, for some $r\in[r_{\min}, r_{\max}(\nu,\eps')]$, a partition $V=V_0\cup\dots\cup V_r$ of the vertices of $\tilde G$ such that $\abs{V_1}=\dots=\abs{V_r}=\tilde n\in[(1-\eps')n/r,n/r]$ and for every $i\in\set{r}$ the number of indices $j\in\set{r}\setminus\{i\}$ such that $\tilde G[V_i, V_j]$ contains a spanning \reg{\eps'} subgraph with $\floor{\tilde n^2\alpha p}$ edges is at least $\frac{2}{3}r$. Since $r\geq n_0$ \autoref{theorem:kss} tells us that then $\tilde G$ must contain a subgraph $G\in \G{C^2_r}{\tilde n}{\alpha p}{\eps'}$ on the partitions $V_1,\dots,V_r$. We shall assume without loss of generality that $V_i$ represents the $i$-th vertex of the cycle. Furthermore for ease of notation we identify $V_{r+i}$ with $V_{i}$. For integers $i\in\set{r}$ and $t\in \ccint{k_0}{2k_0}$ consider a collection of subsets $V'_i\subseteq V_i,\dots$, $V'_{i+t}\subseteq V_{i+t}$ each of size $n'\geq\eps \tilde n$. By definition of \reg{\eps'}ity the sets $V'_{i},\dots,V'_{i+t}$ induce a subgraph $G'\in\G{P^2_t}{n'}{\alpha p}{2\eps'/\eps}$ in $G$. By \autoref{lemma:gtilde} we may pick $\eps'$ small enough depending on $\alpha,\eps,2k_0$ such that a.a.s.\ $G'$ contains a spanning subgraph $G_0\subseteq G'$ with $G_0 \in \tildeG{P^2_t}{n'}{\alpha p}{\eps}$. We call an edge $e\in E(V'_i,V'_{i+1})$ \emph{good} (w.r.t.\ $V'_i,\dots,V'_{i+t}$) if it expands to at least a $0.51$-fraction of the edges in $E(V'_{i+t-1}, V'_{i+t})$ (through $V'_i,\dots,V'_{i+t}$ in $G_0$). \autoref{pathExpansion} with $\eta\leftarrow \eps/2r_{\max}$, $\alpha\leftarrow \alpha$, $\gamma\leftarrow \gamma$, $k\leftarrow t-4\geq k_0-4 \geq \frac{\gamma}{3}$ tells us that all edges in $G_0[V'_i,V'_{i+1}]$ expand to at least a $0.52$-fraction of the edges in $G_0[V'_{i+t-1},V'_{i+t}]$. Since $G_0\subseteq G$ and since the density of $G_0$ and $G$ differs by at most $2\eps\alpha p$ this implies that say a $0.99$-fraction of the edges in $E(V'_i,V'_{i+1})$ are good. We can now find a long square of a path as follows: Fix an edge $e\in E(V_1,V_2)$ which is good with respect to $V_1,\dots,V_{k_0+1}$. $e$ expands to at least a $0.51$ fraction of the edges spanned by $V_{k_0}, V_{k_0+1}$ and a $0.99$ fraction of the edges in $E(V_{k_0}, V_{k_0+1})$ are good with respect to $V_{k_0},\dots,V_{2k_0}$. Thus we may fix a square of a path $P\subseteq G[V_1\cup\dots\cup V_{k_0+1}]$ of length $k_0$ from $e$ to some edge $e'\in E(V_{k_0},V_{k_0+1})$ which is good with respect to $V_{k_0},\dots,V_{2k_0}$. Now remove $V(P)\setminus e'$ from $G$. Observe that since $r\geq 3k_0$ we did not remove any vertices from $V_{k_0},\dots, V_{2k_0}$ and therefore $e'$ is still good (w.r.t.\ $V_{k_0},\dots, V_{2k_0}$). Thus we may extend $P$ to end in an edge $e''\in E(V_{2k_0-1},V_{2k_0})$ which is good w.r.t.\ to $V_{2k_0-1},\dots,V_{3k_0-1}$. This procedure can be continued for as long as $\abs{V_i}\geq \eps\tilde n$ for every $i\in\set{r}$. Thus we obtain a square of a path $P$ which uses at least $(1-2\eps)\tilde n$ vertices from each partition of $G$. This construction can be generalized to obtain a square of the cycle: before fixing the first edge $e$ set aside sets $\tilde V_1\subseteq V_1$, \dots, $\tilde V_{r}\subseteq V_r$ each of size $\eps\tilde n$. Pick $e\in E(\tilde V_1, \tilde V_2)$ such that it expands (backwards) to at least a $0.51$-fraction of the edges in $E(\tilde V_{r+1-k_0},\tilde V_{r+2-k_0})$ and is good (w.r.t.\ $V_1\setminus \tilde V_1,\dots,V_{k_0+1}\setminus \tilde V_{k_0+1}$). Then embed a long path starting with $e$ in $V(G)\setminus \bigcup \tilde V_i$. At any point we may decide to close it by picking the next edge such that it expands to a $0.51$-fraction of the edges in $E(\tilde V_{r+1-k_0},\tilde V_{r+2-k_0})$. With this construction we find a square of a cycle of length at least \[ r\cdot(1-3\eps)\tilde n\geq (1-3\eps) (1-\eps')\frac{n}{r}\geq (1-\mu)n \] provided that $\eps', \eps$ are chosen small enough depending on $\mu$. \end{proof} \section{Proof of \autoref{lemma:gtilde}}\label{sec:gtilde} For the proof of \autoref{lemma:gtilde} we need the following sparse regularity inheritance theorem: \begin{theorem}[Gerke, Kohayakawa, R\"{o}dl, and Steger~\cite{GKRS07}]\label{inheritance} For $0<\beta,\eps'<1$, there exists $\eps_0=\eps_0(\beta,\eps')>0$ and $C=C(\eps')$ such that, for any $0<\eps\leq\eps_0$ and $00$ there exists $\eps_0>0$ and $C>0$ such that for all integers $n,m\in\N$ that satisfy $3^nn^{2n}\le 2^{n^{3/2}}$ and $m\geq C n^{3/2}$ the following holds. The number of graphs $G=(V_1\cup V_2\cup V_3, E)$ in $\G{K_3}{n}{m/n^2}{\eps_0}$ with $m$ edges between each two partitions for which more than $\eps n$ vertices in $v\in V_1$ have neighborhoods in $V_2$, $V_3$ which are not of size $(1\pm \eps)m/n$ or which do not induce an \lreg{\eps}{m/n^2} subgraph in $G[V_2,V_3]$ is at most \[ \beta^{m}\binom{n^2}{m}^3. \] \end{lemma} \begin{proof} Write $p=m/n^2$ and define $\beta_0$ by the equation $\beta_0^{(1-\eps)\eps/2}=\beta/2$. Let $\eps_0=\min\left\{\eps/4,\eps_0(\beta_0,\eps)\right\}$ and $C=\max\left\{1,C(\eps)/(1-\eps)\right\}$, where $\eps_0(\cdot,\cdot)$ and $C(\cdot)$ are the functions given by \autoref{inheritance}. Consider a graph $G=(V_1\cup V_2\cup V_3,E)$ for which the statement fails. For any such graph we may partition $V_1$ into three sets $V_D, V_B, V_G\subseteq V_1$ as follows: the set $V_D$ contains all vertices whose degree into at least one of $V_2$ or $V_3$ is not within $(1\pm\eps)np$. $V_B$ contains all vertices whose degree into both $V_2$ and $V_3$ is within $(1\pm\eps)np$ but whose neighborhoods in $V_2$ and $V_3$ do not induce an \lreg{\eps}{p} graph in $G[V_2,V_3]$. Finally set $V_G=V_1\setminus \left(V_D\cup V_B\right)$. \autoref{l:degreeok} implies that $\abs{V_D}\leq 2\eps_0 n \leq \eps n/2$. Therefore it suffices to enumerate graphs $G$ with $\abs{V_{B}}\geq \eps n/2$. We now construct all graphs $G$ which produce a partition with $\abs{V_B}\geq \eps n/2$. First we pick the \reg{\eps_0} graph spanned by $V_2$, $V_3$. There are at most $\binom{n^2}{m}$ choices. Second we pick a partition $V=V_D\cup V_B \cup V_G$ and fix the degrees of all vertices $v\in V_1$ in $G[V_1,V_2]$ and $G[V_1,V_3]$. The number of choices is at most $3^n\cdot n^{2n}$. Finally we fix the actual neighborhoods of the vertices of $V_1$. For a vertex $v\in V_D \cup V_G$ the number of choices is at most \[ \binom{n}{\deg_{G[V_1,V_2]}(v)}\binom{n}{\deg_{G[V_1,V_3]}(v)}. \] For $v\in V_B$ we have to select a neighborhood which does not induce an \lreg{\eps}{p} subgraph in $G[V_2,V_3]$. Since $\deg_{G[V_1,V_i]}(v)\geq (1-\eps)np \geq C(\eps)p^{-1}$ \autoref{inheritance} tells us that the number of such neighborhoods is at most \[ \beta_0^{(1-\eps)np}\binom{n}{\deg_{G[V_1,V_2]}(v)}\binom{n}{\deg_{G[V_1,V_3]}(v)}. \] Since $\abs{V_B} \geq \eps n/2$ the total number of choices for the neighborhoods of the vertices in $V_1$ is bounded by \begin{align*} \beta_0^{(1-\eps)np\abs{V_B}}\prod_{v\in V_1}\binom{n}{\deg_{G[V_1,V_2]}(v)}\binom{n}{\deg_{G[V_1,V_3]}(v)} &\leq \beta_0^{(1-\eps)\eps m/2} \binom{n^2}{m}^2 \\ &= \left(\frac{\beta}{2}\right)^{m}\binom{n^2}{m}^2, \end{align*} where the inequality follows from Vandermonde's identity. Since $3^n\cdot n^{2n} \leq 2^{n^{3/2}} \leq 2^m$ by assumption on $n$ and $m$, this completes the proof. \end{proof} \autoref{lregnb} immediately implies the following corollary about the number of triangles spanned by almost all edges: \begin{corollary}\label{triangles} For every $\beta, \delta>0$ there exist $\eps_0>0$ and $C>0$ such that for $m\geq C n^{3/2}$ and $n$ sufficiently large the following holds. The number of graphs $G=(V_1\cup V_2\cup V_3, E)$ in $\G{K_3}{n}{m/n^2}{\eps_0}$, with $m$ edges between each two partitions, for which more than $\delta m$ edges of $G[V_1,V_2]$ are contained in fewer than $(1-\delta)n(m/n^2)^2$ triangles is at most \[ \beta^{m}\binom{n^2}{m}^3. \] \end{corollary} \begin{proof} Let $p=m/n^2$ and choose $\eps$ small enough for $(1-\eps)^3\geq (1-\delta)$ to hold. Denote with $V'_1\subseteq V_1$ the set of vertices $v\in V_1$ whose neighborhoods in $V_2, V_3$ are of size $(1\pm \eps)np$ and induce an \lreg{\eps}{p} subgraph in $G[V_1, V_2]$. From \autoref{l:degreeok} we deduce that every vertex in $V_1'$ is incident to at least $(1-\eps)^2np$ edges (with endpoint in $V_2$) which are each contained in at least $(1-\eps)^2np^2\geq(1-\delta)np^2$ triangles. Therefore, the total number of edges which are contained in fewer than $(1-\delta)np^2$ triangles is at most $m-\abs{V'_1}(1-\eps)^2np$. By choice of $\delta$, the only possibility that the desired condition is not fulfilled is thus that $\abs{V'_1}\leq (1-\eps)n$. \autoref{lregnb} handles exactly this case -- and thus concludes the proof if we choose $C$ and $\eps_0$ as in this lemma. \end{proof} With \autoref{triangles} at hand we are now ready to prove \autoref{lemma:gtilde}. \begin{proof}[Proof of \autoref{lemma:gtilde}] Observe first that it suffices to consider a fixed integer $k\leq k_{\max}$, as the lemma then follows by choosing the minimum $\eps'$ for all $k\leq k_{\max}$ and a trivial union bound argument. We first consider property $(i)$ of \autoref{def:gtilde}. The key fact here is that we want the property to hold for {\em every} edge, while \autoref{triangles} guarantees this only for {\em `almost all'} edges. It is thus obvious what we need to do: show that we can remove edges appropriately. To this end \autoref{l:subgraphok} will come in very handy, as it shows that if we choose $\eps'$ small enough then we can take away edges repeatedly, while still keeping some regularity properties. Define constants as follows: $\eps_0(\alpha, \eps)$ will be fixed at the end of the proof, but will be small enough to satisfy $(1-\eps)\leq (1-\eps_0)^3$. Set $\beta = (\alpha/(4e))^3$ and for $i\in\set{k-1}$ define $\delta_i = (\eps_{i-1}/4)^4/2$ and $\eps_i = \min\left\{\delta_i/4, \eps_{cor}\left(\beta,\delta_i\right)\right\}$, where $\eps_{cor}(\cdot,\cdot)$ denotes the function $\eps(\beta,\delta)$ defined in \autoref{triangles}. Finally define $m_i=\ceil{(1-\eps_i)n^2_0p_0}$ and $\eps'=\eps_{k-1}/4$. Observe that $\eps_0>\delta_1>\eps_1>\dots>\delta_{k-1}>\eps_{k-1}>\eps'$. We now proceed as follows: for $i=k-1$ down to $i=1$ we remove edges from $E(V_{i},V_{i+1})$ if they are not contained in enough triangles with $V_{i+2}$ {\em with respect} to the edge set that survived the removal process in the previous round. That is, we remove all edges in $E(V_i,V_{i+1})$ which are contained in fewer than $(1-\eps)n_0p_0^2$ triangles with $V_{i+2}$, only taking in account edges that are still present. Assume first that for all $1\le i < k$ we remove at most $2\delta_i m_i$ edges. Then the resulting subgraph $\tilde G$ is, by construction, such that the graph satisfies property $(i)$ of \autoref{def:gtilde}. We claim that we also have that all pairs are \reg{\eps_0} with density at least $(1-\eps_0)p_0$. Note that this implies that $\tilde G\in G(P^2_{k}, n_0, p_0, \eps_0)$. By definition of $\tildeG{P^2_k}{n_0}{p_0}{\eps'}$ we know that (before removing any edges) the pair $(V_{i},V_{i+1})$ is \reg{\eps'} (and thus \reg{\eps_0/2}) with density at least $(1-\eps')p_0$. If we remove at most $2\delta_i m_i \leq (\eps_0/2)^4\abs{E(V_i,V_{i+1)}}$ edges from $E(V_{i},V_{i+1})$, then \autoref{l:subgraphok} implies that the remaining graph is \reg{\eps_0} with density at least $(1-\eps'-2\delta_i)p_0 \geq (1-3\delta_i)p_0\geq (1-\eps_0) p_0$. So assume the above condition does not hold. Let $i$ denote the largest $1\le i< k$ such that when processing $E(V_i,V_{i+1})$ we have to remove more than $2\delta_i m_i$ edges. We claim that then $G[V_i\cup V_{i+1}\cup V_{i+2}]$ contains one of the subgraphs enumerated by \autoref{triangles}. Indeed, let $G'_{i+1,i+2}\subseteq G[V_{i+1},V_{i+2}]$ denote the subgraph obtained after removing the edges which do not satisfy property (i). If $i=k-1$ then, since we do not touch the last partition, we have $G'_{i+1,i+2}=G[V_{k},V_{k+1}]$ which is trivially \reg{\eps_i/2} with density at least $(1-\eps_i)p_0$. If $i0$, $k>\frac{3}{2}\cdot \frac{1+\gamma}{\gamma}$ and $p=n^{-(1-\gamma)/2}$ a.a.s.\ no pair of edges in $G_{n,p}$ is connected by more than $2n^{k-3}p^{2k-3}$ squares of paths of length $k$. \end{lemma} \begin{proof} This follows directly from a theorem of Spencer on the number of graph extensions in the random graph \cite{spencer90}. $P^2_k$ rooted at both of its end-edges is strictly rooted balanced and $n^{k-3}p^{2(k-3)+3}\gg \log n$. Thus the number of squares of paths of length $k$ connecting any two edges is concentrated around its expectation. \end{proof} The previous lemma easily implies a weaker version of \autoref{pathExpansion} where the constant $0.52$ has to be replaced with a small value that depends on $\alpha$ and $\eta$. And this will indeed be the first step in the proof. Next we prove a small lemma which contains two ad hoc arguments that will allow us to go from a small set of the edges in $V_i,V_{i+1}$ to a slightly larger set of edges in $V_{i+1},V_{i+2}$. \begin{lemma}\label{triangleExpansion} Let $\eta,\alpha,\gamma,\eps>0$ be fixed. For $p=n^{-1/2+\gamma/2}$ in $G_{n,p}$ a.a.s.\ every copy of $G=(V_1\cup V_2\cup V_3, E)\in\tildeG{K_3}{n_0}{p_0}{\eps}$, where $n_0\geq \eta n$ and $p_0=\alpha p$, satisfies the following: for every set of edges $\tilde E\subseteq E\left(V_1,V_2\right)$ denote with $\triangle (\tilde E)$ the number of edges in $E(V_2, V_3)$ which form a triangle with some edge of $\tilde E$ in $G$. Let $\tilde V_2\subseteq V_2$ denote the vertices which are incident to some edge of $\tilde E$ and set $s=\min_{v\in \tilde V_2} \deg_{\tilde E}(v)$. Then \begin{equation*} \triangle(\tilde E) \geq \begin{cases} \abs{\tilde V_2} n_0 p_0^2 /(2p) & \text{if } s\geq \log ^2(n)n_0p/n^\gamma,\\ (1-\eps)^2 \left(\abs{\tilde V_2}-5\eps n_0\right) n_0p_0 & \text{if } s\geq 2\eps n_0p_0. %0 & \text{otherwise.} \end{cases} \end{equation*} \end{lemma} \begin{proof} Fix $v\in \tilde V_2$. Write $V^v_1=\Gamma_{\tilde E}(v)$ and let $V^v_3=V_3\cap\Gamma(v)\cap\Gamma(V^v_1)$ denote the subset of vertices of $V_3$ which form a triangle with $v$ and some edge from $\tilde E$. By definition of $G$ every edge in $\tilde E$ is contained in at least $(1-\eps)n_0p_0^2$ triangles with $V_3$ and therefore \begin{equation}\label{eq:l42} E(V^v_1, V^v_3) \geq (1-\eps)\abs{V^v_1}n_0p^2_0. \end{equation} A.a.s.\ in $G_{n,p}$ all disjoints sets $A$, $B$ of sizes $\abs{A}\geq \log^2(n) n_0p_0/n^\gamma$ and $\abs{B}\leq b = n_0 p^2_0/(2p)$ have at most $(1+\eps)\abs{A} b p$ edges between them. To see this, observe that $\abs{A}bp \gg \log n\max\left\{\abs{A},b\right\}$ and the claim thus follows from Chernoff's inequality together with a straightforward union bound argument over all sets of size $\abs A$ and at most $b$. We now consider the two cases. If $s\geq \log^2(n)n_0p_0/n^\gamma$ then Equation $\eqref{eq:l42}$ implies that $E(V^v_1, V^v_3) \geq (1-\eps) \abs{V^v_1} n_0 p_0^2 = 2(1-\eps) \abs{V^v_1}bp$. For $\abs{V_3^v}\le b$ this would contradict the bounds from the Chernoff inequality in the previous paragraph; thus $\abs{V_3^v}\ge b$, implying the desired bound. %In particular every $v\in \tilde V_2$ is incident to at least $n_0 p_0^2/(2p)$ edges which form a %triangle with some edge of $\tilde E$. Therefore $\triangle(\tilde E)\geq \abs{\tilde V_2} n_0 %p_0^2/(2p)$. Now suppose that $s\geq 2\eps n_0p_0$ and that $v$ is such that its neighborhoods in $V_1$ and $V_3$ are of size $(1\pm\eps)n_0p_0$ and induce a \lreg{\eps}{p} subgraph. As $\abs {V^v_1} \geq s$ the assumption on $p$ and $v$ imply $\abs {V^v_1} \geq \eps \abs{\Gamma(v)\cap V_1}$. Thus we can apply \autoref{l:degreeok} to deduce that at most $\eps\abs{\Gamma(v)\cap V_3}$ vertices in $\Gamma(v)\cap V_3$ have no neighbor in $V^v_1$. Thus $\abs{V^v_3}\geq (1-\eps)\abs{\Gamma(v)\cap V_3} \geq (1-\eps)^2n_0p_0$. By \autoref{l:degreeok} at most $4\eps n_0$ vertices do have neighborhoods of the wrong size in either $V_1$ or $V_3$. By definition of $\tilde{\mathcal G}$ at most $\eps n_0$ vertices have neighborhoods which do not induce an \lreg{\eps}{p} subgraph. Thus $\triangle(\tilde E)\geq \left(\abs{\tilde V_2}-5\eps n_0\right) (1-\eps)^2n_0p_0$, as claimed. \end{proof} With these two lemmas at hand the proof of \autoref{pathExpansion} can be summarized as follows: Use the weak version implied by \autoref{spannedPaths} to expand to a small fraction of the edges spanned by $V_{k}, V_{k+1}$. Then invoke \autoref{triangleExpansion} (four times!) to expand to a $0.52$-fraction of the edges in $V_{k+4}, V_{k+5}$. The details are given below. \pathExpansion* \begin{proof}Write $p_0=\alpha p$. Since $G\in\tildeG{P^2_{k+4}}{n_0}{p_0}{\eps}$ every edge in $G[V_i \cup V_{i+1}]$ forms at least $(1-\eps)n_0p_0^2$ triangles with $V_{i+2}$. In particular every edge spanned by $V_1\cup V_2$ is connected to $E(V_k,V_{k+1})$ by $((1-\eps)n_0p^2_0)^{k-1}$ copies of $P^2_{k}$. Furthermore since $k\geq \frac{3}{\gamma}> \frac{3}{2}\cdot\frac{1+\gamma}{\gamma}$ by \autoref{spannedPaths} every edge in $E(V_1, V_2)$ is connected to at least \[ \frac{((1-\eps)n_0p^2_0)^{k-1}}{2n^{k-3}p^{2k-3}} = \Theta(n^2p) \gg n^2p/n^{\gamma/2}. \] distinct edges in $E(V_k, V_{k+1})$ via the square of a path. Therefore it suffices to show that every set $E_0\subseteq E(V_{k},V_{k+1})$ of size at least $n_0^2p_0/n^{\gamma/2}$ expands to at least a $0.52$-fraction of $E(V_{k+4}, V_{k+5})$. To this end we will apply \autoref{triangleExpansion} four times to $G\leftarrow G[V_{k+i}\cup V_{k+i+1} \cup V_{k+i+2}]$ for $i\in \left\{0,1,2,3\right\}$. Set $s=\log^2(n)n_0p/n^\gamma$. In $G_{n,p}$ a.a.s.\ all degrees are bounded by $(1+o(1))np$. Therefore we can find a set of vertices $\tilde V_{k+1}\subseteq V_{k+1}$ of size \[ \frac{\abs{E_0}-n_0s}{\Theta(np)}=\Theta(n^{1-\gamma/2}) \] and an edge set $\tilde E_0\subseteq E_0$ such that each $v\in \tilde V_{k+1}$ is incident to exactly $s$ edges of $\tilde E_0$. Apply \autoref{triangleExpansion} with $G\leftarrow G[V_{k}\cup V_{k+1}\cup V_{k+2}]$, $\tilde V_2\leftarrow \tilde V_{k+1}$, $\tilde E\leftarrow \tilde E_0$ and denote the set of edges which form a triangle with some edge of $\tilde E_0$ with $E_1\subseteq E(\tilde V_{k+1}, V_{k+2})$. We have $\abs{E_1}\geq \frac{p_0}{2p}\abs{\tilde V_{k+1}} n_0 p_0$. Denote with $\tilde V_{k+2}\subseteq V_{k+2}$ the set of vertices which are incident to more than $s$ edges in $E_1$. A.a.s.\ in $G_{n,p}$ there exists no set $S$ of size $\abs{\tilde V_{k+1}}=\Theta(n^{1-\gamma/2})$ such that more than $\sqrt{n}$ vertices have degree at least $2\abs{\tilde V_{k+1}}p$ into $S$. Therefore for $\eps$ small enough depending on $\alpha$ \[ \abs{\tilde V_{k+2}} \geq\frac{\abs{E_1}-\sqrt{n}\cdot\Theta(np)-n_0s}{2\abs{\tilde V_{k+1}}p} \geq\frac{\frac{p_0}{3p}\abs{\tilde V_{k+1}} n_0 p_0}{2\abs{\tilde V_{k+1}}p} \geq \frac{p_0^2}{6p^2}n_0 \geq 100\eps n_0. \] As before pick a subset $\tilde E_1\subseteq E_1$ such that every $v\in \tilde V_{k+2}$ is incident to exactly $s$ edges of $\tilde E_1$. Apply \autoref{triangleExpansion} a second time with $G\leftarrow G[V_{k+1}\cup V_{k+2}\cup V_{k+3}]$, $\tilde V_2\leftarrow \tilde V_{k+2}$, $\tilde E\leftarrow \tilde E_1$ and denote the set of edges which form a triangle with some edge of $\tilde E_1$ with $E_2\subseteq E(V_{k+2},V_{k+3})$. We have $\abs{E_2}\geq \frac{p_0}{2p}\abs{\tilde V_{k+2}}n_0p_0$. Let $\tilde V_{k+3}\subseteq V_{k+3}$ denote the subset of vertices which are incident to more than $s'=2\eps n_0p_0$ edges in $E_2$. As $E(V_{k+2}, V_{k+3})$ is \reg{\eps}, by \autoref{l:degreeok} there are at most $\eps n_0$ vertices in $V_{k+3}$ with more than $(1+\eps)\abs{\tilde V_{k+2}}p_0$ neighbours in $\tilde V_{k+2}$. And by definition of \reg{\eps}ity these vertices are in total incident to at most $\eps n_0 (1+\eps)|\tilde V_{k+2}| p_0$ edges. Therefore for $\eps$ sufficiently small \[ \abs{\tilde V_{k+3}} \geq\frac{\abs{E_2}- \eps n_0 (1+\eps)\abs{\tilde V_{k+2}}p_0-n_0s'}{(1+\eps) \abs{\tilde V_{k+2}}p_0} \geq \frac{\frac{p_0}{3p}\abs{\tilde V_{k+2}}n_0p_0}{(1+\eps) \abs{\tilde V_{k+2}}p_0} \geq \frac{p_0}{4p}n_0 \geq 100\eps n_0. \] As before pick a subset $\tilde E_2\subseteq E_2$ such that every $v\in \tilde V_{k+3}$ is incident to exactly $s'$ edges of $\tilde E_2$. Apply \autoref{triangleExpansion} a third time with $G\leftarrow G[V_{k+2}\cup V_{k+3}\cup V_{k+4}]$, $\tilde V_2\leftarrow \tilde V_{k+3}$, $\tilde E\leftarrow \tilde E_2$ and denote the set of edges which form a triangle with some edge of $\tilde E_2$ with $E_3\subseteq E(V_{k+3},V_{k+4})$. We have $\abs{E_3}\geq (1-\eps)^2\left(\abs{\tilde V_{k+2}}-5\eps n_0\right)n_0p_0\geq \frac{6}{7}\abs{\tilde V_{k+2}} n_0p_0$. Let $\tilde V_{k+4}\subseteq V_{k+4}$ denote the subset of vertices which are incident to more than $s'=2\eps n_0p_0$ edges in $E_3$. As before we obtain \[ \abs{\tilde V_{k+4}} \geq\frac{\abs{E_3}- \eps n_0 (1+\eps)\abs{\tilde V_{k+3}}p_0-n_0s'}{(1+\eps) \abs{\tilde V_{k+3}}p_0} \geq \frac{\frac{5}{7}\abs{\tilde V_{k+3}}n_0p_0}{(1+\eps) \abs{\tilde V_{k+3}}p_0} \geq \frac{4}{7}n_0. \] Applying \autoref{triangleExpansion} a fourth time we see $E_3$ expands to $(1-\eps)^2(\abs{\tilde V_{k+4}}-5\eps n_0)n_0p_0>0.53n^2_0p_0$ edges in $E(V_{k+4}, V_{k+5})$. This concludes the proof. \end{proof} \section*{Concluding remarks} A referee of our paper pointed out that an alternative approach to prove our result is to use the result on the counting version of the K{\L}R-conjecture by Conlon, Gowers, Samotij, Schacht~\cite{Conlon2014}. That approach, in fact, can also be used to obtain similar results for all $k$-powers of an Hamilton cycle. Similarly to our result, this approach also requires that the density $p$ is bounded away from the lower bound by a factor of $n^\eps$ for some positive constant $\eps >0$. In~\cite{Milos17} it was recently shown that this factor can actually be replaced by a much smaller factor of $C(\log n)^{1/k}$. It is an interesting open problem whether this factor is actually necessary or whether one could go down all the way to the trivial lower bound. Also, even though it is obvious that local resilience does not allow a spanning subgraph of a square of a Hamilton cycle, two natural questions remain: how many vertices do we actually have to miss or what additional constraints do we need to add to local resilience in order to guarantee a spanning $k$-th power of a Hamilton cycle. \bibliographystyle{abbrv} \begin{thebibliography}{10} \bibitem{sparseBandwidth} P.~Allen, J.~B\"{o}ttcher, J.~Ehrenm\"{u}ller, and A.~Taraz. \newblock The bandwidth theorem in sparse graphs. \newblock {\em In preperation}. \bibitem{2016arXiv161106570B} P.~{Bennett}, A.~{Dudek}, and A.~{Frieze}. \newblock {Square of a Hamilton cycle in a random graph}. \newblock {\em ArXiv e-prints}, Nov. 2016. \bibitem{BOLLOBAS198397} B.~Bollob\'{a}s. \newblock Almost all {R}egular {G}raphs are {H}amiltonian. \newblock {\em European Journal of Combinatorics}, 4(2):97 -- 106, 1983. \bibitem{Bollobas1998modern} B.~Bollob\'{a}s. \newblock {\em Modern Graph Theory}. \newblock Springer New York, 1998. \bibitem{Conlon2014} D.~Conlon, W.~T. Gowers, W.~Samotij, and M.~Schacht. \newblock On the {K{\L}R} conjecture in random graphs. \newblock {\em Israel Journal of Mathematics}, 203(1):535--580, Oct 2014. \bibitem{dirac52} G.~A. Dirac. \newblock Some {T}heorems on {A}bstract {G}raphs. \newblock {\em Proceedings of the London Mathematical Society}, s3-2(1):69--81, 1952. \bibitem{GKRS07} S.~Gerke, Y.~Kohayakawa, V.~R\"{o}dl, and A.~Steger. \newblock Small subsets inherit sparse $\epsilon$-regularity. \newblock {\em Journal of Combinatorial Theory Series B}, 97(1):34--56, 2007. \bibitem{GerkeSteger05} S.~Gerke and A.~Steger. \newblock The sparse regularity lemma and its applications. \newblock In {\em Surveys in Combinatorics 2005}. Cambridge University Press, 2005. \bibitem{Kohayakawa1997216} Y.~Kohayakawa. \newblock {S}zemer\'edi's regularity lemma for sparse graphs. \newblock {\em Foundations of Computational Mathematics}, pages 216--230, 1997. \bibitem{BlowUp97} J.~Koml{\'o}s, G.~N. S{\'a}rk\"{o}zy, and E.~Szemer{\'e}di. \newblock Blow-up {L}emma. \newblock {\em Combinatorica}, 17(1):109--123, 1997. \bibitem{KOMLOS198355} J.~Koml\'{o}s and E.~Szemer\'{e}di. \newblock Limit distribution for the existence of {H}amiltonian cycles in a random graph. \newblock {\em Discrete Mathematics}, 43(1):55 -- 63, 1983. \bibitem{KSS96} J.~Koml\'{o}s, G.~N. S\'{a}rk\"{o}zy, and E.~Szemer\'{e}di. \newblock On the square of a {H}amiltonian cycle in dense graphs. \newblock {\em Random Structures \& Algorithms}, 9(1-2):193--211, 1996. \bibitem{doi:10.1137/120871729} D.~K\"{u}hn and D.~Osthus. \newblock On {P}\'{o}sa's conjecture for random graphs. \newblock {\em SIAM Journal on Discrete Mathematics}, 26(3):1440--1457, 2012. \bibitem{LS12} C.~Lee and B.~Sudakov. \newblock Dirac's theorem for random graphs. \newblock {\em Random Structures \& Algorithms}, 41(3):293--305, 2012. \bibitem{Nenadov16} R.~{Nenadov} and N.~{{\v S}kori{\'c}}. \newblock {Powers of cycles in random graphs and hypergraphs}. \newblock {\em ArXiv e-prints}, Jan. 2016. \bibitem{scott_2011} A.~Scott. \newblock Szemer\'{e}di's regularity lemma for matrices and sparse graphs. \newblock {\em Combinatorics, Probability and Computing}, 20(3):455--466, 2011. \bibitem{spencer90} J.~Spencer. \newblock Counting extensions. \newblock {\em Journal of Combinatorial Theory, Series A}, 55(2):247 -- 255, 1990. \bibitem{Szemeredi75} E.~Szemer{\'e}di. \newblock On sets of integers containing no $k$ elements in arithmetic progression. \newblock {\em Acta Arith.}, 27:299--345, 1975. \bibitem{Szemeredi78} E.~Szemer{\'e}di. \newblock Regular partitions of graphs. \newblock In {\em Probl{\`e}mes combinatoires et th{\'e}orie des graphes}, pages 399--401. Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976. \bibitem{Milos17} N.~\v{S}kori\'c, A.~Steger, and M.~Truji\'c. \newblock Local resilience of an almost spanning k-cycle in random graphs. \newblock {\em ArXiv e-prints}, Sept. 2017. \bibitem{west} D.~B. West. \newblock {\em Introduction to Graph Theory}. \newblock Prentice Hall, 2 edition, 2000. \end{thebibliography} \end{document}