C4
1. Introduction
Ramsey theory, in broad terms, is the mathematical study of finding inevitable order in a large chaotic universe. In this paper, our setting will be to consider all edge colourings of some large host graph
$G$
and the inevitable order will be copies of some fixed graph
$H$
in
$G$
that exhibit certain canonical colour patterns. The colour patterns of interest are the following.
Definition 1.1 (Canonical colour pattern). Let
$H$
be a graph,
$\sigma$
an ordering of
$V(H)$
and
$\chi :\,E(H)\rightarrow {\mathbb N}$
an edge colouring of
$H$
. We define
$H$
coloured by
$\chi$
to be canonical (with respect to
$\sigma$
) if one of the following holds
-
(i)
$H$
is monochromatic:
$\chi (e)=\chi (f)$
for all
$e,f\in E(H)$
; -
(ii)
$H$
is rainbow:
$\chi (e)\neq \chi (f)$
for all
$e\neq f\in E(H)$
; -
(iii)
$H$
is lexicographic (with respect to
$\sigma$
): there exists an injective assignment of colours
$\phi \,:\,V(H)\rightarrow {\mathbb N}$
such that for every edge
$e=uv\in E(H)$
with
$u\lt _\sigma v$
, we have that
$\chi (e)=\phi (u)$
.
Examples of all the canonical patterns of
$C_6$
are shown in Figure 1 where the colourings
$(iii.1)-(iii.4)$
correspond to lexicographic colourings with respect to different vertex orders. Note that certain distinct vertex orderings can give the same lexicographic colour pattern.
The canonical colourings are candidates for an ‘unavoidable’ collection of colourings of
$H$
, one of which necessarily occurs when colouring certain host graphs
$G$
. Note that all three types of canonical colouring are necessary in such an unavoidable collection. Indeed, by colouring a host graph
$G$
according to a canonical pattern (i.e., one of the patterns (i), (ii), or (iii) in Definition 1.1), one can see that any copy of
$H$
in
$G$
will be coloured according to the same colour pattern, and so this pattern cannot be omitted from our desired unavoidable collection. As we will see, the canonical colourings of
$H$
are also sufficient to form an unavoidable collection of colour patterns when colouring certain host graphs
$G$
.
Definition 1.2 (The canonical Ramsey property). For graphs
$G$
and
$H$
, we say
$G$
has the
$H$
-canonical Ramsey property, and write
$G\xrightarrow {\scriptstyle \textrm {can}} H$
, if for every edge colouring
$\chi \,:\,E(G)\rightarrow {\mathbb N}$
and every ordering
$\sigma$
of
$V(H)$
, there is a copy of
$H$
in
$G$
which is canonical with respect to
$\sigma$
when coloured by
$\chi$
.
The canonical colourings of
$C_6$
.
We remark that our definition for the canonical Ramsey property requires that we find either a monochromatic copy of
$H$
, a rainbow copy of
$H$
or all possible lexicographic copies of
$H$
. For example, if
$G\xrightarrow {\scriptstyle \textrm {can}} C_6$
, then if we do not find copies of
$C_6$
with colour patterns
$(i)$
or
$(ii)$
in a colouring of
$G$
then we will find copies of
$C_6$
with all the colour patterns
$(iii.1)-(iii.4)$
in Figure 1. This is the strongest possible notion of a canonical Ramsey property for colour patterns that one could ask for, as discussed in more detail after the statement of Theorem 1.5.
The following is a direct consequence of the celebrated canonical Ramsey theorem, proved by Erdős and Rado [Reference Erdős and Rado14] in 1950.
Theorem 1.3 ([Reference Erdős and Rado14]). For a graph
$H$
, one has that
$K_n\xrightarrow {\scriptstyle \textrm {can}} H$
for all sufficiently large
$n\in {\mathbb{N}}$
.
Erdős and Rado worked only on the case when
$H=K_m$
for some
$m\in {\mathbb{N}}$
, and they also proved analogues for hypergraph cliques. In the case that
$H=K_m$
, there is just one lexicographic colour pattern possible. Moreover, we note that a copy of
$K_{v(H)}$
that is lexicographic necessarily contains all possible lexicographic copies of
$H$
. This observation along with the fact that one can find monochromatic/rainbow copies of
$H$
in monochromatic/rainbow copies of
$K_{v(H)}$
gives that Theorem 1.3 does indeed follow directly from the canonical Ramsey theorem of Erdős and Rado [Reference Erdős and Rado14]. We also remark that Erdős and Rado actually worked in a different setting focusing on ordered embeddings of
$K_m$
instead of colour patterns (which nonetheless implies Theorem 1.3 for
$H=K_m$
). Following [Reference Axenovich and Jamison5, Reference Jamison and West16], we choose instead to work with colour patterns and find this approach more natural when considering
$H$
that are not complete. We refer to [Reference Alvarado, Kohayakawa, Morris and Mota3, Section 1.4] for a more detailed discussion of alternative characterisations of the canonical Ramsey property.
Theorem 1.3 built on the classical Ramsey setting where only a bounded number of colours is used. We say that
$G$
has the
$r$
-Ramsey property with respect to
$H$
, denoted
$G\to (H)_r$
, if any
$r$
-colouring of the edge set of
$G$
results in a monochromatic copy of
$H$
. Ramsey’s theorem [Reference Ramsey26], from which Ramsey theory inherits its name, states that for any
$H$
and
$r\in {\mathbb{N}}$
, if
$n$
is sufficiently large, then
$K_n\to (H)_r$
. Thus Theorem 1.3 showed that, although one can no longer guarantee monochromatic copies of
$H$
when the size of the colour palette is allowed to grow with
$n$
, we can still have a strong Ramsey-type statement guaranteeing one of a small collection of unavoidable colour patterns.
1.1 Ramsey properties of random graphs
Extending Ramsey’s theorem in an orthogonal direction, a prominent theme has been to determine the threshold for Ramsey properties in random graphs. Here and throughout, we denote by
${\mathbf G}(n,p)$
the binomial random graph with edge probability
$p=p(n)$
and we say that a function
$\hat p = \hat p(n)$
is the threshold for a monotone increasing graph property
$\mathcal{P}$
if
\begin{equation*} \lim _{n\to \infty }{\mathop {\mathbb{P}}\nolimits }({\mathbf G}(n,p)\text{ satisfies }\mathcal{P}) = \begin{cases}0&\text{if }p =o( \hat p), \\[3pt] 1&\text{if }p =\omega ( \hat p). \end{cases} \end{equation*}
We refer to
$\hat p$
as the threshold for
$\mathcal{P}$
, although it is not uniquely defined but rather defined up to a choice of constant.
Initial interest in studying Ramsey thresholds came from the desire to obtain sparse Ramsey graphs. Indeed, Ramsey’s theorem gives that
$K_n\to (H)_r$
for all large enough
$n\in {\mathbb{N}}$
but in fact one can replace
$K_n$
by much sparser
$n$
-vertex graphs
$G$
. In fact, as shown by Rödl and Ruciński in a seminal series of papers [Reference Rödl and Ruciński27–Reference Rödl and Ruciński29] in the 90s, almost all graphs have the Ramsey property and this remains true when focusing on much sparser graphs. For all
$H$
and
$r\in {\mathbb{N}}$
, they completely determined the threshold for the
$r$
-Ramsey property, showing that it is governed by the parameter
$m_2(H)$
of
$H$
known as its maximum
$2$
-density.
Theorem 1.4 (Rödl–Ruciński [Reference Rödl and Ruciński27–Reference Rödl and Ruciński29]). Let
$r\geq 2$
be an integer and
$H$
be a graph with at least two edges which is not a star forest. Then
$n^{-1/m_2(H)}$
is the threshold for the property
${\mathbf G}(n,p)\to (H)_r$
, where
$m_2(H)$
is the maximum
$2$
-density of
$H$
, defined by
\begin{equation*} m_2(H)\, :\!= \,\max \left \{\tfrac {e(F)-1}{v(F)-2}\,:\,F\subseteq H,\, v(F)\gt 2 \right \}\!. \end{equation*}
The work of Rödl and Ruciński was highly celebrated with both the
$0$
-statement and
$1$
-statement needing intricate proofs. More recently, Nenadov, Person, Škorić, and Steger [Reference Nenadov, Person, Škorić and Steger24] obtained several related
$0$
-statement results, and Nenadov and Steger [Reference Nenadov and Steger25] showed how to reprove the
$1$
-statement using the theory of hypergraph containers [Reference Balogh, Morris and Samotij6, Reference Saxton and Thomason31], leading to an elegant and concise proof.
1.2 Canonical Ramsey property for even cycles in random graphs
With regards to canonical Ramsey properties of random graphs, until recently very little was known. Due to Theorem 1.4, if
$H$
is a graph which is not a star forest and
$p=o(n^{-1/m_2(H)})$
, then asymptotically almost surely (a.a.s. for short)
${\mathbf G}\sim {\mathbf G}(n,p)$
can be
$2$
-coloured, by a colouring
$\chi$
say, avoiding monochromatic copies of
$H$
. For all such
$H\neq K_3$
, there is some ordering
$\sigma$
of
$V(H)$
such that the lexicographic colouring of
$H$
with respect to
$\sigma$
uses more than 2 colours. Hence the colouring
$\chi$
of
$\mathbf G$
avoids at least one lexicographic pattern as well as both the monochromatic and rainbow patterns. This thus gives that the threshold for the property
${\mathbf G}(n,p) \xrightarrow {\scriptstyle \textrm {can}} H$
is at least
$n^{-1/m_2(H)}$
.
Our main theorem shows that this lower bound is tight up to a logarithmic factor in the case that
$H=C_{2k}$
is an even cycle, noting that
$m_2(C_{2k})^{-1}=1 - 1/(2k-1)$
for
$2\leq k\in {\mathbb{N}}$
.
Theorem 1.5.
Let
$k\geq 2$
be an integer. If
$p= \omega \left ( n^{-1+{1}/{(2k-1)}} \, \log {n}\right )$
, then a.a.s.
\begin{equation*} {\mathbf G}(n,p) \xrightarrow {\scriptstyle \textrm {can}} C_{2k}. \end{equation*}
Remark 1.6. We remark that with more care we could prove a slightly stronger statement, requiring only
$p\geq Cn^{-1+{1}/{(2k-1)}} \, \log {n}$
for some large enough constant
$C\gt 0$
, and guaranteeing not just one canonical copy of
$C_{2k}$
but
$\Omega (n^{2k}p^{2k})$
many copies. We opt to prove the form of Theorem 1.5 given here to simplify the exposition. Another reason is that we do not believe that the
$\log n$
factor that we currently have is in fact required (see Section 1.3).
In defining our canonical Ramsey property in Definition 1.2, we required that all lexicographic copies of
$H$
are present when the colouring avoids monochromatic and rainbow copies of
$H$
. At the other end of the spectrum, one could alternatively require just one lexicographic copy of
$H$
.
Definition 1.7 (The weak canonical Ramsey property). For graphs
$H$
and
$G$
, we say
$G$
has the weak
$H$
-canonical Ramsey property, and write
$G\xrightarrow {\scriptstyle \textrm {wcan}} H$
, if for every edge colouring
$\chi \,:\,E(G)\rightarrow {\mathbb N}$
there is a copy of
$H$
in
$G$
coloured by
$\chi$
which is canonical with respect to some ordering
$\sigma$
of
$V(H)$
.
When
$k\geq 3$
, any lexicographic colouring of
$C_{2k}$
uses at least 3 colours and so by the same reasoning as before,
$n^{-1/m_2(C_{2k})}$
is also a lower bound for the weak canonical Ramsey property. However for cycles of length four, we see a change in behaviour and have that the threshold for
${\mathbf G}(n,p)\xrightarrow {\scriptstyle \textrm {wcan}} C_4$
is in fact much smaller than
$n^{-2/3}=n^{-1/m_2(C_4)}$
.
Proposition 1.8.
The threshold for
${\mathbf G}(n,p)\xrightarrow {\scriptstyle \textrm {wcan}} C_4$
is
$n^{-3/4}$
.
1.3 Related works
In general, we believe that
$n^{-1/m_2(H)}$
is the threshold for the canonical Ramsey property with respect to
$H$
for any connected graph
$H$
that is not a star forest or a
$K_3$
. In accompanying work [Reference Alvarado, Kohayakawa, Morris and Mota3, Reference Alvarado, Kohayakawa, Morris and Mota4], we provide evidence for this by showing that when
$p=\omega (n^{-1/m_2(H)})$
, a.a.s. one can find canonical copies of
$H$
in any colouring of
${\mathbf G}(n,p)$
that respects some prefixed bounded lists of colours assigned to each edge. In fact this result in the case that
$H=C_{2k}$
, or rather a slightly stronger version applied to random subgraphs of uniformly dense graphs (see Theorem 4.3), is also a key component of our proof here.
Moreover, in simultaneous and independent work, Kamčev and Schacht [Reference Kamčev and Schacht18, Reference Kamčev and Schacht19] obtained a remarkable result proving that
$n^{-1/m_2(K_m)}$
is indeed the threshold for
${\mathbf G}(n,p)\xrightarrow {\scriptstyle \textrm {can}} K_m$
for
$m\geq 4$
and thus completely resolved the problem for the case when
$H$
is a clique. This beautiful result appeals to the transference principle of Conlon and Gowers [Reference Conlon and Gowers11], which is a very general result obtained by using an analytic approach. This principle pre-dates the theory of hypergraph containers [Reference Balogh, Morris and Samotij6, Reference Saxton and Thomason31] and can be used to get many of the same consequences in random graphs, in the case that the subgraph
$H$
of interest is strictly balanced, that is, when the maximum in the definition of
$m_2(H)$
is achieved by
$F=H$
only. For instance, the transference principle was used to recover the
$1$
-statement of Theorem 1.4 for strictly balanced
$H$
. Kamčev and Schacht [Reference Kamčev and Schacht18, Reference Kamčev and Schacht19] use and adjust this principle to achieve their result for cliques. As a consequence, their methods imply results for all strictly balanced
$H$
, including even cycles, giving canonical copies of
$H$
in any colouring of
${\mathbf G}(n,p)$
a.a.s. when
$p=\omega (n^{-1/m_2(H)})$
. In particular this gives an upper bound on the threshold for the property that
${\mathbf G}(n,p)\xrightarrow {\scriptstyle \textrm {wcan}} H$
and determines this threshold for all strictly balanced
$H$
other than some small examples (as in Proposition 1.8). Their proof does not imply, however, that one can find all lexicographic copies of
$H$
and so does not directly imply Theorem 1.5.
1.4 Proof components
Our proof incorporates several other related problems for subgraphs in random graphs. Indeed, a key component of our proof is to use a canonical Ramsey theorem with list constraints which we previously developed [Reference Alvarado, Kohayakawa, Morris and Mota3, Reference Alvarado, Kohayakawa, Morris and Mota4] and proved using the hypergraph container method. We also use relative Turán results for cycles in random graphs (see Theorem 5.2). Finally, we appeal to a recent result on finding directed cycles in orientations of
${\mathbf G}(n,p)$
(see Lemma 5.3) and use this to find all lexicographic copies of
$C_{2k}$
under certain conditions of our colouring of
${\mathbf G}(n,p)$
. We believe that this somewhat surprising connection to a Ramsey problem involving orientations of graphs is one of the most interesting features of our proof.
Organisation. In Section 2 we collect some notation, basic properties of random graphs and some theory on locally dense graphs. In Section 3, we give the proof of Proposition 1.8. In Section 4, we give a proof overview and reduce Theorem 1.5 to a key lemma, namely Lemma 4.2, which proves the existence of a locally dense ‘rainbow focused’ graph generated by
${\mathbf G}(n,p)$
(see Section 4 for the relevant definitions). In Section 5 we then collect some results on the distribution of even cycles in
${\mathbf G}(n,p)$
that we will need. In Section 6 we prove Lemma 4.2 and hence complete the proof of Theorem 1.5.
2. Preliminaries
In this section, we collect the necessary theory and tools that we will use in our proof. These include simple random graph properties in Section 2.2, properties concerning the distribution of paths in random graphs in Section 2.3 and the theory of locally dense graphs in Section 2.4. Before all of this though, in Section 2.1, we collect the relevant notation.
2.1 Notation
We write
$P_\ell$
for the path with
$\ell$
vertices (and hence
$\ell -1$
edges) and
$C_\ell$
for the cycle with
$\ell$
vertices. For a graph
$G$
, a vertex
$v\in V(G)$
and a vertex subset
$U\subseteq V(G)$
, we have that
$d_G(v,U)$
denotes the number of neighbours of
$v$
in
$U$
and in the case that
$U=V(G)$
, we use the shorthand
$d_G(v)$
to denote the degree of
$v$
in
$G$
. We have that
$G[U]$
denotes the graph induced by
$G$
on the vertex set
$U$
and
$e_G(U)=e(G[U])$
denotes the number of edges in
$G$
that lie in
$U$
. Moreover, for disjoint vertex subsets
$U,W\subseteq V(G)$
,
$e_G(U,W)$
counts the number of edges with one endpoint in
$U$
and the other in
$W$
. Given a fixed (non-empty) graph
$H$
, we say that a graph
$G$
is
$H$
-free if
$G$
contains no copy of
$H$
. Let
$\mathop {\textrm {ex}}\nolimits (n,H) \, :\!= \, \max \{ e(G) \, : \, G \,\,\text{has}\,\, n \,\,\text{vertices and is} \,\,H \,\,\text{-free} \}$
. The Turán density
$\pi (H)$
of
$H$
is defined as
\begin{align} \pi (H) \, :\!= \, \lim _{n\to \infty }\mathop {\textrm {ex}}\nolimits (n,H)\binom {n}{2}^{-1}. \\[-8pt] \nonumber \end{align}
The well-known Erdős–Stone theorem implies that
$\pi (H) = (r-2)/(r-1)$
for every graph
$H$
with chromatic number
$r\geq 2$
.
The binomial random graph, denoted
${\mathbf G}(n,p)$
, refers to the probability distribution of graphs on vertex set
$[n]$
obtained by taking every possible edge independently with probability
$p=p(n)$
. We say an event happens asymptotically almost surely (a.a.s. for short) in
${\mathbf G} \sim {\mathbf G}(n,p)$
if the probability that it happens tends to 1 as
$n$
tends to infinity. We will also use standard asymptotic notation throughout, with asymptotics always being taken as the number of vertices
$n$
tends to infinity. For a Boolean statement
$A$
, we denote by
$\unicode{x1D7D9}[A]$
, the indicator function which evaluates to
$1$
if
$A$
holds and
$0$
if
$A$
does not hold.
Finally, we use the notation
$a=(b\pm c)d$
to denote that
$a\leq (b+c)d$
and
$a\geq (b-c)d$
and omit floors and ceilings throughout, so as not to clutter the arguments.
2.2 Random graph properties
Here we collect some simple properties of random graphs.
Lemma 2.1.
For any
$0\lt \varepsilon \leq 1$
and
$p=p(n)$
such that
$p=\omega (n^{-1})$
, the following properties hold a.a.s. in
${\mathbf G} \sim {\mathbf G} (n,p)$
:
-
(1)
$e_{\mathbf G} (U)=(1\pm \varepsilon ) p |U|^2/2$
for all
$U\subseteq V(G)$
with
$|U|\geq \sqrt {\tfrac {12n}{\varepsilon ^2 p}}$
. -
(2)
$d_{\mathbf G}(v)=(1 \pm \varepsilon )pn$
for all vertices
$v\in V({\mathbf G})$
. -
(3)
$e_{\mathbf G}(U,W)=(1\pm \varepsilon )p|U||W|$
for all pairs of disjoint subsets
$U, W\subseteq V({\mathbf G})$
such that
$|U||W|\geq \tfrac {6n}{\varepsilon ^2 p}$
. -
(4) For every
$U\subseteq V(G)$
with
$|U|\geq \varepsilon n$
, all but at most
$\varepsilon ^2 n$
vertices
$v\in V(G)$
have
$d_{\mathbf G}(v,U)=(1\pm \varepsilon )p|U|$
.
Proof. The first three assertions follow from standard applications of Chernoff bounds (see for example [Reference Janson, Łuczak and Rucinski17, Theorem 2.1]) and union bounds.
In order to prove (4), we can assume
$\varepsilon \leq 1$
as otherwise there is nothing to prove. We also assume that Lemma 2.1 (1)–(3) a.a.s. hold in
${\mathbf G} \sim {\mathbf G}(n,p)$
. Thus, for every pair of disjoint vertex subsets
$U$
and
$W$
with
$|U||W|\geq \tfrac {24 n}{\varepsilon ^2p}$
, one has that
$ e_{\mathbf G}(U,W) = \left (1\pm \tfrac {\varepsilon }{2}\right ) p|U||W|.$
Secondly, we have that
$e_{\mathbf G}(U)=\left (1\pm \tfrac {\varepsilon }{2}\right )p|U|^2/2$
for any set
$U\subseteq V(G)$
with
$|U|\geq \sqrt {\tfrac {48n}{\varepsilon ^2p}}$
. Letting
$G$
be any outcome of
$\mathbf G$
satisfying these two events on a sufficiently large number of vertices
$n$
, we will show that the desired conclusion of the lemma holds in
$G$
. So fix some
$U$
such that
$|U|\geq \varepsilon n$
. Furthermore, let
$B^-$
be the set of vertices
$v$
such that
$d_G(v,U)\lt (1-\varepsilon )p|U|$
and
$B^+$
be the set of vertices
$v$
in
$G$
such that
$d_G(v,U)\gt (1+\varepsilon )p|U|$
. Supposing for a contradiction that
$|B^-| \gt \tfrac {\varepsilon ^2n}{2}$
, let
$B\subseteq B^-$
be a set of size exactly
$\tfrac {\varepsilon ^2n}{2}$
and note that
$|U\setminus B|\geq |U|-\tfrac {\varepsilon ^2 n}{2}\geq \left (1-\tfrac {\varepsilon }{2}\right )|U|$
, using that
$|U|\geq \varepsilon n$
. Therefore, since
$p=\omega (n^{-1})$
and
$n$
is sufficiently large, we have that
$|U\setminus B||B|\geq \tfrac {24 n}{\varepsilon ^2p}$
and counting edges from
$B$
we get that
\begin{equation*}e_G(B,U\setminus B)\lt |B| \cdot (1-\varepsilon )p|U|\leq \left (1-\frac {\varepsilon }{2}\right )p|B||U\setminus B|, \end{equation*}
contradicting our first assumption on
$G$
. The case for vertices of too high degree is similar. We suppose for a contradiction that
$|B^+|\geq \tfrac {\varepsilon ^2n}{2}$
and let
$B'\subseteq B^+$
be a subset of size exactly
$\tfrac {\varepsilon ^2n}{2}$
. Now we claim that
$e_G(B')\leq \tfrac {\varepsilon }{2} p|B'||U|$
. Indeed
$\tfrac {\varepsilon ^2n}{2}=|B'|\geq \sqrt {\tfrac {48n}{\varepsilon ^2p}}$
as
$p=\omega (n^{-1})$
and so our second assumption on
$G$
applied to
$B'$
implies that
$e_G(B')\leq p|B'|^2\leq \tfrac {\varepsilon ^2}{2} pn|B'|\leq \tfrac {\varepsilon }{2}p|B'|U|$
as
$|U|\geq \varepsilon n$
. Therefore, counting edges from
$B'$
, we have that
\begin{equation*}e_G(B',U\setminus B')\gt |B'| \cdot (1+\varepsilon )p|U|-e_G(B')\geq \left (1+\frac {\varepsilon }{2} \right )p|B'||U|\geq \left (1+\frac {\varepsilon }{2} \right )p|B'||U\setminus B'|, \end{equation*}
again contradicting our first condition of
$G$
.
2.3 Paths in random graphs
In this section, we explore the distribution of paths in
${\mathbf G}(n,p)$
. We make the following definitions.
Definition 2.2. For a graph
$G$
on vertex set
$[n]$
,
$\ell \in {\mathbb N}$
and a pair
$\{u,v\}$
of vertices, we let
$X^\ell _G(\{u,v\})$
denote the number of paths with
$\ell$
vertices in
$G$
with endpoints
$u$
and
$v$
. Moreover, for a vertex
$v\in [n]$
, we let
\begin{equation*}X^\ell _G(v)\, :\!= \,\sum _{u\in [n]\setminus \{v\}}X^\ell _{G}(\{u,v\})\end{equation*}
be the number of copies of
$P_\ell$
in
$G$
that have
$v$
as an endpoint.
We need the following statement which will be used to show that if we find a collection of
$\Omega (n^\ell p^{\ell -1})$
copies of
$P_\ell$
in
${\mathbf G}(n,p)$
, then there will be
$\Omega (n^2)$
pairs of vertices
$f\in \binom {[n]}{2}$
that form the endpoints of some path in the collection.
Lemma 2.3.
For any integer
$\ell \gt 2$
,
$\xi \gt 0$
, and
$p=p(n)$
such that
$p =\omega \left ( n^{-1+1/(\ell -1)}\right )$
, the following holds a.a.s. in
${\mathbf G}\sim {\mathbf G}(n,p)$
. Let
$F=F({\mathbf G})$
be the collection of pairs
$f\in \binom {[n]}{2}$
such that
$X_{\mathbf G}^\ell (f)\gt 2n^{\ell -2}p^{\ell -1}$
. Then
\begin{equation*} \sum _{\substack {f\in F}}{X^\ell _{{\mathbf G}}(f)} \leq \xi n^{\ell } p^{\ell -1}. \end{equation*}
Proof. Fix an integer
$\ell \geq 2$
and
$\xi \gt 0$
and let
${\mathbf G}\sim {\mathbf G}(n,p)$
with
$p= \omega \left (n^{-1+\frac {1}{\ell -1}}\right )$
. If we consider
$f$
as a uniform random pair in
$E(K_n)=\binom {[n]}{2}$
(selected independently of
$\mathbf G$
), then due to the fact that
$\binom {n}{2}\leq n^2$
, one can check that our desired conclusion will follow from proving the statement that
\begin{align} {\mathop {\mathbb{P}}\nolimits }_p\left [ \mathop {\mathbb{E}}\nolimits _f\left [ X_{\mathbf G}^\ell (f) \unicode{x1D7D9}{ [ X_{\mathbf G}^\ell (f) \gt 2 n^{\ell -2}p^{\ell -1} ] } \right ] \gt \xi n^{\ell -2}p^{\ell -1} \right ] = o(1), \end{align}
where
${\mathop {\mathbb{P}}\nolimits }_p \, :\!= \, {\mathop {\mathbb{P}}\nolimits }_{{\mathbf G}\sim {\mathbf G}(n,p)}$
and
$\mathop {\mathbb{E}}\nolimits _f \, :\!= \, \mathop {\mathbb{E}}\nolimits _{f\sim \textrm {Unif}(E(K_n))}$
. In order to show equation (2), we use Markov’s Inequality, the Fubini–Tonelli Theorem and the Cauchy–Schwarz Inequality to obtain that
\begin{align} {\mathop {\mathbb{P}}\nolimits }_p & \left [ \mathop {\mathbb{E}}\nolimits _f\left [ X_{\mathbf G}^\ell (f) \unicode {x1D7D9}{[ X_{\mathbf G}^\ell (f) \geq 2 n^{\ell -2}p^{\ell -1} ] } \right ] \gt \xi \, n^{\ell -2}p^{\ell -1}\right ] \nonumber \\[3pt] & \leq \frac {\mathop {\mathbb{E}}\nolimits _p \mathop {\mathbb{E}}\nolimits _f \left [ X_{\mathbf G}^\ell (f) \unicode {x1D7D9}{[ X_{\mathbf G}^\ell (f) \geq 2 n^{\ell -2}p^{\ell -1} ] } \right ] } { \xi n^{\ell -2} p^{\ell -1}} \nonumber \\[3pt] & \leq \frac {\mathop {\mathbb{E}}\nolimits _f \left [ \left (\mathop {\mathbb{E}}\nolimits _p [ X_{\mathbf G}^\ell (f)^2 ]\right )^{1/2} \, \left ({\mathop {\mathbb{P}}\nolimits }_p [{ X_{\mathbf G}^\ell (f) \geq 2 n^{\ell -2}p^{\ell -1}} ]\right )^{1/2} \right ] }{ \xi n^{\ell -2} p^{\ell -1}}. \end{align}
We claim then that it is enough to show that for each (deterministic)
$f\in E(K_n)$
, one has
\begin{align} \mathop {\mathbb{E}}\nolimits _p[ X_{\mathbf G}^\ell (f)^2 ] = (1+o(1)) \mu ^2, \end{align}
where
$\mu \, :\!= \,\mathop {\mathbb{E}}\nolimits _p[X_{\mathbf G}^\ell (f)]=(n-2)_{(\ell -2)} \, p^{\ell -1}$
is the expected number of copies of
$P_\ell$
that have endpoints
$f$
. Indeed, assuming equation (4), by the second moment method we have that
\begin{align*} &{\mathop {\mathbb{P}}\nolimits }_p [{ X_{\mathbf G}^\ell (f) \geq 2 n^{\ell -2}p^{\ell -1} } ] \leq {\mathop {\mathbb{P}}\nolimits }_p [{ X_{\mathbf G}^\ell (f) \geq 2 \mu } ]\\[3pt] &\qquad\quad\,\,\,\, \leq {\mathop {\textrm {Var}}\nolimits }_p[X^\ell _{\mathbf G}(f)] /\mu ^2 = \big [\mathop {\mathbb{E}}\nolimits _p[ X_{\mathbf G}^\ell (f)^2 ]-\mu ^2\big ]/\mu ^2=o(1),\qquad \qquad \end{align*}
and combining this with equation (3), we have that
\begin{equation*} {\mathop {\mathbb{P}}\nolimits }_p\left [ \mathop {\mathbb{E}}\nolimits _f\left [ X_{\mathbf G}^\ell (f) \unicode {x1D7D9}{ [ X_{\mathbf G}^\ell (f) \gt 2 n^{\ell -2}p^{\ell -1} ] } \right ] \gt \xi n^{\ell -2}p^{\ell -1} \right ] = o\left ( \frac {\mu }{ n^{\ell -2}p^{\ell -1}} \right ) = o(1), \end{equation*}
establishing equation (2), as desired.
Thus it only remains to prove equation (4). Note that this is equivalent to the statement that
${\mathop {\textrm {Var}}\nolimits }_p[X_{\mathbf G}^\ell (f)] = o(\mu ^2)$
. Since
$X_{\mathbf G}^\ell (f)$
is a sum of indicators random variables, it is well known (see e.g., [Reference Alon and Spencer2, Chapter 4]) that
${\mathop {\textrm {Var}}\nolimits }_p[X_{\mathbf G}^\ell (f)]\leq \mu (1+\Delta ^*)$
where
$\Delta ^* = \sum _{\substack {P}}{ {\mathop {\mathbb{P}}\nolimits }_p[ P \subset {\mathbf G} \mid Q \subset {\mathbf G} ] }$
, where
$Q$
is an arbitrary copy of
$P_\ell$
in
$K_n$
with endpoints
$f$
, and the sum goes over all copies
$P$
of
$P_\ell$
in
$K_n$
whose endpoints are
$f$
and are such that
$1\leq |E(P) \cap E(Q)| \lt \ell -1$
. By our assumption on
$p$
, we have that
$\mu =\omega (1)$
, and so we only need to show that
$\Delta ^* = o(\mu )$
. Now suppose that
$1\leq r \leq \ell -2$
and
$I\subseteq E(Q)$
is some subset of
$r$
edges of
$Q$
. Then the number of paths
$P$
such that
$E(P)\cap E(Q) = I$
is at most
$ n^{\ell -2-v_I}$
, where
$v_I$
is the number of vertices in
$V(Q)\setminus f$
that belong to the edges in
$I$
. Since
$I$
defines a disjoint union of paths (each path of length at least one), we have that
$v_I \geq r$
. So, the total contribution to
$\Delta ^*$
of paths
$P$
such that
$E(P)\cap E(Q)=I$
is at most
$n^{\ell -2-r}p^{\ell -1-r}$
. Hence, summing all the possible contributions, we obtain that
\begin{align*} \Delta ^* & = \sum _{r=1}^{\ell -2}{ \sum _{\substack {I\subset E(Q)\,:\, |I| = r}}{ n^{\ell -2-r} p^{\ell -1-r} } } = \sum _{r=1}^{\ell -2}{ \binom {\ell -1}{r}{ \frac { n^{\ell -2}p^{\ell -1}}{(np)^r} } }\leq 2^{\ell -1} \cdot \frac {n^{\ell -2}p^{\ell -1}}{np}=o(\mu ), \end{align*}
where the last equation follows because
$pn = \omega \left (n^{\frac {1}{\ell -1}}\right )=\omega (1)$
, and we are done.
2.4 Locally dense graphs
The final tool that we will need is the notion of locally dense graphs.
Definition 2.4 (
$(\rho ,d$
)-dense graphs). For
$\rho ,d\in (0,1]$
, we say a graph
$G$
is
$(\rho ,d$
)-dense if for every
$S\subset V(G)$
with
$|S|\geq \rho n$
, the induced graph
$G[S]$
has at least
$d\binom {|S|}{2}$
edges.
Remark 2.5. In [Reference Rödl and Ruciński29] the authors observed that in order to establish that a graph
$G$
is
$(\rho ,d)$
-dense it suffices to establish the defining property for subsets
$S\subset V(G)$
of size exactly
$\lceil \rho n\rceil$
.
Graphs with the
$(\rho ,d)$
-dense property for
$\rho = o(1)$
are often called locally dense graphs. This property can be viewed as a weak quasirandomness property.
3. The weak canonical threshold for
$C_4$
Here we prove Proposition 1.8, which asserts that the threshold for the weak canonical property
${\mathbf G}(n,p)\xrightarrow {\scriptstyle \textrm {wcan}} C_4$
is
$n^{-3/4}$
.
Proof of Proposition
1.8. This essentially follows from a result of Barros, Cavalar, Parczyk, and the third author of the current paper [Reference Barros, Cavalar, Mota and Parczyk9]. Indeed in [Reference Barros, Cavalar, Mota and Parczyk9] it is shown that
$n^{-3/4}$
is the threshold for
$G={\mathbf G}(n,p)$
to have the anti-Ramsey property with respect to
$C_4$
, meaning that in any proper colouring of
$G$
there is a rainbow copy of
$C_4$
. Thus, if
$p=o(n^{-3/4})$
then a.a.s. there is a proper colouring of
${\mathbf G}\sim {\mathbf G}(n,p)$
avoiding rainbow copies of
$C_4$
. As the colouring is proper, it also avoids monochromatic copies of
$C_4$
and all lexicographic copies of
$C_4$
(as for any ordering
$\sigma$
of
$V(C_4)$
the first vertex in the ordering is incident to two edges of the same colour). This establishes the
$0$
-statement. For the
$1$
-statement, we also follow the approach of [Reference Barros, Cavalar, Mota and Parczyk9], which uses that if
$p=\omega (n^{-3/4})$
, then
${\mathbf G}\sim {\mathbf G}(n,p)$
a.a.s. contains a copy of
$K_{2,4}$
and
$K_{2,4}$
has the anti-Ramsey property with respect to
$C_4$
. Therefore it suffices to consider non-proper colourings of
$K_{2,4}$
. Fix a non-proper colouring of
$K_{2,4}$
and assume that there is no lexicographic copy of
$C_4$
within it. Our aim is to show that it contains a monochromatic copy of
$C_4$
.
Label the vertex set of
$K_{2,4}$
as
$X\cup Y$
with
$X$
the part of size
$2$
and
$Y$
the part of size 4 in the bipartition. Without loss of generality we can assume that colour
$1$
induces a subgraph of
$K_{2,4}$
, say
$G_1$
, such that
$\Delta (G_1)\geq 2$
. Observe that if
$x_1,x_2\in X$
and
$y_1,y_2\in Y$
are distinct vertices with
$y_1\in N_{G_1}(x_1) \cap N_{G_1}(x_2)$
, then
$y_2\in N_{G_1}(x_1) \cup N_{G_1}(x_2)$
, as if this is not the case, then it is easy to check that we obtain a lexicographic copy of
$C_4$
in our colouring. Likewise if
$x_1\in N_{G_1}(y_1) \cap N_{G_1}(y_2)$
, then
$x_2\in N_{G_1}(y_1) \cup N_{G_1}(y_2)$
. In what follows we conclude the proof by showing that
$G_1$
contains a
$C_4$
. Because of the observation just discussed, if there is a vertex
$x\in X$
with at least
$2$
neighbours in
$G_1$
, then there is a path in
$G_1$
with three edges and in particular there exists
$y\in Y$
with
$\deg _{G_1}(y)\geq 2$
. Now, using our observation once more, we have that each vertex in
$Y\setminus \{y\}$
is adjacent to one of the vertices in
$X$
. By the pigeonhole principle, there is a vertex
$x\in X$
which is adjacent to two vertices of
$Y\setminus \{y\}$
, say
$y'$
and
$y''$
. Again by our observation, the remaining vertex
$x'$
in
$X\setminus \{x\}$
is adjacent to either
$y'$
or
$y''$
, completing a
$C_4$
in
$G_1$
in either case, as desired.
4. Proof overview
Our proof uses ideas from both the original proof of Rödl and Ruciński [Reference Rödl and Ruciński29] and the approach of Nenadov and Steger [Reference Nenadov and Steger25] proving the
$1$
-statement of the sparse Ramsey theorem with a finite number of colours. Let us sketch briefly both ideas, restricting our discussion to our case of interest, where the desired monochromatic graph
$H$
is an even cycle, say
$H=C_{2k}$
.
Firstly, the proof of Rödl and Ruciński [Reference Rödl and Ruciński29] uses the idea of colour-focusing, a classical approach in Ramsey theory, along with multi-round exposure techniques. Suppose first that we are interested in the two colour case and we want to show that any red/blue-colouring of
${\mathbf G}(n,p)$
with
$p=\omega \left (n^{-1+1/(2k-1)}\right )$
has a monochromatic copy of
$C_{2k}$
a.a.s. They then reveal
${\mathbf G}(n,p)$
in two rounds. In the first round, they reveal
${\mathbf G}_1={\mathbf G}(n,p_1)$
, where
$p_1=\alpha p$
for some small
$\alpha \gt 0$
, and so a positive fraction of the edges of
${\mathbf G}(n,p)$
has been revealed. Now for any red/blue-colouring
$\chi _1$
of
$E({\mathbf G}_1)$
, they prove that there are
$\Omega (n^{2k}p^{2k-1})$
monochromatic copies of
$P_{2k}$
. The key point is that for each such
$(u,v)$
-path
$P_{2k}$
which is monochromatic, say, blue, if
$uv$
appears in the second exposure, then our hand is forced if we want to colour
$uv$
avoiding a monochromatic copy of
$C_{2k}$
: we have to colour it red. Now using that there are many monochromatic copies of
$P_{2k}$
, they show that there is some colour, say blue, and some locally dense graph
$\Gamma$
on
$\Omega (n)$
vertices of
${\mathbf G}_1$
such that for each edge
$f=uv$
of
$\Gamma$
, there is some
$(u,v)$
-path with
$2k$
vertices in
${\mathbf G}_1$
which is coloured completely blue by
$\chi _1$
. Hence revealing now
${\mathbf G}_2={\mathbf G}(n,p_2)$
such that
${\mathbf G}(n,p)={\mathbf G}_1\cup {\mathbf G}_2$
, we have that if
${\mathbf G}_1$
is coloured by
$\chi _1$
, any edge in
$E({\mathbf G}_2)\cap \Gamma$
must be coloured red if we want to avoid blue copies of
$C_{2k}$
in
$\mathbf G$
. The final step is to show that a.a.s. (in fact, with probability large enough to perform a union bound over all possible colourings of
${\mathbf G}_1$
), we have that
${\mathbf G}_2\cap \Gamma$
contains a copy of
$C_{2k}$
, which is coloured completely red, and hence the colouring
$\chi _1$
cannot be extended to the edges of
${\mathbf G}_2$
without creating a monochromatic cycle. The proof for more colours is achieved by a careful induction on the number of colours, iterating these ideas.
The proof of Nenadov and Steger [Reference Nenadov and Steger25] is entirely distinct and appeals to the method of hypergraph containers. Here, suppose we want to find a monochromatic
$C_{2k}$
in any
$r$
-colouring of a typical
${\mathbf G}={\mathbf G}(n,p)$
. The idea is then to create an auxiliary hypergraph
$\mathcal{H}$
whose vertex set consists of
$r$
copies of
$E(K_n)$
and whose edge set encodes the monochromatic copies of
$C_{2k}$
in
$K_n$
. The key observation then is that any colouring of
$\mathbf G$
that avoids monochromatic copies of
$C_{2k}$
can be identified with an independent set in
$\mathcal{H}$
. Using containers, one can efficiently group together these independent sets and identify a small set of containers
$\mathcal{C}$
such that each independent set of
$\mathcal{H}$
belongs to one such container. The proof then proceeds by showing that for each fixed container
$C\in \mathcal{C}$
, it is very unlikely (i.e., with probability
$\exp (-\Omega (n^2p))$
) that the graph
$\mathbf G$
lies within
$C$
. By this, we mean that there is a colouring of
$\mathbf G$
that, when mapped in the obvious way to a vertex subset of
$\mathcal{H}$
, corresponds to a subset of
$C$
. The proof then follows by performing a union bound over the choices of container
$C\in \mathcal{C}$
.
Neither approach generalises directly to the setting where the number of colours can grow with
$n$
. Indeed, for the first approach, even if one could find many monochromatic copies of
$P_{2k}$
in each random graph
${\mathbf G}_i={\mathbf G}(n,p_i)$
(which may not be the case), one would need
$t=\omega (1)$
iterations in order to focus the colours enough to force a monochromatic copy of
$C_{2k}$
in the final random graph
${\mathbf G}_t$
, thus forcing each
$p_i$
to be of order
$p/t$
. Likewise, the containers approach relies crucially on the fact that the hypergraph
$\mathcal{H}$
that encodes the monochromatic copies of
$C_{2k}$
has
$v(\mathcal{H})=O(n^2)$
. Having an unbounded number of copies of
$E(K_n)$
in
$V(\mathcal{H})$
corresponding to an unbounded number of colours available, leads to an adjustment which renders the upper bound on the number of containers useless and the proof falls apart.
The key idea of our proof is to use the first exposure to follow the idea of colour-focusing used by Rödl and Ruciński [Reference Rödl and Ruciński29], but instead of finding monochromatic paths to globally reduce the number of colours under consideration, we find rainbow paths in order to give local restrictions on the colours that can be used in the second exposure. We make the following definition.
Definition 4.1 (Rainbow focused graph). Let
$\ell \geq 3$
be an integer and let
$G$
be a graph whose edges are coloured with a colouring
$\chi \, : \, E(G)\rightarrow {\mathbb N}$
. Define
$\Gamma = \Gamma (\ell ,G,\chi )$
as the graph with vertex set
$V(G)$
such that
$uv$
is an edge of
$\Gamma$
if there is a
$(u,v)$
-path
$P$
with
$\ell$
vertices in
$G$
which is coloured rainbow by
$\chi$
.
The heart of our argument is the following lemma, which will be used on the first exposure, and shows that if a colouring
$\chi$
of the random graph
${\mathbf G}={\mathbf G}(n,p)$
avoids monochromatic and lexicographic copies of
$C_{2k}$
, then there will be many rainbow copies of
$P_{2k}$
and in fact the rainbow focused graph
$\Gamma (2k,{\mathbf G},\chi )$
will be locally dense.
Lemma 4.2 (Locally dense rainbow focused graph). Given an integer
$k \geq 2$
there exists
$d\gt 0$
such that for all
$0\lt \rho \leq 1$
, the following holds a.a.s. in
${\mathbf G}\sim {\mathbf G}(n,p)$
when
$p=\omega \left (n^{-1+1/(2k-1)}\right )$
. In every edge colouring
$\chi \,:\,E({\mathbf G})\rightarrow {\mathbb N}$
of
$\mathbf G$
, either
-
(i)
$\mathbf G$
contains a monochromatic copy of
$C_{2k}$
, -
(ii) for all orderings
$\sigma$
of
$V(C_{2k})$
, the graph
$\mathbf G$
contains a copy of
$C_{2k}$
which is lexicographic with respect to
$\sigma$
, or
-
(iii) the rainbow focused graph
$\Gamma = \Gamma (2k, {\mathbf G}, \chi )$
is
$(\rho ,d)$
-dense.
Lemma 4.2 will be proved in Section 6. We remark that a relative Turán result for even cycles (see Theorem 5.2) is used to show the existence of a monochromatic cycle if some colour class of
$\chi$
is dense. This is where our proof fails for odd cycles as they are non-degenerate.
Lemma 4.2 will be used on our first exposure
${\mathbf G}_1$
. Note that if
${\mathbf G}_1$
is coloured by
$\chi$
and
$\Gamma =\Gamma (2k,{\mathbf G}_1,\chi )$
, then for every edge
$f=uv\in E(\Gamma )$
, if
$f$
appears in our second exposure and we wish to colour it avoiding a canonical copy of
$C_{2k}$
, then we have restrictions on what colour we use on
$f$
. Indeed, as
$f=uv\in E(\Gamma )$
, there is a rainbow copy of
$P_{2k}$
with endpoints
$u$
and
$v$
. If
$f$
is coloured in any colour other than the colours that feature on this path, we will get a rainbow cycle. Therefore, for each edge
$f$
of
$\Gamma$
there is a list of
$2k-1$
colours from which we have to choose the colour of
$f$
if
$f$
appears in
${\mathbf G}_2$
. The second main intermediate result we need shows that these local restrictions are enough to force a canonical copy of
$C_{2k}$
in the random graph. In fact, this part of our argument holds much more generally and so we state it for all possible
$H$
.
Theorem 4.3 (Canonical Ramsey theorem with list colourings) Let
$H$
be a graph, and let
$1 \leq r\in {\mathbb N}$
and
$d\gt 0$
be given. Then there exists
$\rho$
,
$c\gt 0$
such that the following holds. Let
$\Gamma$
be an
$n$
-vertex
$(\rho ,d)$
-dense graph and let
${\mathcal L}\,:\,E(\Gamma )\rightarrow \mathbb{N}^r$
be a list-assignment (with repeats allowed). If
$p = \omega \left ( n^{-1/m_2(H)} \right )$
, then with probability at least
$1- \exp {(-cp n^2)}$
, any edge colouring
$\chi$
of
$\Gamma \cap {\mathbf G}(n,p)$
such that
$\chi (e)\in \mathcal{L}(e)$
for all
$e\in E(\Gamma \cap {\mathbf G}(n,p))$
contains a canonical copy of
$H$
with respect to
$\sigma$
for all orderings
$\sigma$
of
$V(H)$
.
Theorem 4.3 is proved in a companion paper [Reference Alvarado, Kohayakawa, Morris and Mota3, Reference Alvarado, Kohayakawa, Morris and Mota4] by building on the containers approach of Nenadov and Steger to prove the sparse Ramsey theorem with finitely many colours.
With Lemma 4.2 and Theorem 4.3, the proof of Theorem 1.5 follows readily, as we now show.
Proof of Theorem
1.5. Fix
$2\leq k\in {\mathbb N}$
and
$r=2k-1$
, let
$d=d(k)\gt 0$
be the constant output by Lemma 4.2, and let
$\rho$
,
$c\gt 0$
be the constants output by Theorem 4.3 with inputs
$H=C_{2k}$
,
$r$
and
$d$
. Fix
$p=\omega \left (n^{-1+1/(2k-1)}\log n\right )$
and let
$\mu = pn^{1-1/(2k-1)}\left (\log n\right )^{-1}=\omega (1)$
. Furthermore, let
$p_1=\sqrt {\mu } \cdot n^{-1+1/(2k-1)}=\omega \left (n^{-1+1/(2k-1)}\right )$
and let
$p_2=p_2(n)$
be such that
$p=p_1+p_2(1-p_1)$
. Note that
$p_2=\omega (p_1\log n)$
. If
${\mathbf G}_i\sim {\mathbf G}(n,p_i)$
for
$i=1,\,2$
with the
${\mathbf G}_i$
independent, then
${\mathbf G}={\mathbf G}_1\cup {\mathbf G}_2\sim {\mathbf G}(n,p)$
. Let
$A$
be the event that there is an edge colouring
$\chi \,:\,E({\mathbf G}_1)\cup E({\mathbf G}_2)\rightarrow {\mathbb N}$
with no copies of
$C_{2k}$
which are canonical with respect to
$\sigma$
for some ordering
$\sigma$
of
$V(C_{2k})$
. We will show that the event
$A$
a.a.s. does not happen, and hence a.a.s.
${\mathbf G} \xrightarrow {\scriptstyle \textrm {can}} C_{2k}$
.
Let
$\mathcal{G}_1$
be the set of
$n$
-vertex graphs
$G_1$
such that
$e(G_1)\leq 2p_1\binom {n}{2}$
and such that for any colouring
$\chi _1\,:\,E(G_1)\rightarrow {\mathbb N}$
, there is either a monochromatic copy of
$C_{2k}$
, lexicographic copies of
$C_{2k}$
with respect to all orderings of the vertex set of
$C_{2k}$
, or the rainbow focused graph
$\Gamma (2k,G_1,\chi _1)$
is
$(\rho ,d)$
-dense. By Lemmas 2.1 (1) and 4.2, we have that a.a.s.
${\mathbf G}_1\in \mathcal{G}_1$
and so
\begin{equation*}{\mathop {\mathbb{P}}\nolimits }[ A]\leq {\mathop {\mathbb{P}}\nolimits }[ A\mid {\mathbf G}_1\in \mathcal{G}_1]+{\mathop {\mathbb{P}}\nolimits }[{\mathbf G}_1\notin \mathcal{G}_1] \leq \max \left \{{\mathop {\mathbb{P}}\nolimits }[ A\mid {\mathbf G}_1=G_1]\,:\,G_1\in \mathcal{G}_1\right \}+o(1).\end{equation*}
Hence it suffices to show that for any fixed
$G_1\in \mathcal{G}_1$
, we have
${\mathop {\mathbb{P}}\nolimits }[ A\mid {\mathbf G}_1=G_1]=o(1)$
.
Fix
$G_1\in \mathcal{G}_1$
. Now for any partition
$\mathcal{P}$
of
$E(G_1)$
, we say an edge colouring
$\chi _1\,:\,E(G_1)\rightarrow {\mathbb N}$
induces
$\mathcal{P}$
if the colour classes given by
$\chi _1$
are exactly the parts of the partition
$\mathcal{P}$
. Furthermore, for a partition
$\mathcal{P}$
of
$E(G_1)$
, let
$A(\mathcal{P})$
be the event that there is some colouring
$\chi \,:\,E(G_1)\cup E({\mathbf G}_2)\rightarrow {\mathbb N}$
with no copies of
$C_{2k}$
which are canonical with respect to some ordering
$\sigma$
and such that
$\chi |_{E(G_1)}$
induces
$\mathcal{P}$
. We claim that it is enough to show that for any partition
$\mathcal{P}$
of
$E(G_1)$
, we have
\begin{equation} {\mathop {\mathbb{P}}\nolimits }[A(\mathcal{P})\mid {\mathbf G}_1=G_1] \leq \exp (-cp_2n^2). \end{equation}
Indeed, given that
${\mathbf G}_1=G_1$
, the event
$A$
is contained in the event
$\bigcup A(\mathcal{P})$
where the union goes over all possible partitions
$\mathcal{P}$
of
$E(G_1)$
and so if equation (5) holds, appealing to the union bound, we have that
\begin{equation*}{\mathop {\mathbb{P}}\nolimits }[ A\mid {\mathbf G}_1=G_1]\leq \sum _{\mathcal{P}} {\mathop {\mathbb{P}}\nolimits }[ A(\mathcal{P})\mid {\mathbf G}_1=G_1]\leq \sum _{\mathcal{P}} \exp (-cp_2n^2)\leq \exp (4p_1n^2\log n-cp_2n^2)=o(1),\end{equation*}
where we used that the number of partitions of
$E(G_1)$
is at most
$\exp (e(G_1)\log (e(G_1))\leq \exp (4p_1n^2\log n)$
as
$G_1\in \mathcal{G}_1$
and the fact that
$p_2=\omega (p_1\log n)$
. (We remark that it is here where we need the extra log-factor in our probability, all other parts of our argument would work with
$p=\omega (n^{-1+1/(2k-1)})$
.)
It remains to prove equation (5). So fix some partition
$\mathcal{P}$
of
$E(G_1)$
and let
$\chi _1\, : \,E(G_1)\rightarrow {\mathbb N}$
be some colouring that induces
$\mathcal{P}$
. It suffices to bound the probability that there is a colouring
$\chi \,:\,E(G_1)\cup E({\mathbf G}_2)\rightarrow {\mathbb N}$
with no copies of
$C_{2k}$
which are canonical with respect to some ordering
$\sigma$
and such that
$\chi |_{E(G_1)}=\chi _1$
. Indeed, for any colouring
$\chi$
of
$E(G_1)\cup E({\mathbf G}_2)$
such that
$\chi |_{E(G_1)}$
induces
$\mathcal{P}$
, we can permute the colours so that
$\chi |_{E(G_1)}=\chi _1$
. Now if
$G_1$
has a monochromatic copy of
$C_{2k}$
or lexicographic copies of
$C_{2k}$
with respect to all orderings, when coloured by
$\chi _1$
, we have that
${\mathop {\mathbb{P}}\nolimits }[A(\mathcal{P})\mid {\mathbf G}_1=G_1]=0$
and we are done. So suppose that this is not the case and hence, as
$G_1\in \mathcal{G}_1$
, we have that
$\Gamma \, :\!= \,\Gamma (2k,G_1,\chi _1)$
is
$(\rho ,d)$
-dense. Now for each edge
$e=uv\in \Gamma$
, assign a list
$\mathcal{L}(e)$
of the
$r=2k-1$
colours that feature in a rainbow copy of
$P_{2k}$
in
$G_1$
with endpoints
$u$
and
$v$
. With probability at least
$1-\exp (-cp_2n^2)$
, the graph
${\mathbf G}_2$
satisfies the conclusion of Theorem 4.3 with respect to the lists
$\mathcal{L}$
and we claim that this implies equation (5), as desired. Indeed, for any outcome
$G_2$
of
${\mathbf G}_2$
that satisfies the conclusion of Theorem 4.3, and any colouring
$\chi \,:\,E(G_1)\cup E(G_2)\rightarrow \mathbb{N}$
with
$\chi |_{E(G_1)}=\chi _1$
, we have that if
$\chi (e)\notin \mathcal{L}(e)$
for some edge in
$E(G_2)\cap \Gamma$
, then we have a copy of
$C_{2k}$
in
$G_1\cup G_2$
which is rainbow. However, if
$\chi (e)\in \mathcal{L}(e)$
for all edges in
$E(G_2)\cap \Gamma$
then there is a canonical copy of
$C_{2k}$
with respect to
$\sigma$
for all orderings
$\sigma$
in
$\Gamma \cap G_2$
, as
$G_2$
is a realisation of
${\mathbf G}_2$
satisfying the conclusion of Theorem 4.3. This concludes the proof of the theorem.
5. Even cycles in random graphs
Here we give some auxiliary results on even cycles, which will be useful in our proof of Lemma 4.2. Firstly, in Section 5.1, we give an upper bound on the number of even cycles that intersect a given vertex set more than twice. We then explore Turán properties of random graphs with respect to cycles in Section 5.2 and finally, in Section 5.3, we discuss finding directed even cycles in orientations of
${\mathbf G}(n,p)$
.
5.1 Even cycles intersecting small vertex sets in many vertices
The following lemma will be useful in our proof of Lemma 4.2 to upper bound the number of unlabelled copies of
$C_{2k}$
of a certain unwanted form.
Lemma 5.1.
For any integer
$k\geq 2$
and any
$0\lt \zeta \leq \frac {1}{2k^2}$
, the following holds a.a.s. in
${\mathbf G}\sim {\mathbf G}(n,p)$
when
$p=\omega \left (n^{-1+1/(2k-1)}\right )$
. For any
$U\subseteq V({\mathbf G})$
such that
$|U|\leq \zeta n$
, the number of unlabelled copies of
$C_{2k}$
in
$\mathbf G$
that intersect
$U$
in more than one vertex is at most
$k\zeta ^2n^{2k}p^{2k}$
.
Proof. This proof is similar to [Reference Allen, Böttcher, Corsten, Davies, Jenssen, Morris, Roberts and Skokan1, Lemma 4.1]. First, we introduce some (local) notation. Let
$Z$
be the random variable that counts the number of labelled copies of
$C_{2k}$
in
$\mathbf G$
. For each
$U\subseteq V({\mathbf G})$
and
$i\in \{0,1,\ldots ,2k\}$
, let
$Z^{U}_{i}$
be the random variable that counts the number of labelled copies of
$C_{2k}$
that intersects
$U$
in exactly
$i$
vertices. Set
$Z^{U}_{\geq i} \, :\!= \, \sum _{j\geq i}{Z^{U}_{j}}$
. Our goal is to show that the event
\begin{align} \forall \, U \in {\binom{n}{\zeta n}}\,,\,\, Z^U_{\geq 2} & \leq 4k^2 \zeta ^2 \, p^{2k} n^{2k} \end{align}
a.a.s. occurs. Notice that this result is (essentially) equivalent to our desired conclusion. Indeed, assume that (6) occurs and let
$U\subseteq V({\mathbf G})$
with
$|U| \leq \zeta n$
be given. Since increasing the size of
$U$
only increases the number of cycles intersecting it, we can assume the worst case
$|U| = \zeta n$
. Now,
$Z^U_{\geq 2}/{\textrm {aut}}(C_{2k})=Z^U_{\geq 2}/4k$
is the number of unlabelled copies of
$C_{2k}$
in
$\mathbf G$
that intersect
$U$
in more than one vertex. In particular, if equation (6) holds, then the number of such copies of
$C_{2k}$
is at most
$k\zeta ^2 \, p^{2k} n^{2k}$
, as desired. It remains to show that equation (6) a.a.s. occurs. Note that
$Z^{U}_{\geq 2} = Z - Z^{U}_{0} - Z^{U}_{1}$
. Let
$\epsilon =\zeta ^3$
. We shall prove that there is
$c = c(k,\zeta )\gt 0$
such that
\begin{align} {\mathop {\mathbb{P}}\nolimits }[Z \gt (1+\varepsilon ) \, p^{2k} n^{2k} ] & = o(1), \\[-10pt] \nonumber\end{align}
\begin{align} {\mathop {\mathbb{P}}\nolimits }[Z^{U}_0 \lt (1-\varepsilon ) \, (1-\zeta )^{2k} \, p^{2k} n^{2k} ] & \leq \exp ( - c \, pn^2 ) \\[10pt] \nonumber \end{align}
and
\begin{align} {\mathop {\mathbb{P}}\nolimits }[Z^{U}_1 \lt (1-\varepsilon ) \, 2k \, \zeta (1-\zeta )^{2k-1} \, p^{2k} n^{2k} ] & \leq 2k \, \exp ( - c \, pn^2), \end{align}
for any
$U \in {\binom{n}{\zeta n}}$
. Suppose the event in equation (7) fails as do the events in equations (8) and (9) for a given
$U$
. Then, as we shall check shortly, we have that
$Z^U_{\geq 2} \leq 4k^2\zeta ^2 \, p^{2k} n^{2k}$
for that set
$U$
, which is the desired inequality in equation (6). Thus, the fact that equation (6) holds a.a.s. follows from equations (7), (8), and (9) by the union bound, because
$o(1) + (2k+1){\binom{n}{\zeta n}} \exp (-c \, pn^2) = o(1)$
, where we have used that
$pn^2 = \omega (n)$
. It remains to check that if the events in equations (7), (8), and (9) all fail, then
$Z^U_{\geq 2} \leq 4k^2\zeta ^2 \, p^{2k} n^{2k}$
. Suppose those events do fail. Then
\begin{align*} Z^{U}_{\geq 2} = Z - Z^{U}_{0} - Z^{U}_{1} \leq \left ((1+\varepsilon ) - (1-\varepsilon ) \, (1-\zeta )^{2k} - (1-\varepsilon ) \, 2k \, \zeta (1-\zeta )^{2k-1}\right )p^{2k} n^{2k}. \end{align*}
Applying Boole’s inequality twice and the fact that
$\varepsilon = \zeta ^3$
and
$\zeta \leq 1/{2k^2}$
, we see that
\begin{align*} (1+\varepsilon ) &- (1-\varepsilon ) \, (1-\zeta )^{2k} - (1-\varepsilon ) \, 2k \, \zeta (1-\zeta )^{2k-1} \\[3pt] &\quad = 1 - (1-\zeta )^{2k} - 2k \zeta (1-\zeta )^{2k-1} + \varepsilon ( 1 + (1-\zeta )^{2k} + 2k \zeta (1-\zeta )^{2k-1} ) \\[3pt] &\quad \leq 1 - ( 1 - 2k\zeta ) -2k \zeta (1 - (2k-1) \zeta ) + \varepsilon (2+2k\zeta ) \\[3pt] &\quad \leq 2k\zeta ^2(2k-1)+3\epsilon \\[3pt] &\quad \leq 4k^2 \zeta ^2, \end{align*}
and hence
$Z^U_{\geq 2} \leq 4k^2\zeta ^2 \, p^{2k} n^{2k}$
, as required.
Thus, it is sufficient to prove that equation (7) holds and that equations (8) and (9) hold for any
$U \in {\binom{n}{\zeta n}}$
. These results follow by standard concentration arguments. More exactly, one can show equation (7) by the second moment method, while crucially one can show equations (8) and (9) using Janson inequalities (which give us a good exponential decay). Upper and lower tails for subgraph counts have been extensively studied (see for instance [Reference Janson, Łuczak and Rucinski17]), and noticing that
$Z_0^U$
is the random variable counting labelled copies of
$C_{2k}$
in (a copy of)
${\mathbf G}((1-\zeta )n,p)$
, we just need to justify equation (9). We introduce some formalism for the sake of precision. Let
$C_{2k}^0$
be a
$2k$
-cycle with
$V(C_{2k}^0)=[2k]$
. Also, let
$K_n^0$
be the complete graph with
$V(K_n^0)=[n]$
, and suppose our random graphs
${\mathbf G}\sim {\mathbf G}(n,p)$
are subgraphs of
$K_n^0$
. A labelled copy of
$C_{2k}$
in
$K_n^0$
is an injective map
$\phi :[2k]\to [n]$
. Thus,
$Z_1^U$
is the number of such
$\phi$
such that
$\phi (C_{2k}^0)$
is a subgraph of
$\mathbf G$
and
$|V(\phi (C_{2k}^0))\cap U|=1$
. For convenience, we let
$Z_1^U = \sum _{s \in [2k]}{Z_1^{U;s}}$
, where
$Z_1^{U;s}$
is the number of
$\phi$
with
$\phi (C_{2k}^0)\subset {\mathbf G}$
such that
$V(\phi [C_{2k}^0])\cap U = \{\phi (s)\}$
. Note that, by symmetry, the random variables
$Z_1^{U;s}$
(
$s\in [2k]$
) have the same distribution. Thus, it is enough to show that
\begin{align} {\mathop {\mathbb{P}}\nolimits }[ Z_1^{U;1} \lt (1-\varepsilon ) \, \zeta (1-\zeta )^{2k-1} \, p^{2k} n^{2k} ] \leq \exp (- c \, pn^2) . \end{align}
Following the notation of [Reference Janson, Łuczak and Rucinski17, Chapter 2], we have that
\begin{align} {\mathop {\mathbb{P}}\nolimits }[ Z_1^{U;1} \lt (1-\varepsilon ) \, \mu ] \leq \exp \left (- \frac {\varepsilon ^2 \mu ^2}{2 \Delta + \mu } \right ), \end{align}
where
$\mu = \mathop {\mathbb{E}}\nolimits [ Z_1^{U;1} ] = (1+o(1)) \zeta (1-\zeta )^{2k-1} p^{2k} n^{2k}$
, and
\begin{align*} \Delta \, :\!= \, \Big (\sum _{\psi \sim \phi }{ {\mathop {\mathbb{P}}\nolimits }[\psi [C_{2k}^0] \cup \phi [C_{2k}^0] \subseteq {\mathbf G} ] }\Big )/2 \end{align*}
where
$\psi \sim \phi$
indicates that the sum ranges over all pairs
$(\psi ,\phi )$
of distinct labelled copies of
$C_{2k}^0$
in
$K_n^0$
which send vertex
$1$
to
$U$
and
$|E(\psi [C_{2k}^0])\cap E(\phi [C_{2k}^0])|\geq 1$
. Note that
\begin{equation} \Delta = O(p^{4k-1} n^{4k-2}), \end{equation}
since the expectation of the number of pairs of labelled cycles of length
$2k$
that intersect in at least one edge in
$G(n,p)$
without the restriction of them containing exactly one vertex of
$U$
is
$O(p^{4k-1} n^{4k-2})$
. Furthermore, because of our hypothesis on
$p$
, we have that
$\mu =o(p^{4k-1}n^{4k-2})$
, and hence the denominator in equation (11) is at most
$O(p^{4k-1}n^{4k-2})$
. Taking this into account and plugging in the value of
$\mu$
into equation (11), we conclude equation (10), as desired.
5.2 Turán properties of random graphs
We will use the following theorem established by Haxell, Łuczak, and the second author of the current paper [Reference Haxell, Kohayakawa and Łuczak15].
Theorem 5.2 (Relative Turán Theorem: even-cycle case). Let
$2\leq k\in {\mathbb N}$
and
$\delta \gt 0$
be arbitrary. If
$p=p(n)$
is such that
$p=\omega \left (n^{-1+1/(2k-1)}\right )$
, then a.a.s.
${\mathbf G}\sim {\mathbf G}(n,p)$
has the property that any subgraph
$H\subseteq {\mathbf G}$
with
$e(H)\geq \delta np^2$
contains a copy of
$C_{2k}$
.
We remark that more precise results [Reference Kohayakawa, Kreuter and Steger21, Reference Morris and Saxton23] for even cycles have since been obtained and that Theorem 5.2 falls into the general program of establishing the extremal densities of
$H$
-free subgraphs of
${\mathbf G}(n,p)$
. This line of research culminated in breakthrough results [Reference Conlon and Gowers11, Reference Schacht32] providing the full picture for all graphs
$H$
and subsequent elegant alternative proofs [Reference Balogh, Morris and Samotij6, Reference Saxton and Thomason31] using the method of hypergraph containers (see the next section). We refer the reader to the survey of Rödl and Schacht [Reference Rödl and Schacht30] and Conlon [Reference Conlon13] for more on the topic.
5.3 Directed cycles in orientations of random graphs
We will be interested in finding copies of directed cycles in arbitrary orientations of
${\mathbf G}(n,p)$
. This problem has been studied by Cavalar [Reference Cavalar10] (see also [Reference Barros, Cavalar, Kohayakawa, Mota and Naia7, Reference Barros, Cavalar, Kohayakawa and Naia8]). In particular, it is known that when
$\vec {H}$
is an acyclic orientation of a complete graph or a cycle, then, except for the transitive triangle,
$n^{-1/m_2(H)}$
is the threshold for the property that any orientation of
${\mathbf G}(n,p)$
contains a copy of
$\vec {H}$
. Here we require the following lemma, which is a slight strengthening of a theorem of Cavalar [Reference Cavalar10] (see also [Reference Barros, Cavalar, Kohayakawa, Mota and Naia7]). For simplicity, we restrict ourselves to cycles, as this is the only case we need here.
It will be convenient to introduce the following definition. Let
$3\leq \ell \in {\mathbb N}$
and
$x\geq 0$
be given. We say that a graph
$G$
has the
$(C_\ell ,x)$
-orientation property if for any acyclic orientation
$\, \vec{\kern-2pt C}_\ell$
of
$C_\ell$
and any orientation
$\, \vec {\kern-2pt G}$
of
$G$
, the number of labelled copies of
$\, \vec{\kern-2pt C}_\ell$
in
$\, \vec {\kern-2pt G}$
is at least
$x$
.
Lemma 5.3.
Let
$3\leq \ell \in {\mathbb N}$
and
$\epsilon \gt 0$
be given and suppose
$p=p(n)$
is such that
$p=\omega \big (n^{-1+1/(\ell -1)}\big )$
. Then there is
$\eta \gt 0$
such that for every
$\nu \gt 0$
a.a.s.
${\mathbf G}\sim {\mathbf G}(n,p)$
has the property that for every
$W\subseteq V({\mathbf G})$
with
$|W|\geq \nu n$
, every subgraph
$G\subseteq {\mathbf G}[W]$
with
\begin{equation} e(G)\geq \left (\pi (K_{2^{\ell -1}})+\varepsilon \right ) p\binom {|W|}2 \end{equation}
has the
$\big (C_\ell ,\eta (\nu pn\big )^\ell )$
-orientation property.
Lemma 5.3 can be proved with the sparse regularity method. A sketch of the proof is given in Appendix A.
6. Locally dense rainbow focused graphs
In this section, we prove Lemma 4.2. Before embarking on this, let us sketch the main ideas of the proof. Suppose we have
${\mathbf G}\sim {\mathbf G}(n,p)$
as in Lemma 4.2 and that
$\chi \,:\,E({\mathbf G})\rightarrow {\mathbb N}$
is some edge colouring of
$\mathbf G$
. We can further assume that
$\chi$
has no monochromatic copy of
$C_{2k}$
as otherwise the proof is done and so we aim to prove that either there are lexicographic copies of
$C_{2k}$
for all orderings of its vertices, or the third conclusion of the lemma holds: that is, the rainbow focused graph is locally dense. Firstly, through an application of Lemma 2.3, we will show that in order to prove that the rainbow focused graph is locally dense, it suffices to find
$d|S|^2n^{2k-2}p^{2k-1}$
rainbow copies of
$P_{2k}$
with endpoints in
$S$
for every
$S \subseteq V({\mathbf G})$
with
$|S| = \rho n$
(see Claim 6.4). To simplify this discussion (whilst still conveying the key ideas of the proof), let us focus on the case
$\rho =1$
and so
$S=V({\mathbf G})$
. We begin by classifying the vertices of
$\mathbf G$
, depending on the profile of colours in their neighbourhood. In particular, we will be interested in whether there is some constant proportion of the edges incident to a given vertex that have all been assigned the same colour by
$\chi$
. This leads us to the following definition.
Definition 6.1. Let
$G$
be an
$n$
-vertex graph and
$\chi \,:\,E(G)\rightarrow {\mathbb N}$
an edge colouring of
$G$
. Given
$\alpha \gt 0$
and
$c\in {\mathbb N}$
, we say that
-
•
$v\in V(G)$
is
$(\alpha \,; c)$
-heavy if there are at least
$\alpha d_G(v)$
edges
$uv$
with
$\chi (uv) = c$
; -
•
$U\subseteq V(G)$
is
$\alpha$
-heavy if every
$v\in U$
is
$(\alpha \,; \,c)$
-heavy for some
$c\in {\mathbb N}$
; -
•
$\lambda \, : \, U \rightarrow {\mathbb N}$
is
$\alpha$
-heavy if for every
$c\in {\mathbb N}$
all vertices in
$\lambda ^{-1}(c)\subseteq U$
are
$(\alpha \,; \,c)$
-heavy.
Furthermore, a vertex
$v\in V({\mathbf G})$
is
$\alpha$
-rainbow if
$v$
is not
$(\alpha \,; \,c)$
-heavy for any
$c\in {\mathbb N}$
.
Now we discuss how to find the desired rainbow copies of
$P_{2k}$
, but to give the precise intuition we start by analysing two extreme cases, depending whether all the vertices are heavy or all the vertices are rainbow.
Suppose first that for some small
$\alpha \lt 1/2k$
, all vertices
$v\in V({\mathbf G})$
are
$\alpha$
-rainbow. In this case, we can greedily form rainbow paths, up to length
$2k-1$
, which is our goal. Indeed, suppose we have some rainbow path
$P$
with
$\ell \lt 2k$
vertices such that
$P$
features a collection
$C\subseteq {\mathbb N}$
of
$\ell -1$
colours and
$v\in V({\mathbf G})$
is an endpoint of
$P$
. As
$v$
is
$\alpha$
-rainbow, the number of edges incident to
$v$
which are coloured with colours belonging to
$C$
is less than
$(\ell -1)\alpha d_{\mathbf G}(v)\leq (2k-1)\alpha d_{{\mathbf G}}(v)$
. Thus as
$\alpha \lt 1/2k$
, we have at least
$(1/2k)d_{{\mathbf G}}(v)$
choices of edge that extend
$P$
to a rainbow path with
$\ell +1$
vertices. A simple induction then yields the desired number of rainbow paths with
$2k$
vertices, using that all vertices
$v$
have degree
$d_{\mathbf G}(v)=(1\pm o(1))pn$
by Lemma 2.1 (2).
At the other extreme, let us now suppose that
$V({\mathbf G})$
is
$\alpha$
-heavy and that
$\lambda \,:\, V({\mathbf G})\rightarrow {\mathbb N}$
is some
$\alpha$
-heavy colour allocation. Our approach in this case is again to greedily extend rainbow paths, always using a heavy colour at the endpoint of the path to extend it. That is, if
$P$
is a rainbow path with
$\ell \lt 2k$
vertices and
$v$
is an endpoint of
$P$
, we will extend
$P$
by using one of the
$\alpha d_{\mathbf G}(v)$
edges incident to
$v$
with colour
$\lambda (v)$
. Of course, in order for this path to be rainbow, we need that
$P$
does not feature the colour
$\lambda (v)$
already. To impose this, we need to add extra conditions on our rainbow paths with the foresight that we do not want to end up in such a situation. In more detail, suppose we have a rainbow path
$P$
with
$\ell$
vertices coloured with a set
$C\subset {\mathbb N}$
of
$\ell -1$
colours and an endpoint
$v$
with the added condition that
$\lambda (v)\notin C$
. Then we extend along edges
$e=vw$
coloured with
$\lambda (v)$
but we also impose that
$\lambda (w)\notin C\cup \{\lambda (v)\}$
. This then allows us to continue the inductive process and extend the rainbow path from
$w$
. Now in order to get the correct number of rainbow paths, we need to show that this extra condition of dodging endpoints
$w$
such that
$\lambda (w)\in C\cup \{\lambda (v)\}$
does not restrict the number of choices significantly at each step of the greedy process. Furthermore, we also need to guarantee that there are still at least, say,
$(\alpha /2)d_{\mathbf G}(v)$
edges
$e=vw$
such that
$\chi (e)=\lambda (v)$
and
$\lambda (w)\notin C\cup \{\lambda (v)\}$
. This can be achieved (for almost all
$v$
) and follows from proving that, say,
$|\lambda ^{-1}(c)\cap N_{\mathbf G}(v)|\lt (\alpha /4k)pn$
for all
$c\in {\mathbb N}$
, which is the content of the preparatory Lemma 6.2 (1) (the proof of which relies on the assumption that there is no monochromatic
$C_{2k}$
).
It remains to address the case where we have a mix of heavy and rainbow vertices. That is, there is some maximal
$\alpha$
-heavy subset
$U\subset V({\mathbf G})$
and some
$\alpha$
-heavy colour allocation
$\lambda \,:\, U\rightarrow {\mathbb N}$
, and also there are
$\alpha$
-rainbow vertices outside
$U$
.
We will extend the
$\alpha$
-heavy colour allocation
$\lambda$
to an
$\alpha$
-rainbow vertex
$v\in V({\mathbf G})$
by setting
$\lambda (v)=\star$
for some
$\star \notin {\mathbb N}$
. Now consider the greedy approach as before and suppose we have a rainbow copy
$P$
of
$P_\ell$
with colours
$C\subseteq {\mathbb N}$
and endpoint
$v$
. If
$\lambda (v)=c\in {\mathbb N}$
, then we extend the path
$P$
with the edges coloured with colour
$c$
and if
$\lambda (v)=\star$
, we extend with edges that avoid the colours in
$C$
. Moreover, similarly to the previous case where all vertices were heavy, we impose that the new edge
$e=vw$
is such that
$\lambda (w)\notin C$
. This almost works to produce rainbow paths iteratively as before but note that in order to guarantee that a path given by this process is indeed rainbow, we also need that
$\lambda (w)\neq \chi (e)$
as otherwise our path may contain two consecutive edges of the same colour. In the case that
$v$
is
$(\alpha \,; \,c)$
-heavy for some
$c\in {\mathbb N}$
, we can impose that
$\lambda (w)\neq \chi (e)=\lambda (v)$
as in the previous paragraph. However, in the case that
$\lambda (v)=\star$
, we have a problem. Indeed, it could be the case that all edges
$e=vw$
incident to
$v$
such that
$\chi (e)\notin C$
are such that
$\chi (e)=\lambda (w)$
. What if, for instance, every vertex
$u\in U$
has all incident edges coloured
$\lambda (u)$
? In fact, Lemma 6.2 (3) shows that this cannot be the case (again under the assumption of no monochromatic
$C_{2k}$
) and that there must be some subset
$W\subseteq U$
such that every vertex
$w\in W$
has some significant proportion of its incident edges which are coloured in colours that are not
$\lambda (w)$
. This suggests that we carry out our iterative procedure for building paths imposing that we only use these edges not coloured
$\lambda (w)$
when our paths enter some
$w\in W$
. That is, we will only consider rainbow paths
$P$
with endpoints in
$W$
if the path with endpoint
$w\in W$
has its last edge coloured in some colour other than
$ \lambda (w)$
. This will ensure that we can extend such a path with edges coloured
$\lambda (w)$
as before.
In order for this to work, we will need to run our iterative process with respect to disjoint layers of vertices
$U_1,\ldots ,U_{k-1}$
and setting
$U_0$
to be
$S$
(recall that
$S=V({\mathbf G})$
for the purpose of this sketch). These layers are designed in such a way (Claim 6.5 in the proof of Lemma 4.2) that rainbow paths with endpoints in
$U_\ell$
can be extended to rainbow paths with endpoints in
$U_{\ell -1}$
with the added foresight discussed above that will allow the rainbow paths to be extended further to
$U_{\ell -2}$
and so on. Consequently, we will only count rainbow paths which respect this vertex partition but this will only affect the value of our density constant
$d=d(k)$
.
Finally whilst we can define each
$U_{\ell }$
in such a way that each vertex
$v$
in
$U_{\ell }$
is adjacent to many edges
$vw$
with vertices
$w$
in
$U_{\ell -1}$
that are good in the sense that
$\chi (vw)\neq \lambda (w)$
, we have one final hurdle which prevents us from finding rainbow paths. We need to find edges in
$U_{k-1}$
that can start our paths and be extended by both their endpoints to
$U_{k-2}$
in a rainbow fashion. It turns out that this is not always possible. Indeed consider the following instructive example. Suppose every vertex
$v$
in
$U_{k-1}$
is
$\alpha$
-heavy and in fact all edges from
$v$
to
$U_{k-2}$
are coloured
$\lambda (v)$
. Moreover, suppose that every edge
$e=vv'$
contained in
$U_{k-1}$
shares its colour with one of the heavy colours of its endpoints. That is,
$\chi (e)$
is either
$\lambda (v)$
or
$\lambda (v')$
. In such a colouring, one has that there are no rainbow paths of length three with endpoints in
$U_{k-2}$
and an edge in
$U_{k-1}$
. Our proof will show that such a colouring is essentially the only type of colouring that prevents us finding the right number of rainbow paths. In the case that such a colouring occurs, we will use Lemma 5.3 to prove the existence of lexicographic copies of
$C_{2k}$
with respect to all orderings. This is the content of Lemma 6.3.
First though, given an
$\alpha$
-heavy set
$U\subseteq V({\mathbf G})$
and an
$\alpha$
-heavy allocation
$\lambda \,:\, U \rightarrow {\mathbb N}$
, we need the following definition for an edge
$e=uv\in {\mathbf G}[U]$
:
\begin{align*} &e=uv\in E({\mathbf G}[U])\text{ is}\ {balanced} \text{ if }\lambda (u)\neq \lambda (v),\text{ and}\\[3pt] &e=uv\in E({\mathbf G}[U])\text{ is} \ u-{light} \text{ if }\chi (e)\neq \lambda (u). \end{align*}
The concepts of balanced and light edges appear in the following result, which will be used in the proof of Lemma 4.2 to define the vertex sets
$U_i$
in an appropriate fashion as discussed.
Lemma 6.2.
For all
$\alpha \gt 0$
and
$2\leq k\in {\mathbb N}$
the following holds a.a.s. in
${\mathbf G}\sim {\mathbf G}(n,p)$
when
$p=\omega \left (n^{-1+{1}/(2k-1)}\right )$
. For any monochromatic
$C_{2k}$
-free edge colouring
$\chi$
of
$\mathbf G$
, any
$\alpha$
-heavy
$U\subseteq V({\mathbf G})$
with
$|U|\geq \alpha n$
and any
$\alpha$
-heavy colour allocation
$\lambda \,:\, U \rightarrow {\mathbb N}$
, we have the following.
-
(1) For all but at most
$\alpha n$
vertices
$v$
of
$\mathbf G$
, we have
$|N_{\mathbf G}(v)\cap \lambda ^{-1}(c)|\leq \alpha p |U|$
for any
$c\in {\mathbb N}$
. -
(2)
${\mathbf G}[U]$
contains at least
$(1-2\alpha )p|U|^2/2$
balanced edges.
-
(3) There exists
$W\subseteq U$
such that
$|W|= \tfrac {1}{8}|U|$
and each vertex
$w\in W$
is incident to at least
$\tfrac {p}{5}|U|$
$w$
-light edges in
$\mathbf G$
whose other endpoint is in
$U\setminus W$
.
Proof. Note that we can assume that
$0\lt \alpha \lt \tfrac {1}{100}$
as the statement is stronger for smaller
$\alpha$
. Fix
$k\in {\mathbb N}$
,
$\delta \, :\!= \,\tfrac {\alpha ^3}{32}$
and
$\varepsilon \, :\!= \,\tfrac {\alpha ^2}{4(1+\alpha )}$
and let
$G$
be any outcome of
${\mathbf G}(n,p)$
that satisfies the conclusions of Lemma 2.1 and Theorem 5.2. As these properties all hold a.a.s. in
${\mathbf G}(n,p)$
, it suffices to show that any such
$G$
satisfies the desired conclusions. So fix such a
$G$
and furthermore, fix a monochromatic
$C_{2k}$
-free edge colouring
$\chi$
of
$G$
, some
$\alpha$
-heavy set
$U$
with
$|U|\geq \alpha n$
and some
$\alpha$
-heavy colour allocation
$\lambda \,:\, U \rightarrow {\mathbb N}$
. Appealing to the conclusion of Lemma 2.1 (2), we have that each
$u\in U$
has
$d_G(u)\geq (1-\varepsilon )pn$
and so has at least
$\alpha d_G(u)\geq \tfrac {\alpha }{2} p n$
incident edges coloured
$\lambda (u)$
by
$\chi$
. Therefore, for each
$c\in {\mathbb N}$
, we have
$|\lambda ^{-1}(c)|\leq \frac {\alpha }{8}|U|$
. Indeed if this was not the case then there would be at least
$\delta p n^2$
edges of
$G$
coloured
$c$
by
$\chi$
and by (the assumed conclusion of) Theorem 5.2, there is a copy of
$C_{2k}$
in
$G$
coloured
$c$
, contradicting the fact that
$\chi$
is monochromatic
$C_{2k}$
-free.
In order to prove part (1) of the lemma, we partition
$U$
as
$U=S_1\cup \ldots \cup S_t$
for some
$t\leq \tfrac {4}{\alpha }$
such that each
$S_i$
has size
$|S_i|\leq \tfrac {\alpha }{2}|U|$
and for each
$c\in {\mathbb N}$
, there is some
$i\in [t]$
such that
$\lambda ^{-1}(c)\subseteq S_i$
. In other words, we group the sets
$\lambda ^{-1}(c)$
for
$c\in {\mathbb N}$
together in order to get at most
$\tfrac {4}{\alpha }$
groups, each of which has size at most
$\tfrac {\alpha }{2}|U|$
. This can be done greedily by adding sets
$\lambda ^{-1}(c)$
to
$S_1$
until
$S_1$
has size at least
$\tfrac {\alpha }{4} |U|$
, and then moving on to fill
$S_2$
and repeating until all the sets
$\lambda ^{-1}(c)$
have been placed. Now by (the assumed conclusion of) Lemma 2.1 (4), we have that for each
$1\leq i \leq t$
, there is a set
$B_i\subseteq V(G)$
with
$|B_i|\leq \varepsilon ^2 n$
such that every vertex
$v\in V(G)\setminus B_i$
has
$d_G(v,S_i)\leq \alpha p|U|$
. Note here that even if
$S_i$
has size less than
$\varepsilon n$
, the conclusion of Lemma 2.1 (4) can be applied to a superset of
$S_i$
. Letting
$B=\bigcup _{i=1}^tB_i$
, for any
$c\in {\mathbb N}$
and any vertex
$v\in V(G)\setminus B$
we have that
$|N_G(v)\cap \lambda ^{-1}(c)|\leq \alpha p |U|$
as
$\lambda ^{-1}(c)\subseteq S_i$
for some
$i\in t$
. Noting that
$|B|\leq t\varepsilon ^2n\leq \alpha n$
then completes the proof of (1).
For part (2) of the lemma, we note that any edge in
$G[U]$
that is not contained in
$G[S_i]$
for some
$i\in [t]$
, is balanced. Indeed this follows from the fact that each
$\lambda ^{-1}(c)$
is contained in some
$S_i$
. Hence the number of balanced edges in
$G[U]$
is at least
\begin{equation*}e_G(U)-\sum _{i=1}^te_G(S_i)\geq \frac {(1-\varepsilon )p|U|^2}{2}-\frac {t(1+\varepsilon ) p \left (\frac {\alpha }{2}|U|\right )^2}{2}\geq \frac {(1-2\alpha ) p |U|^2}{2},\end{equation*}
as required, using the assumed conclusion of Lemma 2.1 (1) to lower bound
$e_G(U)$
and upper bound the
$e_G(S_i)$
as well as the upper bounds on
$|S_i|$
for each
$i\in [t]$
and the upper bound on
$t$
.
For part (3), we will say that an edge
$e=uv$
is light if it is
$u$
-light or
$v$
-light. Note that every balanced edge is necessarily light and define
$G^*$
to be the subgraph of
$G[U]$
given by all the light edges. Moreover, for each edge
$e=uv\in E(G^*)$
, we orient the edge so that if it is directed from
$u$
to
$v$
then the edge
$e$
is
$u$
-light. Note that for some edges
$e=uv\in G^*$
, both orientations are allowed as
$\chi (e)\notin \{\lambda (v),\lambda (u)\}$
; for such edges choose an orientation arbitrarily. Now let
$V_0\subseteq U$
be the set of vertices
$v\in U$
, such that
$d^+_{G^*}(v)\geq \tfrac {2p}{5}|U|$
, where
$d^+_{G^*}(v)$
denotes the number of out-neighbours of
$u$
in our oriented
$G^*$
. We claim that
$|V_0|\geq \tfrac {1}{6}|U|$
. Indeed, if this is not the case, then consider a set
$V_1\subseteq U\setminus V_0$
with
$|V_1|=\tfrac {5}{6}|U|$
and
$V_2=U\setminus V_1$
so that
$|V_2|=\tfrac {1}{6}|U|$
and
$V_0\subseteq V_2$
. We upper bound the number of edges in
$G^*$
by
\begin{align*} e_{G^*}(V_1)+e_{G^*}(V_1,V_2)+e_{G^*}(V_2) &\leq \sum _{v\in V_1}d^+_{G^*}(v)+e_{G}(V_1,V_2)+e_G(V_2) \\[3pt] &\leq |V_1|\cdot \frac {2p}{5}|U|+(1+\varepsilon )p|V_1||V_2|+(1+\varepsilon )\frac {p |V_2|^2}{2} \\[3pt] &\leq \left (\frac {1}{3}+(1+\varepsilon )\left (\frac {5}{36}+\frac {1}{72}\right ) \right )p|U|^2\lt \frac {(1-2\alpha )p|U|^2}{2}, \end{align*}
contradicting part (2) of the lemma, as every balanced edge is light. We used here the assumed conclusion of Lemma 2.1 (1) and (3) in
$G$
.
We then know that
$|V_0|\geq \tfrac {1}{6}|U|$
and we fix
$W'\subseteq V_0$
such that
$|W'|=\tfrac {1}{8}|U|+\varepsilon ^2n$
. By the assumed conclusion of Lemma 2.1 (4), we have that there is some
$W\subseteq W'$
with
$|W|=\tfrac {1}{8}|U|$
and every vertex
$w\in W$
has
$d_G(w,W)\leq d_G(w,W')\leq (1+\varepsilon )p|W'|\leq \tfrac {1}{5}p|U|$
. Therefore as
$W\subseteq V_0$
, each vertex
$v\in W$
is incident to at least
$\left (\tfrac {2}{5}-\tfrac {1}{5}\right )p|U|=\tfrac {1}{5}p|U|$
$v$
-light edges whose other endpoint is in
$U\setminus W$
, as required.
We will also need the following lemma which will be used to find lexicographic copies of
$C_{2k}$
in the case that certain colourings are present. Recall that an edge
$e=uv\in G[U]$
$u$
-light if
$\chi (e)\neq \lambda (u)$
and balanced if
$\lambda (u)\neq \lambda (v)$
. Moreover, call an edge
$e=uv\in G[U]$
totally light if
$\chi (e)\notin \{\lambda (u),\lambda (v)\}$
, that is, if it is light with respect to both of its vertices.
Lemma 6.3.
For all positive
$\nu$
and
$\alpha$
and
$2\leq k\in {\mathbb N}$
the following holds a.a.s. in
${\mathbf G}\sim {\mathbf G}(n,p)$
when
$p=\omega \left (n^{-1+{1}/(2k-1)}\right )$
. For any monochromatic
$C_{2k}$
-free edge colouring
$\chi$
of
$\mathbf G$
, any
$\alpha$
-heavy
$U\subseteq V({\mathbf G})$
with
$|U|\geq \nu n$
and any
$\alpha$
-heavy colour allocation
$\lambda \,:\, U \rightarrow {\mathbb N}$
, we have the following.
Either
${\mathbf G}[U]$
contains
$2^{-(8k+1)}p|U|^2$
balanced and totally light edges, or for all orderings
$\sigma$
of
$V(C_{2k})$
, the graph
${\mathbf G}[U]$
contains a copy of
$C_{2k}$
which is lexicographic with respect to
$\sigma$
.
Proof. Let
$\nu \gt 0$
be fixed. Note that we can assume that
$0\lt \alpha \lt \min \{2^{-16k},\nu \}$
as the statement of the lemma is stronger for smaller
$\alpha$
. Moreover, let
$\eta \gt 0$
be as output by Lemma 5.3 with input
$\ell =2k$
and
$\varepsilon =2^{-2\ell }$
. Fix
$0\lt \zeta \lt \eta \nu ^{2k}/(8k)$
and
$\delta =\zeta \alpha /8$
and let
$G$
be an instance of
${\mathbf G}(n,p)$
satisfying the conclusions of Theorem 5.2 and Lemmas 5.1, 5.3 and 6.2. It suffices to show that such a
$G$
satisfies the desired statement as all the listed properties of
$G$
occur a.a.s. in
${\mathbf G}(n,p)$
. So fix such a
$G$
and a monochromatic
$C_{2k}$
-free colouring
$\chi$
. Further, fix some
$\alpha$
-heavy vertex subset
$U\subseteq V(G)$
with
$|U|\geq \nu n$
and an
$\alpha$
-heavy colour allocation
$\lambda \,:\, U \rightarrow {\mathbb N}$
.
As in the proof of Lemma 6.2, we can assume that
$|\lambda ^{-1}(c)|\leq \zeta n/2$
for all
$c\in {\mathbb N}$
, as otherwise such a colour class would have at least
$\delta pn^2$
edges and thus contain a copy of
$C_{2k}$
by the assumed conclusion of Theorem 5.2. As we have assumed that our colouring
$\chi$
of
$G$
is monochromatic
$C_{2k}$
-free, this gives a contradiction. Therefore each
$\lambda ^{-1}(c)$
has size less than
$\zeta n/2$
. Again, as in the proof of Lemma 6.2, we can therefore partition
$U$
as
$U=S_1\cup \cdots \cup S_t$
for some
$t\leq {2/\zeta }$
such that each
$S_i$
has size
$ |S_i|\leq \zeta n$
and for each
$c\in {\mathbb N}$
, there is some
$i\in [t]$
such that
$\lambda ^{-1}(c)\subseteq S_i$
.
Now if there are
$2^{-(8k+1)}p|U|^2$
balanced edges in
$G[U]$
that are also totally light, we are done. So suppose this is not the case. Then by appealing to the assumed conclusion of Lemma 6.2 (2), there is some subgraph
$G^*$
of
$G[U]$
such that every edge in
$G^*$
is balanced (and therefore light) but not totally light and
\begin{equation*}e(G^*)\geq \left (1-2\alpha -2^{-8k}\right )p|U|^2/2\geq (1-2^{-4k})p|U|^2/2.\end{equation*}
We orient
$G^*$
as follows. Each edge
$e=uv\in E(G^*)$
is light with respect to exactly one of its vertices, say
$v$
, and we orient
$e$
from
$u$
to
$v$
. Thus each directed edge
$\vec {uv}$
of
$G^*$
gives an edge
$e=uv$
in
$G$
such that
$\chi (e)=\lambda (u)$
. Indeed
$e$
is light with respect to
$v$
and so
$\chi (e)\neq \lambda (v)$
but
$e$
is not totally light and so we must have that
$\chi (e)=\lambda (u)$
. By the assumed conclusion of Lemma 5.3 and our definition of
$\varepsilon$
, we have that our orientation of
$G^*$
contains
$\eta (\nu np)^{2k}$
copies of
$\vec {H}$
for any acyclic orientation
$\vec {H}$
of
$C_{2k}$
.
Now consider some arbitrary ordering
$\sigma$
of
$V(C_{2k})$
and let
$\vec {H}$
be the orientation of
$C_{2k}$
which has each edge oriented from its first to its second vertex, according to the ordering
$\sigma$
. Note that such an orientation
$\vec {H}$
is necessarily acyclic. Moreover, any copy of
$\vec {H}$
in
$G^*$
corresponds to a copy of
$C_{2k}$
in
$G$
where each edge
$e=uv$
is coloured
$\lambda (\min \{u,v\})$
where the minimum is taken with respect to the ordering
$\sigma$
. Now if
$\lambda$
is injective on the vertices of such a copy of
$C_{2k}$
, then this copy would be lexicographic with respect to
$\sigma$
. In order to guarantee the existence of such a lexicographic copy we upper bound the number of copies of
$C_{2k}$
that have more than one vertex in some set
$\lambda ^{-1}(c)$
. In fact, we bound the number of copies of
$C_{2k}$
with more than one vertex in
$S_i$
for some
$i\in [t]$
, which suffices as for each
$c\in {\mathbb N}$
, there is an
$i\in [t]$
with
$\lambda ^{-1}(c)\subseteq S_i$
. For a fixed
$i\in [t]$
, by the assumed conclusion of Lemma 5.1, there are at most
$k\zeta ^2(np)^{2k}$
copies of
$C_{2k}$
intersecting
$S_i$
in more than one vertex. Thus, there are at most
\begin{equation*}t\cdot k \zeta ^2(np)^{2k}\leq 2k \zeta (np)^{2k} \lt \eta (\nu n p)^{2k}/4\end{equation*}
copies of
$C_{2k}$
with a pair of distinct vertices
$u$
and
$v$
such that
$\lambda (u)=\lambda (v)$
. Hence at least one of the copies of our oriented cycle
$\vec {H}$
that came from the application of Lemma 5.3 corresponds to a copy of
$C_{2k}$
which is lexicographic with respect to
$\sigma$
. As
$\sigma$
was an arbitrary ordering of
$V(C_{2k})$
, this completes the proof.
With Lemmas 6.2 and 6.3 at hand, we are ready to prove Lemma 4.2.
Proof of Lemma
4.2 Fix
$2\leq k\in {\mathbb N}$
,
$0\lt \rho \leq 1$
, and
$p=\omega \left (n^{-1+{1}/({2k-1})}\right )$
as in the statement of the lemma. Note that we can assume
$\rho \lt 1/4$
as the statement of the lemma is stronger for smaller
$\rho$
. We also define the following constants for
$i=0,1,\ldots ,k-1$
:
\begin{equation} \gamma _i\, :\!= \,\frac {1}{4}\left (\frac {1}{20}\right )^i, \quad \theta \, :\!= \, \frac {\gamma _{k-1}}{2^{4k}}, \quad d\, :\!= \,\frac {1}{4}\cdot \left (\frac {\theta }{4}\right )^{2k}\cdot \prod _{i=1}^{k-1}\gamma ^2_i, \quad \xi \, :\!= \,\rho ^2d, \quad \mbox{ and } \quad \varepsilon =\alpha \, :\!= \,\xi ^2. \end{equation}
Recall from Definition 2.2 that, given a graph
$G$
on vertex set
$[n]$
, a vertex
$v$
and a pair of vertices
$f$
, we denote the number of paths with
$\ell$
vertices in
$G$
with endpoints
$f$
by
$X^\ell _G(f)$
. Furthermore, the number of copies of
$P_\ell$
in
$G$
that have
$v$
as an endpoint is denoted by
$X^\ell _G(v)$
. Also, we will frequently use the concept of heavy vertices, sets, and colour allocations, as in Definition 6.1.
We let
$\mathcal{G}$
be the collection of
$n$
-vertex graphs
$G$
satisfying the conclusions of Lemma 2.1, which contains some simple properties of
$G(n,p)$
, of Lemma 2.3 with
$\ell =2k$
, concerning the number of paths between some pairs of vertices in
$G(n,p)$
, and also satisfying the two preparatory results, Lemmas 6.2 and 6.3 with
$\nu \, :\!= \,\gamma _{k-1}$
. Thus, a.a.s.
${\mathbf G}\sim {\mathbf G}(n,p)$
is a subgraph of
$\mathcal{G}$
and so it suffices to show the desired conclusion for any
$G\in \mathcal{G}$
.
Fix some
$G\in \mathcal{G}$
and a colouring
$\chi \,:\,E(G)\rightarrow {\mathbb N}$
. Now assume that neither of the conclusions (i) nor (ii) hold in our colouring and so we aim to prove that condition (iii) holds, which means to prove that the rainbow focused graph
$\Gamma = \Gamma (2k, G, \chi )$
is
$(\rho ,d)$
-dense. In particular, we can assume that
$\chi$
is monochromatic
$C_{2k}$
-free and so
$G$
and
$\chi$
satisfy (1), (2) and (3) of Lemma 6.2 for all
$U$
and
$\lambda$
as in that lemma. We claim that it is enough to prove the following claim.
Claim 6.4.
For every vertex set
$S\subset V(G)$
with
$|S|=\rho n$
, there are at least
$2d\rho ^2n^{2k}p^{2k-1}$
rainbow copies of
$P_{2k}$
in
$G$
whose endpoints lie in
$S$
.
In order to see that Claim 6.4 suffices, note that by Remark 2.5, in order to prove that
$\Gamma =\Gamma (2k,G,\chi )$
is
$(\rho ,d)$
-dense, we just need to show that every
$S$
as in the claim contains at least
$d(\rho n)^2/2$
edges of
$\Gamma$
. Now, fixing such an
$S$
, for
$f\in \binom {S}{2}$
, let
$Y(f)$
be the number of rainbow copies of
$P_{2k}$
in
$G$
with endpoints
$f$
. Let
$F^+\subseteq \binom {S}{2}$
be the set of pairs of vertices
$f$
such that
$Y(f)\gt 0$
and
$F^{++}\subseteq F^+$
be the set of pairs
$f\in F^+$
such that
$Y(f)\gt 2n^{2k-2}p^{2k-1}$
.
Let
$F(G)$
be the collection of pairs
$f\in \binom {[n]}{2}$
such that
$X_G^{2k}(f)\gt 2n^{2k-2}p^{2k-1}$
. Since
$Y(f)\leq X_G^{2k}(f)$
for all pairs
$f\in \binom {S}{2}$
, we have that
\begin{equation} \sum _{f\in F^+\setminus F^{++}}Y(f)\geq \sum _{f\in F^+}Y(f)-\sum _{f\in F(G)}X_G^{2k}(f)\geq d\rho ^2n^{2k}p^{2k-1}, \end{equation}
using the assumed conclusion of Lemma 2.3 in
$G$
, the conclusion of Claim 6.4 and our definition of
$\xi$
equation (14) in the final inequality. By the definition of
$F^{++}$
, we also have that
\begin{equation*}\sum _{f\in F^+\setminus F^{++}}Y(f)\leq 2n^{2k-2}p^{2k-1}|F^+\setminus F^{++}|,\end{equation*}
and so combining with equation (15), we get that
$|F^+|\geq |F^+\setminus F^{++}|\geq d\rho ^2n^2/2$
. As
$F^+$
is precisely the set of edges of
$\Gamma$
on
$S$
, this concludes the proof of Lemma 4.2 assuming Claim 6.4.
Proof of Claim 6.4. Fix some
$S\subseteq V(G)$
with
$|S|=\rho n$
and, for convenience, let
$U_0=S$
. Claim 6.4 will be derived from the following claim that identifies the vertices and edges which will be used to form our desired rainbow paths. We will find disjoint vertex subsets
$U_1,\ldots ,U_{k-1}\subseteq V(G)\setminus U_0$
together with colour allocations satisfying some useful properties. Given
$i=1,\ldots ,k-1$
and
$u\in U_i$
, an edge
$e=uv$
is called good if
$v\in U_{i-1}$
and
$\chi (e)\neq \lambda _{i-1}(v)$
.
Claim 6.5.
There exist disjoint vertex subsets
$U_1,\ldots ,U_{k-1}\subseteq V(G)\setminus U_0$
and colour allocations
$\lambda _i\,:\,U_i\rightarrow \mathbb{N}\cup \{\star \}$
for
$i=0,\ldots ,k-1$
such that the following conditions hold for
$i=1,\ldots ,k-1$
:
-
(i)
$|U_i|=\gamma _i n$
. -
(ii) Either
$\lambda _i(u)=\star$
for all
$u\in U_i$
or
$\lambda _i\,:\,U_i\rightarrow {\mathbb N}$
is an
$\alpha$
-heavy colour allocation.
-
(iii) For every
$u\in U_{i}$
, either
-
(a)
$\lambda _i(u)=c\in \mathbb{N}$
and
$u$
is incident to at least
$\theta p|U_{i-1}|$
good edges coloured
$c$
by
$\chi$
; or
-
(b)
$\lambda _i(u)=\star$
and for any collection
$C\subseteq {\mathbb N}$
of at most
$2k-1$
colours, we have that
$u$
is incident to at least
$\theta p|U_{i-1}|$
good edges
$e$
such that
$\chi (e)\notin C$
.
-
-
(iv) For any
$u\in U_i$
, we have that for any set
$C\subseteq \mathbb{N}$
of at most
$2k-1$
colours,
$u$
is incident to at most
$\tfrac {\theta }{2}p|U_{i-1}|$
edges
$uv$
such that
$v\in U_{i-1}$
and
$\lambda _{i-1}(v)\in C$
.
Let us first see how Claim 6.5 implies Claim 6.4. We will prove by induction that for
$\ell =1,2,\ldots ,k$
there are at least
\begin{equation*}\beta _\ell \, :\!= \,\left (\frac {\theta }{4}\right )^{2\ell }p^{2\ell -1}\prod _{j=1}^{\ell }|U_{k-j}|^2\end{equation*}
rainbow copies of
$P_{2\ell }$
with endpoints in
$U_{k-\ell }$
. Our definition of constants from equation (14) and the fact that
$|U_i|=\gamma _i n$
(part (i) of Claim 6.5) then imply Claim 6.4 by applying the inductive statement with
$\ell =k$
. Now in order to prove the inductive statement, we will in fact only count rainbow copies
$P$
of
$P_{2\ell }$
with endpoints
$u$
,
$v\in U_{k-\ell }$
that satisfy further the following conditions:
-
•
$\lambda _{k-\ell }(u)=\lambda _{k-\ell }(v)$
only if
$\lambda _{k-\ell }(u)=\lambda _{k-\ell }(v)=\star$
, and -
•
$\lambda _{k-\ell }(u)$
,
$\lambda _{k-\ell }(v)\notin \chi (P)\, :\!= \,\{\chi (e)\, : \, e\in E(P)\}$
.
Let us first treat the base case
$\ell =1$
. By Claim 6.5 (ii), we have that either
$\lambda _{k-1}(u)=\star$
for all
$u\in U_{k-1}$
or
$\lambda _{k-1}\, : \, U_{k-1}\rightarrow {\mathbb N}$
is an
$\alpha$
-heavy colour allocation. Suppose first that
$\lambda _{k-1}(u)=\star$
for all
$u\in U_{k-1}$
. In that case, any edge in
$G[U_{k-1}]$
gives a valid path
$P_2$
and we have
$(1-\varepsilon )p|U_{k-1}|^2/2\gt \beta _1$
edges in
$U_{k-1}$
by the assumed conclusion of Lemma 2.1 (1) in
$G$
. On the other hand, if
$\lambda _{k-1} \, : \, U_{k-1}\rightarrow {\mathbb N}$
is an
$\alpha$
-heavy colour allocation, then, using that
$|U_{k-1}|\geq \nu n$
and that there are no lexicographic copies of
$C_{2k}$
for all orderings of its vertices (by assumption, otherwise we satisfy outcome (ii)), Lemma 6.3 implies that there are
$p|U_{k-1}|^2/2^{8k+1}\gt \beta _1$
edges
$e=uv$
in
$G[U_{k-1}]$
such that
$\chi (e)\notin \{\lambda (u),\lambda (v)\}$
and
$\lambda (u)\neq \lambda (v)$
. Each such edge gives a valid copy of
$P_2$
, as required.
Now for the inductive step, suppose that
$2\leq \ell \leq k$
and we have
$\beta _{\ell -1}$
rainbow copies
$P$
of
$P_{2\ell -2}$
with endpoints
$u,v\in U_{k-\ell +1}$
such that
$\chi (P)\cap \{\lambda _{k-\ell +1}(u),\lambda _{k-\ell +1}(v)\}=\emptyset$
and
$\lambda _{k-\ell +1}(u)=\lambda _{k-\ell +1}(v)$
only if
$\lambda _{k-\ell +1}(u)=\lambda _{k-\ell +1}(v)=\star$
. Fix any such copy
$P$
with endpoints
$u,v\in U_{k-\ell +1}$
and let
$C=\chi (P)$
. Furthermore, let
$C'=C$
if
$\lambda _{k-\ell +1}(v)=\star$
and
$C'=C\cup \{\lambda _{k-\ell +1}(v)\}$
if
$\lambda _{k-\ell +1}(v)\in {\mathbb N}$
. Now by Claim 6.5 (iii) there are at least
$\theta p|U_{k-\ell }|$
good edges
$e=uw$
with
$w\in U_{k-\ell }$
such that
$\chi (e)\notin C'$
. Indeed, if
$\lambda _{k-\ell +1}(u)=c\in {\mathbb N}$
, then we apply part (a) of the claim, using that
$c\notin C'=\chi (P)\cup \{\lambda _{k-\ell +1}(v)\}$
by induction and if
$\lambda _{k-\ell +1}(u)=\star$
, we apply (b) directly to avoid colours in
$C'=C$
. As these edges are good, we also have that
$\lambda _{k-\ell }(w)\neq \chi (e)$
. Moreover, by part (iv) of Claim 6.5, at most
$\tfrac {\theta }{2} p|U_{k-\ell }|$
of these edges
$e=uw$
have
$\lambda _{k-\ell }(w)\in C'$
and so we have at least
$\tfrac {\theta }{2} p|U_{k-\ell }|$
choices of edge
$e=uw$
such that
$P\cup \{e\}$
is rainbow,
$\lambda _{k-\ell }(w)\notin \chi (P\cup \{e\})=C\cup \{\chi (e)\}$
and
$\lambda _{k-\ell +1}(v)\notin C''$
, where
$C''$
is defined to be
$C''=\chi (P\cup \{e\})$
if
$\lambda _{k-\ell }(w)=\star$
and
$C''=\chi (P\cup \{e\})\cup \{\lambda _{k-\ell }(w)\}$
if
$\lambda _{k-\ell }(w)\in {\mathbb N}$
. Fixing such an edge
$e=uw$
, we now count the number of ways to extend the path
$P\cup \{e\}$
to a copy of
$P_{2\ell }$
with the desired properties. By Claim 6.5 (iii), we have that there are at least
$\tfrac {\theta }{2} p|U_{k-\ell }|-1$
(the
$-1$
accounts for the fact that we have to avoid
$w$
) good edges
$f=vz$
with
$z\in U_{k-\ell }\setminus \{w\}$
such that
$\chi (f)\notin C''$
. Here we use that
$\lambda _{k-\ell +1}(v)\notin C''$
if we are in case (a) and we apply the conclusion of (b) directly to avoid colour
$C''$
edges if
$\lambda _{k-\ell +1}(v)=\star$
. As these edges
$f=vz$
are good, we also have that
$\lambda _{k-\ell }(z)\neq \chi (f)$
. Moreover, by part (iv) of Claim 6.5, at most
$\tfrac {\theta }{2} p|U_{k-\ell }|$
of these edges
$f=vz$
have
$\lambda _{k-\ell }(z)\in C''$
and so we have at least
$\tfrac {\theta }{2} p|U_{k-\ell }|-1\geq \tfrac {\theta }{4} p|U_{k-\ell }|$
choices of edge
$f=vz$
such that
$P\cup \{e,f\}$
is a rainbow copy of
$P_{2\ell }$
with endpoints
$w,z$
such that
$\lambda _{k-\ell }(w),\lambda _{k-\ell }(z)\notin \chi (P\cup \{e,f\})$
and
$\{\lambda _{k-\ell }(w)\}\cap \{\lambda _{k-\ell }(z)\}\subseteq \{\star \}$
. Summing over all choices of rainbow copies
$P$
of
$P_{2\ell -2}$
(appealing to induction) and choices of extending edges
$e$
and
$f$
, we get at least
$\beta _{\ell -1}\cdot \tfrac {\theta ^2}{8}p^2|U_{k-\ell }|^2\geq \beta _\ell$
rainbow copies of
$P_{2\ell }$
with the desired properties, completing the induction, and the proof of Claim 6.4.
It remains to prove Claim 6.5.
Proof of Claim
6.5. We proceed by induction on
$i=0,\ldots , k-1$
. At the time of fixing
$U_i$
and
$\lambda _i$
for
$i=0,\ldots ,k-1$
, we will ensure that
$U_i$
satisfies conditions (i)–(iv) of the claim. For
$i=0,1,\ldots ,k-2$
, we will also impose an extra condition that will allow the induction to continue. Namely, we will guarantee the following extra condition holds:
-
(v) For
$i=0,\ldots ,k-2$
, fixing
$Z_i=V(G)\setminus \left (\bigcup _{j=0}^iU_j\right )$
, there are at least
$ \gamma _i pn|U_i|$
edges
$e=uz$
such that
$u\in U_i$
,
$z\in Z_i$
and
$\chi (e)\neq \lambda _i(u)$
.
For our base case
$i=0$
, we let
$\lambda _0(u)=\star$
for all
$u\in U_0$
, and check that this choice works. Note that conditions (i)–(iv) of the claim are not required for
$i=0$
, and hence it is only (v) that we need to check. By the assumed conclusion of Lemma 2.1 (3), we have that there are at least
$(1-\varepsilon )p|U_0||Z_0|\geq \gamma _0 pn|U_0|$
edges
$e=uz$
with
$u\in U_0$
and
$z\in Z_0$
, using here that we have
$(1-\varepsilon )|Z_0|\geq \gamma _0 n$
as
$|U_0|=\rho n\leq n/4$
. Moreover, each such edge
$e=uz$
certainly has
$\chi (e)\neq \lambda _0(u)$
as
$\lambda _0(u)=\star$
. This concludes the base case.
For the induction step, suppose that
$1\leq i\leq k-1$
and we have
$U_0,\ldots , U_{i-1},\gamma _0,\ldots ,\gamma _{i-1}$
already defined satisfying all the conditions of Claim 6.5 and
$Z_{i-1}\, :\!= \,V(G)\setminus \left (\bigcup _{j=0}^{i-1}U_j\right )$
such that there is a collection
$E'\subseteq E(G)$
of at least
$\gamma _{i-1} pn|U_{i-1}|$
edges
$e=uz$
with
$u\in U_{i-1}$
,
$z\in Z_{i-1}$
, and
$\chi (e)\neq \lambda _{i-1}(u)$
(condition (v)). Now let
$G'\subseteq G$
be the bipartite subgraph (with parts
$U_{i-1}$
and
$Z_{i-1}$
) of
$G$
defined by the set of edges
$E'$
. Let
$Z'\subseteq Z_{i-1}$
be the set of vertices
$z\in Z_{i-1}$
such that
$d_{G'}(z,U_{i-1})\geq \tfrac {\gamma _{i-1}}{4}p|U_{i-1}|$
. We claim that
$|Z'|\geq \tfrac {5\gamma _{i-1}}{8}n$
. Indeed, if this was not the case, then we would have
\begin{align*} & |E'|\leq e_{G'}(U_{i-1},Z_{i-1}\setminus Z')+e_{G}(U_{i-1}, Z')\\[3pt]&\quad \quad\quad\quad\qquad\qquad\leq n\cdot \frac {\gamma _{i-1}}{4}p|U_{i-1}|+(1+\varepsilon )p|U_{i-1}|\cdot \frac {5\gamma _{i-1}}{8}n\lt \gamma _{i-1} pn|U_{i-1}|,\qquad \end{align*}
contradicting our lower bound on the number of edges in
$G'$
. Here, we used the assumed conclusion of Lemma 2.1 (3) in
$G$
to upper bound
$e_G(U_{i-1},Z')$
: if
$|U_{i-1}||Z'|\geq 6n/\epsilon p$
, then we have
$e_G(U_{i-1},Z')\leq (1+\epsilon )p|U_{i-1}||Z'|\lt (1+\epsilon )p|U_{i-1}|(5\gamma _{i-1}/8)n$
, but if not, we consider a set
$\widetilde Z$
disjoint from
$U_{i-1}$
with
$Z'\subset \widetilde Z$
and
$|\widetilde Z|=5\gamma _{i-1}n/8$
and use that
$e_G(U_{i-1},Z')\leq e_G(U_{i-1},\widetilde Z)$
. So we indeed have that
$|Z'|\geq \tfrac {5\gamma _{i-1}}{8}n$
and by the assumed conclusion of Lemma 6.2 (1), we have that there is a subset
$Z''\subset Z'$
such that
$|Z''|\geq \left (\tfrac {5\gamma _{i-1}}{8}-\alpha \right )n\geq \tfrac {\gamma _{i-1}}{2}n$
and for all
$c\in {\mathbb N}$
and every
$z\in Z''$
, we have
$|N_G(z)\cap \lambda _{i-1}^{-1}(c)|\leq \alpha pn$
. Indeed this is immediate if
$\lambda _{i-1}^{-1}(\star )=U_{i-1}$
(we can take
$Z''=Z'$
) and if this is not the case, then condition (ii) for
$i-1$
(which is assumed by induction) implies that
$\lambda _{i-1}\,:\,U_{i-1}\rightarrow {\mathbb N}$
is an
$\alpha$
-heavy colour allocation and we can apply Lemma 6.2 (1). Now we aim to find
$U_{i}\subseteq Z''$
and we remark that this will imply that condition (iv) is satisfied. Indeed, this follows from the fact that
$\alpha \lt \tfrac {\theta }{4k}$
and our condition on vertices in
$Z''$
.
Now we define
$\lambda _i\,:\,Z''\rightarrow {\mathbb N}\cup \{\star \}$
as follows. For
$z\in Z''$
, if there is some colour
$c \in {\mathbb N}$
such that there are
$\theta p |U_{i-1}|$
edges in
$G'$
incident to
$z$
that are coloured
$c$
by
$\chi$
, we define
$\lambda _{i}(z)=c$
. If no such colour exists, we set
$\lambda _{i}(z)=\star$
. Now if
$|\lambda _i^{-1}(\star )|\geq \gamma _i n$
, we fix
$U_i\subseteq \lambda _i^{-1}(\star )\subseteq Z''$
with
$|U_i|=\gamma _i n$
and claim that all the conditions on
$U_i$
and
$\lambda _i$
(restricted to
$U_i$
) in Claim 6.5 as well as condition (v) (if
$i\leq k-2$
) are satisfied. Indeed, conditions (i) and (ii) are immediate and we have already established (iv) as
$U_i\subseteq Z''$
. For (iii), we use that
$\theta \lt \tfrac {\gamma _{i-1}}{8k}$
. Indeed, for
$u\in U_i$
and any set
$C\subseteq {\mathbb N}$
of size at most
$2k-1$
, we have that
$u$
is incident to at most
$(2k-1)\theta p |U_{i-1}|$
edges of
$G'$
that are coloured with colours in
$C$
. Hence, as
$d_{G'}(u,U_{i-1})\geq \tfrac {\gamma _{i-1}}{4} p|U_{i-1}|$
(as
$U_i\subseteq Z'$
), we have that there are at least
$\theta p|U_{i-1}|$
edges of
$G'$
incident to
$u$
which avoid the colours in
$C$
. As each of these edges
$uv\in E(G')$
with
$v\in U_{i-1}$
has
$\chi (e)\neq \lambda _{i-1}(v)$
, condition (iii) of Claim 6.5 follows. If
$i\leq k-2$
, in order to establish (v), we appeal to the assumed conclusion of Lemma 2.1 (3) in
$G$
which gives that
$e_G(U_i,Z_i)\geq (1-\varepsilon )p|U_i||Z_i|\geq \gamma _i pn|U_i|$
as
$(1-\varepsilon )|Z_i|\geq \gamma _i n$
because of condition (i) on the sizes of
$U_0,U_1,\ldots ,U_{i}$
which have been established so far. As any edge
$e=uz\in E(G)$
with
$u\in U_i$
and
$z\in Z_i$
has
$\chi (e)\neq \lambda _i(u)=\star$
, all the edges in
$G$
between
$U_i$
and
$Z_i$
are valid for condition (v) and we are done.
Thus it remains to treat the case when
$|\lambda _i^{-1}(\star )|\leq \gamma _i n$
. In this case, we let
$U\subseteq Z''\setminus \lambda _i^{-1}(\star )$
such that
$|U|=\gamma _{k-1} n$
if
$i=k-1$
and
$|U|=8\gamma _{i} n$
if
$i\leq k-2$
, which is possible as
$\gamma _i\lt \tfrac {\gamma _{i-1}}{18}$
. Now note that every vertex
$u\in U$
has at least
$\theta p |U_{i-1}|\geq 2\alpha p n\geq \alpha d_G(u)$
incident edges in colour
$\lambda _i(u)$
and so
$\lambda _i$
(restricted to
$U$
) is an
$\alpha$
-heavy colour allocation. Moreover, we certainly have that
$|U|\geq \alpha n$
and so the assumed conclusion of Lemma 6.2 (3) gives some subset
$W\subseteq U$
as in that lemma. Now if
$i=k-1$
, we fix
$U_i=U$
and if
$i\leq k-2$
we fix
$U_i=W$
. Let us check the conditions of Claim 6.5 (and condition (v)). By our choice of
$U_i$
, we certainly have that conditions (i) and (ii) (with
$\lambda _i$
restricted to
$U_i$
) both hold and we have already established condition (iv) as
$U_i\subseteq Z''$
. To see condition (iii), note that each
$u\in U_i$
is incident to at least
$\theta p|U_{i-1}|$
edges in
$G'$
which are coloured
$\lambda _i(u)$
, by our definition of
$\lambda _i$
and the fact that
$\lambda ^{-1}_i(\star )\cap U_i=\emptyset$
. Moreover all the edges
$e=uv\in E(G')$
with
$u\in U_i$
are good as defined just before the statement of Claim 6.5, as by the definition of
$G'$
they have
$v\in U_{i-1}$
and
$\chi (e)\neq \lambda _{i-1}(v)$
.
It remains to establish (v) in the case that
$i\leq k-2$
. We defined
$U_i=W\subseteq U$
from our application of Lemma 6.2 (3) and so we have that
$|U_i|=\tfrac {1}{8}|U|$
and each vertex
$u\in U_i$
is incident to at least
$p|U|/5\geq p|U_{i}|$
edges
$e=uv$
with
$v\in U\setminus U_i$
and
$\chi (e)\neq \lambda _i(u)$
. As
$U\setminus U_i\subseteq Z_i\, :\!= \,V(G)\setminus \left (\bigcup _{j=0}^iU_j\right )$
, summing over all
$u\in U_i$
, we get at least
$p|U_i|^2\geq \gamma _i pn|U_i|$
edges
$e=uz$
with
$u\in U_i$
,
$z\in Z_i$
, and
$\chi (e)\neq \lambda _i(u)$
, establishing (v), completing the induction step and concluding the proof of Claim 6.5.
Acknowledgements
We are grateful to Nina Kamčev and Mathias Schacht for insightful conversations about this topic and the anonymous referees for their careful work.
J. D. Alvarado was partially supported by FAPESP (2020/10796-0). Y. Kohayakawa was partially supported by CNPq (407970/2023-1, 420838/2025-2, 315258/2023-3) and FAPESP (2023/03167-5). P. Morris was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) Walter Benjamin programme - project number 504502205 and by the European Union’s Horizon Europe Marie Skłodowska-Curie grant RAND-COMB-DESIGN – project number 101106032
. G. O. Mota was partially supported by CNPq (315916/2023-0, 420838/2025-2) and FAPESP (2024/13859-4, 2023/03167-5). This study was financed in part by CAPES, Coordenação de Aperfeiçoamento de Pessoal de Nível Superior, Brazil, Finance Code 001. FAPESP is the São Paulo Research Foundation. CNPq is the National Council for Scientific and Technological Development of Brazil.
A. Proof of Lemma 5.3
Let
$\, \vec {\kern-2pt G}$
be an oriented graph, and let
$A$
and
$B\subset V(\, \vec {\kern-2pt G})$
be disjoint. We write
$\, \vec {\kern-2pt G}[A,B]$
for the oriented graph with vertex set
$A\cup B$
and arc set
$\{\overrightarrow {ab}\in E(\, \vec {\kern-2pt G}) : a\in A,\,b\in B \}$
. Set
$e_{\, \vec {\kern-2pt G}}(A,B) \, :\!= \, e(\, \vec {\kern-2pt G}[A,B])$
. Define the
$p$
-density of
$(A,B)$
in
$\, \vec {\kern-2pt G}$
as
\begin{align*} d_{\, \vec {\kern-2pt G},p}(A,B) \, :\!= \, \frac {e_{\, \vec {\kern-2pt G}}(A,B)}{p|A||B|}. \end{align*}
Let us say that
$\, \vec {\kern-2pt G}[A,B]$
is
$(\delta ,p)$
-regular if
\begin{align*} |d_{\, \vec {\kern-2pt G},p}(X,Y)-d_{\, \vec {\kern-2pt G},p}(A,B)|\leq \delta \end{align*}
for every
$X\subset A$
and
$Y\subset B$
with
$|X|\geq \delta |A|$
and
$|Y|\geq \delta |B|$
.
Given an
$n$
-vertex oriented graph
$\, \vec {\kern-2pt G}$
and
$\delta \gt 0$
, a partition
$\{V_0,V_1,\ldots ,V_k\}$
of the vertex set of
$\, \vec {\kern-2pt G}$
is called
$(\delta ,k)$
-equitable if
$|V_0|\leq \delta n$
and
$|V_1|=\ldots = |V_k|$
. Moreover, we say that a
$(\delta ,k)$
-equitable partition is
$(\delta ,\, \vec {\kern-2pt G},p)$
-regular if for all, but at most
$\delta k^2$
, of the distinct pairs
$(i,j)\in [k]^2$
the oriented graphs
$\, \vec {\kern-2pt G}[V_i,V_j]$
are
$(\delta ,p)$
-regular. Finally, say that an
$n$
-vertex graph
$G$
with density
$p$
is
$(\xi ,D,p)$
-upper uniform if we have
\begin{align*} e_{G}(X,Y) \leq D p |X| |Y| \end{align*}
for all disjoint vertex subsets
$X$
and
$Y$
with
$|X| \geq \xi n$
and
$|Y| \geq \xi n$
.
Now, we state a well-known version of the Sparse Szemerédi Regularity Lemma (SRL) for oriented graphs. This version can be easily deduced from its non-oriented counterparts [Reference Kohayakawa20, Reference Kohayakawa and Rödl22].
Theorem A.1 (SRL version for oriented graphs). For every
$\delta ,D\gt 0$
and every integer
$m\geq 1$
there are
$\xi \gt 0$
and an integer
$M\geq m$
such that every (sufficiently large)
$(\xi ,D,p)$
-upper uniform graph
$G$
has the following property. For any orientation
$\, \vec {\kern-2pt G}$
of
$G$
, there exists a
$(\delta ,\, \vec {\kern-2pt G},p)$
-regular partition into
$k+1$
classes with
$m\leq k \leq M$
.
Analogous to the non-oriented version of the (sparse) regularity method, we define the ‘reduced’ (dense) structure associated with a regular partition. Let
$\mathcal{P} = \{V_0,\ldots ,V_k\}$
be a
$(\delta ,\, \vec {\kern-2pt G} ,p)$
-regular partition and let
$\theta \gt 0$
be a parameter. The reduced digraph
$\vec R = \vec R(\mathcal{P},\theta ;\delta ,\, \vec {\kern-2pt G},p)$
associated with
$\mathcal{P}$
has vertex set
$[k]$
and for every distinct pair
$(i,j)\in [k]^2$
we draw the arc
$\overrightarrow {ij}$
in
$\vec R$
if and only if
$\, \vec {\kern-2pt G}[V_i,V_j]$
is
$(\delta ,p)$
-regular and
$d_{\, \vec {\kern-2pt G},p}(V_i,V_j) \geq \theta$
.
Let us now define graphs of a certain type whose appearance in
$G$
implies the existence of many cycles in
$G$
, which, in turn, can be made to imply the existence of many copies of the orientations
$\, \vec{\kern-2pt C}_\ell$
of
$C_\ell$
that we are after in Lemma 5.3. Let
$J$
be a graph with a given vertex partition
$V(J)=\bigcup _{0\leq i\lt \ell }U_i$
, with
$|U_i|=u$
for every
$i$
. In what follows, the indices of the sets
$U_i$
will be considered modulo
$\ell$
. We further assume that
$E(J)=\bigcup _{0\leq i\lt \ell }E(U_{i-1},U_i)$
, that is, the edges of
$J$
connect vertices in consecutive sets
$U_i$
. Thus
$J$
has a ‘cyclic’ structure. Finally, assume that
$J[U_{i-1},U_i]$
is
$(\delta ,p)$
-regularFootnote
1
for every
$0\leq i\lt \ell$
and that
$d_p(U_{i-1},U_i)\geq \theta$
. We then say that
$J$
is a
$(C_{\ell },\theta ,\delta ,u,p)$
-regular system. A crucial fact is that ‘large’
$(C_{\ell },\theta ,\delta ,u,p)$
-regular systems that occur as subgraphs of random graphs contain many copies of
$C_\ell$
, as long as the involved parameters are appropriate. In order to state this more precisely, we denote by
$\iota _{\ell }(J)$
the number of transversalFootnote
2
copies of
$C_{\ell }$
in
$J$
. The following lemma is a straightforward consequence of Theorem 1.6 in [Reference Conlon, Gowers, Samotij and Schacht12].
Lemma A.2 (KŁR conjecture for cycles in random graphs: counting version). Let
$p=p(n)=\omega (n^{-1+1/(\ell -1)})$
where
$3\leq \ell \in {\mathbb N}$
. For any
$\theta \gt 0$
there are
$\zeta \gt 0$
and
$\delta \gt 0$
such that for any
$\mu \gt 0$
a.a.s.
${\mathbf G}\sim {\mathbf G}(n,p)$
has the following property. For every
$u\geq \mu n$
and every
$(C_{\ell },\theta ,\delta ,u,p)$
-regular system
$J \, \subset \, {\mathbf G}$
, we have that
$\iota _{\ell }(J) \geq \zeta \, (\mu p n)^{\ell }$
.
Now, we are able to prove Lemma 5.3, which we remind here for convenience. Given
$3\leq \ell \in {\mathbb N}$
and
$\epsilon \gt 0$
, we want to show that the following holds for
$p=\omega \big (n^{-1+1/(\ell -1)}\big )$
: there is
$\eta \gt 0$
such that for every
$\nu \gt 0$
a.a.s.
${\mathbf G}\sim {\mathbf G}(n,p)$
has the property that for every
$W\subseteq V({\mathbf G})$
with
$|W|\geq \nu n$
, every subgraph
$G\subseteq {\mathbf G}[W]$
with
\begin{equation} e(G)\geq \left (\pi (K_{2^{\ell -1}})+\varepsilon \right ) p\binom {|W|}2 \end{equation}
has the
$\big (C_\ell ,\eta (\nu pn\big )^\ell )$
-orientation property.
Proof of Lemma
5.3. Of course, we can assume that
$0\lt \varepsilon \lt 1$
. Given the parameters
$\ell \geq 3$
,
$\varepsilon \gt 0$
, and
$\nu \gt 0$
, and setting
$\varepsilon ' \, :\!= \, \frac {\varepsilon }{72}$
, we choose the parameters
$\theta = \theta (\varepsilon ) \, :\!= \, \varepsilon '$
and
$D = D(\varepsilon ) \, :\!= \, 1 + \varepsilon '$
. Applying Lemma A.2 we set
$\delta = \delta (\ell ,\varepsilon ) \, :\!= \, \min \{\delta _{A.2}(\ell ,\theta ) , \varepsilon ' \}$
and
$\zeta \, :\!= \,\zeta (\ell , \varepsilon ) \, :\!= \, \zeta _{A.2} (\ell ,\theta )$
. Applying Theorem A.1 for
$m = m(\ell ,\varepsilon ) \, :\!= \, \max {\{ N(\ell ,\varepsilon ),1/{\varepsilon }' \} }$
,Footnote
3
we set
$\xi = \xi (\ell ,\varepsilon ) \, :\!= \, \xi _{A.1}(\delta ,D,m)$
and
$M = M(\ell ,\varepsilon ) \, :\!= \, M_{A.1}(\delta ,D,m)$
. Now, we define the parameters
$\mu \, :\!= \, \frac {1-\delta }{M} \, \nu$
and
\begin{align*} \eta = \eta (\ell ,\varepsilon ) \, :\!= \, \zeta \, \left (\frac {1-\delta }{M} \right )^{\ell }. \end{align*}
Of course, this
$\eta$
was defined in order to be our desired parameter in Lemma 5.3.
Let
$p = \omega (n^{-1+1/(\ell -1)})$
. We fix any outcome of
$\mathbf G$
which satisfies the following properties. Set
$\mu ' \, :\!= \, \min \{ \xi , \mu \}$
.
-
(i) For each
$U \in \binom {n}{ \geq \mu ' n }$
we have that
\begin{align*} e_{{\mathbf G}}(U) = (1 \pm \varepsilon ') p |U|^2/2. \end{align*}
-
(ii) For every disjoint sets
$U,W \in \binom {n}{ \geq \mu ' n }$
we have that
\begin{align*} e_{{\mathbf G}}(U,W) = (1 \pm \varepsilon ') p |U||W|. \end{align*}
-
(iii) For every
$u\geq \mu n$
and every
$(C_{\ell },\theta ,\delta ,u,p)$
-regular system
$J\subseteq {\mathbf G}$
we have that
\begin{align*} \iota _{C_{\ell }}(J) \geq \zeta \, (\mu p n)^{\ell }. \end{align*}
Note that by Lemma 2.1 (
$1$
) and (
$3$
), and Lemma A.2 applied to these parameters (together with a simple union bound), we conclude that these properties (
$i$
), (
$ii$
), and
$(iii)$
a.a.s. occur. In view of this, the rest of the proof is deterministic (and we take
$n$
sufficiently large as necessary).
Thus, fix
$W \in \binom {V({\mathbf G})}{\geq \nu n}$
and
$G\subseteq {\mathbf G}[W]$
with
\begin{align*} e(G) \geq (\pi (\ell ) + \varepsilon ) p \binom {|W|}{2}. \end{align*}
where
$\pi (\ell ) \, :\!= \, \pi \left (K_{2^{\ell -1}}\right )$
. Our aim is to show that
$G$
has the
$(C_{\ell }, \eta (\nu pn)^{\ell })$
-property. Next, fix an arbitrary orientation of
$\, \vec {\kern-2pt G}$
and an acyclic orientation
$\vec C_{\ell }$
of
$C_{\ell }$
. We want to show that
$\, \vec {\kern-2pt G}$
contains at least
$\eta (\nu pn)^{\ell }$
copies of
$\vec C_{\ell }$
. Note that
$G$
is
$(\xi ,D,p)$
-upper uniform, more precisely
$G$
is
$(\mu ',D,p)$
-upper uniform because
$\mathbf G$
satisfies such property by (
$ii$
) and
$G\subseteq {\mathbf G}$
. Then, we apply Theorem A.1 (with our choice of parameters) to conclude that there exists a
$(\delta , \, \vec {\kern-2pt G},p)$
-regular partition
$\mathcal{W} = \{ W_0,W_1,\ldots ,W_k \}$
of
$W$
with
$k\in [m,M]$
. Now, let
$\vec R = \vec R(\mathcal{W},\theta ;\delta ,\, \vec {\kern-2pt G},p)$
be the reduced digraph associated with
$\mathcal{W}$
. Note that
$|W_i| \geq un$
for each
$i\in [k]$
, where
$u \, :\!= \, \frac {|W|-|W_0|}{k}$
. Clearly,
$u\geq \frac {(1-\delta )\nu n}{M} = \mu n$
.
The key observation is the following ‘transference’ claim.
Claim A.3 (Edge-density Inheritance). Let
$\, \vec {\kern-2pt G}$
and
$\vec R$
be as above. Then,
\begin{align} e(R) \geq (\pi (\ell ) + \varepsilon /2) \binom {k}{2}. \end{align}
In particular,
$R$
contains a copy of
$K_{2^{\ell -1}}$
.
Proof. First, note that the second part of the claim is a straightforward consequence of equation (17) together with the fact that
$k$
is large enough, specifically
$k \geq N(\ell ,\varepsilon )$
. Thus, in order to show equation (17), we proceed by contradiction. Suppose that
$e(R) \lt (\pi (\ell ) + \varepsilon /2) \binom {k}{2}$
and set
$\tilde {n} \, :\!= \, |W|$
. Then, since
$G$
is
$(\mu ,D,p)$
-upper uniform and
$\mu n \leq |W_i| \leq \tilde {n}/k$
for
$i\in [k]$
, we obtain that
\begin{align*} \sum _{ij\in R}{e_G(W_i,W_j)} & \leq \sum _{ij\in R}{(1+\varepsilon ')p|W_i||W_j|} \\[3pt] & \leq (1+\varepsilon ')p \tilde {n}^2/k^2 \times e(R) \\[3pt] & \lt (1+\varepsilon ')p \tilde {n}^2/k^2 \times (\pi (\ell ) + \varepsilon /2) k^2/2 \\[3pt] & \leq (\pi (\ell ) + \varepsilon /2 + 2 \varepsilon ') p\tilde {n}^2/2. \end{align*}
On the other hand,
\begin{align} \sum _{ij\notin R}{e(G[W_i,W_j])} & = \sum _{ij\in \binom {k}{2}}{(e_{\, \vec {\kern-2pt G}}(W_i,W_j) + e_{\, \vec {\kern-2pt G}}(W_j,W_i)) \unicode {x1D7D9}[{ij\notin R}}] \nonumber \\[3pt] & \leq \sum _{ij\in \binom {k}{2}}{e_{\, \vec {\kern-2pt G}}(W_i,W_j) \unicode {x1D7D9}[{\overrightarrow {ij} \notin \vec R }] + e_{\, \vec {\kern-2pt G}}(W_j,W_i) \unicode {x1D7D9}[{\overrightarrow {ji} \notin \vec R } }] \nonumber \\[3pt] & \leq \sum _{ij\in \binom {k}{2}}{e_{\, \vec {\kern-2pt G}}(W_i,W_j) \unicode {x1D7D9}[{d_{\, \vec {\kern-2pt G},p}(W_i,W_j) \lt \theta }] + e_{\, \vec {\kern-2pt G}}(W_j,W_i) \unicode {x1D7D9}[{d_{\, \vec {\kern-2pt G},p}(W_j,W_i) \lt \theta }}]\nonumber \\[3pt] & \quad + \sum _{ij\in \binom {k}{2}}{ e_{\, \vec {\kern-2pt G}}(W_i,W_j) \unicode {x1D7D9}[{\, \vec {\kern-2pt G}[W_i,W_j] \mbox{ is not $(\delta ,p)$-regular} }} ] \nonumber \\[3pt] & \quad + \quad e_{\, \vec {\kern-2pt G}}(W_j,W_i) \unicode {x1D7D9}[{ \, \vec {\kern-2pt G}[W_j,W_i] \mbox{ is not $(\delta ,p)$-regular} }] \nonumber \\[3pt] & \leq k^2 \theta p \tilde {n}^2/k^2 \nonumber \\[3pt] & \quad + 2 (1+\varepsilon ') p\tilde {n}^2/k^2 \sum _{ij\in \binom {k}{2}}{ \unicode {x1D7D9}[{\, \vec {\kern-2pt G}[W_i,W_j] \mbox{ or } \, \vec {\kern-2pt G}[W_j,W_i] \mbox{ is not $(\delta ,p)$-regular} } } ] \nonumber \\[3pt] & \leq \theta p\tilde {n}^2 + 2 (1+\varepsilon ') \delta p\tilde {n}^2 \leq (\theta + 4\delta ) p\tilde {n}^2\nonumber \\[3pt] & \leq 10 \varepsilon ' \frac {p\tilde {n}^2}{2}. \end{align}
So, summing both estimations, we get that
$e(G[\mathcal{W} \setminus \{W_0\}]) \leq (\pi (\ell ) + \varepsilon /2 + 12 \varepsilon ') p\tilde {n}^2/2$
. Finally, due to property (
$i$
) of
$\mathbf G$
, we conclude that
\begin{align*} e(G) & = e(G[\mathcal{W}\setminus \{W_0\}]) + \sum _{i=1}^{k}{e(G[W_i])} + ( e(G[W_0]) + e(G[W_0,W\setminus W_0]) ) \\[3pt] & \leq e(G[\mathcal{W}\setminus \{W_0\}]) + \sum _{i=1}^{k}{e({\mathbf G}[W_i])} + ( e({\mathbf G}[W_0]) + e({\mathbf G}[W_0,W\setminus W_0]) ) \\[3pt] & = e(G[\mathcal{W}\setminus \{W_0\}]) + \sum _{i=1}^{k}{e({\mathbf G}[W_i])} + (e({\mathbf G}[W]) - e({\mathbf G}[W-W_0]) )\\[3pt] & \leq (\pi (\ell ) + \varepsilon /2 + 12 \varepsilon ') \frac {p\tilde {n}^2}{2} + k (1+ \varepsilon ') \frac { p \tilde {n}^2}{2 k^2} + \left ((1+\varepsilon ') \frac {p \tilde {n}^2}{2} - (1-\varepsilon ') (1-\delta )^2 \frac { p \tilde {n}^2}{2} \right ) \\[-20pt] \end{align*}
\begin{align*} & \leq (\pi (\ell ) + \varepsilon /2 + 2/m + 16 \varepsilon ') \frac {p\tilde {n}^2}{2} \\[3pt] & \leq (\pi (\ell ) + \varepsilon /2 + 18 \varepsilon ' ) \frac {p\tilde {n}^2}{2} \\[3pt] & \leq (\pi (\ell ) + 3 \varepsilon /4) \frac {p\tilde {n}^2}{2}, \end{align*}
which is the desired contradiction.
By Claim A.3, we conclude that
$\vec R$
contains an orientation
$\vec K_{2^{\ell -1}}$
of
$K_{2^{\ell -1}}$
. Now we show that we can find a copy of any acyclic orientation of
$C_{\ell }$
in
$\vec K_{2^{\ell -1}}$
. To see this, it is enough to show that any orientation of
$K_{2^{\ell -1}}$
contains a transitive tournament with
$\ell$
vertices (denoted as
$TK_{\ell }$
), since all acyclic orientations of
$C_{\ell }$
lie inside
$TK_{\ell }$
. Indeed, we proceed by induction over
$\ell \geq 1$
. The base case
$\ell =1$
is trivial. Suppose that it holds for
$\ell -1$
, and pick a vertex in
$V(\vec K_{2^{\ell -1}})$
, say
$v$
. By the pigeonhole principle we can assume (w.l.o.g.) that
$|N^{\textrm {in}}(v)| \geq 2^{\ell -2}$
. Thus, by the induction hypothesis, one can find a copy of
$TK_{\ell -1}$
within
$N^{\textrm {in}}(v)$
. Then, by connecting this copy with the vertex
$v$
, we build the desired copy of
$TK_{\ell }$
.
Note that such
$\vec C_{\ell }$
in
$\vec R$
define (by lifting) a
$(C_{\ell }, \theta , \delta ,u,p)$
-regular system
$J \subseteq {\mathbf G}$
with a natural orientation
$\vec J \subseteq \, \vec {\kern-2pt G}$
of
$J$
which obeys the behaviour of
$\vec C_{\ell }$
.
Finally, by property (
$iii$
), we conclude that
\begin{align*} \iota _{C_{\ell }}(J) \geq \zeta (\mu p n)^{\ell } = \frac {\zeta (1-\delta )^\ell \nu ^{\ell }}{M^\ell } (pn)^{\ell } = \eta (\nu pn)^{\ell }. \end{align*}
Therefore, since each transversal
$\ell$
-cycle in
$J$
induces a copy of
$\vec C_{\ell }$
in
$\vec J \subseteq \, \vec {\kern-2pt G}$
, the proof is complete.
C6
