---
abstract: 'We find the exact value of the Ramsey number $R(C_{2\ell},K_{1,n})$, when $\ell$ and $n=O(\ell^{10/9})$ are large. Our result is closely related to the behaviour of Turán number ${\mathrm{ex}}(n, C_{2\ell})$ for an even cycle whose length grows quickly with $n$.'
address:
- |
    Adam Mickiewicz University\
    Faculty of Mathematics and Computer Science\
    Umultowska 87, 61-614 Poznań, Poland
- |
    Adam Mickiewicz University\
    Faculty of Mathematics and Computer Science\
    Umultowska 87, 61-614 Poznań, Poland
- |
    Hebei Normal University\
    18. School of Mathematical Sciences\
    Shijiazhuang, P.R.China
author:
- Tomasz Łuczak
- Joanna Polcyn
- Yanbo Zhang
date: 'March 6th, 2020'
title: |
    The Ramsey number of\
    a long even cycle versus a star 
---

[^1]

Introduction
============

For a graph $H$ by $${\mathrm{ex}}(n,H)=\max\{|E|: G=(V,E)\not\supseteq H \ \&\ |V|=n\}$$ we denote its Turán number. Let us recall that for graphs $H$ with chromatic number at least three the asymptotic value of ${\mathrm{ex}}(n,H) $ was determined over fifty years ago by Erdős and Stone [@ESt], and Erdős and Simonovits [@ESi], while for most of bipartite graphs $H$ the behaviour of ${\mathrm{ex}}(H,n)$ is not well-understood. Let us recall some results on the case when $H$ is an even cycle $C_{2\ell}$. The best upper bound for ${\mathrm{ex}}(n, C_{2\ell})$ for general $\ell$ is due to Bukh and Jiang [@BJ] who improved the classical theorem of Bondy and Simonovits [@BS] to $${\mathrm{ex}}(n, C_{2\ell})\le 80\sqrt{\ell} \ln \ell n^{1+1/\ell}+ 10\ell^2 n.$$ The best lower bound which holds for all $\ell$ follows from the construction of a regular graph of large girth by Lubotzky, Phillips, and Sarnak [@LPS], which gives $${\mathrm{ex}}(n, C_{2\ell})\ge n^{1+(2+o(1))/3 \ell}.$$ The correct exponent $\alpha_\ell$ for which ${\mathrm{ex}}(n,C_{2\ell})=n^{\alpha_\ell+o(1)}$ is known only for $\ell=2,3,5$, when it is equal to $1+1/\ell$ (see the survey of Füredi and Simonovits [@FS] and references therein), and finding it for every $\ell$ is one of the major open problems in extremal graph theory. Can it become easier when we allow the length of an even cycle to grow with $n$? This paper was inspired by this question. However, instead of the original problem we consider its, nearly equivalent, partition version. Thus, instead of ${\mathrm{ex}}(n,C_{2\ell})$, we study the Ramsey number $R(C_{2\ell}, K_{1,n})$. Note that from the result of Bukh and Jiang and the construction of Lubotzky, Phillips, and Sarnak mentioned above we get $$\label{eq1}
n+ n^{(2+o(1))/3\ell} \le R(C_{2\ell}, K_{1,n})\le n+ 81\sqrt{\ell} \ln \ell n^{1/\ell}+ 11\ell^2.$$ Since a graph on $N$ vertices with minimum degree at least $N/2$ is hamiltonian (Dirac [@D]), and if its minimum degree is larger than $N/2$, it is pancyclic (Bondy [@B]), for $\ell \ge n\ge 2 $, we have $R(C_{2\ell},K_{1,n})=2\ell$. Moreover, Zhang, Broersma, and Chen [@ZBC] showed that if $n/2<\ell<n$ then $R(C_{2\ell},K_{1,n})=2n$, while for $3n/8+1\le \ell\le n/2$, we get $R(C_{2\ell},K_{1,n})=4\ell-1$. Our main result determines the value of $R(C_{2\ell},K_{1,n})$ for all large $\ell$ and $n \le 0.1\ell^{10/9}$.

\[thm1\] For every $t\ge 2$, $\ell\ge (19.1t)^9$, and $n$ such that $(t-1)(2\ell-1)\le n-1 < t(2\ell-1)$, we have $$\label{eq:main}
    R(C_{2\ell}, K_{1,n}) =f_t(\ell,n)+1,$$ where $$\label{eq:main2}
f_t(\ell,n)=\max\{t(2\ell-1), n+ \lfloor (n-1)/t\rfloor  \}.$$

We do not know how much one can relax the condition $n\le 0.1\ell^{10/9}$ in Theorem \[thm1\]. We suspect that the result holds for $n$ growing polynomially with $\ell$, but it is conceivable that it remains true even for $n$ which grows exponentially with $\ell$. On the other hand, because of , the assertion of Theorem \[thm1\] fails for, say, $n\ge \ell^{2\ell}$.

We remark that, as we mentioned above, one can use similar technique to find the value of ${\mathrm{ex}}(n,C_{2\ell})$ when $n$ is not much larger than $\ell$. The difference between this problem, when we try to maximize the number of edges in the graph, and the Ramsey setting we chose, when we maximize its minimum degree, is not substantial. However, the result for ${\mathrm{ex}}(n,C_{2\ell})$ is more predictable, since in this case one needs to maximize the number of blocks of size $2\ell-1$ and supplement it with at most one smaller block. The behaviour of $R(C_{2\ell},K_{1,n})$ seems to us more intriguing. Indeed, for a given $\ell$ and $(t-1)(2\ell-1)\le n-1< \frac{t^2}{t+1}(2\ell-1)$ we have $$f_t(\ell,n) =(2\ell-1)t,$$ i.e. for this range of $n$ the value of $R(C_{2\ell}, K_{1,n})$ does not depend on the size of the star. On the other hand, as it is shown in the next section, for $\frac{t^2}{t+1}(2\ell-1)\le n-1< t(2\ell-1) $, when $$f_t(\ell,n) = n+ \lfloor (n-1)/t\rfloor\,$$ the ‘extremal graphs’ which determine the value of $R(C_{2\ell}, K_{1,n})$ typically have all blocks much smaller than $2\ell-1$.

The lower bound for $R(C_{2\ell}, K_{1,n})$ {#sec:lower}
===========================================

In this section we show that for given integers $t$, $\ell$, and $n$ such that $(t-1)(2\ell-1) \le n-1 < t(2\ell - 1)$, we have $$\label{eq:lower}
R(C_{2\ell},K_{1,n}) >f_t(\ell,n)=\max\{t(2\ell-1), n+ \lfloor (n-1)/t\rfloor \}.$$

Let us consider first the graph $H_1$ which consists of $t$ vertex-disjoint copies of the complete graph $K_{2\ell-1}$. Clearly, $|V(H_1)| = t(2\ell-1)$ and $H_1\nsupseteq C_{2\ell}$. Moreover, $\Delta({    \sbox{\myboxA}{$\m@thH$}    \setbox\myboxB\null    \ht\myboxB=\ht\myboxA    \dp\myboxB=\dp\myboxA    \wd\myboxB=0.75\wd\myboxA    \sbox\myboxB{$\m@th\overline{\copy\myboxB}$}    \setlength\mylenA{\the\wd\myboxA}    \addtolength\mylenA{-\the\wd\myboxB}    \ifdim\wd\myboxB<\wd\myboxA    \rlap{\hskip 0.5\mylenA\usebox\myboxB}{\usebox\myboxA}    \else
    \hskip -0.5\mylenA\rlap{\usebox\myboxA}{\hskip 0.5\mylenA\usebox\myboxB}    \fi}_1) = (t-1)(2\ell-1) \le n-1$ yielding ${    \sbox{\myboxA}{$\m@thH$}    \setbox\myboxB\null    \ht\myboxB=\ht\myboxA    \dp\myboxB=\dp\myboxA    \wd\myboxB=0.75\wd\myboxA    \sbox\myboxB{$\m@th\overline{\copy\myboxB}$}    \setlength\mylenA{\the\wd\myboxA}    \addtolength\mylenA{-\the\wd\myboxB}    \ifdim\wd\myboxB<\wd\myboxA    \rlap{\hskip 0.5\mylenA\usebox\myboxB}{\usebox\myboxA}    \else
    \hskip -0.5\mylenA\rlap{\usebox\myboxA}{\hskip 0.5\mylenA\usebox\myboxB}    \fi}_1 \nsupseteq K_{1,n}$. Hence $$R(C_{2\ell},K_{1,n}) >t(2\ell-1)\,.$$

Now let $k=n-1 - t\lfloor (n-1)/t\rfloor$ and $m=\lfloor (n-1)/t\rfloor + 1$. We define a graph $H_2$ as a union of $k$ vertex-disjoint complete graphs $K_m$ and $t+1-k$ other copies of $K_m$ which are ‘almost’ vertex-disjoint except that they share exactly one vertex. Then $$\begin{aligned}
|V(H_2)|&=km+(t+1-k)(m-1) + 1=(t+1)m-(t-k)\\
&=(t+1)(\lfloor (n-1)/t\rfloor + 1) -t + n-1 - t\lfloor (n-1)/t\rfloor\\
&=n+\lfloor (n-1)/t\rfloor.         \end{aligned}$$ Note also that $n-1< t(2\ell-1)$, and so $m=\lfloor (n-1)/t\rfloor +1\le 2\ell-1$. Hence $H_2\not\supseteq C_{2\ell}$. Finally, $$\begin{aligned}
\Delta({    \sbox{\myboxA}{$\m@thH$}    \setbox\myboxB\null    \ht\myboxB=\ht\myboxA    \dp\myboxB=\dp\myboxA    \wd\myboxB=0.75\wd\myboxA    \sbox\myboxB{$\m@th\overline{\copy\myboxB}$}    \setlength\mylenA{\the\wd\myboxA}    \addtolength\mylenA{-\the\wd\myboxB}    \ifdim\wd\myboxB<\wd\myboxA    \rlap{\hskip 0.5\mylenA\usebox\myboxB}{\usebox\myboxA}    \else
    \hskip -0.5\mylenA\rlap{\usebox\myboxA}{\hskip 0.5\mylenA\usebox\myboxB}    \fi}_2) = |V| - m= n+\lfloor (n-1)/t\rfloor   -\lfloor (n-1)/t\rfloor - 1 =n-1.\end{aligned}$$ Therefore $$R(C_{2\ell},K_{1,n}) >|V(H_2)|= n+ \lfloor (n-1)/t\rfloor,$$ and follows.

Let us remark that the two graphs $H_1$ and $H_2$ we used above are by no means the only ‘extremal graphs’ with $R(C_{2\ell},K_{1,n})-1$ vertices. Let us take, for example, $n=4.1\ell$. Then $R(C_{2\ell},K_{1,n})=3(2\ell-1)+1$ and the lower bound for $R(C_{2\ell},K_{1,n})$ is ‘certified’ by the graph $H'_1$ which consists of three vertex disjoint cliques $K_{2\ell-1}$. However, if we replace each of these cliques by a graph on $2\ell-1$ vertices and the minimum degree $1.91\ell$, the complement of the resulting graph will again contain no $K_{1,n}$, so each such graph shows that $R(C_{2\ell},K_{1,n})>3(2\ell-1)$ as well. On the other hand, adding to $H'_1$ a triangle with vertices in different cliques does not result in a copy of $C_{2\ell}$, so $H'_1$ is not even a maximal extremal graph certifying that $R(C_{2\ell},K_{1,n})>3(2\ell-1)$.

Cycles in 2-connected graphs
============================

In order to show the upper bound for $R(C_{2\ell},K_{1,n})$ we have to argue that large graphs with a high enough minimum degree contain $C_{2\ell}$. In this section we collect a number of results on cycles in 2-connected graphs we shall use later on.

Let us recall first that the celebrated theorem of Dirac [@D] states that each 2-connected graph $G$ on $n$ vertices contains a cycle of length at least $\min\{ 2\delta(G),n\}$, and, in particular, each graph with the minimum degree at least $n/2$ is hamiltonian. Below we mention some generalizations of this result. Since we are interested mainly in even cycles, we start with the following observation due to Voss and Zuluaga [@VZ].

\[l:VZ\] Every 2-connected graph $G$ on $n$ vertices contains an even cycle $C$ of length at least $\min\{2\delta(G), n-1\}$.

The following result by Bondy and Chvátal [@BC] shows that the condition $\delta(G)\ge n/2$, sufficient for hamiltonicity, can be replaced by a somewhat weaker one. Recall that the closure of a graph $G=(V,E)$ is the graph obtained from $G$ by recursively joining pairs of non-adjacent vertices whose degree sum is at least $|V|$ until no such pair remains.

\[l:BC\] A graph $G$ is hamiltonian if and only if its closure is hamiltonian.

If we allow $\delta(G)>n/2$, then, as observed by Bondy [@B], $G$ becomes pancyclic. We use the following strengthening of this result, proved under slightly stronger assumptions, due to Williamson [@W].

\[l:W\] Every graph $G=(V,E)$ on $n$ vertices with $\delta(G)\ge  n/2+1$ has the following property. For every $v,w\in V$ and every $k$ such that $2\le k\le n-1$, $G$ contains a path of length $k$ which starts at $v$ and ends at $w$. In particular, $G$ is pancyclic.

Finally, we state a theorem of Gould, Haxell, and Scott [@GHS], which is crucial for our argument. Here and below $\textrm{ec}(G)$ denotes the length of the longest even cycle in $G$.

\[l:GHS\] Let $a>0$, $\hat K = 75\cdot 10^4 a^{-5}$, and $G$ be a graph with $n\ge 45 \hat K/a^4$ vertices and minimum degree at least $an$. Then for every even $r\in [4,\textrm{ec}(G)-\hat K]$, $G$ contains a cycle of length $r$.

Let us also note the following consequence of the above results.

\[l:small\] For $c\ge 1$ we set $$\label{eq:ks}
K(c) = 24\cdot 10^6 c^5 = 75\cdot 10^4 (1/2c)^{-5},$$ and let $\ell \ge 360c^4K(c)$. Then for every 2-connected $C_{2\ell}$-free graph $H=(V,E)$ such that $|V|\le 2\ell c$ and $\delta(H) \ge \ell + K(c)$, we have $$|V|\le 2\ell - 1.$$

Let us consider first the case $|V| < 2\ell + 2K(c)-2$. Then, since $$\delta(H) \ge \ell +K(c) > { |V|}/{2}+1,$$ from Lemma \[l:W\] we infer that $H$ is pancyclic. But $C_{2\ell} \nsubseteq H$ meaning that $|V|\le 2\ell - 1$, as required.

On the other hand, for $|V|\ge 2\ell + 2K(c)-2$ Lemma \[l:VZ\] implies that $$\textrm{ec}(H) \ge 2\ell + 2K(c)-2>2\ell+K(c)$$ Moreover, as $|V|\le 2\ell c$ and $\ell \ge 360c^4K(c)$, one gets $$\delta(H)> \ell \ge \frac{1}{2c}|V|\quad \textrm{and}\quad |V| > 2\ell \ge 45\left(\frac{1}{2c}\right)^{-4}K(c).$$ Therefore, from Lemma \[l:GHS\] applied to $H$ with $a=1/(2c)$, we infer that $H$ contains a cycle of length ${2\ell}$, contradicting $C_{2\ell}$-freeness of $H$.

Proof of the main result
========================

The two examples of graphs we used to verify the lower bound for $R(C_{2\ell}, K_{1,n})$ (see Section \[sec:lower\]) suggest that a natural way to deal with the upper bound for $R(C_{2\ell}, K_{1,n})$ is to show first that each $C_{2\ell}$-free graph $G$ with a large minimum degree has all blocks smaller than $2\ell$. However, most results on the existence of cycles in 2-connected graphs are using the minimum degree condition, and even if the minimum degree of $G$ is large, some of its blocks may contain vertices of small degree. Nonetheless we shall prove that the set of vertices in each such $G$ contains a ‘block-like’ family of 2-connected subgraphs without vertices of very small degree. Then, based on the results of the last section, we argue that each subgraph in such family is small. In the third and final part of our proof we show that if this is the case, then $G$ has at most $f_t(\ell, n)$ vertices.

Before the proof of Theorem \[thm1\] we state two technical lemmata. The first one will become instrumental in the first part of our argument, when we decompose the graph $G$ into 2-connected subgraphs without vertices of small degree.

\[l:dec\] Let $n\ge k\ge 2$. For each graph $G$ with $n$ vertices and minimum degree $\delta(G)\ge n/k + k$, there exists an $s<k$ and a set of vertices $U\subset V(G)$, $|U| \le s-1$, such that $G-U$ is a union of $s$ vertex-disjoint 2-connected graphs.

Consider a sequence $U_0,U_1,\dots, U_{t}=U$ of subsets of $V$ which starts with $U_0=\emptyset$ and, if $G-U_i$ contains a cut vertex $v_i$, we put $U_{i+1}=U_i\cup \{v_i\}$. The process terminates when each component of $G-U_i$ is 2-connected. Note that in each step the number of components of a graph increases by at least one, so $G-U_i$ has at least $i+1=|U_i|+1$ components. Moreover, the process must terminate for $t< k-1$ since otherwise the graph $G-U_{k-1}$ would have $n-k+1$ vertices, at least $k$ components, and the minimum degree at least $n/k+1$ which, clearly, is impossible. Hence the graph $G-U=G-U_t$ has $n-t$ vertices, $s\ge |U|+1= t+1$ components, and the minimum degree larger than $n/k+1$. Finally, let us notice that, again, since each component has more than $n/k$ vertices, we must have $s<k$.

The following result is crucial for the final stage of our argument, when we show that each graph $G$ with a large minimum degree, which admits a certain block-like decomposition into small 2-connected subgraphs, cannot be too large.

\[l:V\] For a given set $V$ and positive integers $\ell, s,t,n\ge 2$, satisfying $(t-1)(2\ell-1)\le n-1 < t(2\ell-1)$, let $V_1, V_2, \dots, V_s$ be subsets of $V$ such that

1.  \[it:1\] $V = V_1\cup V_2\cup \dots \cup V_s$,

2.  \[it:2\] $|V_i|\le 2\ell-1$ for $i=1,2,\dots,s$,

3.  \[it:3\] $|V\setminus V_i|\le n-1$ for $i=1,2,\dots,s$,

4.  \[it:4\] $|V_1| + |V_2| + \cdots + |V_s| \le |V| + s -1$.

Then $$|V|\le f_t(\ell,n)= \max \{t(2\ell-1),n+\lfloor (n-1)/t\rfloor\}\,.$$

Note first that if $s\le t$, then \[it:1\] and \[it:2\] imply that $|V|\le t(2\ell-1)$. Thus, let us assume that $s\ge t+1$. Then, $$\begin{aligned}
        s(n-1)
        &\overset{\textrm{\ref{it:3}}}{\ge}&
        \sum_{i=1}^s |V\setminus V_i|=s|V| - (|V_1|+|V_2|+\dots+|V_s|) \\
        &\overset{\textrm{\ref{it:4}}}{\ge }&
        s|V| - (|V|+s-1) = (s-1)|V| - (s-1),
    \end{aligned}$$ and thereby $$\hfill  |V| \le \frac{s}{s-1}(n-1) +1 = n + \frac{n-1}{s-1}\le n+ \frac{n-1}{t}.$$ Since $|V|$ is an integer, the assertion follows.

Since we have already bound $R(C_{2\ell},K_{1,n})$ from below in Section \[sec:lower\], we are left with the task of showing that $$\label{l:up}
R(C_{2\ell},K_{1,n}) \le f_t(\ell,n)+1.$$ For this purpose, let $t\ge 2$, $$\label{eq:el}
\ell \ge  (19.1t)^9> 360(t+1)^4\cdot K(t+1),$$ where $K(t+1) = 24\cdot 10^6 (t+1)^5$ is a function defined in , and $$(t-1)(2\ell-1) \le n-1 < t(2\ell-1).$$ Moreover, let $G=(V,E)$ be a $C_{2\ell}$-free graph on $$\label{eq:Nf}
|V| 
=f_t(\ell,n)+1$$ vertices such that ${    \sbox{\myboxA}{$\m@thG$}    \setbox\myboxB\null    \ht\myboxB=\ht\myboxA    \dp\myboxB=\dp\myboxA    \wd\myboxB=0.75\wd\myboxA    \sbox\myboxB{$\m@th\overline{\copy\myboxB}$}    \setlength\mylenA{\the\wd\myboxA}    \addtolength\mylenA{-\the\wd\myboxB}    \ifdim\wd\myboxB<\wd\myboxA    \rlap{\hskip 0.5\mylenA\usebox\myboxB}{\usebox\myboxA}    \else
    \hskip -0.5\mylenA\rlap{\usebox\myboxA}{\hskip 0.5\mylenA\usebox\myboxB}    \fi} \nsupseteq K_{1,n}$ (or equivalently, $\Delta({    \sbox{\myboxA}{$\m@thG$}    \setbox\myboxB\null    \ht\myboxB=\ht\myboxA    \dp\myboxB=\dp\myboxA    \wd\myboxB=0.75\wd\myboxA    \sbox\myboxB{$\m@th\overline{\copy\myboxB}$}    \setlength\mylenA{\the\wd\myboxA}    \addtolength\mylenA{-\the\wd\myboxB}    \ifdim\wd\myboxB<\wd\myboxA    \rlap{\hskip 0.5\mylenA\usebox\myboxB}{\usebox\myboxA}    \else
    \hskip -0.5\mylenA\rlap{\usebox\myboxA}{\hskip 0.5\mylenA\usebox\myboxB}    \fi}) \le n-1$).

Recall that $f_t(\ell, n) = \max\{t(2\ell-1), n+ \lfloor (n-1)/t\rfloor \}$ and observe that $$\label{eq:estimate}
    (n-1)+\frac{ t(2\ell-1)}{t+1} <
    f_t(\ell,n)    < (t+1)(2\ell-1)\,.$$ Indeed, the upper bound follows immediately from the fact that $n-1 < t(2\ell - 1)$, so it is enough to verify the lower bound for $f_t(\ell,n)$. If $$(n-1) + \frac{t(2\ell-1)}{t+1} < {t(2\ell-1)}$$ then we are done, otherwise we have $$\frac{t(2\ell-1)}{t+1}\le\frac{n-1}{t}$$ and, since $f_t(\ell,n)\ge n+\lfloor \frac{n-1}{t}\rfloor$, holds as well.

Our aim is to show that $G$ contains a family of 2-connected subgraphs $G_i=(V_i,E_i)$, $i=1,2,\dots,s$, such that their vertex sets fulfil the conditions \[it:1\]-\[it:4\] listed in Lemma \[l:V\]. We first apply Lemma \[l:dec\] to $G$ with $k = \frac{(t+1)^2+1}{t}$. We are allowed to do this, because tells us that $$\label{eq:dd}
\begin{aligned}
\delta(G) &= |V|-1 - \Delta({    \sbox{\myboxA}{$\m@thG$}    \setbox\myboxB\null    \ht\myboxB=\ht\myboxA    \dp\myboxB=\dp\myboxA    \wd\myboxB=0.75\wd\myboxA    \sbox\myboxB{$\m@th\overline{\copy\myboxB}$}    \setlength\mylenA{\the\wd\myboxA}    \addtolength\mylenA{-\the\wd\myboxB}    \ifdim\wd\myboxB<\wd\myboxA    \rlap{\hskip 0.5\mylenA\usebox\myboxB}{\usebox\myboxA}    \else
    \hskip -0.5\mylenA\rlap{\usebox\myboxA}{\hskip 0.5\mylenA\usebox\myboxB}    \fi}) \ge f_t(\ell,n)-(n-1)>  \frac{t(2\ell-1)}{t+1}\ge \frac{t|V|}{(t+1)^2}
\end{aligned}$$ However, both $|V|$ and $\ell$ are much larger than $t$, in particular, $|V|\ge 2\ell> (19.1t)^9$. Hence, $$\delta(G) \ge \frac{t|V|}{(t+1)^2} 
>
\frac{t}{(t+1)^2+1}|V| + \frac{(t+1)^2+1}{t}$$ and the assumptions of Lemma \[l:dec\] hold with $k= \frac{(t+1)^2+1}{t}\le t+3$. Thus, there exists $s\le t+2$ and a set of vertices $U\subset V$, $|U|\le s-1$, such that $G-U$ is a union of $s$ vertex-disjoint, 2-connected graphs, $G'_i=(V'_i, E'_i)$. Note that since $|U|\le t+1$ and $\ell > 4K(t+1)$ are large, $$\label{eq:deltaup}
\delta(G'_i) \ge \delta(G)-|U| > \frac{2(2\ell-1)}{3} - (t+1) > \ell + K(t+1).$$ Moreover, clearly, $|V'_i|\le |V| <(t+1)2\ell$, so Lemma \[l:small\] applied to $G'_i$, with $c=t+1$, gives $$\label{eq:Gi}
|V'_i| \le 2\ell - 1 \quad \textrm{for}\quad i=1,2,\dots,s.$$ Now, for every $i=1,2,\dots,s$, we define $$U_i = \{u\in U: \deg_G(u, V'_i) \ge 4t\},\quad  V_i = V'_i\cup U_i, \quad \textrm{and}\quad\ G_i = G[V_i].$$ We will show that the sets $V_1, V_2, \dots, V_s$ satisfy the conditions \[it:1\]-\[it:4\] of the hypothesis of Lemma \[l:V\].

In order to verify \[it:1\] observe that since the minimum degree of $G$ is large, i.e. $\delta(G)\ge 8t^2$, every vertex $u\in U$ belongs to at least one of the sets $U_i$, and therefore $V = V_1 \cup V_2 \cup \dots\cup V_s$.

To prove that $|V_i|\le 2\ell -1$, let us assume that $|V_i|\ge 2\ell$. Now take any subset $\hat U_i$ of $U_i$, with $|\hat U_i| = 2\ell - |V_i'|$ elements and set $H_i=G[V'_i\cup \hat U_i]$. Note that $H_i$ has $2\ell$ vertices. We will argue that $H_i$ is hamiltonian. To this end, consider the closure of $H_i$. From we know that all vertices from $V'_i$ have degree at least $\delta(G'_i)> \ell+K(t+1)$, so in the closure of $H_i$ the set $V'_i$ spans a clique of size at least $2\ell-|U|\ge 2\ell -t-1$. On the other hand, each vertex from $\hat U_i$ has in $V'_i$ at least $4t$ neighbours, so the closure of $H_i$ is the complete graph and therefore, by Lemma \[l:BC\], $H_i$ is hamiltonian. However it means that $C_{2\ell}\subseteq H_i\subseteq G$ which contradicts our assumption that $G$ is $C_{2\ell}$-free. Consequently, for every $i=1,2,\dots, s$, we have $|V_i|\le 2\ell-1$, as required by \[it:2\].

Note that from it follows that $|V'_i|> \delta(G'_i)> \ell$. Since $U\setminus U_i$ sends at most $4t|U|\le 4t(t+1)<\ell$ edges to the set $V'_i$, there exists a vertex $v_i\in V'_i\subseteq V_i$ which has all its neighbours in $G_i$. It means however that, since ${    \sbox{\myboxA}{$\m@thG$}    \setbox\myboxB\null    \ht\myboxB=\ht\myboxA    \dp\myboxB=\dp\myboxA    \wd\myboxB=0.75\wd\myboxA    \sbox\myboxB{$\m@th\overline{\copy\myboxB}$}    \setlength\mylenA{\the\wd\myboxA}    \addtolength\mylenA{-\the\wd\myboxB}    \ifdim\wd\myboxB<\wd\myboxA    \rlap{\hskip 0.5\mylenA\usebox\myboxB}{\usebox\myboxA}    \else
    \hskip -0.5\mylenA\rlap{\usebox\myboxA}{\hskip 0.5\mylenA\usebox\myboxB}    \fi}\not\supseteq K_{1,n}$, the set $V\setminus V_i$, which contains only vertices which are not adjacent to $v_i$, has at most $n-1$ elements, and so \[it:3\] holds.

Finally, to verify \[it:4\] consider an auxiliary bipartite graph $F=(V_F, E_F)$, where $V_F=\{V'_1, V'_2, \dots, V'_s\}\cup U$ and $$E_F=\{uV'_i:u\in U_i\}.$$ We claim that $F$ is a forest. Indeed, assume for a sake of contradiction that $F$ contains a cycle $C=V'_{i_1}u_{j_1}\dots V'_{i_w}u_{j_w}V'_{i_{w+1}}$, ${i_1} = {i_{w+1}}$. Observe that every vertex $u_{j_x}$, $x= 1,2,\dots,w$, has at least two neighbours in both sets $V'_{i_x}$ and $V'_{i_{x+1}}$. Moreover, $\delta(G'_i) > \ell+1$ and $|V'_i| \le 2\ell - 1$, so from Lemma \[l:W\] it follows that any two vertices of $V'_i$ can be connected by a path of length $y$ for every $y=2,3,\dots, |V_i|-1$. Therefore, since $w\le |U|\le t+1\le \ell/4$, the existence of $C$ in $F$ implies the existence of a cycle $C_{2\ell}$ in $G$, contradicting the fact that $G$ is $C_{2\ell}$-free.

Since $F$ is a forest it contains at most $|U|+s-1$ edges, i.e. $$\sum_{u\in U}\deg_F(u) \le |U|+s-1.$$ Note that in the sum $|V_1|+|V_2|+\cdots+|V_s|$ each vertex from $\bigcup_i V'_i = V\setminus U$ is counted once, and each vertex $u\in U$ is counted precisely $\deg_F(u)$ times, so $$|V_1|+\dots +|V_s| = |V| -|U|+\sum_{u\in U}\deg_F(u)  \le  |V|+s-1,$$ as required by \[it:4\].

Now we can apply Lemma \[l:V\] and infer that $|V|\le f_t(\ell,n)$ while we have assumed that $|V|=f_t(\ell,n)+1$. This final contradiction completes the proof of the upper bound for $R(C_{2\ell}, K_{1,n})$ and, together with , concludes the proof of Theorem \[thm1\].

[^1]: The first author was partially supported by National Science Centre, Poland, grant 2017/27/B/ST1/00873. The third author was partially supported by NSFC under grant numbers 11601527, 11971011, and 11801520.
