% !TEX TS-program = pdflatex
% !TEX encoding = UTF-8 Unicode
% This is a simple template for a LaTeX document using the "article" class.
% See "book", "report", "letter" for other types of document.
\documentclass[12pt]{article} % use larger type; default would be 10pt
\usepackage{e-jc}
\specs{P3.56}{24(3)}{2017}
\synctex=1
\usepackage{amssymb, amsmath, amsthm, xcolor, enumerate}
\usepackage{mathtools}
\usepackage[utf8]{inputenc}
%\usepackage{fullpage}
\usepackage{hyperref}
\usepackage{microtype}
\usepackage{graphicx}
%%% SECTION TITLE APPEARANCE
%\usepackage{sectsty}
%\allsectionsfont{\sffamily\mdseries}
%%% ToC (table of contents) APPEARANCE
%\usepackage[nottoc,notlof,notlot]{tocbibind} % Put the bibliography in the ToC
%\usepackage[titles,subfigure]{tocloft} % Alter the style of the Table of Contents
%\renewcommand{\cftsecfont}{\rmfamily\mdseries\upshape}
%\renewcommand{\cftsecpagefont}{\rmfamily\mdseries\upshape} % No bold!
\usepackage{enumerate}
\newcommand{\eps}{\varepsilon}
\newcommand{\NN}{\mathbb N}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{obsv}{Observation}
%\newtheorem{prop}[theorem]{Proposition}
%\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
%\newtheorem*{sk}{High-level Sketch}
%\newtheorem{conj}[theorem]{Conjecture}
%\theoremstyle{definition}
%\newtheorem{rmk}[theorem]{Remark}
\newtheorem{definition}{Definition}
\DeclarePairedDelimiter{\floor}{\lfloor}{\rfloor}
\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
\newcommand{\parag}[1]{\vskip\baselineskip\noindent\textbf{#1}\hskip1em}
\title{\textbf{Stability for vertex cycle covers}}
\author{
J\'ozsef Balogh\thanks{Research is partially supported by Simons Fellowship, NSF
CAREER Grant DMS-0745185, Marie Curie FP7-PEOPLE-2012-IIF 327763.}\\
\small Department of Mathematical Sciences\\[-0.8ex]
\small University of Illinois at Urbana-Champaign\\[-0.8ex]
\small Urbana, Illinois 61801, USA\\
\small\tt jobal@math.uiuc.edu\\
\and
Frank Mousset\thanks{Supported by grant no.\ 6910960 of the Fonds National de la Recherche, Luxembourg.}\\
\small Institute of Theoretical Computer Science\\[-0.8ex]
\small ETH Z\"urich\\[-0.8ex]
\small 8092 Z\"urich, Switzerland\\
\small\tt frank.mousset@inf.ethz.ch\\
\and
Jozef Skokan\\
\small Department of Mathematics\\[-0.8ex]
\small London School of Economics\\[-0.8ex]
\small Houghton Street, London, WC2A 2AE, United Kingdom\\[-0.8ex]
\small and\\[-0.8ex]
\small Department of Mathematical Sciences\\[-0.8ex]
\small University of Illinois at Urbana-Champaign\\[-0.8ex]
\small Urbana, Illinois 61801, USA\\
\small\tt jozef@member.ams.org}
\date{\dateline{Apr 14, 2015}{Aug 31, 2017}{Sep 8, 2017}\\
\small Mathematics Subject Classifications: 05C35, 05C38, 05C75}
\begin{document}
\maketitle
\vspace{-0.8cm}
\begin{abstract}
In 1996 Kouider and Lonc proved the following natural generalization of Dirac's
Theorem: for any integer $k\geq 2$, if $G$ is an $n$-vertex graph with
minimum degree at least $n/k$, then there are $k-1$ cycles in $G$ that
together cover all the vertices.
This is tight in the sense that there are $n$-vertex graphs that
have minimum degree $n/k-1$ and that do not contain $k-1$ cycles with
this property. A concrete example is given by $I_{n,k} =
K_n\setminus K_{(k-1)n/k+1}$ (an edge-maximal graph on $n$ vertices with an
independent set of size $(k-1)n/k+1$). This graph has minimum degree
$n/k-1$ and cannot be covered
with fewer than $k$ cycles. More generally, given positive integers
$k_1,\dotsc,k_r$ summing to $k$, the disjoint union $I_{k_1n/k,k_1}+ \dotsb
+ I_{k_rn/k,k_r}$ is an $n$-vertex graph with the same properties.
In this paper, we show that there are no extremal examples
that differ substantially from the ones given by this construction. More
precisely, we obtain the following stability result: if a graph $G$
has $n$ vertices and minimum degree \emph{nearly} $n/k$, then it either
contains $k-1$ cycles covering all vertices, or else it must be close
(in `edit distance') to a subgraph of $I_{k_1n/k,k_1}+ \dotsb +
I_{k_rn/k,k_r}$, for some sequence $k_1,\dotsc,k_r$ of positive integers
that sum to $k$.
Our proof uses Szemer\'edi's Regularity Lemma and the related
machinery.
\end{abstract}
\section{Introduction}
The theorem of Dirac~\cite{Dir1952} saying that any graph $G$ on $n\ge 3$ vertices
with minimum degree at least $n/2$ contains a Hamilton cycle is one of the
classical results of graph theory. There is a rich collection of extensions of
this theorem in various directions. One possibility to replace the Hamilton
cycle with another spanning subgraph and ask what minimum degree guarantees its
existence.
For example, Bollob\'as~\cite{Bol1978} conjectured that for $c>1/2$ and
$\Delta>0$, every sufficiently large $n$-vertex graph $G$ with minimum degree
at least $cn$ contains every spanning tree of maximum degree at most $\Delta$.
The proof of this conjecture was given by Koml\'os, S\'ark\"ozy and
Szemer\'edi~\cite{KSS1995}, using the regularity method. Another example is the
famous Hajnal-Szemer\'{e}di theorem~\cite{HS1970}, saying that every graph on $kn$
vertices with minimum degree $(k-1)n$ contains $n$ vertex-disjoint copies of
$K_k$. Yet another well-known example is the conjecture of P\'osa
\cite{Erd1964} and Seymour \cite{Sey1974} that any $n$-vertex graph with
minimum degree at least $kn/(k+1)$ contains the $k$-th power of a Hamilton
cycle. If true, this would imply both Dirac's theorem and the Hajnal-Szemer\'{e}di
theorem. The P\'{o}sa-Seymour conjecture was proved for large $n$ by Koml\'os, S\'ark\"ozy, and
Szemer\'edi~\cite{KSS1996a}, \cite{KSS1998}. Later, Levitt, S\'ark\"ozy,
Szemer\'edi \cite{LSS2010} and Chau, DeBiasio, and Kierstead~\cite{CDK2011}
proved the same result with different methods, for smaller values of~$n$. When
we consider the square of a~Hamilton path instead of the square of a Hamilton
cycle, Fan and Kierstead~\cite{FK1996} proved that $(2n-1)/3$ is the optimal
minimum degree for every $n$.
All of these results are about graphs with minimum degree larger than $n/2$.
Indeed, as soon as the minimum degree can be below $n/2$, one loses a lot of
global structure: for example, the graph may no longer be connected. Here we
will explore the direction where the minimum degree can be smaller than $n/2$.
Already Dirac observed that every $2$-connected graph $G$ contains a cycle of
length at least $\min{\{v(G),2\delta(G)\}}$~\cite{Dir1952}. The connectivity
assumption in this result might seem artificial, and indeed several
researchers have looked at the case without this assumption.
Alon~\cite{Alo1986} proved that any $n$-vertex graph $G$ with minimum degree at
least $n/k$ must contain a cycle of length at least $\floor{n/(k-1)}$. Later
Bollob\'as and H\"{a}ggkvist~\cite{BH1989} proved that such a graph must in fact
contain a cycle of length $\ceil{n/(k-1)}$, which is optimal. An Ore-type
condition for the same problem is considered in~\cite{EM1989}. More recently,
Nikiforov and Schelp~\cite{NS2006} and Allen~\cite{All} have considered the
problem of finding cycles of a specified length in graphs of minimum degree at
least $n/k$.
In 1987 Enomoto, Kaneko and Tuza~\cite{EKT1988} conjectured that any graph $G$
on $n$ vertices with $\delta(G)\geq n/k$ contains a collection of at most $k-1$
cycles that cover all vertices of $G$. Note that in the case $k=2$ this reduces
to Dirac's theorem. Moreover, since at least one of these cycles would need to
have length at least $\ceil{n/(k-1)}$, the conjecture implies the result of
Bollob\'{a}s and H\"{a}ggkvist mentioned above. The case $k=3$ was already shown by Enomoto,
Kaneko and Tuza~\cite{EKT1988}. For the case of $2$-connected graphs $G$, the
conjecture was shown by Kouider in~\cite{Kou1994}. An Ore-type condition for
$k=3$ was given in~\cite{EKKT1995}. Finally, Kouider and Lonc solved the
conjecture (even in the stronger Ore-version) in~\cite{KL1996}. Thus:
\begin{theorem}[Kouider and Lonc~\cite{KL1996}]\label{thm:kl}
Let $k\geq 2$ be an integer and let $G$ be an $n$-vertex graph
with minimum degree $\delta(G)\ge n/k$. Then the vertex set of $G$
can be covered with $k-1$ cycles\footnote{Edges and vertices count as cycles.}.
\end{theorem}
This leaves open the problem of determining the structure of the extremal
examples. The minimum degree condition in Theorem~\ref{thm:kl} is tight by a
family of examples of graphs with $n$ vertices and minimum degree $n/k-1$ that
cannot be covered with $k-1$ cycles.
First, we can consider the disjoint union of $k$ copies of $K_{n/k}$. This
graph has $n$ vertices and minimum degree $n/k-1$ and yet clearly cannot be
covered with $k-1$ cycles, because every cycle must be confined to a single
copy of $K_{n/k}$. On the other extreme, we can imagine a graph on $n$ vertices
with minimum degree $n/k-1$ that contains an independent set of size
$(k-1)n/k+1$. A concrete example is given by the graph $I_{n,k}:= K_{n}
\setminus K_{(k-1)n/k+1}$, although there are also sparser examples that still
have minimum degree $n/k-1$. Note that every cycle in such a graph can cover at
most $n/k-1$ vertices of the independent set, so at least $k$ cycles are needed
to cover all vertices. Finally, the we can interpolate between these two types
of examples as follows. For any sequence $k_1,\dotsc,k_r$ of positive integers
such that $k_1+\dotsb=k_r=k$, we may consider the disjoint union $G= I_{k_1n/k,k_1}+ \dotsb +
I_{k_rn/k,k_r}$. Then $G$ is an
$n$-vertex graph with minimum degree $n/k-1$ that
cannot be covered with $k-1$ cycles.
Note here that $I_{n/k,1}=K_{n/k}$, so this construction includes the disjoint union
of cliques.
It is natural to ask whether there are families of examples that are
substantially different. The main result of this paper is that this is not
the case: if the minimum degree is close to $n/k$ then either
the graph can be covered by $k-1$ cycles, or it is close to a subgraph of
$I_{k_1n/k,k_1}+ \dotsb + I_{k_rn/k,k_r}$ for a sequence $k_1,\dotsc,k_r$ of
positive integers summing to $k$. To make this precise, we need the following definitions:
\begin{definition}[separable partition]
A partition of the vertices of a graph $G$ into sets
$X_1,\dotsc,X_r$ is \emph{separable} if for all $i\neq
j$ there exists a single-vertex $X_i$-$X_j$-cut in $G$.
\end{definition}
\begin{definition}[$(k',k,\beta)$-stable]\label{def:stable}
Let $G$ be a graph of order $n$. Given a positive integer $k$ and real numbers
$k'\in [1,k]$ and $\beta\in (0,1)$, we say that a subset $X\subseteq V(G)$ is
\emph{$(k', k, \beta)$-stable} if there exists a subset $I\subseteq X$
such that:
\begin{enumerate}[(S1)]
\item $|X|= k'n/k\pm \beta n$ and $|I|= (k'-1)n/k\pm \beta n$;
\item we have $\delta(G[X])\geq n/k^4-\beta n$ and all but at most
$\beta n$ vertices in $X$ have degree at least $n/k-\beta n$ in
$G[X]$;
\item $e(G[I])\leq\beta n^2$.
\end{enumerate}
\end{definition}
With these definitions, our main result reads as follows:
\begin{theorem}\label{thm:stability}
Given an integer $k\geq 2$ and $\beta>0$, there is $\alpha>0$ such that the
following holds for sufficiently large $n$. Assume that $G$ is a graph with
$n$ vertices and minimum degree at least $(1-\alpha)n/k$ whose vertices
cannot be covered by $k-1$ cycles.
Then there is a separable partition $X_1,\dotsc,X_r$ of the vertices of $G$
and positive integers $k_1,\dotsc,k_r$ such that
\begin{itemize}
\item each $X_i$ is $(k_i, k, \beta)$-stable in $G$, and
\item $k_1+\dotsb+k_r = k$.
\end{itemize}
\end{theorem}
Note that if $X_i$ is $(k_i,k,\beta)$-stable, then $G[X_i]$ is `$\beta$-close'
to a subgraph of $I_{k_in/k,k_i}$ with minimum degree $n/k$, with the set
$I$ in Definition~\ref{def:stable} playing the role of the (nearly) independent set.
Note also that if
$X_1,\dotsc,X_r$ is a separable partition, then $G$ can only contain very few
(say, at most $n$) edges going between different parts $X_i$ and $X_j$. Thus every
graph $G$ as in the theorem can be turned into a
subgraph of $I_{k_1n/k,k_1}+\dotsb +I_{k_rn/k,k_r}$ by changing at most
$C \beta n^2$ edges, for a constant $C>0$ independent of $\beta$.
Results of this type are usually referred to as
\emph{stability theorems}, the most famous example being the
Erd\H{o}s-Simonovits stability theorem for the Tur\'{a}n
problem~\cite{Sim1968}. It would also be interesting to find the
characterization of extremal families when $k=k(n)\to\infty$ as $n\to\infty$.
For the proof of Theorem~\ref{thm:stability}, we use the method of connected
matchings, invented by \L{}uczak~\cite{L1999}, which is based on an application
of Szemer\'edi's Regularity Lemma~\cite{Sze1976}. This method seems to be
widely applicable; for more applications (especially in Ramsey theory)
see~\cite{BBG+2014, BS2009a, BHP2012, FL2007, SSS2013, LS2017}.
\section{Preliminaries}
The following lemma states several useful properties of stable sets. The proof
of the lemma is not very interesting but quite technical, so we postpone it to
Section~\ref{sec:stable-sets} at the end of this paper.
\begin{lemma}[Properties of stable sets]\label{lemma:connecting}
For every integer $k\geq 2$, there is some $\beta >0$ such that the
following holds for all sufficiently large $n$. Let $G$ be a graph
of order $n$ and assume that $X$ is an $(k',k,\beta)$-stable subset of
$V(G)$, for some $k'\in [1,k]$. Then
\begin{enumerate}[(a)]
\item the vertices of $G[X]$ can be covered with $\ceil{k'}$
cycles;
\item given any two vertices $x,y\in X$, the vertices of $G[X]$ can be
covered by $\ceil{k'}-1$ cycles and a single path with endpoints $x$ and
$y$;
\item if, additionally, all but at most $n/k^3$ vertices $x\in X$ satisfy
$d(x,X)\geq |X|/k'$, then the vertices of $G[X]$ can be covered with
$\ceil{k'}-1$ cycles.
\end{enumerate}
\end{lemma}
We will also have occasion to use Szemer\'{e}di's Regularity Lemma~\cite{Sze1976}
and some related results. Given $\eps\in(0,1)$, we say that a pair $(A,B)$ of
disjoint sets of vertices of a graph $G$ is \emph{$\eps$-regular} if, for all
subsets $X\subseteq A$ and $Y\subseteq B$ such that $|X|\geq \eps |A|$ and
$|Y|\geq
\eps |B|$, we have \[ \big| d_G(X,Y) - d_G(A,B)\big| \leq \eps. \]
A pair
$(A,B)$ is called $(\eps,\delta)$-\emph{super-regular} if it is
$\eps$-regular and \[ d_G(a,B) \geq \delta |B| \text{ for all } a\in A\qquad
\text{and} \qquad d_G(b,A) \geq \delta|A| \text{ for all } b\in B. \]
\begin{theorem}[Degree form of the Regularity Lemma~\cite{KS1996}]
\label{thm:regularity} For every $\eps >0$ and every positive integer
$t_0$, there is an $M=M(\eps, t_0)$ such that the following holds for
every graph $G=(V, E)$ of order $n\ge M$ and every real number $d \in [0,1]$.
There exists an integer $t\in [t_0, M]$, a partition $(V_i)_{i=0}^t$ of the
vertex set $V$ into $t+1$ sets (called \emph{clusters}), and a subgraph
$G'\subseteq G$ with the following properties:
\begin{enumerate}
\item[(R1)] $|V_{0}| \leq \eps |V|$,
\item[(R2)] all clusters $V_{i}$ are of the same size $m\in ((1-\eps)n/t, n/t)$,
\item[(R3)] $d_{G'}(v) > d_{G}(v) -(d+\eps)n$ for all $v\in V\setminus V_0$,
\item[(R4)] $e(G'\left[V_{i}\right])=0$ for all $1\leq i\leq t$,
\item[(R5)] for all $1\leq i< j \leq t$, the pair $(V_{i},V_{j})$ is
$\eps$-regular, with a density either $0$ or greater than $d$.
\end{enumerate}
\end{theorem}
A partition as in Theorem~\ref{thm:regularity} is usually called an
\emph{$\eps$-regular partition} with \emph{exceptional set} $V_0$. Given a
partition $(V_i)_{i=0}^t$ of the vertex set $V$ and a subgraph $G'\subseteq G$
satisfying conditions (R1)--(R5), we define the \emph{$(\eps, \delta)$-reduced
graph} as the graph $R$ with vertex set $[t]$ and edges corresponding to those
pairs $ij$ for which $(V_i, V_j)$ is $\eps$-regular and with density at least
$\delta$.
We shall also use the following special case of the famous Blow-up Lemma of
Koml\'{o}s, S\'{a}rk\"{o}zy, and Szemer\'{e}di~\cite{KSS1996} (see also Lemma 24 and the first
remark after Lemma~25 in~\cite{Kom1999}).
\begin{lemma}[Blow-up Lemma]\label{lemma:blowup} For every $\delta>0$ there exists an
$\eps >0$ such that the following holds. Assume that a graph $G$ contains
an $(\eps,\delta)$-super-regular pair $(A,B)$ with $|A|= |B|$ and let $x
\in A, y \in B$. Then $G[A,B]$ contains a Hamilton path with endpoints $x$
and $y$.
\end{lemma}
We will also need the Chernoff bounds for binomial and hypergeometric random
variables. Recall that a random variable $X$ is binomially distributed
if it is a sum of a fixed number of i.i.d.\ $\{0,1\}$-valued random variables,
while it is hypergeometrically distributed with parameters $N,K,n$ if it counts
the number of successes in a subset of size $n$ drawn uniformly at random from
a population of $N$ elements that
contains $K$ successes.
\begin{lemma}[Chernoff bounds~{\cite[Theorem 1.17]{Doe2011}}]\label{lemma:cher}
Assume that $X$ is either binomially or hypergeometrically distributed.
Then for all $\eps\in (0,1)$
\[ \Pr[|X-\mathbf E[X]|\geq \eps\mathbf E[X]] \leq 2\exp(-\eps^2\mathbf E[X]/3). \]
\end{lemma}
\section{Proof of Theorem \ref{thm:stability}}
Let $k\ge 2$ be a fixed integer. Without loss of generality, we may assume that
the given $\beta>0$ is sufficiently small. Let us choose constants
$\eps,d,\alpha\in (0,1)$ and $t_0\in \NN$ such that \[ \frac{1}{t_0} \prec
\alpha \prec \eps \prec d \prec \beta, \] where by $a \prec b$ we mean that $a$
is chosen to be sufficiently smaller than $b$.
Let $G$ be a graph of order $n$ with $\delta(G)\geq (1-\alpha)n/k$, where $n$
is sufficiently large. Let $\hat\eps := \eps/(4k)$ and $\hat d := d+(k+1)\hat
\eps$. We apply the Regularity Lemma (Theorem~\ref{thm:regularity}) to $G$ with
parameters $\hat\eps$, $t_0$, and $\hat d$ to obtain a partition
$(V_i)_{i=0}^t$ and a subgraph $G'\subseteq G$ satisfying (R1--5), for some
integer $t_0\le t\le M$ and with $\hat\eps,\hat d$ instead of $\eps,\delta$. We
denote by $R$ the $(\hat \eps,\hat d)$-reduced graph corresponding to this
partition.
\subsection*{Structure of the reduced graph.} The reduced graph $R$ is has $t$ vertices and it satisfies
\begin{equation}\label{eq:mindeg-R}
\delta(R) \geq \frac{(1-2dk)t}{k}> \frac{t}{k+1}.
\end{equation}
To see this, simply observe that the vertices of every cluster in $R$ with
degree less than $(1-2dk)t/k$ would have degree at most $(1-2dk)(t/k)\cdot
(n/t) +\hat\eps n < (1-\alpha)n/k - (\hat d+\hat\eps)n$ in $G'$,
contradicting property (R3) of Theorem~\ref{thm:regularity}.
Let us denote by $r$ the number of components of $R$ and by
$R_1,\ldots,R_r$ the components themselves. Since each component has size at
least $\delta(R)> t/(k+1)$, there can be at most $k$ components altogether,
i.e., $r \leq k$.
For each component $R_i$, define a real number
\begin{equation}\label{eq:def-s_i}
s_i:=\frac{k v(R_i)}{(1-2dk)t}\in (1,k+1),
\end{equation}
where the given bounds follow from $\delta(R_i) < v(R_i) \leq t$ and \eqref{eq:mindeg-R}.
Note that by combining \eqref{eq:mindeg-R} and \eqref{eq:def-s_i} we have
\begin{equation}\label{eq:mindegree-in-reduced-component}
\delta(R_i)\geq v(R_i)/s_i.
\end{equation}
Finally, since $v(R_1)+\dotsc+v(R_r) = t$, we have
\begin{equation}\label{eq:s_i-sum}
\sum_{i=1}^r s_i =\frac{ k}{1-2dk} \leq (1+3dk)k,
\end{equation}
a fact that will be important later.
The components where $s_i < 2+4dk^2$ have such a large minimum degree that we
can treat them by a special argument. For the others, we have the following
structural lemma, whose proof we postpone to a later point.
\begin{lemma}\label{lemma:matchings}
Let $i\in [r]$ and assume that $s_i \geq 2+4dk^2$. Let $m_i =
\floor{s_i-4dk^2}$ and $t_i = v(R_i)$. Then at least one of the following is
the case:
\begin{enumerate}[(i)]
\item the graph $R_i$ contains a subset $I\subseteq V(R_i)$ of size $(s_i-1)t_i/s_i-6dk^2 s_i t_i$
that is almost independent in the sense that $e(I) \leq 4dk^2 s_i t_i^2$, or
\item the graph $R_i$ contains matchings $M_1,\ldots,M_{m_i}$
and disjoint subsets of vertices $D_1,D_2$ with the following properties:
\begin{enumerate}[(a)]
\item $D_1\cap V(M_1)=\emptyset$, and for $j>1$, $D_2\cap V(M_j) = \emptyset$;
\item each vertex of $R_i$ has at least $d t_i/(3s_i)$ neighbours in each set $D_1,D_2$;
\item the matchings $M_1,\dotsc,M_{m_i}$ cover the vertex set of $R_i$.
\end{enumerate}
\end{enumerate}
\end{lemma}
We apply Lemma~\ref{lemma:matchings} to each component $R_i$ where $s_i \geq
2+4dk^2$. From all such components that are in case (ii) of the lemma, we
obtain a collection $\mathcal M$ of matchings in $R$. Since each component
$R_i$ contributes at most $m_i$ matchings, and using~\eqref{eq:s_i-sum}, we see
that $\mathcal M$ contains at most $k$ matchings.
The significance of the matchings and the sets $D_1$ and $D_2$ will become
clear at a later point. Essentially, we will see that for each matching $M\in
\mathcal M$, we can cover the vertices in the subgraph of $G$ induced by the
clusters participating in the matching using a single cycle (covering also a
certain number of exceptional vertices in $V_0$ that are `assigned' to the
matching $M$). This will be an application of the Blow-up Lemma. Here the sets
$D_1$ and $D_2$ are used on the one hand to balance the sizes of the clusters
in $M$ and also to absorb the exceptional vertices assigned to
the matching.
However, to be able to apply the Blow-up Lemma, we need to modify the
regular partition a little, which we will do next.
\subsection*{Modifying the regular partition.}
We need to modify the initial regular partition $V_0,\dotsc,V_t$ in such a
way that each edge in each matching in $\mathcal M$ corresponds not just to an
$\hat \eps$-regular pair of density at least $\hat d$, but in fact to an
$(\eps, d$)\emph{-super-regular} pair (this is the reason why we applied
the Regularity Lemma with the slightly stronger parameters $\hat\eps,\hat
d$ instead of $\eps,d$). For this, we proceed as follows. For each edge
$(V_i,V_j)$ of a given matching $M\in \mathcal M$, we observe that by
regularity, at most $\hat \eps |V_i|$ vertices of $V_i$ have fewer then
$\hat d|V_j| - \hat\eps |V_j| = d|V_j|+k\hat\eps |V_j|$ neighbours in
$V_j$ and vice-versa. We move all vertices in these sets to the exceptional
set. Since $\mathcal M$ contains at most $k$ matchings, we remove at most
$k\hat \eps |V_i|$ vertices from each cluster $V_i$. By removing some
additional vertices, we can make sure that after this, all clusters are still
of the same size. Then one can check that the properties (R1--5) of
Theorem~\ref{thm:regularity} hold for the new partition with $\eps, d$
instead of $\hat\eps,\hat d$ (and with the same $G'$ and $t$). Moreover, we
have gained the property that the edges of the matchings in $\mathcal M$
correspond to $(\eps,d)$-super-regular pairs in $G$.
\subsection*{Partitioning into stable sets.}
For each $i\in[r]$, let us define $G_i$ as the subgraph of $G$ induced by the
vertices in clusters in $R_i$. Note that
\[ \bigcup_{i=1}^r V(G_i) = V(G)\setminus V_0. \]
Using (R2), we have \[ \frac{(1-\eps) n v(R_i)}{t} \leq v(G_i) \leq
\frac{nv(R_i)}{t}, \] so by plugging in the definition of $s_i$, we get
\begin{equation}\label{eq:g_i-size} \frac{(1-\eps)(1-2dk)n s_i}{k} \leq
v(G_i) \leq \frac{(1-2dk) n s_i}{k}. \end{equation} Using the inequalities \[
(1+dk)(1-2dk) = 1-dk-2d^2k^2 \leq 1-\alpha -(d+\eps)k \] and $\delta(G)\geq
(1-\alpha)n/k$ and properties (R3)--(R5), we obtain that
\begin{equation}\label{eq:mindegree-in-component} \delta(G_i) \geq
\frac{(1-\alpha)n}{k}-(d+\eps)n \geq (1+dk)\frac{v(G_i)}{s_i}.
\end{equation}
Since $1\leq r\leq k$ and since $|V(G_1)\cup \dotsb \cup V(G_r)| \geq n - \eps
n$, it is clear that for every vertex $v\in V(G)$, there exists at least one
$i\in [r]$ such that the degree of $v$ into $V(G_i)$ is at least
$(\delta(G)-\eps n)/k$. Thus, we can partition the exceptional set $V_0$
into sets $U_1,\dotsc,U_r$, where $U_i$ contains only vertices with at least \[
(1-\alpha-k\eps)n/k^2 \geq n/k^3 \] neighbours in $V(G_i)$. The sets $Y_i:=
V(G_i)\cup U_i$ form a partition of the vertex set of $G$. This is
\emph{almost} the partition $X_1,\dotsc,X_r$ that Theorem~\ref{thm:stability}
asks for; as we will see, the sets $Y_i$ for which $s_i\in [2,2+4dk^2)$ might
have to be partitioned further.
To complete the proof of Theorem~\ref{thm:stability}, we need to distinguish
three cases. Each case is handled by one of the following lemmas.
\begin{lemma}\label{lemma:dirac}
If $1\leq s_i < 2$, then $G[Y_i]$ is Hamiltonian. Moreover,
if $s_i < 1+4dk^2$, then $Y_i$ is actually $(1, k, \beta)$-stable in $G$.
\end{lemma}
\begin{lemma}\label{lemma:almost-dirac}
If $2 \leq s_i < 2+4dk^2$, then at least one of the following holds:
\begin{enumerate}[(i)]
\item $G[Y_i]$ is Hamiltonian,
\item $Y_i$ is $(2,k,\beta)$-stable in $G$, or
\item there is a partition of $Y_i$ into two $(1,k,\beta)$-stable sets in $G$.
\end{enumerate}
\end{lemma}
\begin{lemma}\label{lemma:non-dirac}
If $2+4dk^2 \leq s_i$, then either $Y_i$ can be covered with $\floor{s_i-4dk^2}$
cycles in $G[Y_i]$, or $Y_i$ is $(\floor{s_i},k,\beta)$-stable in $G$.
\end{lemma}
The proofs of the first two lemmas are elementary. However, for the last lemma,
we will need to use the structure given by Lemma~\ref{lemma:matchings} and the
Blow-up Lemma (Lemma~\ref{lemma:blowup}). Given these three lemmas, we can
complete the proof of Theorem~\ref{thm:stability}.
\begin{proof}[Proof of Theorem \ref{thm:stability}]
By combining Lemmas~\ref{lemma:connecting}, \ref{lemma:dirac},
\ref{lemma:almost-dirac} and \ref{lemma:non-dirac}, we see that each graph
$G[Y_i]$ can be covered with at most $\floor{s_i}$ cycles. By
\eqref{eq:s_i-sum}, we have $\floor{s_1} + \dotsb + \floor{s_r} \leq k$.
Since we assume that $G$ cannot be covered with $k-1$ cycles, this
inequality is really an equality, i.e., $\floor{s_1}+\dotsb+\floor{s_r} = k$.
This implies that for every $i\in [r]$, we have $\floor{s_i}\leq s_i <
\floor{s_i} + 4dk^2$, as otherwise~\eqref{eq:s_i-sum} yields the
contradiction
\[ k = \sum_{i=1}^r\floor{s_i} = \sum_{i=1}^r s_i-\sum_{i=1}^r
(s_i-\floor{s_i}) \leq (1+3dk)k-4dk^2 < k. \]
But then, using again that we cannot cover the vertices of $G$ with $k-1$ cycles,
Lemmas~\ref{lemma:dirac}, \ref{lemma:almost-dirac} and \ref{lemma:non-dirac}
tell us that the situation is as follows:
\begin{itemize}
\item if $1\leq s_i < 2$, then $Y_i$ is $(1,k,\beta)$-stable;
\item if $2 \leq s_i < 2+ 4dk^2$, then $Y_i$ is either $(2,k,\beta)$-stable
or the union of two disjoint $(1,k,\beta)$-stable sets;
\item if $s_i \geq 2+4dk^2$, then $Y_i$ is $(\floor{s_i},k,\beta)$-stable.
\end{itemize}
By splitting some of the sets $Y_i$ into two stable sets (if they are in the
second case and not stable already), we obtain a partition of the vertices
into $r'\geq r$ sets $X_1,\dotsc,X_{r'}$ such that each $X_i$ is
$(k_i,k,\beta)$-stable for some integer $k_i$, where moreover
$k_1+\dotsb+k_{r'}=k$.
To complete the proof, we show that $X_1,\dotsc,X_{r'}$ is a separable
partition. For this, let $i\neq j$ and assume for a contradiction that there is no
single-vertex $X_i$-$X_j$-cut in $G$. Then by Menger's theorem there are
two vertex-disjoint $X_i$-$X_j$-paths in $G$, and so using
Lemma~\ref{lemma:connecting} (b) it is possible to cover $X_i\cup X_j$ by a
$k_i+k_j-1$ cycles in $G$. Moreover, by Lemma~\ref{lemma:connecting} (a) it is
possible to cover all other sets $X_\ell$ by $k_\ell$ cycles. Hence, there is
a cover of the vertices of $G$ by $k_1+\dotsb+k_{r'}-1 =k-1$ cycles, which we
assumed is not the case.
\end{proof}
It remains to give the proofs of Lemmas~\ref{lemma:matchings}, \ref{lemma:dirac},
\ref{lemma:almost-dirac}, and \ref{lemma:non-dirac}.
\begin{proof}[Proof of Lemma \ref{lemma:matchings}]
Since by \eqref{eq:mindeg-R}, we have $v(R_i) \geq t/(k+1)\geq t_0/(k+1)$, we
can assume that $t_i=v(R_i)$ is very large compared to $1/d$. The only other
property of $R_i$ that we will need is that $\delta(R_i)\geq v(R_i)/s_i$,
by~\eqref{eq:mindegree-in-reduced-component}.
First, we show that it is possible to choose disjoint subsets
$D_1,D_2\subseteq V(R_{i})$, each of size at most $2d t_i$, in such a way
that every vertex in $V(R_{i})$ has at least $d t_i/(3s_i)$ neighbours in
$D_j$, for $j\in\{1,2\}$. For this, let $D$ be a random subset of $V(R_i)$ in
which every cluster is included independently with probability $d$. Then let
$D_1\cup D_2 = D$ be a partition of $D$ into two sets chosen uniformly at
random. The expected size of $D_1$ and $D_2$ is $dt_i/2$. Thus, by Markov's
inequality, with probability at least $1/2$, we have $|D_1|,|D_2|\leq 2d
t_i$. Fix some vertex $v\in V(R_i)$. The expected number of neighbours of $v$
that are in $D_1$ is at least $d \delta(R_i)/2 \geq dt_i/(2s_i)$. Using the
Chernoff bounds, the probability that the neighborhood of $v$ does not
contain at least $d t_i/(3s_i)$ elements of $D_1$ is smaller than $1/(4t_i)$,
provided that $t_i$ is large enough. Similarly, the probability that the
neighborhood of $v$ does not contain at least $\beta t_i/(3s_i)$ elements of
$D_2$ is smaller than $1/(4t_i)$. The union bound shows that there exists a
good choice for $D_1$ and $D_2$. From now on, fix such a choice.
Let $m_i:=\floor{s_i-4dk^2}$ and observe that by assumption, we have $m_i\geq
2$. We want to cover the set $V(R_i)$ by $m_i$ matchings
$M_1,\dotsc,M_{m_i}$, so that $M_1$ is disjoint from $D_1$ and $M_2,\dotsc,
M_{m_i}$ are disjoint from $D_2$. To do this, we first let $M_1$ be a maximal
matching in $R_i$ that covers $D_2$ and is disjoint from $D_1$.
Note that there certainly exists such a matching because of the minimum
degree condition~\eqref{eq:mindegree-in-reduced-component} and because
$D_1$ and $D_2$ are very small. Now, to choose the matchings $M_j$ for $j\geq
2$, we partition the set $V(R_i)\setminus V(M_1)$ equitably into sets
$A_2,\dotsc,A_{m_i}$. Then we let $M_j$ be a matching that is disjoint from
$D_2$ and that covers the maximum number of vertices of $A_j$ (among all
matchings that are disjoint from $D_2$); moreover, we assume that $M_j$ has
maximum size among all such matchings. There are now two cases.
\subsection*{Non-extremal case.} If $|M_1|\geq t_i/s_i+ 2dk^2 s_i t_i$, then we
claim that we are in case (ii) of the lemma. The only thing to check is
whether the matchings cover $R_i$. The set $V(R_i)\setminus V(M_1)$ has size
\begin{align*}
t_i-2|M_1| &\leq t_i -\frac{2t_i}{s_i} -4dk^2s_i t_i =\frac{t_i(s_i-2-4dk^2 s_i^2)}{s_i}\\
& \leq \frac{t_i(s_i-4dk^2-2)(1-2ds_i)}{s_i} \leq \frac{t_i(m_i-1)(1-2ds_i)}{s_i},
\end{align*}
so for each $2\leq j\leq m_i$, we have \[|A_j| \leq
\ceil*{\frac{t_i-2|M_1|}{m_i-1}} \leq \ceil{t_i/s_i - 2d t_i}
\leq \delta(R_i) - |D_2|.\] Thus, there exists a matching disjoint from $D_2$
that covers $A_j$ completely, and since $M_j$ was chosen to cover the most
vertices of $A_j$ among all matchings disjoint from $D_2$, the matchings
cover every vertex of $R_i$.
\subsection*{Extremal case.} If $|M_1|1$, $D_2\cap V(M_j) = \emptyset$;
\item each vertex of $R_i$ has at least $d t_i/(3s_i)$ neighbours in each set $D_1,D_2$;
\item the matchings $M_1,\dotsc,M_{m_i}$ cover the vertex set of $R_i$.
\end{enumerate}
\end{enumerate}
Recall that $U_i$ is a set of at most $\eps n$ vertices that have degree at
least $n/k^3$ into $V(G_i)$. If (i) is the case, then it follows easily from
\eqref{eq:mindegree-in-component} and the
properties of regularity that $Y_i=V(G_i)\cup U_i$ is a $(s_i,k,\beta)$-stable
set in $G$ (note that $\eps,d$ are tiny compared to $\beta$).
Since by \eqref{eq:mindegree-in-component}, all but $|U_i|\leq \eps n$ vertices
of $Y_i$ have degree at least $|Y_i|/s_i$ in $G[Y_i]$,
it follows from Lemma~\ref{lemma:connecting} (c) that $G[Y_i]$
can be covered with $\ceil{s_i}-1$ cycles. Therefore, either
we can cover $G[Y_i]$ with $\floor{s_i-4dk^2}$ cycles, or $
\floor{s_i-4dk^2} < \ceil{s_i}-1\leq s_i$ and so $s_i \leq \floor{s_i}+4dk^2$.
In the former case, we are done, and in the latter case, it is again easy to verify
that $Y_i$ must actually be $(\floor{s_i},k,\beta)$-stable (again, the extra
$4dk^2$ gets lost in the much larger $\beta$). Thus if we are in case (i),
then the lemma holds.
From now on, assume that we are in case (ii). Recall that each edge of each
matching $M_j$ is $(\eps,d)$-super-regular. We may assume that $\eps$
is so small that Lemma~\ref{lemma:blowup} applies with $\delta = d$. The
general idea is to use Lemma~\ref{lemma:blowup} to cover the preimage of each
matching (meaning: the vertices of $G$ participating in clusters of the
matching) by a single cycle in $G[Y_i]$, and to do this in such a way that
all the vertices in $U_i$ are absorbed. Of course, if we manage to do so,
then we are done. We start by assigning the exceptional vertices of $U_i$ to
clusters $C$ into which they have large degree.
\subsection*{Assigning the exceptional vertices.} For each matching $M_j$, let us
write $V_{M_j}\subseteq V(G_i)$ for the union of all clusters in $M_j$. As
the matchings $M_j$ cover the vertices of $R_i$, we have
$\bigcup_{j=1}^{m_i}V(M_j)=V(G_i)$. Since each vertex of $U_i$ has degree at
least $n/k^3$ into $V(G_i)$, and since $m_i\leq k$, we see that for every
$u\in U_i$ there exists a $j_u\in [m]$ such that $u$ has $n/k^4$ neighbours
in $V_{M_{j_u}}$. Let us write $U_i^{(j)} := \{u\in U_i \mid j_u = j\}$ for
the exceptional vertices assigned to the matching $M_j$ in this way.
Since $|V(M_j)|\leq |V(R)|\leq t$ and since each cluster has size at most
$2n/t$, it follows that for each vertex $u\in U_i^{(j)}$, there are at least
$t/(4k^4)$ clusters $C\in V(M_j)$ such that $d(u,C)\geq n/(2k^4 t)$. Indeed,
if this were not true, then the degree of $u$ into $V(M_j)$ would be strictly
below \[ t\cdot \frac{n}{2k^4t} + \frac{t}{4k^4}\cdot \frac{2n}{t} =
\frac{n}{k^4}, \] a contradiction with the definition of $U_i^{(j)}$.
We now assign the vertices of $U^{(j)}_i$ to clusters in $V(M_j)$ in such a way that
\begin{enumerate}[(i)]
\item if $u$ is assigned to the cluster $C$, then $d(u,C)\geq n/(2k^4t)$, and
\item at most $4k^4\eps n/t$ vertices are assigned to each cluster.
\end{enumerate}
Since $|U_i^{(j)}|\leq \eps n$ and since each vertex has $t/(4k^4)$ candidates, such an assignment
exists. Take any such assignment and write $U_C$
for the exceptional vertices assigned to the cluster $C\in V(M_j)$.
\subsection*{Covering the matchings.}
From the above, it is clear that the sets
\[V_{M_1}\cup U_i^{(1)},V_{M_2}\cup U_i^{(2)},\dotsc,V_{M_{m_i}}\cup U_i^{(m_i)}\]
cover the set $Y_i$.
In the following,
we will cover each set $V_{M_j}\cup U_i^{(j)}$ by a single cycle in $H_i$
(however, this cycle might use vertices outside of $V_{M_j}\cup U_i^{(j)}$).
Fix some $j\in [m_i]$, and assume $\ell\in \{1,2\}$ is such that $D_\ell$ is
disjoint from the matching $M_j$. The embedding proceeds in two steps: first,
for each cluster $C\in V(M_j)$, we connect the vertices of $U_C$ by a short
path using only vertices from $D_\ell$, $C$, and $U_C$ (and making sure that
the paths for different $C$ are vertex-disjoint); second, we use Lemma~\ref{lemma:blowup} to
connect these short paths into a cycle spanning the whole of $V_{M_j}\cup
U_i^{(j)}$.
In the first step, it is important to make sure that each path uses exactly
the right number of vertices in the cluster $C$, as otherwise the second step
might fail. Because we do not want to make this completely precise at this
point, we assign to each cluster $C$ an integer
\[ \ell_C\in [8k^4 \eps n/t, 100k^4\eps n/t],\]
and we will make sure that after creating the short path for $C$, the number
of vertices of $C$ not used by the path is exactly $|C|-\ell_C$. The bounds
of $\ell_C$ allow us enough control over the number of remaining vertices per
cluster, without hurting the super-regularity of the pairs corresponding to
edges of $M_j$ in a significant way.
% We will also assume that for each $j' n/2$. Then $G$ is Hamiltonian.
%\end{lemma}
\begin{lemma}[{Berge~\cite[Chapter 10.5, Theorem
15]{Ber1973}}]\label{lemma:ham-connect-bp}
Let $G=(A,B,E)$ be a bipartite graph with $|A|=|B|=n\geq 2$ such that for
each $2\leq j\leq (n+1)/2$, fewer than $j-1$ vertices have degree at most
$j$ in $G$. Then for any two vertices $a\in A$ and $b\in B$, there is a Hamilton
path with endpoints $a$ and $b$.
\end{lemma}
\begin{lemma}\label{obs}
Let $G=(A,B,E)$ be a bipartite graph. Let $s,t$ be
positive integers. Suppose that $G$ contains a cycle $C$ and a collection
of paths $P_1,\dotsc,P_t$ such that $|V(P_1)\cup \dotsb \cup V(P_t)| \leq
s$ and such that the following hold:
\begin{itemize}
\item each $P_i$ has one endpoint in $a_i\in A$ and one endpoint in $b_i\in B$;
\item these endpoints satisfy $d(b_i,A) > (|A|+s)/2$ and $d(a_i,B)
> (|B|+s)/2$, for every $i\in [t]$;
\item $C,P_1,\dotsc,P_t$ are vertex-disjoint and cover all vertices of $G$.
\end{itemize}
Then $G$ is Hamiltonian.
\end{lemma}
\begin{proof}
We can define a sequence $C_0,C_1,\dotsc,C_t$ of cycles in $G$ such that
$C_i$ covers exactly the vertices in $V(C)\cup V(P_1)\cup \dotsb \cup
V(P_i)$. For this, let $C_0 = C$. Suppose that we have defined $C_{i-1}$.
Using the condition on the degrees of $a_i$ and $b_i$, the pigeonhole
principle implies that $C_{i-1}$ contains some edge $uv$ such that $a_iu$ and
$b_iv$ are edges of $G$. Then we can define $C_i := C_{i-1} - uv + a_iu +
b_iv + P_i$. Finally, $C_t$ is a Hamilton cycle in $G$.
\end{proof}
To keep the proof of Lemma~\ref{lemma:connecting} as short as possible,
we define the following notion:
\begin{definition}[Good pair]
Let $G$ be a graph of order $n$ and let an integer $r\geq 1$ and real
numbers $\gamma,\delta \in (0,1)$ be given. A pair $(A,B)$ of disjoint
subsets of $V(G)$ is said to be \emph{$(\gamma,\delta,r)$-good} if the
following hold:
\begin{enumerate}[(P1)]
\item $\gamma n \leq |A|\leq |B| \leq r\cdot |A|$;
\item $d(b,A) \geq |A|-\delta n$ for all but at most $\delta n$ vertices $b\in B$;
\item $d(a,B) \geq |B|-\delta n$ for all but at most $\delta n$ vertices $a\in A$;
\item for all $a\in A$ and $b\in B$, we have $d(b,A)\geq \gamma n$ and
$d(a,B)\geq \gamma n$.
\end{enumerate}
\end{definition}
\begin{lemma}\label{lemma:goodpair}
For every integer $k\geq 1$ and every $\gamma > 0$, there is an integer $n_0$
and a real number $\delta \in (0,1)$ such that the following holds for every
$n\geq n_0$. Let $G$ be a graph on $n$ vertices and let
$(A,B)$ be a $(\gamma,\delta,r)$-good pair in $G$, for some integer $r\in
[k]$. Then $G[A, B]$ can be covered by at most $r$ cycles.
\end{lemma}
\begin{proof}
Let $k$ and $\gamma$ be given and let $G$ be a graph $n\geq n_0$ vertices, where
$n_0 = n_0(k,\gamma)$ is a sufficiently large constant. Suppose further that
$\delta=\delta(k,\gamma)$ is sufficiently small. For $r\in [k]$ let us
define $\gamma_r := \gamma\cdot (2k)^{r-k}$. We will show by induction on $r$
that $(\gamma_r,\delta,r)$-good pair $(A,B)$ in $G$ can be covered by at most
$r$ cycles, for all $1\leq r \leq k$. Then the lemma follows by noting that
$\gamma_r \leq \gamma$ for all $r\in [k]$.
The base case $r=1$ follows easily from Lemma~\ref{lemma:ham-connect-bp}
applied to $G[A,B]$.
Indeed, suppose $(A,B)$ is $(\gamma_1,\delta,r)$-good in $G$. Then by (P1) we
have $|A| = |B|\geq 2$, and for $\gamma_1 n \leq j\leq (|A|+1)/2$, the number
of vertices with degree at most $j$ is at most $\delta n < j-1$, while for
$j<\gamma_1 n$, the number of vertices of degree at most $j$ is zero. Hence,
$G[A,B]$ is Hamiltonian.
% Let $S\subseteq A\cup B$ denote the `special' set of vertices $x\in A\cup B$
% for which both $d(x,A) < |A|-\delta_1 n$ and $d(x,B) < |B|-\delta_1 n$. By
% (P2) and (P3), we have $|S|\leq 2\delta_1 n$. By (P4) and because $\gamma_r n$ is
% much larger than $|S|$, we can greedily find a collection
% $P_1,\dotsc,P_{|S|}$ of paths of length three such that
% $S\subseteq V(P_1)\cup \dotsb \cup V(P_{|S})$ and such that
% each $P_i$ has endpoints $a_i\in A$ and $b_i\in B$ such that
% $d(b_i,A) \geq |A|-\delta_1 n$ and $d(a_i,B) \geq |B|-\delta_1 n$.
%
% Let $T := V(P_1)\cup \dotsb \cup V(P_{|S|})$. Since $|T\cap A|= |T\cap
% B|\leq 2|S| \leq 4\delta_1 n$ and since $S\subseteq T$, by (P2) and (P3)
% the graph $G[A\setminus T, B\setminus T]$ has minimum degree at least $|A|
% - 5\delta_1 n> |A|/2 = |B|/2$, where we used that $|A|= |B|\geq \gamma_1
% n>10\delta_1 n$. Moreover, $|A\setminus T| = |B\setminus T| \geq \gamma_1 n
% - 4\delta_1 n \geq 2$. Then by Lemma~\ref{lemma:bp-dirac}, $G[A\setminus
% T,B\setminus T]$ contains a Hamilton cycle $C$. By Lemma~\ref{obs}
% applied to $C,P_1,\dotsc,P_{|S|}$, we get that $G[A\cup B]$ is Hamiltonian,
% thus completing the proof in the case $r=1$.
For the induction step, suppose that $r\geq 2$ and recall that $\gamma_r =
\gamma\cdot (4k)^{r-k}$. Let $(A,B)$ be a $(\gamma_r,\delta,r)$-good
pair in $G$.
We claim that there
exist subsets $B_1,B_2\subseteq B$ such that $B = B_1\cup B_2$ and such
that $(A,B_1)$ is $(\gamma_1,\delta,1)$-good and $(A,B_2)$ is
$(\gamma_{r-1},\delta,r-1)$-good. If such a partition exists, then
the claim follows by applying the induction hypothesis on the pairs
$(A,B_1)$ and $(A,B_2)$.
To find the sets $B_1$ and $B_2$, we use the probabilistic method. Let $B_1$
be a subset of $B$ chosen uniformly at random among all subsets of size $|A|$
(such a set exists because $|B|\geq |A|$). Let $B_2' := B\setminus B_1$ and let
$B_2''$ be a subset of $B_1$ chosen uniformly at random among all subsets of
size $\max{\{0,|A|-|B_2'|\}}$. Finally, let $B_2 := B_2' \cup B_2''$. Note
that $|B_2| = \max{\{|A|,|B|-|A|\}}$. Clearly $B_1$ and $B_2$ cover $B$,
and it is enough to show that with positive
probability, $(A,B_1)$ is $(\gamma_1,\delta,1)$-good and $(A,B_2)$ is
$(\gamma_{r-1},\delta,r-1)$-good.
We first show that $(A,B_2)$ is $(\gamma_{r-1},\delta,r-1)$-good with
probability at least $0.6$. Since $(A,B)$ is $(\gamma_r,\delta,r)$-good we
have $\gamma_r n \leq |A|\leq |B|\leq r|A|$. Thus also \[ \gamma_{r-1} n\leq
\gamma_r n\leq |A|\leq |B_2| = \max{\{|A|,|B|-|A|\}} \leq (r-1)|A|, \]
verifying (P1) for the pair $(A,B_2)$. It is easy to see that (P2) and (P3)
hold for $(A,B_2)$ automatically, using the assumption that $(A,B)$ satisfies
(P2) and (P3). As far as (P4) is concerned, it follows from the goodness of
$(A,B)$ that for all $b\in B_2$ we have $d(b,A) \geq \gamma_r n \geq
\gamma_{r-1}n$. It remains to show that with probability at least $0.6$ we
also have $d(a,B_2) \geq \gamma_{r-1}n$ for all $a\in A$. Fix some $a\in A$.
The degree $d(a,B_2)$ is distributed hypergeometrically with mean \[ \mathbf
E[d(a,B_2)] \geq d(a,B)\cdot \frac{|B_2|}{|B|}\geq \gamma_r n/r \geq
2\gamma_{r-1} n, \] where we used $|B_2| \geq |A| \geq |B|/r$ and the
definition of $\gamma_r$. By the Chernoff bounds,
we obtain \[ \mathbf P[d(a,B_2) < \gamma_{r-1} n ] \leq e^{-\gamma_{r-1}n/12}
\leq 0.6/n, \] if $n$ is sufficiently
large given $\gamma$ and $k$. By the union bound, with probability $0.6$,
every $a\in A$ satisfies $d(a,B_2)\geq \gamma_{r-1}$, and so (P4) holds with
probability at least $0.6$.
Analogously, one shows that $(A,B_1)$ is $(\gamma_1,\delta,r)$-good with
probability at least $0.6$, so there exists a choice of $B_1$ and $B_2$
such that $(A,B_1)$ is $(\gamma_1,\delta,1)$-good and $(A,B_2)$ is
$(\gamma_{r-1},\delta,r-1)$-good.
\end{proof}
Before continuing, we show that for certain stable sets $X$ (namely,
those where $k'$ is not too small) we can find a
partition $X = A\cup B$ that is `almost good'. For this, we have the following
claim. Note that (P2'), (P3') and (P4') in the claim correspond exactly to
(P2), (P3) and (P4) in the definition of a good pair (with $\gamma=1/(7k^4)$).
Condition (P5') tells us something about the structure of $G[B]$ in the case
where $|B| > (\ceil{k'}-1)|A|$.
\begin{lemma}\label{lemma:ag}
For every $\delta>0$ and $k\in \NN$, there is $\beta>0$ such that
the following holds for all sufficiently large $n$.
Let $G$ be a graph of order $n$ and suppose that $X$ is $(k',k,\beta)$-stable
in $G$ where $2-4k\beta\leq k'\leq k$. Then there exists a partition $X =
A\cup B$ with the following properties:
\begin{enumerate}[(P1')]
\item $|A|= n/k\pm \delta n$ and $|B| = (k'-1)n/k \pm \delta n$ and
$|B|\geq |A|$;
\item $d(b,A) \geq |A|-\delta n$ for all but at most $\delta n$ vertices $b\in B$;
\item $d(a,B) \geq |B|-\delta n$ for all but at most $\delta n$ vertices $a\in A$;
\item for all $a\in A$ and $b\in B$, we have $d(b,A)\geq n/(7k^4)$ and
$d(a,B)\geq n/(7k^4)$.
\item we have $\Delta(G[B])\leq n/(6k^4)$ or $|B|\leq (\ceil{k'}-1)|A|$.
\end{enumerate}
\end{lemma}
\begin{proof}
It is enough to show the required properties with $18\delta$ instead of
$\delta$.
Assume that $\beta$ is sufficiently smaller than $\delta$. Let
$I\subseteq X$ be a nearly independent set as in Definition~\ref{def:stable}.
As a first approximation, we may choose $A'' := X\setminus I$ and $B'' := I$.
Then we have (say) $|A''|= n/k \pm \delta n$ and $|B''| = (k'-1)n/k \pm
\delta n$, using (S1). Moreover, one can use the properties (S1--3) and an
averaging argument to show that $d(b,A'') \geq |A''|-\delta n$ holds for
all but at most $\delta n$ vertices $b\in B''$ and $d(a,B'') \geq
|B''|-\delta n$ holds for all but at most $\delta n$ vertices $a\in A''$.
Thus we already have (P2') and (P3') and also very nearly (P1') (but not
quite, because it could be that $|B|<|A|$).
We now modify $(A'',B'')$ to make sure that (P4') holds. Let $S\subseteq X$
be the set of at most $2\delta n$ vertices with a deficient degree, i.e.,
the set of vertices $x\in A''$ for which $d(x,A'') < |A''|-\delta n$ and of
vertices $x\in B''$ for which $d(x,B'') < |B''| - \delta n$. Since by (S2)
we have $\delta(G[X]) \geq n/k^4-\beta n$, we can
partition $S$ into disjoint sets $S_A\cup S_B$ such that the vertices of
$S_A$ have at
least $k^{-4}n/3$ neighbours in $B''$ and the vertices of $S_B$ have at least
$k^{-4}n/3$ neighbours in $A''$. Then we let $A' := A''\cup S_A\setminus S_B$
and $B' := B''\cup S_B\setminus S_A$. Since we only moved around
at most $2\delta n$ vertices, we still have
$|A'|= n/k \pm 3\delta n$ and $|B'| = (k'-1)n/k \pm 3\delta n$,
and we have $d(a,B') \geq |B'|-3\delta n$ for all but at most $3\delta n$
vertices $a\in A'$, and similarly for the vertices in $B'$.
However, we have gained the property that every vertex in $A$ has degree
at least $k^{-4}n/4$ in $B$, and vice-versa.
Next, we make sure that (P1') holds. The only issue is that it might be that
$|B'|< |A'|$. If so, then
\[ (k'-1)n/k - 3\delta n\leq |B'| < |A'| \leq n/k+3\delta n \]
implies $k'\leq 2+6k\delta n$. Since we further assumed that
$k' \geq 2-4k\beta\geq 2-6k\delta n$, we see that in fact, we have
$|A'|= (k'-1)n/k \pm 9\delta n$ and $|B'|= n/k\pm 9\delta
n$, and so by switching $A'$ with $B'$ we obtain (P1'). Note that this
swtiching cannot invalidate any of the symmetric properties (P2'), (P3'), or
(P4').
Finally, to obtain (P5'), we further modify these sets $A'$ and $B'$
as follows: as long as both $\Delta(G[B']) > k^{-4}n/6$ and $|B'| >
(\ceil{k'}-1)|A'|$, we move a vertex $b\in B'$ with $d(b,B') > k^{-4}n/6$
from $B'$ to $A'$. Since we have $|B'| \leq (k'-1)|A'| + 9\delta n$, we do
no move more than $9\delta n$ vertices during this process. Call the sets
resulting from these modifications $A$ and $B$. Then it is easy to verify
that (P1'--P5') hold with $18\delta$ instead of $\delta$
-- note in particular that it is still the case that $|A|\leq|B|$ since
we stop the process
the latest
when $|B|=(\ceil{k'}-1)|A|\geq |A|$.
\end{proof}
The next lemma will take care of the stable sets where $k'\leq 2-4k\beta$.
\begin{lemma}\label{lemma:ac}
Let $k\in \NN$ and $\beta>0$, where $\beta>0$ is sufficiently small. Let $G$
be a graph of order $n\geq 3$ and let $X$ be $(k',k,\beta)$-stable in $G$ where
$1\leq k' \leq 2-4k\beta$. Then for any two distinct vertices $x,y\in X$,
there exists a Hamilton path in $G[X]$ whose endpoints are $x$ and $y$.
\end{lemma}
\begin{proof}
This follows easily from Lemma~\ref{lemma:ham-connect}.
Indeed, by (S1) the graph $G[X]$ has at most
\[ |X| \leq k'n/k+ \beta n\leq (2-4k\beta)n/k+\beta n \leq 2n/k-3\beta n
\] vertices.
By (S2), every vertex in $G[X]$ has degree at least $n/k^4-\beta n
\geq n/(2k^4)$
and all but $\beta n$ vertices have degree at least $n/k-\beta n
> (|X|+1)/2$.
Thus, for $n/(2k^4)\leq j \leq (|X|+1)/2$, there are at most
$\beta n< j-1$ vertices with degree at most $j$, while for $j <
n/(2k^4)$, there are no vertices with degree at most $j$.
% Let $S$ be the set of vertices in $X$ that do not have degree at least
% $n/k-\beta n$ in $G[X]$. Note that by (S2) we have $|S| \leq \beta n$.
% Using (S1) and $k' \leq 2-15k\beta n$, we have
% $|X|\leq k'n/k + \beta n \leq 2n/k - 14\beta n$.
% Therefore, every vertex $x\in X\setminus S$ satisfies
% \begin{equation}\label{eq:d1}
% d(x,X) \geq n/k-\beta n \geq |X|/2+ 6\beta n.
% \end{equation}
%
% Let $x',y'\in X\setminus S$ be such that $xx'\in E(G)$ and $yy'\in
% E(G)$ and such that $x,y,x',y'$ are all distinct. Such vertices must exist
% because by (S2) the minimum degree of $G[X]$ is at least $n/k^4-\beta n
% \geq |S| + 2$, if $\beta$ is sufficiently small. Let us
% write $A := X\setminus (S\cup \{x,x',y,y'\})$ and $B := S
% \setminus \{x,x',y,y'\}$, Note that $A\cup B = X\setminus \{x,x',y,y'\}$.
%
% Since $|X\setminus A| \leq 2\beta n$, we have
% \[ |X|/2 = |A|/2 + |X\setminus A|/2 \geq |X\setminus A| + |A|/2 - \beta n. \]
% As $A\subseteq X\setminus S$, it follows from this and~\eqref{eq:d1} that any two
% vertices in $A$ have at least $10\beta n \geq 3|B|$ common neighbours in $A$.
% Additionally, using (S2), every vertex of $B$ has at least $n/k^4-2\beta n -4
% \geq 2|B|$ neighbours in $A$.
%
% We now claim that $G[A\cup B]$ contains a path $P$ of length at most $4|B|-2$
% such that the endpoints of $P$ lie in $A$ and such that
% $B\subseteq V(P)$. Indeed, by the observations in the previous
% paragraph, a path like this can be built as follows: first, for every vertex $x_i$ of
% $B$, we may choose two neighbours $x_{2i}, x_{2i+1}\in A$ in such a way that
% all chosen neighbours are distinct (since by (S3) each $x_i$ has more than
% $2|B|$ neighbours in $A$); then, using the fact that any two vertices of $A$
% have at least $3|B|$ common neighbours in $A$, we can connect each
% $x_{2i+1}$ to $x_{2(i+1)}$ via a path of length two that avoids all other
% involved vertices.
%
% Since $|A\setminus V(P)| \geq |X|-5\beta n$, it follows from \eqref{eq:d1}
% that $G[A\setminus V(P)]$ satisfies Dirac's condition and thus contains a
% Hamilton cycle $C$. Since the endpoints $u,v$ of $P$ lie in $A\subseteq X\setminus S$,
% \eqref{eq:d1} and the pigeonhole principle imply that there exists an edge
% $u'v'\in E(C)$ such that $uu'$ and $vv'$ are edges of $G$. Then $C' :=
% (C-u'v') + uu' + vv' + P$ is a Hamilton cycle in $G[A\cup B]$. Finally, again
% using~\eqref{eq:d1} and the pigeonhole principle, there exists an edge
% $x''y''\in E(C')$ such that $x'x''$ and $y'y''$ are edges of $G$ (recall that
% $x',y'\in X$). Then $P' := (C'-x''y'') + xx' + yy' + x'x'' + y'y''$ is a
% Hamilton path in $G[X]$ with endpoints $x$ and $y$, as required.
\end{proof}
\begin{proof}[Proof of Lemma \ref{lemma:connecting}]
Let $G$ be a graph on $n$ vertices and assume that $X$ is
$(k',k,\beta)$-stable in $G$ for some real number $k'\in [1,k]$,
i.e., $X$ satisfies properties (S1), (S2) and (S3) from
Definition~\ref{def:stable}. Throughout the proof, we will assume that
$\delta>0$ and $\beta>0$ are sufficiently small constants, where $\beta$ is
assumed to be much smaller than $\delta$, and that $n$ is sufficiently large.
The case $k'\leq 2-4k\beta$ of the lemma follows immediately from
Lemma~\ref{lemma:ac}. Therefore, we will from now on assume that $k'\geq
2-4k\beta$. In particular there is a partition $(A,B)$ of $X$ satisfying the
properties (P1'--P5') of Lemma~\ref{lemma:ag}. We now prove the different
parts of Lemma~\ref{lemma:connecting}.
\subsection*{Proof of (a).} Note that if $\delta$ is sufficiently small,
which we assume, then the pair
$(A,B)$ is automatically $(k^{-4}/7,\delta,\ceil{k'})$-good. Thus by
Lemma~\ref{lemma:goodpair}, the graph $G[A,B]$ can be covered by $\ceil{k'}$
cycles, which immediately yields statement (a) of
Lemma~\ref{lemma:connecting}.
\subsection*{Proof of (b).} To see that (b) holds, fix two vertices $x,y\in X$.
By
(P2'), (P3') and (P4'), it is straightforward to find vertices $a\in A$ and
$b\in B$ such that $x,y,a,b$ are all distinct, such that $d(a,B)\geq |B|-\delta
n$ and $d(b,A)\geq |A|-\delta n$, and such that there exist two vertex-disjoint
paths of length at most two from $x$ to $a$ and from $y$ to $b$, respectively.
Let $P_1$ and $P_2$ be these paths and let $A' := A\setminus (V(P_1)\cup
V(P_2))$ and $B' := B\setminus (V(P_1)\cup V(P_2))$. Since $k'\geq 2-4k\beta
n$, one can check that one of the pairs $(A',B')$ and $(B',A')$ is
$(k^{-4}/8,2\delta,\ceil{k'})$-good (note that $(A',B')$ can fail to be good if
$|B'|<|A'|$). By Lemma~\ref{lemma:goodpair} this allows us to cover $G[A'\cup
B']$ with at most $\ceil{k'}$ cycles. At least one of these
cycles, call it $C$, has length at least $|A'|/k\geq n/k^3$. Then, since
$d(b,A)\geq |A|-\delta n$ and $d(a,B) \geq |B|-\delta n$, the pigeonhole
principle implies that we can find an edge $uv$ in $C$ such that $au,bv$ are
edges of $G$ that are not used by any of the cycles used for covering $A'\cup
B'$. Then we can replace $C$ by the $x$-$y$-path $P_1 + P_2 + au+ bv
+(C-uv)$.
\subsection*{Proof of (c).} Here we assume that all but at most $n/k^3$
vertices $x\in X$ satisfy $d(x,X) \geq |X|/k'$, and we need to show that
$G[X]$ can be covered with $\ceil{k'}-1$ cycles. If we have $|B|\leq
(\ceil{k'}-1)|A|$ then $(A,B)$ is a $(k^{-4}/7,\delta,\ceil{k'}-1)$-good pair
and using Lemma~\ref{lemma:goodpair}, we are done immediately.
So assume that $|B|> (\ceil{k'}-1)|A|$. Then by property (P5'), we have
$\Delta(G[B]) \leq n/(6k^4)$.
We first claim that $G[B]$ contains a matching of size
$|B|-(\ceil{k'}-1)|A|$. To see this, observe that if a vertex $x\in B$
satisfies $d(x,X)\geq |X|/k'$ then \[ d(x,B) = d(x,X) - d(x,A) \geq |X|/k' -
|A| = \frac{|B|-(k'-1)|A|}{k'}, \] using $|X| =|A|+ |B|$ for the last
equality. Since there are at least $|B|-n/k^3 \geq n/(2k)$ vertices $x\in B$
such that $d(x,X)\geq |X|/k'$, this implies \[ e(G[B]) \geq
\frac{|B|-(k'-1)|A|}{4k^2}\cdot n. \] Since the maximum degree of $G[B]$ is
at most $n/(6k^4)$, Vizing's theorem implies that the edges of $G[B]$ can be
properly edge-colored with $n/(5k^4)$ colors. This in turn means that $G[B]$
contains a matching of size at least \[ \frac{e(G[B])}{n/(5k^4)} \geq
|B|-(k'-1)|A| \geq |B| - (\ceil{k'}-1)|A|, \] as claimed.
Denote by $M$ any matching of size $|B|-(\ceil{k'}-1)|A|$ in $G[B]$. Note
that by (P1') we have $|M| \leq |B|-(k'-1)|A| \leq k\delta n$. By (P4') each
vertex in $B$ has at least $n/(7k^3) \geq 5|M|$ neighbours in $A$. Similarly,
each vertex of $A$ has at least $n/(7k^3)-\delta n \geq 5|M|$ neighbours in
$B$. Using these properties, we can now greedily find a system of $|M|$
vertex-disjoint paths $P_1,\dotsc,P_{|M|}$ of length four with the following
properties: each $P_i$ contains one edge of $M$ and visits exactly three
vertices in $B$ and two vertices in $A$; moreover, the endpoints of $P_i$ are
vertices $a_i\in A$ and $b_i\in B$ such that $d(a_i,B)\geq |B|-\delta n$ and
$d(b_i,A)\geq |A|-\delta n$.
Let $S := V(P_1)\cup \dotsb \cup V(P_{|M|})$.
We will use a probabilistic
argument to show that there exists a partition of $B$ into disjoint sets
$B_1$ and $B_2$ such that the pairs $(A,B_1)$ and $(A\setminus S,
B_2\setminus S)$ are $(k^{-5}/30,\delta,\ceil{k'}-2)$-good and
$(k^{-5}/30,\delta,1)$-good, respectively. If we manage to do so, it will
be easy to
complete the proof. Indeed, by Lemma~\ref{lemma:goodpair} we will be able to
cover $G[A,B_1]$ with $\ceil{k'}-2$ cycles and cover
$G[A\setminus S,B_2\setminus S]$ by a single cycle $C$. Then it follows from
Lemma~\ref{obs} applied to $C,P_1,\dotsc,P_{|M|}$ that we can in fact
cover $G[A,B_2]$ by a single cycle, meaning that we can cover $G[A,B]$ with
$\ceil{k'}-1$ cycles, as required.
It remains for us to show how to obtain $B_1$ and $B_2$. Let $B_1 \subseteq
B\setminus S$ be a subset of $B\setminus S$ chosen uniformly at random among
all subsets of size $(\ceil{k'}-2)|A|$ and let $B_2 := B\setminus B_1$. Note
that since $|M|=|B|-(\ceil{k'}-1)|A|$, we have
\[ |B_2| = |B|- (\ceil{k'}-2)|A| = |M| + |A|. \]
We claim that with positive probability, the pairs $(A,B_1)$ and $(A\setminus
S, B_2\setminus S)$ are $(k^{-5}/30,\delta,\ceil{k'}-2)$-good and
$(k^{-5}/30,\delta,1)$-good, respectively. First of all, both pairs satisfy
(P1). For $(A,B_1)$ this is clear since
$|B_1|=(\ceil{k'}-2)|A|$.
For $(A\setminus S, B_2\setminus S)$,
we have
\[ |B_2\setminus S| = |B_2| - 3|M| = |A| -2|M| = |A\setminus S|, \]
since every path $P_i$ uses three vertices of $B_2$ and two vertices of $A$.
Properties (P2) and (P3) hold because of (P2') and (P3'). Finally, using
Chernoff bounds we may show that (P4) holds for both
pairs with positive probability. For example, for the pair
$(A\setminus S, B_2\setminus S)$, we proceed as follows: for $a\in A$, the degree
$d(a,B_2\setminus S)$ is distributed hypergeometrically with mean
\[\mathbf E[d(a,B_2\setminus S)] \geq \frac{n}{7k^4} \cdot \frac{|B_2\setminus S|}{|B|}
\geq \frac{n}{15k^5}, \]
using $|B_2\setminus S| \geq |A|-|S| \geq n/(2k)$. Then the required bound
on the probability that some $a\in A$ satisfies $d(a,B_2)< n/(30k^5)$ follows from
the Chernoff and union bounds.
On the other hand, we have $d(b,A\setminus S) \geq n/(7k^4) - |S| \geq n/(8k^4)$
for all $b\in B_2$ deterministically. The argument for $(A,B_1)$ is similar.
\end{proof}
\begin{thebibliography}{99}
\bibitem{All}
Peter Allen.
\newblock Minimum degree conditions for cycles.
\newblock Unpublished.
\bibitem{Alo1986}
Noga Alon.
\newblock The longest cycle of a graph with a large minimal degree.
\newblock {\em J. Graph Theory}, 10(1):123--127, 1986.
\bibitem{BBG+2014}
J\'{o}zsef Balogh, J\'{a}nos Bar\'{a}t, D\'{a}niel Gerbner, Andr\'{a}s Gy\'{a}rf\'{a}s, and
G\'{a}bor~N. S\'{a}rk\"{o}zy.
\newblock Partitioning $2$-edge-colored graphs by monochromatic paths and
cycles.
\newblock {\em Combinatorica}, 34:507--526, 2014.
\bibitem{BS2009a}
Fabricio~S. Benevides and Jozef Skokan.
\newblock The 3-colored {R}amsey number of even cycles.
\newblock {\em J. Combin. Theory Ser. B}, 99:690--708, 2009.
\bibitem{Ber1973}
Claude Berge.
\newblock {\em Graphs and Hypergraphs}.
\newblock North-Holland, Amsterdam, second edition, 1973.
\bibitem{Bol1978}
B\'{e}la Bollob\'{a}s.
\newblock {\em Extremal {G}raph {T}heory}.
\newblock Academic Press, London, 1978.
\bibitem{BH1989}
B\'{e}la Bollob\'{a}s and Roland H\"{a}ggkvist.
\newblock The circumference of a graph with a given minimal degree.
\newblock In A.~Baker, B.~Boll\'obas, and A.~Hajnal, editors, {\em A Tribute to
Paul Erd\H{o}s}. Cambridge University Press, 1989.
\bibitem{BHP2012}
Julia B\"{o}ttcher, Jan Hladk\'{y}, and Diana Piguet.
\newblock The tripartite {R}amsey number for trees.
\newblock {\em J. Graph Theory}, 69(3):264--300, 2012.
\bibitem{CDK2011}
Phong Chau, Louis DeBiasio, and Henry~A. Kierstead.
\newblock P\'osa's conjecture for graphs of order at least $2\cdot 10^8$.
\newblock {\em Random Structures Algorithms}, 39:507--525, 2011.
\bibitem{Dir1952}
Gabriel~A. Dirac.
\newblock Some theorems on abstract graphs.
\newblock {\em Proc. London Math. Soc.}, s3-2(1):69--81, 1952.
\bibitem{Doe2011}
Benjamin Doerr.
\newblock Analyzing randomized search heuristics: tools from probability
theory.
\newblock In A.~Auger and B.~Doerr, editors, {\em Theory of Randomized Search
Heuristics}. World Scientific, Singapore, 2011.
\bibitem{EM1989}
Yoshimi Egawa and Takashi Miyamoto.
\newblock The longest cycles in a graph {$G$} with minimum degree at least
{$|G|/k$}.
\newblock {\em J. Combin. Theory Ser. B}, 46(3):356--362, 1989.
\bibitem{EKKT1995}
Hikoe Enomoto, Atsushi Kaneko, Mekkia Kouider, and Zsolt Tuza.
\newblock Degree sums and covering cycles.
\newblock {\em J.~Graph Theory}, 20(4):419--422, 1995.
\bibitem{EKT1988}
Hikoe Enomoto, Atsushi Kaneko, and Zsolt Tuza.
\newblock {$P_3$}-factors and covering cycles in graphs of minimum degree
$n/3$.
\newblock In {\em Combinatorics} (Colloq. Math. Soc. J\'{a}nos Bolyai 52, Eger), 213--220. North-Holland, Amsterdam,
1988.
\bibitem{Erd1964}
Paul Erd\H{o}s.
\newblock {\em Theory of graphs and its applications}.
\newblock Czech Acad. Sci. Publ., Prague, 1964.
\bibitem{FK1996}
Genghua Fan and Henry~A. Kierstead.
\newblock Hamiltonian square-paths.
\newblock {\em J. Combin. Theory Ser. B}, 67:167--182, 1996.
\bibitem{FL2007}
Agnieszka Figaj and Tomasz \L{}uczak.
\newblock The {R}amsey number for a triple of long even cycles.
\newblock {\em J. Combin. Theory Ser. B}, 97(4):584--596, 2007.
\bibitem{HS1970}
Andr\'{a}s Hajnal and Endre Szemer\'{e}di.
\newblock Proof of a conjecture of {P}. {E}rd\H{o}s.
\newblock In P.~Erd\H{o}s, A.~R\'{e}nyi, and V.~T. S\'{o}s, editors, {\em Combinatorial
theory and its applications}, volume~2, pages 601--623. North-Holland,
Amsterdam, 1970.
\bibitem{Kom1999}
J{\'{a}}nos Koml{\'{o}}s.
\newblock The blow-up lemma.
\newblock {\em Combin. Probab. Comput.}, 8:161--176, 1999.
\bibitem{KSS1995}
J{\'{a}}nos Koml{\'{o}}s, G{\'{a}}bor~N. S{\'{a}}rk{\"{o}}zy, and Endre
Szemer{\'{e}}di.
\newblock Proof of a packing conjecture of {B}ollob\'{a}s.
\newblock {\em Combin. Probab. Comput.}, 4:241--255, 1995.
\bibitem{KSS1996}
J{\'{a}}nos Koml{\'{o}}s, G{\'{a}}bor~N. S{\'{a}}rk{\"{o}}zy, and Endre
Szemer{\'{e}}di.
\newblock The blow-up lemma.
\newblock {\em Combinatorica}, 17:109--123, 1996.
\bibitem{KSS1996a}
J{\'{a}}nos Koml{\'{o}}s, G{\'{a}}bor~N. S{\'{a}}rk{\"{o}}zy, and Endre
Szemer{\'{e}}di.
\newblock On the square of a {H}amiltonian cycle in dense graphs.
\newblock {\em Random Structures Algorithms}, 9:193--211, 1996.
\bibitem{KSS1998}
J{\'{a}}nos Koml{\'{o}}s, G{\'{a}}bor~N. S{\'{a}}rk{\"{o}}zy, and Endre
Szemer{\'{e}}di.
\newblock Proof of the {S}eymour conjecture for large graphs.
\newblock {\em Ann. Comb.}, 2(1):43--60, 1998.
\bibitem{KS1996}
J{\'{a}}nos Koml{\'{o}}s and Mikl\'{o}s Simonovits.
\newblock Szemer\'edi's regularity lemma and its applications in graph theory.
\newblock In D.~Mikl\'{o}s, T.~Sz\H{o}nyi, and V.~T. S\'{o}s, editors, {\em
Combinatorics, Paul Erd\H os is Eighty, 2}, Bolyai Soc. Math. Stud., pages
295--352, 1996.
\bibitem{Kou1994}
Mekkia Kouider.
\newblock Covering vertices by cycles.
\newblock {\em J.~Graph Theory}, 18(8):757--776, 1994.
\bibitem{KL1996}
Mekkia Kouider and Zbigniew Lonc.
\newblock Covering cycles and $k$-term degree sums.
\newblock {\em Combinatorica}, 16(3):407--412, 1996.
\bibitem{LS2017}
Richard Lang and Maya Stein.
\newblock Local colourings and monochromatic partitions in complete bipartite
graphs.
\newblock {\em European J. Combin.}, 60:42--54, 2017.
\bibitem{LSS2010}
Ian Levitt, G\'{a}bor~N. S\'ark\"ozy, and Endre Szemer\'edi.
\newblock How to avoid using the {R}egularity {L}emma: {P}\'osa's conjecture
revisited.
\newblock {\em Discrete Math.}, 310:630--641, 2010.
\bibitem{L1999}
Tomasz \L{}uczak.
\newblock $r(c_n,c_n,c_n)\le (4+o(1))n$.
\newblock {\em J. Combin. Theory Ser. B}, 75:174--187, 1999.
\bibitem{NS2006}
Vladimir Nikiforov and Richard~H. Schelp.
\newblock Cycle lengths in graphs with large minimum degree.
\newblock {\em J. Graph Theory}, 52(2):157--170, 2006.
\bibitem{SSS2013}
G\'{a}bor~N. S\'ark\"ozy, Stanley~M. Selkow, and Fei Song.
\newblock An improved bound for vertex partitions by connected monochromatic
k-regular graphs.
\newblock {\em J. Graph Theory}, 73:127--145, 2013.
\bibitem{Sey1974}
Paul Seymour.
\newblock Problem section.
\newblock In T.~P. McDonough and V.~C. Mavron, editors, {\em Combinatorics} (British Combinatorial Conference 1973), 201--202. Cambridge University Press,
1974.
\bibitem{Sim1968}
Mikl\'{o}s Simonovits.
\newblock A method for solving extremal problems in graph theory, stability
problems.
\newblock In {\em Theory of Graphs} (Tihany), pages 279--319. Academic Press, New York,
1968.
\bibitem{Sze1976}
Endre Szemer\'{e}di.
\newblock Regular partitions of graphs.
\newblock In {\em Probl\`{e}mes Combinatoires et Th\'{e}orie des Graphes} (Colloques internationaux CNRS 260, Orsay), pages
399--401, 1976.
\end{thebibliography}
\end{document}