# On the restricted size Ramsey number
for a pair of cycles

Tomasz Łuczak  Adam Mickiewicz University
Faculty of Mathematics and Computer Science
Umultowska 87, 61-614 Poznań, Poland<EMAIL_ADDRESS>,  Joanna Polcyn  Adam
Mickiewicz University
Faculty of Mathematics and Computer Science
Umultowska 87, 61-614 Poznań, Poland<EMAIL_ADDRESS>and  Zahra Rahimi
Institute for Research in Fundamental Sciences (IPM)
School of Mathematics
P.O. Box: 19395- 5746
Tehran, Iran<EMAIL_ADDRESS>
###### Abstract.

For graphs $H_{1},H_{2}$ by $r^{*}(H_{1},H_{2})$ we denote the minimum number
of edges in a graph $G$ on $r(H_{1},H_{2})$ vertices such that
$G\to(H_{1},H_{2})$. We show that for each pair of natural numbers $k,n$,
$k\leq n$, where $k$ is odd and $n$ is large enough, we have

$r^{*}(C_{n},C_{k})=\lceil(n+1)(2n-1)/2\rceil\,.$

###### Key words and phrases:

Ramsey number, cycles

###### 2010 Mathematics Subject Classification:

Primary: 05D10, secondary: 05C38, 05C55.

The last author was supported in part by a grant from IPM (No.1401050039) and
by insf (N0. 99013670)

##  1\. Introduction

In the paper we use the standard arrow notation and write
$G\to(H_{1},H_{2},\dots,H_{r})$ if any coloring of the edges of a graph $G$
with $r$ colors leads to a copy of $H_{i}$ in the $i$th color for some
$i=1,2,\dots,r$. Let us recall that the Ramsey number
$r(H_{1},H_{2},\dots,H_{r})$ is the minimum number of vertices in graph $G$
such that $G\to(H_{1},H_{2},\dots,H_{r})$, while the size Ramsey number
$\hat{r}(H_{1},H_{2},\dots,H_{r})$ is the minimum number of edges in a graph
$G$ with such a property. In general Ramsey numbers are hard to find, yet it
have been computed, or estimated, for some simple families of graphs. In
particular, $r(H_{1},H_{2})$ is known for $H_{1},H_{2}$ which are either paths
or cycles (see Gerencsér, Gyárfás [GG], Rosta [R], Faudree, Schelp [FS], or
Radziszowski [Ra] for a survey of results on Ramsey Theory). The size Ramsey
number for paths and cycles are not so well understood. In the fundamental
paper on this subject Beck [B] proved that $\hat{r}(P_{n},P_{n})=O(n)$. The
exact value of the hidden constant is not known and finding it seems to be
hard. The best estimates we have got so far are those by Bal, DeBiasio [BD],
and Dudek, Prałat [DP]

$(3.75-o(1))n\leq\hat{r}(P_{n},P_{n})\leq 74n\,.$

The size Ramsey number for cycles was studied by Haxell, Kohayakawa, and
Łuczak [HKL] who proved that $\hat{r}(C_{n},C_{n})\leq An$ for some huge
constant $A$. The value of the constant $A$ has been substantially improved by
Javadi, Khoeini, Omidi, and Pokrovskiy [JKOP], and then by Javadi and Miralaei
[JM]; both of the above papers also considered the case of more than one
color. However, finding the exact value of the limit $\hat{r}(C_{n},C_{k})/n$
(or even prove that it exists) seems to be out of reach right now.

In this paper we study yet another version of Ramsey number. By the restricted
size Ramsey number $r^{*}(H_{1},H_{2},\dots,H_{r})$ we denote the minimum
number of edges in a graph $G$ on $r(H_{1},H_{2},\dots,H_{r})$ vertices such
that $G\to(H_{1},H_{2},\dots,H_{r})$. Although this notion has been around for
quite some time (see Faudree and Schelp [FS]) there are rather few results on
the restricted Ramsey number in the literature. The goal of this note is to
find the exact value of $r^{*}(C_{n},C_{k})$ where $k$ is odd and $n$ is
large. Note that for such choice of $k$ and $n$, $r(C_{n},C_{k})=2n-1$ and one
of the colorings used to show the lower bound is when we divide $K_{2n-2}$
into two equal parts and color all edges between them in the second color.

######  Theorem 1.1.

There exists a constant $n_{0}$ such that for every $n\geq n_{0}$ and any odd
$k$, with $3\leq k\leq n$, we have

$r^{*}(C_{n},C_{k})=\lceil(n+1)(2n-1)/2\rceil\,.$

The structure of the paper is the following. In the next section we derive
Theorem 1.1 from two Lemmata 2.1 and 2.2 on colorings of a pseudorandom graph
$\tilde{G}_{n}$. A precise definition of $\tilde{G}_{n}$, and the way one can
construct it, is given in Section 3, while the proofs of Lemmata 2.1 and 2.2
can be found in Sections 4 and 5 respectively.

We conclude this part of the paper with some remarks and comments. Note that
calculating $r^{*}(C_{n},C_{n})$, in a way, supplements results related to
Shelp’s problem who asked about the minimum $a$ so that every graph $G$ on
$N=r(C_{n},C_{n})$ vertices and the minimum degree $aN$ has the property
$G\to(C_{n},C_{n})$ (see Benevides et al. [Ben] for the solution of Shelp’s
problem, and Łuczak and Rahimi [LZ1, LZ2] for the case of three colors).

Finding $r^{*}(H_{\ell},H_{\ell})$ can be also viewed as a special case of the
following question: given a graph $H_{\ell}$ on $n$ vertices, and a function
$k=k(\ell)$, what is the minimum number of edges in a graph $G$ on
$r(H_{\ell},H_{\ell})+k$ vertices such that $G\to(H_{\ell},H_{\ell})$?
Although in this formulation this problem looks slightly artificial, a moment
of reflection reveals that it could be (and usually is) related to the
following question on random graphs: what is the largest $\ell$ so that with
probability $1-o(1)$ each coloring of the edges of the random graph $G(n,p)$
with two colors leads to a monochromatic copy of $H_{\ell}$? As far as we know
this problem was first addressed and solved for paths by Letzter [Let] when
$p=p(n)=\Theta(1/n)$, whereas for cycles and all range of $p=p(n)$ it was
treated in the recent paper of Araújo et al. [A].

Finally, one can ask about the value of $r^{*}(C_{n},C_{k})$ when $k\leq n$ is
an even number. This question seems to be particularly interesting when $k$ is
much smaller than $n$. For instance, in the simplest case when $k=4$, we have
$r(C_{n},C_{4})=n+1$ and so one can expect that
$r^{*}(C_{n},C_{4})=n^{1/2+o(1)}$, but at this moment the lower and upper
bounds for $r^{*}(C_{n},C_{4})$ we can prove are both far from the conjectured
$n^{1/2+o(1)}$.

##  2\. Proof of Theorem 1.1

Here we describe how to show Theorem 1.1 using two Lemmata 2.1 and 2.2 proofs
of which we postpone until the following sections of the article. As we
shortly see the lower bound for $r^{*}(C_{n},C_{k})$ is quite simple to
obtain, so the main part of the proof is to find a graph $\tilde{G}_{n}$ with
$r(C_{n},C_{k})$ vertices and $r^{*}(C_{n},C_{k})$ edges, and verify that any
coloring of edges of $\tilde{G}_{n}$ leads to either $C_{n}$ in the first
color, or $C_{k}$ in the other color.

For $\tilde{G}_{n}$ we take a pseudorandom $(n+1)$-regular (or almost
$(n+1)$-regular, if $n$ is even) graph on $2n-1$ vertices which we call
$n$-fit; in the following Section 3 we give a precise definition of $n$-fit
graphs and describe how to construct them. Our argument consists of two parts.
Firstly, we use the Regularity Lemma to verify that any coloring of
$\tilde{G}_{n}$ without monochromatic $C_{n}$ and $C_{k}$ in the appropriate
colors resembles the extremal coloring of $K_{2n-2}$ which avoids such $C_{n}$
and $C_{k}$, i.e. it contains a large induced bipartite subgraph in one of the
colors. Our result, proved in Section 4, can be stated as follows.

######  Lemma 2.1.

There exists $n_{1}$ such that for every $n\geq n_{1}$ the following holds. If
$k\leq n$ is odd and the edges of an $n$-fit graph $\tilde{G}_{n}$ are colored
with two colors so that there are no copies of $C_{n}$ in the first color and
no copies of $C_{k}$ in the second color, then there exists two disjoint
subsets of vertices of $\tilde{G}_{n}$, $V^{\prime}$ and $V^{\prime\prime}$,
$|V^{\prime}|,|V^{\prime\prime}|\geq 0.99n$, such that all edges between
$V^{\prime}$ and $V^{\prime\prime}$ are of the same color.

Then we supplement the above with the following result proved in Section 5.

######  Lemma 2.2.

There exists $n_{2}$ such that for every $n\geq n_{2}$ the following holds.
Let us suppose that the edges of an $n$-fit graph $\tilde{G}_{n}$ are colored
with two colors so that there exists two disjoint subsets of vertices
$\tilde{G}_{n}$, $V^{\prime}$ and $V^{\prime\prime}$,
$|V^{\prime}|,|V^{\prime\prime}|\geq 0.99n$, such that all edges between
$V^{\prime}$ and $V^{\prime\prime}$ are of the same color. Then the subgraph
induced by one of the colors contains a copy of cycle $C_{\ell}$ for each
$3\leq\ell\leq n$.

Now we are ready to complete the proof of Theorem 1.1.

###### Proof of Theorem 1.1.

Clearly, for $n\geq\max\\{n_{1},n_{2}\\}$ we must have
$\tilde{G}_{n}\to(C_{n},C_{k})$ since otherwise Lemmata 2.1 and 2.2 lead to a
contradiction. Hence $r^{*}(C_{n},C_{k})\leq\lceil(n+1)(2n-1)/2\rceil$.

Moreover, each graph $G=(V,E)$ such that $|V|=r(C_{n},C_{k})=2n-1$ and
$|E|<\lceil(n+1)(2n-1)/2\rceil$, contains a vertex $v$ of degree at most $n$.
Let $V^{\prime}\subseteq V$ be a set of $n-1$ vertices which contains all,
except at most one, neighbors of $v$, and $V^{\prime\prime}=V\setminus
V^{\prime}$. Now color all edges between $V^{\prime}$ and $V^{\prime\prime}$
with the second color and all other edges by the first color. Then, there are
no $C_{n}$ with edges colored in the first color and no odd cycles with edges
colored in the second color. ∎

##  3\. $n$-fit graphs

Our proofs of Lemmata 2.1 and 2.2 rely on the fact that in the graph
$\tilde{G}_{n}$ we are to color the edges are ‘uniformly’ distributed. The
following definition makes it precise. Here, for two sets of vertices $S$ and
$T$ of a graph $G=(V,E)$, we put

$e(S,T)=|\\{(v,w):v\in S,w\in T,\\{v,w\\}\in E\\}|,$

i.e. $e(S,T)$ denote the number of edges with one end in $S$, the second in
$T$, where all edges contained in $S\cap T$ are counted twice. Moreover, by
$N_{G}(v)=N(v)$ we denote all neighbors of the vertex $v$ in $G$.

######  Definition 3.1.

A graph $G=(V,E)$ is called $\mathbf{n}$-fit if the following holds:

  1. ( )

$|V|=2n-1$ and $|E|=\lceil(n+1)(2n-1)/2\rceil$;

  2. ( )

the minimum degree of $G$ is $n+1$ (i.e. $G$ is $(n+1)$-regular if $n$ is odd
and it has $2n-2$ vertices of degree $n+1$ and one of degree $n+2$ if $n$ is
even);

  3. ( )

for all $v,w\in V$, $v\neq w$, we have

$\big{|}|N(v)\cap N(w)|-n/2\big{|}\leq n^{0.7};$

  4. ( )

for all $S,T\subseteq V$ we have

$\big{|}e(S,T)-|S||T|/2\big{|}\leq n^{1.7}.$

The main result of this section states that for every $n$ large enough one can
find an $n$-fit graph.

######  Lemma 3.2.

There exists $n_{0}$ such that $n$-fit graphs exist for each $n\geq n_{0}$.

###### Proof.

Although it is expected that a random graph with a degree sequence as
described in ( ) ‣ 3.1 and ( ) ‣ 3.1 fulfills also conditions ( ) ‣ 3.1 and (
) ‣ 3.1, instead of employing somewhat complicated formula for the number of
graphs with a given degree sequence found by Liebenau and Wierman [LW], we use
the standard binomial model of random graph, which, due to the independence of
edges, is much easier to deal with.

Consider the random graph $\mathcal{G}_{2n-1}$ which is chosen at random from
all graphs with $2n-1$ vertices, or, equivalently, a graph with vertex set
$[2n-1]=\\{1,2,\dots,2n-1\\}$ in which each edge appears independently with
probability $1/2$. It is easy to verify using Chernoff bounds that for $n$
large enough with positive probability (in fact with probability $1-o(1)$) the
graph $\mathcal{G}_{2n-1}$ has the following properties:

  1. ( )

for every vertex $v$ we have

$\big{|}\deg(v)-n\big{|}\leq n^{0.6};$

  2. ( )

for every pair of vertices $v$, $w$

$\big{|}|N(v)\cap N(w)|-n/2\big{|}\leq n^{0.6};$

  3. ( )

for every two subsets of vertices $S,T$

$\big{|}e(S,T)-|S||T|/2\big{|}\leq n^{1.6}.$

Thus, let $\hat{G}=([2n-1],\hat{E})$ be a graph for which ( ) ‣ 3, ( ) ‣ 3,
and ( ) ‣ 3 hold. Clearly, it has also properties ( ) ‣ 3.1 and ( ) ‣ 3.1 with
a large margin. In order to adjust its degree sequence we modify slightly the
edge set of $\hat{G}$ and show that there exists sets
$E_{1},E_{2}\subseteq[2n-1]^{(2)}$ such that the graph
$\tilde{G}_{n}=([2n-1],(\hat{E}\setminus E_{1})\cup E_{2})$ has all vertices
of degree $n+1$, except, perhaps one of degree $n+2$, and furthermore the
maximum degree of the graph $G_{1}=([2n-1],E_{1}\cup E_{2})$ is smaller than
$136n^{0.6}$, so ( ) ‣ 3.1 and ( ) ‣ 3.1 hold and the graph $\tilde{G}_{n}$ is
$n$-fit.

Let us first delete from $\hat{G}=([2n-1],\hat{E})$ some edges so that the
resulting graph has maximum degree $n+1$. We do it recursively examining all
vertices of $\hat{G}$ one by one. For each vertex $v$ we need to delete not
more than $\deg(v)-(n+1)$ surplus edges incident to $v$ which connect $v$ to
those of its neighbors whose degrees changed the least during the procedure.
Note that from ( ) ‣ 3 it follows that in the whole process we remove
$|E^{\prime}_{1}|\leq 2n^{1.6}$ edges. We want to argue, by a direct recursive
argument, that a graph $([2n-1],E^{\prime}_{1})$ has maximum degree at most
$7n^{0.6}$. To this end note that because of $|E^{\prime}_{1}|\leq 2n^{1.6}$,
in each stage at most $2n/3$ vertices has more than $6n^{0.6}$ incident edges
deleted. Thus, since by ( ) ‣ 3 and the recursive assumption in each step of
the process the vertex $v$ has at least $n-n^{0.6}-7n^{0.6}>2n/3+n^{0.6}$
neighbors in $\hat{G}$, we never delete any edge which join $v$ to its
neighbor who already lost at least $6n^{0.6}$ edges incident to it. Because we
remove at most $n^{0.6}$ edges incident to $v$, its degree in
$([2n-1],E^{\prime}_{1})$ is at most $7n^{0.6}$.

Now we need to add edges to $\hat{G}=([2n-1],\hat{E}\setminus E^{\prime}_{1})$
so that the resulting graph has the correct degree sequence. Note that by ( )
‣ 3 and the estimate for $E^{\prime}_{1}$ we need to add to it
$|E^{\prime\prime}|\leq 4n^{1.6}$ edges. In fact we add to it $E_{2}$,
$E_{2}=2|E^{\prime\prime}|$, edges and delete another $E^{\prime\prime}_{1}$,
$|E^{\prime\prime}_{1}|=|E^{\prime\prime}|$, edges recursively in the
following way. Let us suppose that two vertices, $v^{\prime}$ and
$v^{\prime\prime}$ have degree smaller than required. We find two other
vertices, $w^{\prime}$ and $w^{\prime\prime}$, such that $w^{\prime}$ is not
incident to $v^{\prime}$, $w^{\prime\prime}$ is not incident to
$v^{\prime\prime}$, but $w^{\prime}$ and $w^{\prime\prime}$ are connected by
an edge. Then we delete from the graph an edge $w^{\prime}w^{\prime\prime}$
(and put it in the set $E^{\prime\prime}_{1}$) and add to the graph (and to
the set $E_{2}$) edges $v^{\prime}w^{\prime}$ and
$v^{\prime\prime}w^{\prime\prime}$. In order to assure that the graph
$\hat{G}=([2n-1],E^{\prime\prime}_{1}\cup E_{2})$ has small maximum degree for
each pair of vertices $v^{\prime}$ and $v^{\prime\prime}$ we select
$w^{\prime}$ and $w^{\prime\prime}$ in the following way. We first choose a
set $W^{\prime}$ of $n/10$ non-neighbors of $v^{\prime}$ which are neighbors
of $v^{\prime\prime}$ and which have smallest degree in currently generated
part of $\hat{G}=([2n-1],E^{\prime\prime}_{1}\cup E_{2})$. In a similar way
$W^{\prime\prime}\subseteq V\setminus W^{\prime}$ is the set of $n/10$
vertices of smallest degree, counted in currently generated part of
$\hat{G}=([2n-1],E^{\prime\prime}_{1}\cup E_{2})$, in the set
$N(v^{\prime})\setminus N(v^{\prime\prime})$.

$v^{\prime}$$v^{\prime\prime}$$w^{\prime}$$w^{\prime\prime}$$W^{\prime}$$W^{\prime\prime}$
Figure 3.1. The switching procedure.

Note that because of $|E^{\prime\prime}_{1}\cup E_{2}|\leq 12n^{1.6}$, the
graph $\hat{G}$ contains at most $n/5$ vertices of degree larger than
$120n^{0.6}$ and since both sets $N(v^{\prime})\setminus N(v^{\prime\prime})$
and $N(v^{\prime\prime})\setminus N(v^{\prime})$ have at least
$n/2-O(n^{0.6})\geq n/3$ vertices in the above procedure none of the sets
$W^{\prime}$ and $W^{\prime\prime}$ contains a vertex whose degree has been
changed more than $120n^{0.6}$ times. Moreover, by ( ) ‣ 3, between sets
$W^{\prime}$ and $W^{\prime\prime}$ there exist at least
$|W^{\prime}||W^{\prime\prime}|/2-O(n^{1.6})=\Theta(n^{2})$ edges, so we can
always choose two adjacent vertices $w^{\prime}$ and $w^{\prime\prime}$ from
these two sets. Hence, since by ( ) ‣ 3 and the first part of the proof all
vertices of $\hat{G}=([2n-1],\hat{E}\setminus E^{\prime}_{1})$ have degree at
least $n-8n^{0.6}$, the maximum degree of
$\hat{G}=([2n-1],E^{\prime\prime}_{1}\cup E_{2})$ is bounded from above by
$128n^{0.6}+1$.

Thus, we have shown that the maximum degree of $([2n-1],E^{\prime}_{1}\cup
E^{\prime\prime}_{1}\cup E_{2})$ is bounded from above by $136n^{0.6}$. Hence
from ( ) ‣ 3 it follows that for any two vertices $v$ and $w$ in
$\tilde{G}_{n}=([2n-1],(\hat{E}\setminus(E^{\prime}_{1}\cup
E^{\prime\prime}_{1}))\cup E_{2})$ we have

$\big{|}|N(v)\cap N(w)|-n/2\big{|}\leq n^{0.6}+272n^{0.6}\leq n^{0.7},$

and, by ( ) ‣ 3, for any two sets $S$ and $T$ of vertices of $\tilde{G}_{n}$

$\big{|}e(S,T)-|S||T|/2\big{|}\leq n^{1.6}+136n^{0.6}\max\\{|S|,|T|\\}\leq
n^{1.7}.\qed$

##  4\. Proof of Lemma 2.1

The main tool in the proof of Lemma 2.1 is the Regularity Lemma so we start
with recalling some definitions and basic facts (for a survey of results
concerning the Regularity Lemma see Komlós and Simonovits [KS]).

Let $G=(V,E)$ be a graph and let $V_{1},V_{2}\subseteq V$ be a pair of
disjoint subsets of vertices of $G$. The _density_ of $(V_{1},V_{2})$ is
defined as

$d(V_{1},V_{2})=\frac{e(V_{1},V_{2})}{|V_{1}||V_{2}|}\,.$

We say that a pair $(V_{1},V_{2})$ is _$\varepsilon$ -regular_ for some
$\varepsilon>0$ if for every pair of subsets $W_{1}\subseteq V_{1}$ and
$W_{2}\subseteq V_{2}$ such that $|W_{1}|\geq\varepsilon|V_{1}|$ and
$|W_{2}|\geq\varepsilon|V_{2}|$ we have

$|d(V_{1},V_{2})-d(W_{1},W_{2})|\leq\varepsilon\,.$

We call an $\varepsilon$-regular pair $(V_{1},V_{2})$ _strongly
$\varepsilon$-regular_ if every vertex $v_{1}\in V_{1}$ has at least
$d(V_{1},V_{2})|V_{2}|/10$ neighbors in $V_{2}$, and every vertex $v_{2}\in
V_{2}$ has at least $d(V_{1},V_{2})|V_{1}|/10$ neighbors in $V_{1}$.

The next result states some elementary results on regular pairs.

######  Fact 4.1.

For every $0<\varepsilon<d/100$ there exists $n^{\prime}$ such that for every
subsets $V_{1}$, $V_{2}$ of vertices of $G=(V,E)$ such that
$|V_{1}|,|V_{2}|\geq n^{\prime}$ the following holds.

  1. ( )

For each $\varepsilon$-regular pair $(V_{1},V_{2})$ of density $d$ there are
sets $W_{1}\subseteq V_{1}$, $|W_{1}|\geq(1-2\varepsilon)|V_{1}|$,
$W_{2}\subseteq V_{2}$, $|W_{2}|\geq(1-2\varepsilon)|V_{2}|$, such that the
pair $(W_{1},W_{2})$ is strongly $\varepsilon$-regular.

  2. ( )

If $(V_{1},V_{2})$ is a strongly $\varepsilon$-regular pair and $v_{1}\in
V_{1}$, $v_{2}\in V_{2}$ then for every odd $k$ such that

$3\leq k\leq 2(1-2\varepsilon/d)\min\\{|V_{1}|,|V_{2}|\\}$

there exists a path of length $k$ which starts at $v_{1}$ and ends in $v_{2}$.

###### Proof.

Both parts of the above results are well known and direct consequence of the
definition. Thus, part ( ) ‣ 4.1 is obtained by removing vertices of small
degree from both sets of $\varepsilon$-regular pairs. A path required in ( ) ‣
4.1 can be built greedily, when in each step we choose a vertex which has a
lot of neighbors among vertices which do not belong to the part of the path we
generated so far. ∎

Finally, let us define an $\varepsilon$-regular partition of a graph $G=(V,E)$
to be a partition of vertices of $G$ into $s$ parts $V=W_{1}\cup
W_{2}\cup\dots\cup W_{s}$ so that

  1. ( )

$\big{|}|W_{i}|-|W_{j}|\big{|}\leq 1$, for all $1\leq i<j\leq s$;

  2. ( )

among $\binom{s}{2}$ pairs $(W_{i},W_{j})$ all but at most $\varepsilon
s^{2}/2$ are $\varepsilon$-regular.

Our argument is based on the following version of the well known Szemerédi’s
Regularity Lemma.

######  Lemma 4.2.

For every $\varepsilon>0$ there exists $S$ with the following property. For
every graph $G=(V,E)$ whose edges were colored with two colors, i.e.
$E={\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}R}\cup{\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}B}$,
there is a partition $V=W_{1}\cup W_{2}\cup\dots\cup W_{s}$ of vertices of $G$
into $s$ parts, where $1/\varepsilon\leq s\leq S$, which is
$\varepsilon$-regular for both graphs
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}G_{R}}=(V,{\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}R})$
and
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}G_{B}}=(V,{\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}B})$.

The main motivation of using the Regularity Lemma for studying the Ramsey
numbers of sparse structures such as cycles is based on the following simple
observation due to Łuczak [L]. Let us suppose that we apply Lemma 4.2 to a
graph with some $\varepsilon>0$. We construct a (2-colored)
$\varepsilon$-reduced graph $\mathbf{G}_{s}^{\varepsilon}$ by replacing each
subset $W_{i}$ by a single vertex $\mathbf{w}_{i}$, and if a pair
$(W_{i},W_{j})$ is $\varepsilon$-regular in both colors we color the edge
$\mathbf{w}_{i}\mathbf{w}_{j}$ with the color which appear more frequently
among edges joining these sets (in case of a draw we can choose any of the
colors, say, the first one). In such a way we obtain a 2-coloring of edges of
a graph $K_{s}^{\varepsilon}$ obtained from the complete graph from which we
removed not more than $\varepsilon s^{2}$ edges. Note that if $G$ is $n$-fit
and the edge $\mathbf{w}_{i}\mathbf{w}_{j}$ of $\mathbf{G}_{s}^{\varepsilon}$
is colored with some color, the density of the pair $(W_{i},W_{j})$ in
$\tilde{G}_{n}$ in this color is at least $1/5$. It turns out that, instead of
looking for a long monochromatic cycle in $G$, it is enough to find large
matching contained in one monochromatic component in the auxiliary graph
$\mathbf{G}_{s}^{\varepsilon}$.

In order to make this statement precise, we say that a graph has property
$M_{t}$ if there exists a matching saturating $\lceil t\rceil$ vertices which
is contained in one non-bipartite component of this graph. It is well known
(see Łuczak [L] and Figaj and Łuczak [FL1, FL2]) that if a graph induced by
one of the colors of 2-colored $\varepsilon$-reduced graph
$\mathbf{G}_{s}^{\varepsilon}$ has property $M_{t}$, then $G$ contains cycles
in this color for every length from $3s$ to $(t/s-12\varepsilon)2n$. Here we
need a slightly stronger statement.

######  Lemma 4.3.

Let us suppose that an $n$-fit graph $\tilde{G}_{n}=(V,E)$ is colored with two
colors, red and blue, and $\mathbf{G}_{s}^{\varepsilon}$ is an
$\varepsilon$-reduced graph for this coloring for some $\varepsilon$, where
$0<\varepsilon<10^{-5}$. Then, for any constant $a$, $0<a<1$, the following
holds. If the subgraph induced in $\mathbf{G}_{s}^{\varepsilon}$ by one of the
colors, say blue, has property $M_{as}$, then there exists a set $W\subseteq
V$ such that $|W|\geq(a-2\varepsilon)2n$ and for every two vertices
$w,w^{\prime}\in W$ and each $\ell$, $3s\leq\ell\leq(a-12\varepsilon)2n$,
there exists a monochromatic path of length $\ell$ joining $w,w^{\prime}$.

###### Sketch of the proof of Lemma 4.3.

The proof follows closely the argument presented in [L, FL1, FL2] so we just
outline it omitting technical details. Consider a blue component of
$\mathbf{G}_{s}^{\varepsilon}$ which contains a matching
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}\mathbf{M}}$
saturating $\lceil as\rceil$ vertices. Let
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}\mathbf{U}}$
be a unicyclic blue subgraph which contains an odd cycle and all edges of
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}\mathbf{M}}$.
It is easy to see that then there exists a closed walk
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}\mathbf{L}}$
which goes through every edge of
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}\mathbf{U}}$
twice. Thus, for every two vertices $\mathbf{w}^{\prime}$,
$\mathbf{w}^{\prime\prime}$ of
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}\mathbf{U}}$
there exists two walks
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}\mathbf{L}_{e}(\mathbf{w}^{\prime},\mathbf{w}^{\prime\prime})},\,{\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}\mathbf{L}_{o}(\mathbf{w}^{\prime},\mathbf{w}^{\prime\prime})}\subseteq{\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}\mathbf{L}}$,
of even and odd lengths respectively, which start at $\mathbf{w}^{\prime}$,
end in $\mathbf{w}^{\prime\prime}$ and contain each edge of
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}\mathbf{M}}$.
Note that none of these walks is longer than $2s$.

Now take all pairs $(W_{t},W_{u})$ which correspond to the edges in the
matching
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}\mathbf{M}}$
and delete from each of them some vertices in order to make them strongly
$\varepsilon$-regular. The union of all sets which belong to these pairs is
our set $W$. Note that, by Fact 4.1( ) ‣ 4.1, $|W|\geq(a-2\varepsilon)2n$.

Next, let us choose $\ell$, $3s\leq\ell\leq(a-12\varepsilon)2n$, and take any
two vertices $v_{i},v_{j}\in W$ such that $v_{i}\in W_{i}$ and $v_{j}\in
W_{j}$. Then there exists in $\mathbf{G}_{s}^{\varepsilon}$ a blue walk
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}\mathbf{L}(\mathbf{w}_{i},\mathbf{w}_{j})}$
of length at most $2s$ and of the same parity as $\ell$ from $\mathbf{w}_{i}$
to $\mathbf{w}_{j}$ which traverses all the edges from the matching
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}\mathbf{M}}$.
Now ‘lift’ this walk to a blue path
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}P}$ in
$\tilde{G}_{n}$ of length at most $2s+4\leq 3s$ which joins $v_{i}$ and
$v_{j}$ and uses at least one edge from each pair $(W_{t},W_{u})$ which
corresponds to an edge of the matching
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}\mathbf{M}}$.
A slight increase in the length is caused by the fact that the ends of the
path
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}P}$,
vertices $v_{i}$ and $v_{j}$, could have few or no neighbors outside the
strongly $\varepsilon$-regular pairs they belong to; for instance $v_{i}\in
W_{i}$ could have no neighbors outside the strongly regular pair
$(W_{i},W_{k})$. In this case we need to start the path
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}P}$
with vertices $v_{i}u_{1}u_{2}$, where $u_{1}\in W_{k}$, $u_{2}\in W_{i}$,
where $u_{2}$ has a lot of neighbors in the next set which correspond to the
second vertex of the walk
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}\mathbf{L}(\mathbf{w}_{i},\mathbf{w}_{j})}$.
Once we have such a path
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}P}$ we
can increase its length by replacing each edge contained in a strongly
$\varepsilon$-regular pairs by an odd path of required length (see Fact 4.1( )
‣ 4.1). ∎

Note that the above results allow us to study properties of colorings of
$K_{s}^{\varepsilon}$ instead of colorings of an $n$-fit graph
$\tilde{G}_{n}$. Thus, we show that if a coloring of $\tilde{G}_{n}$ avoids
monochromatic cycles of required length (which means that in
$\mathbf{G}_{s}^{\varepsilon}$ monochromatic graphs either have no property
$M_{t}$ or contain no triangles), then in $\mathbf{G}_{s}^{\varepsilon}$ there
exists a large monochromatic bipartite component (see Lemmata 4.6 and 4.7
below). In the final step of the proof, we ‘lift’ a part of this component to
a large monochromatic bipartite graph in $\tilde{G}_{n}$.

We start with a few observations on a graph $K_{s}^{\varepsilon}$ which, let
us recall, is obtain from the complete graph $K_{s}$ by removing at most
$\varepsilon s^{2}$ edges.

######  Fact 4.4.

All but at most $\sqrt{\varepsilon}s$ vertices of $K_{s}^{\varepsilon}$ have
at least $(1-2\sqrt{\varepsilon})s$ neighbors.

###### Proof.

Indeed, otherwise the number of ‘missing’ edges would be larger than

$(\sqrt{\varepsilon}s)\cdot(2\sqrt{\varepsilon}s)/2=\varepsilon s^{2},$

contradicting the definition of $K_{s}^{\varepsilon}$. ∎

######  Fact 4.5.

Let $\varepsilon>0$, $s\geq 1/\sqrt{\varepsilon}$, and let $W\subseteq V$,
$|W|\geq 11\sqrt{\varepsilon}s$, be any set of vertices of
$K_{s}^{\varepsilon}$. Then there exists $\widetilde{W}\subseteq W$,
$|\widetilde{W}|\geq|W|-2\sqrt{\varepsilon}s$, such that the graph
$K_{s}^{\varepsilon}[\widetilde{W}]$ spanned by $\widetilde{W}$ in
$K_{s}^{\varepsilon}$ is hamiltonian and contains a triangle (and so it is a
non-bipartite connected graph with a perfect matching).

###### Proof.

We let $\widetilde{W}$ to be a set of vertices of $V(K_{s}^{\varepsilon})$
obtained from $W$ by removing all vertices with degree in
$K_{s}^{\varepsilon}$ less than $(1-2\sqrt{\varepsilon})s$ plus, perhaps, one
vertex more so that $|\widetilde{W}|$ is even. Then, from Fact 4.4, we get

$|\widetilde{W}|\geq|W|-\sqrt{\varepsilon}s-1\geq 9\sqrt{\varepsilon}s,$

and

$\delta(K_{s}^{\varepsilon}[\widetilde{W}])\geq|\widetilde{W}|-4\sqrt{\varepsilon}s>|\widetilde{W}|/2.$

Hence, from Dirac’s Theorem, $K_{s}^{\varepsilon}[\widetilde{W}]$ is
hamiltonian and the above condition also clearly implies that it contains a
triangle. ∎

Now we can state and prove two main results concerning the coloring of
$K_{s}^{\varepsilon}$.

######  Lemma 4.6.

For every positive real $\varepsilon\leq 10^{-5}$ and integer $s\geq
1/\sqrt{\varepsilon}$ the following holds. If the edges of
$K_{s}^{\varepsilon}$ are partitioned into two graphs
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}B}$ and
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}R}$ in
such a way that $R$ does not have property
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}M_{(1/2+13\varepsilon)s}}$
and
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}K_{3}}\not\subseteq{\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}B}$,
then
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}B}$
contains an induced bipartite subgraph with a bipartition $({W_{1}},{W_{2}})$,
such that $|{W_{1}}|,|{W_{2}}|\geq(1/2-13\sqrt{\varepsilon})s$.

###### Proof.

Since
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}K_{3}}\not\subseteq{\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}B}$,
from Fact 4.5 it follows that
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}R}$
contains no independent sets on $11\sqrt{\varepsilon}s$ vertices.
Consequently, none of components of
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}R}$
with more than $22\sqrt{\varepsilon}s$ vertices is bipartite. Hence, our
assumption that the red graph
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}R}$
does not have property
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}M_{(1/2+13\varepsilon)s}}$
implies that
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}R}$
contains no components with more than

$(1/2+13\varepsilon)s+11\sqrt{\varepsilon}s\leq(1/2+12\sqrt{\varepsilon})s$

vertices.

Furthermore, from Fact 4.4 we infer that at most $\sqrt{\varepsilon}s$
vertices of $K_{s}^{\varepsilon}$ have less than
$(1-2\sqrt{\varepsilon})s>0.9s$ neighbors. Consequently, because of
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}K_{3}}\nsubseteq{\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}B}$,
the set of vertices of degrees larger than $0.9s$ spans in
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}R}$
only two components on vertex sets ${W_{1}}$, ${W_{2}}$,

$(1/2+12\sqrt{\varepsilon})s\geq|{W_{1}}|\geq|{W_{2}}|\geq
s-|{W_{1}}|-\sqrt{\varepsilon}s\geq(1/2-13\sqrt{\varepsilon})s.$

Now the assertion follows from the fact that each pair of vertices from
${W_{i}}$ has a blue common neighbor in ${W_{j}}$, $\\{i,j\\}=\\{1,2\\}$ and
thereby, since
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}K_{3}}\not\subseteq{\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}B}$,
all the edges contained in either $W_{1}$ or $W_{2}$, must be red. ∎

######  Lemma 4.7.

For every positive real $\varepsilon\leq 10^{-5}$ and a large enough integer
$s$ the following holds. If the edges of $K_{s}^{\varepsilon}$ are partitioned
into two graphs
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}B}$ and
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}R}$ in
such a way that none of them has property $M_{(1/2+13\varepsilon)s}$, then one
of the colors contains an induced bipartite subgraph with a bipartition
$({W_{1}},{W_{2}})$, such that
$|{W_{1}}|,|{W_{2}}|\geq(1/2-4\sqrt{\varepsilon})s$.

###### Proof.

Benevides et al. [Ben] proved that if $t$ is large enough, then for every
graph $G$ on $t$ vertices with the minimum degree at least $0.74t$ we have
$G\to({\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}P_{0.66t}},{\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}P_{0.66t}})$.
Thus, because of $1-3\sqrt{\varepsilon}>0.74$, from Fact 4.4 it follows that
in one of the colors, say red, there exists a monochromatic path
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}P}$
whose length is at least

$0.66(1-\sqrt{\varepsilon})s\geq 0.65s>(1/2+14\varepsilon)s\,.$

Since the red graph
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}R}$
does not have property $M_{(1/2+13\varepsilon)s}$, the red component
containing
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}P}$
must be bipartite with bipartition ${(W_{1},W_{2})}$, where
$|W_{1}|\geq|W_{2}|$. All the edges inside $W_{1}$ and $W_{2}$ are blue, so
our assertion and Fact 4.5 imply that

$0.51s\geq(1/2+13{\varepsilon}+2\sqrt{\varepsilon})s\geq|W_{1}|\geq|W_{2}|\geq
0.65s-|W_{1}|\geq 0.14s\geq 11\sqrt{\varepsilon}s.$ (4.1)

Consequently, using Fact 4.5 again we infer that the blue subgraph induced by
$W_{1}\cup W_{2}$ contains two large cycles
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}C_{1}}$
and
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}C_{2}}$
with at least

$|W_{1}\cup W_{2}|-4\sqrt{\varepsilon}s\geq
0.65s-4\sqrt{\varepsilon}s>(1/2+13\varepsilon)s$

vertices combined, both contained in non-bipartite blue components. Therefore,
because
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}B}$
does not have property $M_{(1/2+13\varepsilon)s}$, there is no vertex in
$T=V\setminus(W_{1}\cup W_{2})$ with blue neighbors in both, $W_{1}$ and
$W_{2}$. This, in turn, in view of Fact 4.4 and (4.1), implies that
$|T|\leq\sqrt{\varepsilon}s$, and thereby

$|W_{1}|\geq|W_{2}|=s-|T|-|W_{1}|\geq(1/2-4\sqrt{\varepsilon})s\,.$

This completes the proof of Lemma 4.7. ∎

###### Proof of Lemma 2.1.

Let us assume that, for some large enough $n_{1}$, integers $n\geq n_{1}$, and
odd $\ell\leq n$ are given. Suppose also that we color the edges of an $n$-fit
graph $\tilde{G}_{n}$ with two colors, red and blue, so that there are no red
copies of
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}C_{n}}$
and no blue copies of
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}C_{\ell}}$.
We argue that there exists two disjoint subsets of vertices $\tilde{G}_{n}$,
$V_{1}$ and $V_{2}$, $|V_{1}|,|V_{2}|\geq 0.99n$, such that all the edges
between $V_{1}$ and $V_{2}$ are of the same color.

To this end we apply the Regularity Lemma to a coloring of $n$-fit graph
$\tilde{G}_{n}$ with some small enough $\varepsilon>0$, so that all arguments
hold. Consider an $\varepsilon$-reduced graph $\mathbf{G}_{s}^{\varepsilon}$
and denote by
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}R}$ and
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}B}$ its
subgraphs consisting of red and blue edges respectively.

We first observe that from our assertion and Lemma 4.3 it follows that the red
graph
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}R}$
does not have property ${M_{(1/2+13\varepsilon)s}}$. For the same reason, if
$\ell\geq 3s$, the blue graph
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}B}$
does not have property ${M_{(1/2+13\varepsilon)s}}$. Moreover, if $\ell\leq
7s$,
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}B}$
does not contain a blue triangle
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}K_{3}}$.
Indeed, note that for even $\ell$, $4\leq\ell\leq 7s$, the existence of a
cycle ${C_{\ell}}$ in an $\varepsilon$-regular pair $(V_{1},V_{2})$ is
guaranteed by Fact 4.1. If in addition also pairs $(V_{1},V_{3})$ and
$(V_{2},V_{3})$ are $\varepsilon$-regular, again by Fact 4.1( ) ‣ 4.1, we can
find in $V_{3}$ a vertex with many neighbors in both $V_{1}$ and $V_{2}$, and
thereby, using the $\varepsilon$-regularity of the pair $(V_{1},V_{2})$, a
cycle $C_{\ell}$ of all odd length $3\leq\ell\leq 7s$.

Thus we can apply Lemma 4.6, if $\ell\leq 7s$, and Lemma 4.7 otherwise, to
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}R}$ and
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}B}$
concluding that one of these graphs contains an induced bipartite subgraph
with a bipartition $(\mathbf{{W_{1}}},\mathbf{{W_{2}}})$, such that
$|\mathbf{{W_{1}}}|,|\mathbf{{W_{2}}}|\geq(1/2-13\sqrt{\varepsilon})s$. If, in
addition, $\ell\leq 7s$, this bipartite subgraph is blue. So assume first that
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}\mathbf{G}_{s}^{\varepsilon}[\mathbf{{W_{1}}}]},\,{\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}\mathbf{G}_{s}^{\varepsilon}[\mathbf{{W_{2}}}]}\subseteq{\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}R}$.

Now, Fact 4.5 tells us that for both $i=1,2$, there exists
$\mathbf{\widetilde{W}_{i}}\subseteq\mathbf{{W}_{i}}$,

$|\mathbf{\widetilde{W}_{i}}|\geq|\mathbf{{W}_{i}}|-2\sqrt{\varepsilon}s\geq(1/2-15\sqrt{\varepsilon})s>0.498s,$

such that the graph
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}\mathbf{G}_{s}^{\varepsilon}[\mathbf{\widetilde{W}_{i}}]}$
is connected, non-bipartite, and contains a perfect matching. In other words,
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}\mathbf{G}_{s}^{\varepsilon}[\mathbf{{W}_{i}}]}$
has the property ${M}_{0.498s}$ and thereby, in view of Lemma 4.3, there
exists a set $V^{\prime}_{i}$ of vertices of $\tilde{G}_{n}$, which is
contained in the union of the sets corresponding to vertices
$\mathbf{w}\in\mathbf{W_{i}}$, such that
$|V^{\prime}_{i}|\geq(0.498-2\varepsilon)2n\geq 0.995n,$ and every two
vertices of $V^{\prime}_{i}$ are connected in $\tilde{G}_{n}$ by a red path
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}P_{k}}$
of length $k$ for all $k$,

$3s\leq k\leq 0.9n\leq(0.495-12\varepsilon)(2n).$

Consequently, if there exist two disjoint red edges in
$\tilde{G}_{n}[V^{\prime}_{1},V_{2}^{\prime}]$, one can connect their ends by
red paths of lengths $\lfloor\ell/2\rfloor$ and $\lceil\ell/2\rceil-2$, thus
obtaining a red cycle
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}C_{\ell}}$,
of any length $\ell$, $7s\leq\ell\leq n$. But
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}C_{n}}\nsubseteq{\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}R}$
so if we remove from $\tilde{G}_{n}[V^{\prime}_{1},V_{2}^{\prime}]$ ends of
one red edge (if there exists any) we remove them all. Thus, we arrive at
$V_{1},V_{2}\subseteq V$ with $|V_{i}|\geq|V^{\prime}_{i}|-1$ for $i=1,2$ and
all edges joining $V_{1}$ and $V_{2}$ in red color.

In case
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}\mathbf{G}_{s}^{\varepsilon}[\mathbf{{W}_{i}}]}\subseteq{\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}B}$
we have $\ell\geq 7s$ and one can repeat the above reasoning with swapped
colors. ∎

##  5\. Proof of Lemma 2.2

Our goal in this section is to establish Lemma 2.2. To this end, in what
follows, we study an $n$-fit graph _ $\tilde{G}_{n}=(V,E)$_ whose edges are
colored with two colors, red and  blue, so that there exist two disjoint sets
_$V_{1},V_{2}\subseteq V$_ , $|V_{1}|=|V_{2}|=0.99n$, such that all edges
between these two sets are colored with the same color, say blue. Denote by
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}R}$ and
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}B}$
subgraphs of $\tilde{G}_{n}$ induced by red and blue edges respectively. Set
_$W=V\setminus(V_{1}\cup V_{2})$_. Moreover, we assume that $n$ is large
enough so that all inequalities below hold.

We start with a few simple observations. The first one says that most vertices
have a lot of neighbors in both sets, $V_{1}$ and $V_{2}$.

######  Claim 5.1.

All vertices, except at most one, have at least $0.23n$ neighbors in each of
the sets $V_{1}$ and $V_{2}$.

###### Proof.

Let us suppose that there exists a vertex $w$ of $\tilde{G}_{n}$, which has
fewer than $0.23n$ neighbors in one of the sets $V_{1}$, $V_{2}$, say $V_{1}$.
Each vertex $v$ shares with $w$ at least $0.5n-n^{0.7}>0.49n$ neighbors, and
so

$|N(v)\cap V_{2}|\geq|N(v)\cap N(w)|-|N(w)\cap
V_{1}|-|W|>0.49n-0.23n-0.02n>0.23n\,.$

Moreover,

$|N(v)\cup N(w)|=|N(v)|+|N(w)|-|N(v)\cap N(w)|\geq 1.5n-n^{0.7}>1.49n,$

so

$|N(v)\cap V_{1}|\geq|N(v)\cup N(w)|-|V\setminus V_{1}|-|N(w)\cap V_{1}|\\\
\geq 1.49n-1.01n-0.23n>0.23n\,.\qed$

If $\tilde{G}_{n}$ contains a vertex which has fewer than $0.23n$ neighbors in
one of the sets we call it _special_ and denote by _$s$_. In order to simplify
the notation we shall always assume that if such special vertex exists, it
does not belong to $V_{1}\cup V_{2}$. Otherwise we just remove $s$ from
$V_{1}\cup V_{2}$ and the tiny change of the size of one of the sets
$V_{1},V_{2}$ would not affect our estimates, which are always quite crude.

Now we show that if there are vertices with a lot of blue neighbors in both
$V_{1}$ and $V_{2}$, we are done.

######  Claim 5.2.

If there exists a vertex $w\in V$ with at least $n^{0.9}$ blue neighbors in
both sets $V_{1}$ and $V_{2}$, then the blue graph
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}B}$
contains a cycle $C_{\ell}$ for each $\ell$ with $3\leq\ell\leq n$.

###### Proof.

Note first that the pair $(V_{1},V_{2})$ is strongly $\varepsilon$-regular in
the blue graph for every constant $\varepsilon>0$ (in fact one can take even
$\varepsilon=n^{-0.01}$). Thus, by Fact 4.1( ) ‣ 4.1, each blue edge joining
vertices $v_{1}\in V_{1}$, $v_{2}\in V_{2}$, is contained in a cycle of each
even length $\ell_{e}$, where $4\leq\ell_{e}\leq n$. The very same Fact 4.1( )
‣ 4.1 implies that $w$ belongs to a blue cycle of odd length $\ell_{o}$,
provided $5\leq\ell_{o}\leq n$. Finally, by the definition of $n$-fit graphs,
the sets
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}N_{B}(w)}\cap
V_{1}$ and
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}N_{B}(w)}\cap
V_{2}$ are joined by more than $n^{1.8}/5$ edges and all of them are blue,
hence $B$ contains a lot of triangles. ∎

Therefore, from now on we assume that all vertices have a lot of blue
neighbors only in one of the sets $V_{1}$, $V_{2}$. In particular, in view of
Claim 5.1, sets $W_{1}$ and $W_{2}$, defined for $i=1,2$,

$W_{i}=\\{w\in
V\colon{|{\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}N_{R}(w)}\cap
V_{i}|}\geq 0.22n\textrm{ and
}{|{\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}N_{B}(w)}\cap
V_{i}|}\leq n^{0.9}\\},$ (5.1)

cover the whole set $V$ except, perhaps, the special vertex $s$. Note also
that $V_{i}\subseteq W_{i}$ for $i=1,2$. Our next claim states that the
subgraph spanned in the red graph by each of the sets $W_{i}$, $i=1,2$, is
pancyclic. In fact we prove a slightly stronger statements.

######  Claim 5.3.

For every $i=1,2$ and each $\ell$, where $3\leq\ell\leq|W_{i}|$, the subgraph
spanned by $W_{i}$ in the red graph contains a cycle of length $\ell$.
Moreover, if for some $i=1,2$ there exists a vertex $v\notin W_{i}$ which has
at least two red neighbors in $W_{i}$, then the red graph contains a cycle of
length $|W_{i}|+1$.

###### Proof.

Let us first find red cycles of length $\ell\leq 0.97n$. To this end, take any
vertex $w\in V_{i}$, and partition $V_{i}\setminus\\{w\\}$ into two roughly
equal sets $V_{i}=W^{\prime}_{i}\cup W^{\prime\prime}_{i}$ such that each of
them contains at least $0.1n$ red neighbors of $w$. Note that for each small
constant $\varepsilon>0$ the pair $(W^{\prime}_{i},W^{\prime\prime}_{i})$ is
$\varepsilon$-regular in $\tilde{G}_{n}$ and, more importantly, by Claim 5.2,
also in
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}R}$.
Thus, by Fact 4.1( ) ‣ 4.1 it contains a strongly $\varepsilon$-regular pair
$(\hat{W}^{\prime}_{i},\hat{W}^{\prime\prime}_{i})$ in
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}R}$ of
almost the same size. From that we infer, in the same way as we did in Claim
5.2, that $V_{i}$ contains cycles of all length $\ell$ up to
$|V_{i}|-30\varepsilon n\geq 0.97n$.

In search of longer cycles we use the well-known argument of Chvátal and Erdős
[CE]. Let us observe first that if $v$ has at least two red neighbors in
$W_{i}$ then it is contained in a red cycle of length at least $0.96n$.
Indeed, then one can split $V_{i}$ into two equal sets such that one contains
at least $0.1n$ red neighbors of one red neighbor of $s$, the other contains
at least $0.1n$ red neighbors of the other red neighbor of $s$, and repeat
verbatim our previous argument.

Now let us assume that we have already constructed a red cycle
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}C_{\ell}}={\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}v_{1}v_{2}\cdots
v_{\ell}v_{1}}$ for some $\ell\geq 0.96n$, and let $w$ denote a vertex of
$W_{i}$ which does not belong to it. Since $w$ has at least $0.22n$ red
neighbors in $V_{i}$, at least $0.17n$ of them lay on
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}C_{\ell}}$.
We say that a red neighbor of $w$ in
$V({\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}C_{\ell}})$
is _good_ if its predecessor in
${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}C_{\ell}}$
belongs to $V_{i}$. Denote the set of predecessors in $C_{\ell}$ of all good
vertices by $U$. Observe that because of $|W_{i}-V_{i}|\leq 0.02n$, $|U|\geq
0.1n$ and thereby $\tilde{G}_{n}[U]$ contains $O(n^{2})$ edges. This however,
in view of (5.1), implies that there are two red good neighbors of $w$, say
$v_{i}$ and $v_{j}$, $i<j$, whose predecessors are adjacent in $\tilde{G}_{n}$
by a red edge. Then, the cycle

${\color[rgb]{0.8,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.8,0,0}v_{1}v_{2}\cdots
v_{i-1}v_{j-1}v_{j-2}\cdots v_{i}wv_{j}v_{j+1}\cdots v_{\ell}v_{1}}$

is a red cycle of length $\ell+1$ (see Figure 5.1).

$w$$v_{i}$$v_{j}$$v_{i-1}$$v_{j-1}$$v_{1}$$C_{\ell}$ Figure 5.1. The enlarged
cycle.

In such a way we can include to the cycle all remaining vertices of $W_{i}$
one by one. ∎

###### Proof of Lemma 2.2.

From Claim 5.3 it follows that we are done unless $|W_{1}|=|W_{2}|=n-1$,
$W_{1}\cap W_{2}=\emptyset$, and the special vertex $s$ exists and has at most
one red neighbor in each of the sets $W_{1}$ and $W_{2}$. Note that since
$\delta(\tilde{G}_{n})=n+1$, $s$ must have in each of the sets $W_{1}$,
$W_{2}$, at least one blue neighbor. Moreover, by Claim 5.2, in one of these
sets, say $W_{2}$, $s$ has fewer than $n^{0.9}$ blue neighbors. Since the
degree of $s$ is at least $n+1$ so it has at least $n-1-n^{0.9}$ blue
neighbors in $W_{1}$ and so

$|{\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}N_{B}(s)}\cap
V_{1}|>n-1-n^{0.9}-|W|>0.97n.$ (5.2)

Now let $w$ denote a blue neighbor of $s$ in $W_{2}$. Note that if $w$ has at
least two red neighbors in $V_{1}$ we are done by Claim 5.3. Thus, in view of
Claim 5.1, $w$ must have at least $0.23n-2\geq 0.2n$ blue neighbors in
$V_{1}$. We show that in this case the graph
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}B}$
contains a blue cycle $C_{\ell}$ of any length $\ell$, $3\leq\ell\leq n$.

Let $v_{1}$ denote and blue neighbor of $w$ in
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}N_{B}(s)}\cap
V_{1}$, $v_{2}$ stand for a blue neighbor of $v_{1}$ in $V_{2}$ such that
$v_{2}\neq w$, and let $v_{3}$ be a blue neighbor of $v_{2}$ in
$({\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}N_{B}(s)}\cap
V_{1})\setminus\\{v_{1}\\}$. Note that from (5.2) and Claim 5.1 it follows
that such vertices $v_{1},v_{2},v_{3}$ always exist. Then
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}swv_{1}s}$
and
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}swv_{1}v_{2}v_{3}s}$
are blue cycles of length 3 and $5$, respectively. Moreover, the pair
$(V_{1}\setminus\\{v_{1}\\},V_{2}\setminus\\{w\\})$ is strongly
$\varepsilon$-regular for each constant $\varepsilon>0$, so Fact 4.1( ) ‣ 4.1
implies that for every odd length $\ell_{o}$, $7\leq\ell_{o}\leq n+4$ the path
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}v_{3}swv_{1}v_{2}}$
is contained in an odd blue cycle of length $\ell_{o}$ and the blue edge
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}v_{2}v_{3}}$
belongs to an even blue cycle of length $\ell_{e}$ for each $4\leq\ell_{e}\leq
n$. Thus, the blue graph
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}B}$
contains cycles of every length between $3$ and $n$. This completes the proof
of Lemma 2.2.

$s$$w$$v_{1}$$v_{2}$$v_{3}$$P_{\ell_{e}}=P_{\ell_{o}-3}$$W_{2}$$W_{1}$$V_{2}$$V_{1}$
Figure 5.2. Constructing blue cycles. Short odd cycles
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}swv_{1}s}$
and
${\color[rgb]{0,0,0.8}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0.8}swv_{1}v_{2}v_{3}s}$
are clearly visible, while all odd cycles of length at least 7, as well as all
even cycles, are constructed using wavy paths of appropriate lengths.

∎

## References


Then (E.16) follows from (E.20) and (E.21).

Assuming now Supp$(b)\subset B_{2^{-j}}(0)\setminus B_{2^{-j-1}}(0)$, we have
that $\varphi$ is harmonic on $B_{2^{-j-1}}(0)$. The monotonicity formula for
harmonic map implies that

$\begin{array}[]{l}\displaystyle\forall
r<2^{-j-1}\quad\quad\frac{1}{r^{2}}\int_{B_{r}(0)}|\nabla\varphi|^{2}\
dx^{2}\leq 2^{2j+2}\ \int_{B_{2^{-j-1}}(0)}|\nabla\varphi|^{2}\
dx^{2}\\\\[14.22636pt] \displaystyle\quad\leq C\ 2^{2j+2}\
\int_{B_{1}(0)}|\nabla a|^{2}\ dx^{2}\ \int_{B_{1}(0)}|\nabla b|^{2}\
dx^{2}\end{array}$ (E.22)

and (E.17) follows by taking $r=2^{-k}$. This concludes the proof of lemma
E.3. $\Box$

Proof of lemma E.1 Let us write

$\varphi=\sum_{k=0}^{\infty}\varphi_{k}\ ,$

where

$\left\\{\begin{array}[]{l}-\Delta\varphi_{k}=\nabla^{\perp}a\cdot\nabla
b_{k}\text{ in }B_{1}\\\\[14.22636pt] \varphi_{k}=0\text{ in }\partial
B_{1}.\end{array}\right.$ (E.23)

where $b_{k}$ are given by lemma E.2. We keep denoting
$A_{k}=B_{2^{-k}}(0)\setminus B_{2^{-(k+1)}}(0)$ and we also introduce the
following notation for slightly larger anuli
$\tilde{A}_{k}=B_{2^{-k+1}}(0)\setminus B_{2^{-(k+1)}}(0)$.

We then have by the Dominated Convergence Theorem,

$\displaystyle\int_{A_{k}}|\nabla\varphi|^{2}$
$\displaystyle=\int_{A_{k}}\sum_{i,j}\nabla\varphi_{j}\cdot\nabla\varphi_{j}=\sum_{i,j}\int_{A_{k}}\nabla\varphi_{i}\cdot\nabla\varphi_{j},$
(E.24)

and

$\sum_{k=0}^{\infty}\int_{A_{k}}|x|^{2}|\nabla\varphi|^{2}\
dx^{2}=\sum_{k=0}^{\infty}2^{-2k}\,\int_{A_{k}}|\nabla\varphi|^{2}\ dx^{2}\
\cong\
\sum_{k=0}^{\infty}2^{-2k}\sum_{i,j}\int_{A_{k}}\nabla\varphi_{i}\cdot\nabla\varphi_{j}.$
(E.25)

We now consider the case of each possible pairing of frequencies separately.

$\begin{array}[]{l}\displaystyle\sum_{k=0}^{\infty}2^{-2k}\int_{A_{k}}|\nabla\varphi|^{2}=\sum_{k=0}^{\infty}2^{-2k}\bigg{(}\int_{A_{k}}\sum_{|i-k|<2,|j-k|<2}\nabla\varphi_{i}\cdot\nabla\varphi_{j}\displaystyle+2\int_{A_{k}}\sum_{|i-k|<2,j>k+2}\nabla\varphi_{i}\cdot\nabla\varphi_{j}\\\\[14.22636pt]
\displaystyle+2\int_{A_{k}}\sum_{|i-k|<2,j<k-2}\nabla\varphi_{i}\cdot\nabla\varphi_{j}+2\int_{A_{k}}\sum_{|i-k|>2,|j-k|>2}\nabla\varphi_{i}\cdot\nabla\varphi_{j}\bigg{)}\
.\end{array}$ (E.26)

We study each of the 4 cases separately

Case 1: Using (E.6) we obtain

$\begin{array}[]{l}\displaystyle\sum_{k=0}^{\infty}2^{-2k}\sum_{\begin{subarray}{c}|i-k|<2\\\
|j-k|<2\end{subarray}}\int_{A_{k}}\nabla\varphi_{i}\cdot\nabla\varphi_{j}\leq\sum_{k=0}^{\infty}2^{-2k}\sum_{\begin{subarray}{c}|i-k|<2\\\
|j-k|<2\end{subarray}}\bigg{(}\int_{A_{k}}|\nabla\varphi_{i}|^{2}\bigg{)}^{1/2}\bigg{(}\int_{A_{k}}|\nabla\varphi_{j}|^{2}\bigg{)}^{1/2}\\\\[14.22636pt]
\displaystyle\leq
C\sum_{k=0}^{\infty}2^{-2k}\sum_{|i-k|<2}\int_{A_{k}}|\nabla\varphi_{i}|^{2}\leq
C\sum_{k=0}^{\infty}2^{-2k}\sum_{|i-k|<2}\int_{\tilde{A}_{i}}|\nabla
b_{i}|^{2}\int_{D^{2}}|\nabla a|^{2}\\\\[14.22636pt] \displaystyle\leq
C\sum_{k=0}^{\infty}\int_{\tilde{A}_{k}}|\nabla
b_{k}|^{2}2^{-2k}\int_{D^{2}}|\nabla a|^{2}\leq C\int_{D^{2}}|\nabla
b|^{2}|x|^{2}\int_{D^{2}}|\nabla a|^{2}.\end{array}$ (E.27)

Notice that the weight for these frequencies can be taken to be $f(r)=r^{2}.$
Case 2: Lemma E.3 is implying

$\displaystyle 2\sum_{k=0}^{\infty}2^{-2k}\sum_{\begin{subarray}{c}|i-k|\leq
2\\\
j>k+2\end{subarray}}\int_{A_{k}}\nabla\varphi_{i}\cdot\nabla\varphi_{j}\leq
2\sum_{k=0}^{\infty}2^{-2k}\sum_{|i-k|\leq
2}\bigg{(}\int_{A_{k}}|\nabla\varphi_{i}|^{2}\bigg{)}^{1/2}\sum_{j>k+2}\bigg{(}\int_{A_{k}}|\nabla\varphi_{j}|^{2}\bigg{)}^{1/2}$
(E.28) $\displaystyle\leq\int_{D^{2}}|\nabla
a|^{2}\sum_{k=0}^{\infty}2^{-2k}\bigg{(}\sum_{|i-k|\leq
2}\bigg{(}\int_{\tilde{A}_{i}}|\nabla
b_{i}|^{2}\bigg{)}^{1/2}\bigg{)}\bigg{(}\sum_{j>k+2}2^{-(j-k)}\bigg{(}\int_{\tilde{A}_{j}}|\nabla
b_{j}|^{2}\bigg{)}^{1/2}\bigg{)}$ (E.29) $\displaystyle\leq\int_{D^{2}}|\nabla
a|^{2}\sum_{k=0}^{\infty}2^{k}2^{-2k}\bigg{(}\int_{\tilde{A}_{k}}|\nabla
b_{k}|^{2}\bigg{)}^{1/2}\sum_{j>k+2}\bigg{(}\int_{\tilde{A}_{j}}|\nabla
b_{j}|^{2}2^{-2j}\bigg{)}^{1/2}$ (E.30) $\displaystyle\leq\int_{D^{2}}|\nabla
a|^{2}\sum_{k=0}^{\infty}\bigg{(}\int_{\tilde{A}_{k}}2^{-2k}|\nabla
b_{k}|^{2}\bigg{)}^{1/2}\sum_{j>k+2}\frac{1}{j}\bigg{(}\int_{\tilde{A}_{j}}|\nabla
b_{j}|^{2}2^{-2j}\log^{2}(1+2^{j})\bigg{)}^{1/2}$ (E.31)
$\displaystyle\leq\int_{D^{2}}|\nabla a|^{2}\sum_{k\geq
1}\frac{1}{k}\bigg{(}\int_{\tilde{A}_{k}}|\nabla
b_{k}|^{2}2^{-2k}\log^{2}(1+2^{k})\bigg{)}^{1/2}\bigg{(}\sum_{j=1}^{\infty}\int_{\tilde{A}_{j}}2^{-2j}|\nabla
b_{j}|^{2}\log^{2}(1+2^{j})\bigg{)}^{1/2}$ (E.32)
$\displaystyle\leq\int_{D^{2}}|\nabla a|^{2}\left[\sum_{k\geq
1}\frac{1}{k^{2}}\right]\
\sum_{k=1}^{\infty}\int_{\tilde{A}_{k}}2^{-2k}|\nabla
b_{k}|^{2}\log^{2}(1+2^{k})$ (E.33) $\displaystyle\leq\int_{D^{2}}|\nabla
a|^{2}\int_{D^{2}}|\nabla b|^{2}\log^{2}\left(1+\frac{1}{|x|}\right)\ |x|^{2}$
(E.34)

Case 3: Lemma E.3 again is implying

$\displaystyle\sum_{k=0}^{\infty}2^{-2k}\sum_{\begin{subarray}{c}|i-k|<2\\\
j<k-2\end{subarray}}\int_{A_{k}}\nabla\varphi_{i}\cdot\nabla\varphi_{j}\leq\sum_{k=0}^{\infty}2^{-2k}\sum_{|i-k|<2}\bigg{(}\int_{A_{k}}|\nabla\varphi_{i}|^{2}\bigg{)}^{1/2}\sum_{0\leq
j\leq k-2}\bigg{(}\int_{A_{k}}|\nabla\varphi_{j}|^{2}\bigg{)}^{1/2}$ (E.36)
$\displaystyle\leq
C\sum_{k=0}^{\infty}2^{-2k}\bigg{(}\int_{A_{k}}|\nabla\varphi_{k}|^{2}\bigg{)}^{1/2}\sum_{0\leq
j\leq k-2}\bigg{(}\int_{A_{k}}|\nabla\varphi_{j}|^{2}\bigg{)}^{1/2}$ (E.37)
$\displaystyle\leq
C\sum_{k=0}^{\infty}2^{-2k}\bigg{(}\int_{A_{k}}|\nabla\varphi_{k}|^{2}\bigg{)}^{1/2}\sum_{0\leq
j\leq k-2}2^{-k}2^{j}\bigg{(}\int_{\tilde{A}_{j}}|\nabla
b_{j}|^{2}\int_{D^{2}}|\nabla a|^{2}\bigg{)}^{1/2}$ (E.38) $\displaystyle\leq
C\sum_{k=0}^{\infty}2^{-k}\bigg{(}\int_{A_{k}}|\nabla
b_{k}|^{2}2^{-2k}\bigg{)}^{1/2}\sum_{0\leq j\leq
k-2}2^{-k}2^{2j}\bigg{(}\int_{\tilde{A}_{j}}|\nabla
b_{j}|^{2}2^{-2j}\bigg{)}^{1/2}\ \int_{D^{2}}|\nabla a|^{2}$ (E.39)

and we have

$\displaystyle\sum_{k=0}^{\infty}2^{-k}\bigg{(}\int_{A_{k}}|\nabla
b_{k}|^{2}2^{-2k}\bigg{)}^{1/2}\sum_{0\leq j\leq
k-2}2^{-k}2^{2j}\bigg{(}\int_{\tilde{A}_{j}}|\nabla
b_{j}|^{2}2^{-2j}\bigg{)}^{1/2}$ (E.40) $\displaystyle\leq
C\bigg{(}\sum_{k=0}^{\infty}\int_{A_{k}}|\nabla
b_{k}|^{2}2^{-2k}\bigg{)}^{1/2}\bigg{(}\sum_{k=0}^{\infty}2^{-4k}\bigg{(}\sum_{0\leq
j\leq k-2}2^{-k}2^{2j}\bigg{(}\int_{\tilde{A}_{j}}|\nabla
b_{j}|^{2}2^{-2j}\bigg{)}^{1/2}\bigg{)}^{2}\bigg{)}^{1/2}$ (E.41)
$\displaystyle\leq C\bigg{(}\sum_{k=0}^{\infty}\int_{A_{k}}|\nabla
b_{k}|^{2}2^{-2k}\bigg{)}^{1/2}\left(\sum_{k=0}^{\infty}2^{-4k}\left[\sum_{j\leq
k}\frac{2^{4j}}{j^{2}}\right]\ \sum_{0\leq j\leq
k-1}\int_{\tilde{A}_{j}}|\nabla
b_{j}|^{2}2^{-2j}\log^{2}(1+2^{j})\right)^{1/2}$ (E.42) $\displaystyle\leq
C\bigg{(}\sum_{k=0}^{\infty}\int_{A_{k}}|\nabla
b_{k}|^{2}2^{-2k}\log^{2}(1+2^{k})\bigg{)}\bigg{(}\sum_{k=0}^{\infty}2^{-4k}\sum_{j\leq
k}\frac{2^{4j}}{j^{2}}\bigg{)}^{1/2}$ (E.43) $\displaystyle\leq
C\int_{D^{2}}|\nabla b|^{2}|x|^{2}\log^{2}\left(1+\frac{1}{|x|}\right)$ (E.44)

Case 4:

$\sum_{|i-k|>2,|j-k|>2}\int_{A_{k}}\nabla\varphi_{i}\cdot\nabla\varphi_{j}$
(E.46)

We treat each of the four sub-cases separately and we make again an intensive
use of lemma E.3.
Case 4.1: $(i>k+2,j>k+2)$

$\displaystyle\sum_{k=0}^{\infty}2^{-2k}\sum_{i=k+2}^{\infty}\sum_{j=k+2}^{\infty}\int_{A_{k}}\nabla\varphi_{i}\cdot\nabla\varphi_{j}$
(E.47) $\displaystyle\leq$
$\displaystyle\sum_{k=0}^{\infty}2^{-2k}\sum_{i=k+2}^{\infty}\sum_{j=k+2}^{\infty}\bigg{(}\int_{A_{k}}|\nabla\varphi_{i}|^{2}\bigg{)}^{1/2}\bigg{(}\int_{A_{k}}|\nabla\varphi_{j}|^{2}\bigg{)}^{1/2}$
(E.48) $\displaystyle\leq$
$\displaystyle\sum_{k=0}^{\infty}2^{-2k}\sum_{i=k+2}^{\infty}\sum_{j=k+2}^{\infty}2^{-(i-k)}2^{-(j-k)}\bigg{(}\int_{\tilde{A}_{i}}|\nabla
b_{i}|^{2}\bigg{)}^{1/2}\bigg{(}\int_{\tilde{A}_{j}}|\nabla
b_{j}|^{2}\bigg{)}^{1/2}\int_{D^{2}}|\nabla a|^{2}$ (E.49) $\displaystyle\leq$
$\displaystyle\sum_{k=0}^{\infty}\bigg{(}\sum_{i=k+2}^{\infty}2^{-i}\bigg{(}\int_{\tilde{A}_{i}}|\nabla
b_{i}|^{2}\bigg{)}^{1/2}\bigg{)}^{2}\int_{D^{2}}|\nabla a|^{2}$ (E.50)
$\displaystyle\leq$
$\displaystyle\sum_{k=0}^{\infty}\bigg{(}\sum_{i=k+2}^{\infty}\frac{1}{i^{2}}\bigg{)}\bigg{(}\sum_{i=k+2}^{\infty}\int_{\tilde{A}_{i}}|\nabla
b_{i}|^{2}2^{-2i}\ i^{2}\bigg{)}\int_{D^{2}}|\nabla a|^{2}$ (E.51)
$\displaystyle\leq$
$\displaystyle\sum_{k=0}^{\infty}\frac{1}{k+2}\sum_{i=k+2}^{\infty}\int_{\tilde{A}_{i}}|\nabla
b_{i}|^{2}2^{-2i}\log^{2}(1+2^{i})\int_{D^{2}}|\nabla a|^{2}$ (E.52)
$\displaystyle=$
$\displaystyle\bigg{(}\sum_{i=2}^{\infty}\int_{\tilde{A}_{i}}|\nabla
b_{i}|^{2}2^{-2i}\log^{2}(1+2^{i})\sum_{k=0}^{i-2}\frac{1}{k+2}\bigg{)}\int_{D^{2}}|\nabla
a|^{2}$ (E.53) $\displaystyle\leq$
$\displaystyle\bigg{(}\sum_{i=2}^{\infty}\int_{\tilde{A}_{i}}|\nabla
b_{i}|^{2}2^{-2i}\log^{2}(1+2^{i})\log(1+i)\bigg{)}\int_{D^{2}}|\nabla a|^{2}$
(E.54) $\displaystyle\leq$ $\displaystyle C\int_{D^{2}}|\nabla
b|^{2}|x|^{2}\log^{2}\left(1+\frac{1}{|x|}\right)\log(1+\log(|x|^{-1}))\int_{D^{2}}|\nabla
a|^{2}$ (E.55)

Case 4.2: $(i<k-2,j<k-2)$ Recall that since $\Delta\varphi_{i}=0$ in
$B_{2^{-k}}(0)$ we have

$\displaystyle\int_{A_{k}}|\nabla\varphi_{i}|^{2}\ dx^{2}$ $\displaystyle\leq
C2^{-2k}2^{2i}\int_{A_{i}}|\nabla\varphi_{i}|^{2}\ dx^{2}$ (E.57)
$\displaystyle\leq 2^{-2k}2^{4i}\int_{\tilde{A}_{i}}|\nabla
b_{i}|^{2}\,2^{-2i}\,dx^{2}\ \int_{D^{2}}|\nabla a|^{2}\ dx^{2}.$ (E.58)

We can now estimate

$\displaystyle\sum_{k=0}^{\infty}2^{-2k}\sum_{i,j<k-2}\int_{A_{k}}\nabla\varphi_{i}\cdot\nabla\varphi_{j}$
(E.59) $\displaystyle\leq$
$\displaystyle\sum_{k=0}^{\infty}2^{-2k}\bigg{(}\sum_{i<k-2}\bigg{(}\int_{A_{k}}|\nabla\varphi_{i}|^{2}\bigg{)}^{1/2}\bigg{)}^{2}$
(E.60) $\displaystyle\leq$
$\displaystyle\sum_{k=0}^{\infty}2^{-2k}\bigg{(}\sum_{i<k-2}2^{-k}2^{2i}\bigg{(}\int_{\tilde{A}_{i}}|\nabla
b_{i}|^{2}2^{-2i}\bigg{)}^{1/2}\bigg{)}^{2}\int_{D^{2}}|\nabla a|^{2}$ (E.61)
$\displaystyle\leq$ $\displaystyle
C\sum_{k=0}^{\infty}2^{-4k}\bigg{(}\sum_{i<k-2}\frac{2^{4i}}{i^{2}}\bigg{)}\bigg{(}\sum_{i<k-2}\int_{\tilde{A}_{i}}|\nabla
b_{i}|^{2}2^{-2i}\log^{2}(1+2^{i})\bigg{)}\int_{D^{2}}|\nabla a|^{2}$ (E.62)
$\displaystyle\leq$ $\displaystyle
C\sum_{k=0}^{\infty}2^{-4k}\sum_{0<i<k-2}\frac{2^{4i}}{i^{2}}\bigg{(}\sum_{i=0}^{\infty}\int_{\tilde{A}_{i}}|\nabla
b_{i}|^{2}2^{-2i}\log^{2}(1+2^{i})\bigg{)}\int_{D^{2}}|\nabla a|^{2}$ (E.63)
$\displaystyle\leq$ $\displaystyle C\int_{D^{2}}|\nabla
b|^{2}|x|^{2}\log^{2}\left(1+\frac{1}{|x|}\right)\ \int_{D^{2}}|\nabla a|^{2}$
(E.64)

Case 4.3: $(i<k-1,j>k+2)$

$\displaystyle\sum_{k=0}^{\infty}2^{-2k}\sum_{\begin{subarray}{c}j>k+2\\\
i<k-1\end{subarray}}\int_{A_{k}}\nabla\varphi_{i}\cdot\nabla\varphi_{j}$
(E.66) $\displaystyle\leq$
$\displaystyle\sum_{k=0}^{\infty}2^{-2k}\sum_{i<k-2}\bigg{(}\int_{A_{k}}\nabla\varphi_{i}|^{2}\bigg{)}^{1/2}\bigg{(}\sum_{j>k+2}\bigg{(}\int_{A_{k}}|\nabla\varphi_{j}|^{2}\bigg{)}^{1/2}\bigg{)}$
(E.67) $\displaystyle\leq$
$\displaystyle\sum_{k=0}^{\infty}2^{-2k}\bigg{(}\sum_{i<k-2}2^{-k}2^{2i}\bigg{(}\int_{\tilde{A}_{i}}|\nabla
b_{i}|^{2}2^{-2i}\bigg{)}^{1/2}\bigg{)}\sum_{j>k+2}2^{k}\bigg{(}\int_{\tilde{A}_{j}}|\nabla
b_{j}|^{2}2^{-2j}\bigg{)}^{1/2}\int_{D^{2}}|\nabla a|^{2}$ (E.68)
$\displaystyle\leq$
$\displaystyle\sum_{k=0}^{\infty}2^{-2k}\bigg{(}\sum_{i<k-2}\frac{2^{4i}}{i^{2}}\bigg{)}^{1/2}\bigg{(}\sum_{i<k-2}\int_{\tilde{A}_{i}}|\nabla
b_{i}|^{2}2^{-2i}\log^{2}(1+2^{i})\bigg{)}^{1/2}$ (E.69)
$\displaystyle\bigg{(}\sum_{j>k+2}\frac{1}{j^{2}}\bigg{)}^{1/2}\bigg{(}\sum_{j>k+2}\int_{\tilde{A}_{j}}|\nabla
b_{j}|^{2}2^{-2j}\log^{2}(1+2^{j})\bigg{)}^{1/2}\int_{D^{2}}|\nabla a|^{2}$
(E.70) $\displaystyle\leq$
$\displaystyle\bigg{(}\sum_{k=0}^{\infty}2^{-4k}\sum_{i<k-2}\frac{2^{4i}}{i^{2}}\bigg{)}^{1/2}\bigg{(}\sum_{k=0}^{\infty}\bigg{(}\sum_{j>k+2}\frac{1}{j^{2}}\bigg{)}\sum_{j>k+2}\int_{\tilde{A}_{j}}|\nabla
b_{j}|^{2}2^{-2j}\log^{2}(1+2^{j})\bigg{)}^{1/2}$ (E.71)
$\displaystyle\bigg{(}\sum_{i<\infty}\int_{\tilde{A}_{i}}|\nabla
b_{i}|^{2}2^{-2i}\log^{2}(1+2^{i})\bigg{)}^{1/2}\int_{D^{2}}|\nabla a|^{2}$
(E.72)

With the estimate

$\displaystyle\sum_{k=0}^{\infty}\bigg{(}\sum_{j>k+2}\frac{1}{j^{2}}\bigg{)}\sum_{j>k+2}\int_{\tilde{A}_{j}}|\nabla
b_{j}|^{2}2^{-2j}\log^{2}(1+2^{j})$ (E.74) $\displaystyle\leq$
$\displaystyle\sum_{k=0}^{\infty}\frac{1}{k+1}\sum_{j>k+2}\int_{\tilde{A}_{j}}|\nabla
b_{j}|^{2}2^{-2j}\log^{2}(1+2^{j})$ (E.75) $\displaystyle=$
$\displaystyle\sum_{j=1}^{\infty}\int_{\tilde{A}_{j}}|\nabla
b_{j}|^{2}2^{-2j}\log^{2}(1+2^{j})\sum_{k=1}^{j}\frac{1}{k+1}$ (E.76)
$\displaystyle\leq$
$\displaystyle\sum_{j=1}^{\infty}\int_{\tilde{A}_{j}}|\nabla
b_{j}|^{2}2^{-2j}\log^{2}(1+2^{j})\log(1+j)$ (E.77)

we obtain the desired result. Collecting all the estimates above give the
weighted Wente inequality E.2 and lemma E.1 is proved. $\Box$

##  Appendix F Morrey decrease of Annulus Energies for Solutions to Wente type
Equation.

We start with some preliminary results.

######  Lemma F.1.

Let $a,b\in W^{1,2}(B_{1}(0))$ and $\varphi$ be a solution of

$-\Delta\varphi=\partial_{x_{1}}a\ \partial_{x_{2}}b-\partial_{x_{2}}a\
\partial_{x_{1}}b\quad\mbox{in $B_{1}(0)$}$ (F.1)

Then the following estimate hold.

$\displaystyle\int_{B_{\frac{1}{2}}(0)\setminus
B_{\frac{1}{4}}(0)}|\nabla\varphi|^{2}\ dx^{2}$ $\displaystyle\leq$
$\displaystyle\frac{2}{3}\int_{B_{1}(0)\setminus
B_{\frac{1}{2}}(0)}|\nabla\varphi|^{2}+C\ \int_{B_{1}(0)}|\nabla a|^{2}\
dx^{2}\ \int_{B_{1}(0)}f(|x|)\ |\nabla b|^{2}\ dx^{2}$ (F.2)

where $f$ is given by (E.3) and $C>0$ is a universal constant. $\Box$

Proof of Lemma F.1. We decompose $\varphi=\sigma+\xi$ with $\sigma,$ $\xi$
satisfying respectively

$\left\\{\begin{array}[]{cc}\displaystyle\Delta\sigma=0&~{}~{}\mbox{in
$B_{1}(0)$}\\\\[14.22636pt] \displaystyle\sigma=\varphi&~{}~{}\mbox{on
$\partial
B_{1}(0)$}\end{array}\right.~{}~{}\quad\mbox{and}\quad~{}~{}~{}\left\\{\begin{array}[]{cc}\displaystyle\Delta\xi=\Delta\varphi&~{}~{}\mbox{in
$B_{1}(0)$}\\\\[14.22636pt] \xi=0&~{}~{}\mbox{on $\partial
B_{1}(0)$}\end{array}\right.$ (F.3)

Since $\sigma$ is harmonic the monotonicity formula for harmonic functions
gives

$\displaystyle\int_{B_{\frac{1}{2}}(0)}|\nabla\sigma|^{2}\ dx^{2}$
$\displaystyle\leq$
$\displaystyle\frac{1}{4}\int_{B_{1}(0)}|\nabla\sigma|^{2}\ dx^{2}$ (F.4)
$\displaystyle=$ $\displaystyle\frac{1}{4}\int_{B_{1}(0)\setminus
B_{\frac{1}{2}}(0)}|\nabla\sigma|^{2}\
dx^{2}+\frac{1}{4}\int_{B_{\frac{1}{2}}(0)}|\nabla\sigma|^{2}\ dx^{2}\ .$

From (F.4) it follows that

$\int_{B_{\frac{1}{2}}(0)}|\nabla\sigma|^{2}\
dx^{2}\leq\frac{1}{3}\int_{B_{1}(0)\setminus
B_{\frac{1}{2}}(0)}|\nabla\sigma|^{2}\ dx^{2}$ (F.5)

We also have by the Dirichlet principle that

$\int_{B_{1}(0)}|\nabla\sigma|^{2}\
dx^{2}\leq\int_{B_{1}(0)}|\nabla\varphi|^{2}\ dx^{2}$ (F.6)

As far as the function $\xi$ is concerned we can apply the weighted Wente
Lemma E.1 and deduce that

$\int_{B_{1}(0)\setminus B_{\frac{1}{4}}(0)}|\nabla\xi|^{2}\ dx^{2}\leq
C\int_{B_{1}(0)}|\nabla a|^{2}\ dx^{2}\ \int_{B_{1}(0)}\ f(|x|)\ |\nabla
b|^{2}\ dx^{2}\ .$ (F.7)

Next we have combining the previous inequalities

$\begin{array}[]{l}\displaystyle\int_{B_{\frac{1}{2}}(0)\setminus
B_{\frac{1}{4}}(0)}|\nabla\varphi|^{2}\
dx^{2}=\displaystyle\int_{B_{\frac{1}{2}}(0)\setminus
B_{\frac{1}{4}}(0)}|\nabla\xi+\nabla\sigma|^{2}\ dx^{2}\\\\[14.22636pt]
\displaystyle\quad\leq\displaystyle\frac{3}{2}\
\int_{B_{\frac{1}{2}}(0)\setminus B_{\frac{1}{4}}(0)}|\nabla\sigma|^{2}\
dx^{2}+3\,\int_{B_{\frac{1}{2}}(0)\setminus
B_{\frac{1}{4}}(0)}|\nabla\xi|^{2}\ dx^{2}\\\\[14.22636pt]
\displaystyle\quad\leq\displaystyle\frac{1}{2}\int_{B_{1}(0)\setminus
B_{\frac{1}{2}}(0)}|\nabla\sigma|^{2}+3\,\int_{B_{\frac{1}{2}}(0)\setminus
B_{\frac{1}{4}}(0)}|\nabla\xi|^{2}\ dx^{2}\\\\[14.22636pt]
\displaystyle\quad\leq\displaystyle\frac{2}{3}\int_{B_{1}(0)\setminus
B_{\frac{1}{2}}(0)}|\nabla\varphi|^{2}+9\,\int_{B_{1}(0)\setminus
B_{\frac{1}{4}}(0)}|\nabla\xi|^{2}\ dx^{2}\\\\[14.22636pt]
\displaystyle\quad\leq\displaystyle\frac{2}{3}\int_{B_{1}(0)\setminus
B_{\frac{1}{2}}(0)}|\nabla\varphi|^{2}+C\ \int_{B_{1}(0)}|\nabla a|^{2}\
dx^{2}\ \int_{B_{1}(0)}\ f(|x|)\ |\nabla b|^{2}\ dx^{2}\ .\end{array}$ (F.8)

This concludes the proof of lemma F.1. $\Box$

######  Lemma F.2.

Under the hypothesis of lemma F.1, for any $\alpha\in(0,2)$ there exists
$C_{\alpha}>0$ such that for any $k\in{\mathbb{N}}$

$\displaystyle{\int_{A_{k+1}}}|\nabla\varphi|^{2}\ dx^{2}$ $\displaystyle\leq$
$\displaystyle\gamma^{k+1}{\int_{A_{0}}}|\nabla\varphi|^{2}\
dx^{2}+C_{\alpha}\ \int_{B_{1}(0)}|\nabla a|^{2}\ dx^{2}\
\sum_{n=0}^{\infty}\gamma^{|n-k|}\int_{A_{n}}|\nabla b|^{2}\ dx^{2}\ .$ (F.9)

where $\gamma=\max(2^{-\alpha},\frac{2}{3})$ and we are making use of the
notation $A_{k}:=B_{2^{-k}}(0)\setminus B_{2^{-k-1}}(0)$. $\Box$

Proof of Lemma F.2. By rescaling and iterating the estimate (F.8) we get for
any $k\geq 0$

$\displaystyle{\int_{A_{k+1}}}|\nabla\varphi|^{2}$ $\displaystyle\leq$
$\displaystyle\frac{2}{3}{\int_{A_{k}}}|\nabla\varphi|^{2}+C\
\int_{B_{1}(0)}|\nabla a|^{2}\ dx^{2}\int_{B_{2^{-k}}(0)}f(2^{k}|x|)\,|\nabla
b|^{2}\ dx^{2}$ $\displaystyle\leq$
$\displaystyle\frac{2}{3}\left[\frac{2}{3}{\int_{A_{k-1}}}|\nabla\varphi|^{2}+C\int_{B_{1}(0)}|\nabla
a|^{2}\ dx^{2}\ \int_{B_{2^{-k+1}}(0)}f(2^{k-1}|x|)\ |\nabla b|^{2}\
dx^{2}\right]$ $\displaystyle+$ $\displaystyle C\int_{B_{1}(0)}|\nabla a|^{2}\
dx^{2}\ \int_{B_{2^{-k}}(0)}f(2^{k}|x|)\ |\nabla b|^{2}\ dx^{2}$
$\displaystyle\ldots$ $\displaystyle\leq$
$\displaystyle\left(\frac{2}{3}\right)^{k+1}{\int_{A_{0}}}|\nabla\varphi|^{2}+C\
\int_{B_{1}(0)}|\nabla a|^{2}\ dx^{2}\
\sum_{j=0}^{k}\left(\frac{2}{3}\right)^{j}\int_{B_{2^{-k+j}}(0)}\
f(2^{k-j}|x|)\ |\nabla b|^{2}\ dx^{2}\ .$

We observe that $f(r)=o(r^{\alpha})$ as $r\to 0$ for every $\alpha\in(0,2).$
We have

$\displaystyle\sum_{j=0}^{k}\left(\frac{2}{3}\right)^{j}\int_{B_{2^{-k+j}}(0)}\,2^{\alpha(k-j)}|x|^{\alpha}|\nabla
b|^{2}\ dx^{2}$ $\displaystyle\lesssim$
$\displaystyle\sum_{j=0}^{k}\left(\frac{2}{3}\right)^{j}\sum_{n=k-j}^{\infty}\int_{A_{n}}2^{\alpha(k-j-n)}|\nabla
b|^{2}\ dx^{2}$ $\displaystyle=$
$\displaystyle\sum_{j=0}^{k}\left(\frac{2}{3}\right)^{j}2^{\alpha(k-j)}\sum_{n=k-j}^{\infty}2^{-n\alpha}\int_{A_{n}}|\nabla
b|^{2}\ dx^{2}$ $\displaystyle=$
$\displaystyle\sum_{i=0}^{k}\left(\frac{2}{3}\right)^{k-i}\ 2^{\alpha i}\
\sum_{n=i}^{\infty}2^{-n\alpha}\int_{A_{n}}|\nabla b|^{2}\ dx^{2}$
$\displaystyle=$
$\displaystyle\left(\frac{2}{3}\right)^{k}\sum_{n=0}^{\infty}2^{-n\alpha}\,\sum_{i=0}^{\inf(n,k)}\left(2^{\alpha}\frac{3}{2}\right)^{i}\
\int_{A_{n}}|\nabla b|^{2}\ dx^{2}$ $\displaystyle\leq$
$\displaystyle\left(\frac{2}{3}\right)^{k}\sum_{n=0}^{\infty}2^{-n\alpha}\left(2^{\alpha}\frac{3}{2}\right)^{\inf(n,k)}\int_{A_{n}}|\nabla
b|^{2}\ dx^{2}$ (F.11) $\displaystyle=$
$\displaystyle\left(\frac{2}{3}\right)^{k}\sum_{n=0}^{k}2^{-n\alpha}\left(2^{\alpha}\frac{3}{2}\right)^{n}\int_{A_{n}}|\nabla
b|^{2}\ dx^{2}$ $\displaystyle+$
$\displaystyle\left(\frac{2}{3}\right)^{k}\sum_{n=k+1}^{\infty}2^{-n\alpha}\left(2^{\alpha}\frac{3}{2}\right)^{k}\int_{A_{n}}|\nabla
b|^{2}\ dx^{2}$ $\displaystyle=$
$\displaystyle\sum_{n=0}^{k}\left(\frac{3}{2}\right)^{n-k}\int_{A_{n}}|\nabla
b|^{2}\ dx^{2}+\sum_{n=k+1}^{\infty}2^{(k-n)\alpha}\int_{A_{n}}|\nabla b|^{2}\
dx^{2}$ $\displaystyle\leq$
$\displaystyle\sum_{n=0}^{\infty}\gamma^{|n-k|}\int_{A_{n}}|\nabla b|^{2}\
dx^{2}\ .$

Then the estimate (F.9) holds. This concludes the proof of the Lemma F.2.
$\Box$

##  Appendix G A lemma on weighted series

######  Lemma G.1.

Let $\gamma\in(0,1)$. For any $s_{1}<s_{2}$ in ${\mathbb{N}}$ for any pair of
sequences of non negative numbers $(a_{n})_{n\in{\mathbb{N}}}$ and
$(b_{n})_{n\in{\mathbb{N}}}$ satisfying for $s_{1}\leq k\leq s_{2}$

$a_{k}\leq b_{k}+\varepsilon_{0}\,\sum_{n=0}^{\infty}\gamma^{|n-k|}a_{n}\ .$
(G.1)

for some $\varepsilon_{0}>0$. Then for any $\gamma<\mu<1$ there exists
$C_{\mu,\gamma}>0$ such that

$\displaystyle\sum_{\ell=s_{1}}^{s_{2}}\mu^{|\ell-k|}\,a_{\ell}$
$\displaystyle\leq$
$\displaystyle\sum_{\ell=s_{1}}^{s_{2}}\mu^{|\ell-k|}b_{\ell}+C_{\mu,\gamma}\
\varepsilon_{0}\ \sum_{\ell=0}^{\infty}\mu^{|\ell-k|}\,a_{\ell}$ (G.2)

$\Box$

Proof of lemma G.1. From (G.1) we get:

$\sum_{\ell=s_{1}}^{s_{2}}\mu^{|\ell-k|}a_{\ell}\leq\sum_{\ell=s_{1}}^{s_{2}}\mu^{|\ell-k|}b_{\ell}+\varepsilon_{0}\sum_{n=0}^{\infty}a_{n}\left[\sum_{\ell=s_{1}}^{s_{2}}\gamma^{|n-\ell|}\mu^{|\ell-k|}\right]$
(G.3)

Case 1. $s_{1}\leq n<k$

$\displaystyle\sum_{\ell=s_{1}}^{s_{2}}\gamma^{|n-\ell|}\mu^{|\ell-k|}=\sum_{\ell=s_{1}}^{n}\gamma^{|n-\ell|}\mu^{|\ell-k|}$
(G.4) $\displaystyle+$
$\displaystyle\sum_{\ell=n}^{k}\gamma^{|n-\ell|}\mu^{|\ell-k|}+\sum_{\ell=k+1}^{s_{2}}\gamma^{|n-\ell|}\mu^{|\ell-k|}$
$\displaystyle=$
$\displaystyle\sum_{\ell=s_{1}}^{n}\gamma^{n-\ell}\mu^{k-\ell}+\sum_{\ell=n}^{k}\gamma^{\ell-n}\mu^{k-\ell}+\sum_{\ell=k+1}^{s_{2}}\gamma^{\ell-n}\mu^{\ell-k}$
$\displaystyle\leq$
$\displaystyle\gamma^{n}\mu^{k}\sum_{\ell=s_{1}}^{n}(\mu\gamma)^{-\ell}+\gamma^{-n}\mu^{k}\sum_{\ell=n}^{k}(\mu^{-1}\gamma)^{\ell}+\gamma^{-n}\mu^{-k}\sum_{\ell=k+1}^{\infty}(\mu\gamma)^{\ell}$
$\displaystyle\leq$
$\displaystyle\left[\frac{(\mu\gamma)^{-s_{1}+n}}{1-\mu\gamma}+\frac{1}{1-\mu^{-1}\gamma}\right]\,\mu^{k-n}+\frac{\mu\gamma}{1-\mu\gamma}\,\gamma^{k-n}\leq
C_{\mu,\gamma}\,\mu^{k-n}.$

Case 2. $n\leq s_{1}$

$\displaystyle\sum_{\ell=s_{1}}^{s_{2}}\gamma^{|n-\ell|}\mu^{|\ell-k|}=\sum_{\ell=s_{1}}^{k}\gamma^{|n-\ell|}\mu^{|\ell-k|}+\sum_{\ell=k+1}^{s_{2}}\gamma^{|n-\ell|}\mu^{|\ell-k|}$
(G.5) $\displaystyle=$
$\displaystyle\sum_{\ell=s_{1}}^{k}\gamma^{\ell-n}\mu^{k-\ell}+\sum_{\ell=k+1}^{s_{2}}\gamma^{\ell-n}\mu^{\ell-k}$
$\displaystyle\leq$
$\displaystyle\gamma^{-n}\mu^{k}\sum_{\ell=n}^{k}(\mu^{-1}\gamma)^{\ell}+\gamma^{-n}\mu^{-k}\sum_{\ell=k+1}^{\infty}(\mu\gamma)^{\ell}$
$\displaystyle\leq$
$\displaystyle\frac{1}{1-\mu^{-1}\gamma}\,\mu^{k-n}+\frac{\mu\gamma}{1-\mu\gamma}\,\gamma^{k-n}\leq
C_{\mu,\gamma}\,\mu^{k-n}.$

Case 3. $k\leq n\leq s_{2}$

$\displaystyle\sum_{\ell=s_{1}}^{s_{2}}\gamma^{|n-\ell|}\mu^{|\ell-k|}=\sum_{\ell=s_{1}}^{k}\gamma^{n-\ell}\mu^{k-\ell}+\sum_{\ell=k+1}^{n}\gamma^{n-\ell}\mu^{\ell-k}+\sum_{\ell=n+1}^{s_{2}}\gamma^{\ell-n}\mu^{\ell-k}$
(G.6) $\displaystyle\leq$
$\displaystyle\frac{\gamma^{n-k}}{1-\gamma\,\mu}+\frac{\mu^{n-k}}{1-\gamma\mu^{-1}}+\frac{\mu^{n-k}}{1-\gamma\,\mu}\leq
C_{\mu,\gamma}\,\mu^{n-k}.$

Case 4. $s_{2}\leq n$

$\displaystyle\sum_{\ell=s_{1}}^{s_{2}}\gamma^{|n-\ell|}\mu^{|\ell-k|}=\sum_{\ell=s_{1}}^{k}\gamma^{n-\ell}\mu^{k-\ell}+\sum_{\ell=k+1}^{s_{2}}\gamma^{n-\ell}\mu^{\ell-k}$
(G.7) $\displaystyle\leq$
$\displaystyle\frac{\gamma^{n-k}}{1-\gamma\,\mu}+\frac{\gamma^{n-s_{2}}\,\mu^{-k+s_{2}}}{1-\gamma\mu^{-1}}\leq
C_{\mu,\gamma}\,\mu^{n-k}.$

Combining all the above cases and (G.3) gives (G.2) and lemma G.1 is proved.
$\Box$

## References

  * [1] Bethuel, Fabrice, Un résultat de régularité pour les solutions de l’équation de surfaces à courbure moyenne prescrite, C.R. Acad.Sci.Paris Sér. I Math. 414, 13 (1992), 1003-1007.
  * [2] Brezis, Haïm Functional analysis, Sobolev spaces and partial differential equations. Universitext. Springer, New York, 2011.
  * [3] Chodosh, Otis; Mantoulidis, Christos Minimal surfaces and the Allen-Cahn equation on 3-manifolds: index, multiplicity, and curvature estimates. Ann. of Math. (2) 191 (2020), no. 1, 213-328.
  * [4] Da Lio, Francesca; Pigati, Alessandro Free boundary minimal surfaces: a nonlocal approach. Ann. Sc. Norm. Super. Pisa Cl. Sci. (5) 20 (2020), no. 2, 437-489.
  * [5] Da Lio, Francesca; Rivière, Tristan Three-term commutator estimates and the regularity of $1/2-$harmonic maps into spheres. Anal. PDE 4 (2011), no. 1, 149-190.
  * [6] Da Lio, Francesca; Rivière, Tristan Sub-criticality of non-local Schrödinger systems with antisymmetric potentials and applications to half-harmonic maps. Adv. Math. 227 (2011), no. 3, 1300-1348.
  * [7] Da Lio, Francesca; Mazowiecka, Katarzyna; Schikorra, Armin A fractional version of Rivière’s $GL(n)-$gauge. Ann. Mat. Pura Appl. (4) 201 (2022), no. 4, 1817-1853.
  * [8] Del Pino, Manuel; Kowalczyk, Michal ; Wei, Juncheng ; Yang, Jun Interface foliation near minimal submanifolds in Riemannian manifolds with positive Ricci curvature.  Geom. Funct. Anal. 20 (2010), no. 4, 918-957.
  * [9] Dierkes, Ulrich; Hildebrandt, Stefan; Sauvigny, Friedrich Minimal surfaces. Grundlehren der mathematischen Wissenschaften, 339. Springer, Heidelberg, 2010.
  * [10] Grafakos, Loukas Classical Fourier analysis. Third edition. Graduate Texts in Mathematics, 249. Springer, New York, 2014.
  * [11] Grüter, Michael Conformally invariant variational integrals and the removability of isolated singularities. Manuscripta Math. 47 (1984), no. 1-3, 85-104.
  * [12] Hélein, Frédéric Harmonic maps, conservation laws and moving frames. Translated from the 1996 French original. With a foreword by James Eells. Second edition. Cambridge Tracts in Mathematics, 150. Cambridge University Press, Cambridge, 2002.
  * [13] Hummel, C.: Gromov’s Compactness Theorem for Pseudo-Holomorphic Curves. Progress in Mathematics, vol. 151, Birkäuser, Basel (1997).
  * [14] M. Karpukhin, D. L. Stern, Min-max harmonic maps and a new characterization of conformal eigenvalues. arXiv:2004.04086
  * [15] T. Lamm and T. Rivière Conservation laws for fourth order systems in four dimensions. Comm. Partial Differential Equations 33 (2008), no. 1-3, 245-262.
  * [16] Lamm, Tobias ; Sharp, Ben Global estimates and energy identities for elliptic systems with antisymmetric potentials.  Comm. Partial Differential Equations 41 (2016), no. 4, 579-608.
  * [17] Laurain, Paul; Rivière, Tristan Angular energy quantization for linear elliptic systems with antisymmetric potentials and applications. Anal. PDE 7 (2014), no. 1, 1-41.
  * [18] Laurain, Paul; Rivière, Tristan Energy quantization for biharmonic maps. Adv. Calc. Var. 6 (2013), no. 2, 191-216.
  * [19] Lin, Fang-Hua; Rivière, Tristan A quantization property for moving line vortices. Comm. Pure Appl. Math. 54 (2001), no. 7, 826-850.
  * [20] F.-H. Lin and T. Rivière Energy quantization for harmonic maps. Duke Math. J. 111:1 (2002), 177-193.
  * [21] Lin, Fanghua; Wang, Changyou Energy identity of harmonic map flows from surfaces at finite singular time. Calc. Var. Partial Differential Equations 6 (1998), no. 4, 369-380.
  * [22] Marques, Fernando C.; Neves, André Morse index of multiplicity one min-max minimal hypersurfaces. Adv. Math. 378 (2021), Paper No. 107527, 58 pp.
  * [23] Michelat, Alexis; Rivière, Tristan Pointwise Expansion of Degenerating Immersions of Finite Total Curvature. J. Geom. Anal. 33 (2023), no. 1, 24.
  * [24] Moore, John Douglas Introduction to global analysis. Minimal surfaces in Riemannian manifolds. Graduate Studies in Mathematics, 187. American Mathematical Society, Providence, RI, 2017.
  * [25] Moore, John Douglas and Ream, Robert Minimal two-spheres of low index in manifolds with positive complex sectional curvature.  Math. Z. 291 (2019), no. 3-4, 1295-1335.
  * [26] Parker, Thomas H. Bubble tree convergence for harmonic maps. J. Differential Geom. 44 (1996), no. 3, 595-633.
  * [27] Qing, Jie ; Tian, Gang Bubbling of the heat flows for harmonic maps from surfaces. Comm. Pure Appl. Math. 50 (1997), no. 4, 295-310.
  * [28] Rivière, Tristan Interpolation spaces and energy quantization for Yang-Mills fields. Comm. Anal. Geom. 10 (2002), no. 4, 683-708.
  * [29] Rivière, Tristan Conservation laws for conformally invariant variational problems. Invent. Math. 168 (2007), no. 1, 1-22.
  * [30] Rivière, Tristan Lower semi-continuity of the index in the viscosity method for minimal surfaces. Int. Math. Res. Not. IMRN 2021, no. 8, 5651-5675.
  * [31] Simon, Leon Asymptotics for a class of nonlinear evolution equations, with applications to geometric problems. Ann. of Math. (2) 118 (1983), no. 3, 525-571.
  * [32] Smith, R. T. The second variation formula for harmonic mappings. Proc. Amer. Math. Soc. 47 (1975), 229-236.
  * [33] Yin, Hao Generalized neck analysis of harmonic maps from surfaces.  Calc. Var. Partial Differential Equations 60 (2021), no. 3, Paper No. 117, 31 pp.
  * [34] Yin, Hao Higher-order neck analysis of harmonic maps and its applications.  Ann. Global Anal. Geom. 62 (2022), no. 2, 457-477.
  * [35] Zhu, Miaomiao Harmonic maps from degenerating Riemann surfaces. Math. Z. 264 (2010), no. 1, 63-85.


Table : Summary of fixed and random effects for number of commands per task
-Linear mixed effects model

Model: number of command per task ~Speaker Type*Device
Condition+(1—Participant)+(1—Task)
Fixed Effect Unstandardised $\beta$ SE $\beta$ t statistic p Intercept 2.21
0.26 8.39 ¡.001*** L2 Speakers -0.39 0.37 -1.06 .29 Smartphone 0.12 0.27 0.43
.67 L2 Speaker*Smartphone 0.33 0.38 0.88 .38 Random Effects Group SD
Participant 0.71 Task 0.18 Residual 1.78

Table : Summary of fixed and random effects for word count per command in each
task -Linear mixed effects model

Model: word count per command in each task ~Speaker Type*Device
Condition+(1—Participant)+(1—Task)
Fixed Effect Unstandardised $\beta$ SE $\beta$ t statistic p Intercept 8.07
0.42 19.36 ¡.001*** L2 Speakers -0.65 0.59 -1.11 .27 Smartphone 0.50 0.34 1.45
.15 L2 Speaker*Smartphone -0.45 0.49 -0.92 .36 Random Effects Group SD
Participant 1.35 Task 0.13 Residual 2.29

Table : Summary of fixed and random effects for general lexical diversity in
each task- Linear mixed effects model

Model: Diversity from First command~Speaker Type*Device
Condition+(1—Participant)+(1—Task)
Fixed Effect Unstandardised $\beta$ SE $\beta$ t statistic p Intercept 2.61
0.08 32.31 ¡.001* L2 Speakers -0.15 0.11 -1.38 .18 Smartphone -0.01 0.08 0.19
.85 L2 Speaker*Smartphone 0.12 0.11 1.14 .26 Random Effects Group SD
Participant 0.23 Task 0.05 Residual 0.51

Table : Summary of fixed and random effects for diversity from first command
in each task- Linear mixed effects model

Model: Diversity from First command~Speaker Type*Device Condition+(1—Task)
Fixed Effect Unstandardised $\beta$ SE $\beta$ t statistic p Intercept 0.98
0.13 7.34 ¡.001* L2 Speakers -0.26 0.18 -1.43 .16 Smartphone -0.17 0.17 -1.01
.32 L2 Speaker*Smartphone 0.33 0.25 1.35 .18 Random Effects Group SD Task 0.11
Residual 0.91

Table : Summary of fixed and random effects for diversity from previous
command in each task -Linear mixed effects model

Model: Diversity from previous command ~Speaker Type*Device
Condition+(1—Participant)+(1—Task)
Fixed Effect Unstandardised $\beta$ SE $\beta$ t statistic p Intercept 2.10
0.12 17.74 ¡.001*** L2 Speakers -0.04 0.16 -0.28 .78 Smartphone 0.14 0.14 0.98
.32 L2 Speakers:Smartphone -0.24 0.20 -1.20 .23 Random Effects Group SD
Participant 0.14 Item 0.14 Residual 0.62

Table : Descriptive statistics of raw NASA-TLX score by speaker and device Participants | Devices | Mean | SD |
---|---|---|---|---
L1 |  | Home
---
Phone
Total
| 28.63
---
30.19
29.41
| 21.07
---
17.51
19.07
L2 |  | Home
---
Phone
Total
| 49.94
---
40.38
43.66
| 17.24
---
10.33
14.37
Total |  | Home
---
Phone
Total
| 37.78
---
35.28
36.53
| 21.10
---
15.06
18.22
Table : Descriptive statistics of number of commands per task by speaker and device Participants | Devices |  | Mean | Median | S.D.
---|---|---|---|---|---
| Home |  | 2.24 | 1.0 | 2.18
L1 | Smartphone |  | 2.35 | 1.0 | 2.14
| Total |  | 2.29 | 1.0 | 2.15
| Home |  | 1.84 | 1.0 | 1.28
L2 | Smartphone |  | 2.30 | 1.0 | 2.02
| Total |  | 2.07 | 1.0 | 1.70
Total | Home |  | 2.04 | 1.0 | 1.79
| Smartphone |  | 2.33 | 1.0 | 2.07
Table : Descriptive statistics of words per command in each task by speaker and device Participants | Devices |  | Mean | Median | S.D.
---|---|---|---|---|---
| Home |  | 8.08 | 8.0 | 2.87
L1 | Smartphone |  | 8.57 | 8.0 | 3.07
| Total |  | 8.32 | 8.0 | 2.97
| Home |  | 7.39 | 8.0 | 2.58
L2 | Smartphone |  | 7.45 | 7.83 | 2.11
| Total |  | 7.42 | 8.0 | 2.35
Total | Home |  | 7.74 | 8.0 | 2.74
| Smartphone |  | 8.01 | 8.0 | 2.69
Table : Descriptive statistics of lexical diversity in each task by speaker and device Participants | Devices |  | Mean | Median | S.D.
---|---|---|---|---|---
| Home |  | 2.61 | 2.71 | 0.53
L1 | Smartphone |  | 2.58 | 2.65 | 0.58
| Total |  | 2.60 | 2.65 | 0.56
| Home |  | 2.45 | 2.59 | 0.60
L2 | Smartphone |  | 2.55 | 2.67 | 0.53
| Total |  | 2.50 | 2.65 | 0.57
Total | Home |  | 2.53 | 2.65 | 0.57
| Smartphone |  | 2.57 | 2.65 | 0.56
Table : Descriptive statistics of lexical diversity from first command by speaker and device Participants | Devices |  | Mean | Median | S.D.
---|---|---|---|---|---
| Home |  | 0.98 | 0.88 | 0.96
L1 | Smartphone |  | 0.80 | 0.51 | 0.91
| Total |  | 0.88 | 0.65 | 0.93
| Home |  | 0.71 | 0.31 | 0.93
L2 | Smartphone |  | 0.88 | 0.77 | 0.89
| Total |  | 0.80 | 0.50 | 0.91
Total | Home |  | 0.85 | 0.55 | 0.95
| Smartphone |  | 0.84 | 0.60 | 0.90
Table : Descriptive statistics of lexical diversity from previous command by speaker and device Participants | Devices |  | Mean | Median | S.D.
---|---|---|---|---|---
| Home |  | 2.12 | 2.10 | 0.67
L1 | Smartphone |  | 2.24 | 2.21 | 0.61
| Total |  | 2.19 | 2.13 | 0.66
| Home |  | 2.05 | 2.12 | 0.66
L2 | Smartphone |  | 1.96 | 2.08 | 0.71
| Total |  | 2.00 | 2.11 | 0.68
Total | Home |  | 2.09 | 2.10 | 0.66
| Smartphone |  | 2.10 | 2.14 | 0.67