heightadjust=object, valign=c

# The extremal number of cycles with all diagonals

Domagoj Bradač Department of Mathematics, ETH, Zürich, Switzerland. Research
supported in part by SNSF grant 200021_196965. Emails: {domagoj.bradac,
abhishek.methuku<EMAIL_ADDRESS>Abhishek
Methuku11footnotemark: 1 Benny Sudakov11footnotemark: 1

###### Abstract

In 1975, Erdős asked the following natural question: What is the maximum
number of edges that an $n$-vertex graph can have without containing a cycle
with all diagonals? Erdős observed that the upper bound $O(n^{5/3})$ holds
since the complete bipartite graph $K_{3,3}$ can be viewed as a cycle of
length six with all diagonals.

In this paper, we resolve this old problem. We prove that there exists a
constant $C$ such that every $n$-vertex with $Cn^{3/2}$ edges contains a cycle
with all diagonals. Since any cycle with all diagonals contains cycles of
length four, this bound is best possible using well-known constructions of
graphs without a four-cycle based on finite geometry. Among other ideas, our
proof involves a novel lemma about finding an _almost-spanning_ robust
expander which might be of independent interest.

##  1 Introduction

One of the most central topics in extremal combinatorics, the Turán problem,
asks how many edges are needed in an $n$-vertex graph to guarantee the
existence of a certain substructure. In this paper we resolve the problem of
finding a cycle with all diagonals and develop a novel method which may have
other applications.

The study of extremal problems for cycles goes back to the influential result
of Mantel [34] from 1907 on triangle-free graphs, and the work of Erdős [12]
connecting Sidon sets with the extremal problem for four-cycles. Since then
Turán-type problems have been extensively studied, which lead to the
development of many tools and methods, with applications in many other fields
such as discrete geometry and information theory. Formally, the _extremal
number_ of a graph $F$, introduced by Turán in 1941 and denoted by
$\mathrm{ex}(n,F)$, is the maximum possible number of edges in an $n$-vertex
graph not containing $F$ as a subgraph. The celebrated Erdős–Stone–Simonovits
theorem [14, 13] states
$\mathrm{ex}(n,F)=(1-\frac{1}{\chi(F)-1}+o(1))\binom{n}{2}.$ This result
implies that if $F$ is not bipartite, $\mathrm{ex}(n,F)=\Theta(n^{2})$.
However, if $F$ is bipartite, it only shows that $\mathrm{ex}(n,F)=o(n^{2})$.
In fact, there are still only a few bipartite graphs $F$ for which the order
of magnitude of $\mathrm{ex}(n,F)$ is known. A fundamental result of Bondy and
Simonovits [3] shows that $\mathrm{ex}(n,C_{2\ell})=O(n^{1+1/\ell})$, where
$C_{2\ell}$ denotes a cycle of length $2\ell$. Matching lower bound
constructions are only known for cycles of length four, six and ten [5, 41,
17]. In particular, it is known that $\mathrm{ex}(n,C_{4})=\Theta(n^{3/2})$.
For the complete bipartite graph $K_{s,t}$, a well-known result of Kővári, Sós
and Turán [30] from 1954 shows the upper bound
$\mathrm{ex}(n,K_{s,t})=O(n^{2-1/s})$ holds for any $t\geq s$, and matching
lower bound constructions are known when $s=t=2,3$ and when $t$ is large
enough compared to $s$, see for example [28, 1, 7]. Even the extremal numbers
of simple graphs such as the cube and $K_{4,4}$ remain elusive.

Questions about finding cycles in graphs with given properties have been
extensively studied, see for instance [9, 11, 39, 33], and the nice survey
[40]. In particular, there has been a lot of research on problems concerning
finding cycles with chords. In 1975, Erdős [15] conjectured that there is a
constant $c$ such that any $n$-vertex graph with $cn$ edges contains two
cycles $C_{1},C_{2}$ where the edges of $C_{2}$ are chords of the cycle
$C_{1}$. Bollobás [2] later proved this conjecture. Extending his result,
Chen, Erdős and Staton [8] proved that there is a constant $c_{k}$ such that
any $n$-vertex graph with $c_{k}n$ edges contains $k$ cycles
$C_{1},\ldots,C_{k}$, such that the edges of $C_{i+1}$ are chords of the cycle
$C_{i}$. Fernández, Kim, Kim and Liu [19] strengthened the aforementioned
result of Bollobás by finding cycles $C_{1},C_{2}$ where the edges of $C_{2}$
do not cross each other and form chords of the cycle $C_{1}$. Recently,
improving an old result of Chen, Erdős and Staton [8], Draganić, Methuku,
Munhá Correia and Sudakov [10] showed that any $n$-vertex graph with
$\Omega(n\log^{8}n)$ edges contains a cycle with at least as many chords as it
has vertices.

In this paper we are interested in finding a cycle containing all chords
joining vertices at maximum distance on the cycle. Such chords are called
_diagonals_. Since the extremal number of any non-bipartite graph is
$\Theta(n^{2})$, it is more interesting to find an even cycle with all
diagonals. Formally, a cycle of length $2\ell$ with all diagonals, denoted
$C^{\textrm{dia}}_{2\ell}$, is a graph with the vertex set
$V(C^{\textrm{dia}}_{2\ell})\coloneqq\\{x_{1},\dots,x_{2\ell}\\}$ and the edge
set $E(C^{\textrm{dia}}_{2\ell})\coloneqq
E(C_{2\ell})\cup\\{x_{i}x_{i+\ell}\mid i=1,\dots,\ell\\}$ (see Figure 1).

Figure 1: Two different ways of drawing the graph $C^{\textrm{dia}}_{10}$.

In 1975, Erdős [16] asked the following natural extremal question: What is the
maximum number of edges that an $n$-vertex graph can have if does not contain
a cycle with all diagonals? In 1995, this problem was reiterated in a well-
known paper of Pyber, Rödl, and Szemerédi [36] on the Erdős-Sauer problem [16,
24]. Erdős [16] observed that the upper bound
$\mathrm{ex}(n,K_{3,3})=O(n^{5/3})$ holds since the complete bipartite graph
$K_{3,3}$ can be viewed as the cycle of length six with all diagonals. In this
paper, we resolve this old problem.

######  Theorem 1.1.

There exists a constant $C>0$ such that every $n$-vertex graph with at least
$Cn^{3/2}$ edges contains a cycle with all diagonals.

Observe that every cycle with all diagonals contains cycles of length four.
Hence, by the aforementioned lower bound
$\mathrm{ex}(n,C_{4})=\Omega(n^{3/2})$, the bound in Theorem 1.1 is tight up
to a constant factor.

Note that $C^{\textrm{dia}}_{2\ell}$ is bipartite if and only if $\ell$ is
odd. Hence, in this paper, we focus on finding a cycle
$C^{\textrm{dia}}_{2\ell}$ where $\ell=2k+1$ for some integer $k\geq 1$. It is
convenient to view the graph
$C^{\textrm{dia}}_{2\ell}=C^{\textrm{dia}}_{4k+2}$ as an “odd cycle of four-
cycles" of length $2k+1$. See the drawing on the right in Figure 1 for an
example (and see Claim 4.9 for a formal argument). Note that one of the four-
cycles in the figure contains a “twist”, otherwise the resulting graph is not
bipartite.

Related results. Let us now mention some closely related results, and briefly
explain how our approach differs from the existing methods and the
difficulties we encounter.

The _$\ell$ -prism_ $C_{\ell}^{\square}:=C_{\ell}\square K_{2}$ is the
Cartesian product of the cycle $C_{\ell}$ of length $\ell$ and an edge. In
other words, $C_{\ell}^{\square}$ consists of two vertex disjoint
$\ell$-cycles and a matching joining the corresponding vertices on these two
cycles. For instance, $C_{4}^{\square}$ is the notorious cube graph, and the
best known upper bound is $\mathrm{ex}(n,C_{4}^{\square})=O(n^{8/5})$ [35].
Observe that the _$\ell$ -prism_ $C_{\ell}^{\square}$ and
$C^{\textrm{dia}}_{2\ell}$ are both “cycles of four-cycles" on $2\ell$
vertices but the crucial difference is that in $C^{\textrm{dia}}_{2\ell}$ one
of the four-cycles contains a twist, while in $C_{\ell}^{\square}$ none of the
four-cycles have a twist. This is the reason why, if $\ell$ is odd,
$C^{\textrm{dia}}_{2\ell}$ is bipartite but $C_{\ell}^{\square}$ is not
bipartite. He, Li and Feng [22] studied the odd prisms and determined
$\mathrm{ex}(n,C_{2k+1}^{\square})$ for $k\geq 1$ and large $n$. In that case
$\mathrm{ex}(n,C_{2k+1}^{\square})=\Theta(n^{2})$ since $C_{2k+1}^{\square}$
is not bipartite. Gao, Janzer, Liu and Xu [20] studied the even prisms and
showed that $\mathrm{ex}(n,C_{2\ell}^{\square})=\Theta(n^{3/2})$ for every
$\ell\geq 4$. Let us compare the problem of finding $C_{2\ell}^{\square}$ with
that of finding $C^{\textrm{dia}}_{2\ell}$. As discussed above,
$C_{2\ell}^{\square}$ corresponds to an “even cycle of four-cycles" but
$C^{\textrm{dia}}_{2\ell}$ corresponds to an “odd cycle of four-cycles". Since
forcing an odd cycle in a graph is significantly more difficult than forcing
an even cycle (because the extremal number of an odd cycle is
$\mathrm{ex}(n,C_{2k+1})=\Omega(n^{2})$), we need a new approach for finding
$C^{\textrm{dia}}_{2\ell}$, which we discuss in detail in Section 2.

Next, let us mention a problem about finding (topological) cycles in pure
simplicial complexes with an interesting parallel to the problem of finding
$C^{\textrm{dia}}_{2\ell}$ and $C_{2\ell}^{\square}$. A $3$-uniform hypergraph
$\mathcal{H}$ corresponds to the $2$-dimensional pure simplicial complex
obtained by taking the downset generated by the set of edges of $\mathcal{H}$.
A tight cycle of even length is homeomorphic to the cylinder $S^{1}\times
B^{1}$, while a tight cycle of odd length is homeomorphic to the Möbius strip
(see Figure 1 in [38]). In [31], Kupavskii, Polyanskii, Tomon, and Zakharov
proved that every $3$-uniform hypergraph with $n$ vertices and at least
$n^{2+\alpha}$ edges contains a triangulation of the cylinder. However, their
proof does not work for finding a triangulation of the Möbius strip. This is
because they reduce this problem to a problem about finding rainbow cycles in
certain properly edge colored graphs where an even cycle corresponds to a
cylinder, but an odd cycle corresponds to a Möbius strip. As the extremal
number of odd cycles is $\Omega(n^{2})$, their method completely breaks down
for finding a triangulation of the Möbius strip. Note that, interestingly, a
triangulation of the Möbius strip is analogous to a cycle with all diagonals
(as they both contain a twist) and a triangulation of the cylinder is
analogous to a prism $C_{2\ell}^{\square}$. Overcoming this issue, Tomon [38]
proved that every $3$-uniform hypergraph with $n$ vertices and at least
$n^{2+\alpha}$ edges contains a triangulation of the Möbius strip by passing
to a subhypergraph which is an expander (where subsets of $1$-dimensional
faces expand via $2$-dimensional faces). Along these lines, a natural approach
for finding a cycle with all diagonals in a graph $G$ would be to pass to an
expander where four-cycles expand via edges. However, this approach
immediately fails for our problem because it is completely possible that such
an expander is bipartite in our case, hence it is impossible to find an odd
cycle in it. This issue is explained in more detail in Section 2. To overcome
this fundamental obstacle, we develop a novel lemma that finds an almost-
spanning expander.

Let us now discuss the extremal numbers of two more natural graphs containing
four-cycles: the _grid_ and the _blow-up of a cycle_. For a positive integer
$t$, the grid $F_{t,t}:=P_{t}\square P_{t}$ is the Cartesian product of two
vertex-disjoint paths $P_{t}$. Since $F_{t,t}$ contains four-cycles, we have
$\mathrm{ex}(n,F_{t,t})=\Omega(n^{3/2})$. Bradač, Janzer, Sudakov and Tomon
[4] showed that $\mathrm{ex}(n,F_{t,t})=O(n^{3/2})$. Gao, Janzer, Liu and Xu
[20] later gave a very simple proof of this bound. Roughly speaking, it is
easier to find the grid compared to the graphs $C^{\textrm{dia}}_{2\ell}$ or
$C_{2\ell}^{\square}$ because the four-cycles in the grid are not arranged in
a cyclic manner. Finally, let us consider blow-ups of cycles. The $2$-blowup
of a cycle is the graph obtained by replacing each vertex of the cycle with an
independent set of size $2$ and each edge of the cycle by a four-cycle. Jiang
and Newman [27] asked the following question. What is the maximum number of
edges that an $n$-vertex graph can have without containing the $2$-blowup of a
cycle? Janzer [23] proved that an upper bound of $O(n^{3/2}(\log n)^{7/2})$
holds, and it is known that a lower bound of $\Omega(n^{3/2})$ holds. It is an
interesting question to decide whether the logarithmic factor in the upper
bound can be removed.

Notation. For a set $S$, we denote its complement by $\overline{S}$. For a
graph $G$, let $v(G)$ denote the number of vertices of $G$, let $e(G)$ denote
the number of edges of $G$ and let $e_{G}(X,Y)$ denote the number of edges of
$G$ with one endpoint in $X$ and another endpoint in $Y$. For a set
$S\subseteq V(G)$, let $e_{G}(S)$ denote the number of edges of $G$ spanned by
$S$, and let $N_{G}(S)\coloneqq\\{y\not\in S\mid xy\in E(G)\text{ for some
}x\in S\\}$ be the neighbourhood of $S$ in $G$. Sometimes we write $N(S)$ and
$e(S)$ instead of $N_{G}(S)$ and $e_{G}(S)$ respectively if the graph $G$ is
clear from context. For any two distinct vertices $u,v\in V(G)$, let
$d_{G}(u,v)$ denote the size of the common neighbourhood of $u$ and $v$ in
$G$. Let $\delta(G)$ and $\Delta(G)$ denote the minimum degree and maximum
degree of $G$ respectively. For a set of vertices $V^{\prime}\subseteq V(G)$,
let $G\setminus V^{\prime}$ denote the graph obtained by removing the vertices
of $V^{\prime}$ from $G$, and for a set of edges $E^{\prime}\subseteq E(G)$,
let $G-E^{\prime}$ denote the graph obtained by removing the edges in
$E^{\prime}$ from $G$.

Organisation of the paper. In Section 2, we give a detailed overview of the
proof of Theorem 1.1. In Section 3, we introduce the notion of edge-expansion
we use and prove a preliminary lemma. In Section 4, we prove Theorem 1.1 which
is split into three well-defined subsections. Our main lemma about finding an
almost-spanning expander is proved in Section 4.1. Finally, we give some
concluding remarks and open problems in Section 5.

##  2 Overview of the proof

Even though our proof is relatively short, in this section we give a detailed
overview of the proof of Theorem 1.1 highlighting certain novel aspects of the
proof. Suppose $G$ is an $n$-vertex graph with $Cn^{3/2}$ edges where $C$ is a
large enough constant, and we may assume $G$ is bipartite using standard
arguments. Our aim is to show that $G$ contains a cycle with all diagonals.

As noted in the introduction, since a cycle of length $2\ell$ with all
diagonals, $C^{\textrm{dia}}_{2\ell}$, is bipartite if and only if $\ell$ is
odd, we assume $\ell=2k+1$ for some integer $k\geq 1$, and we view the graph
$C^{\textrm{dia}}_{2\ell}=C^{\textrm{dia}}_{4k+2}$ as an “odd cycle of four-
cycles” of length $2k+1$ as shown in Figure 1 (see Claim 4.9 for a formal
argument).

This suggests the following natural strategy. Consider an auxiliary graph
$\Gamma_{0}$ whose vertex set is the set of edges of $G$ and $xy,uv\in E(G)$
are adjacent in $\Gamma_{0}$ if $xyuv$ is a four-cycle in $G$. We call
$\Gamma_{0}$ the _$C_{4}$ -graph_ of $G$. By a standard supersaturation
result, $G$ has at least $\Omega(C^{4}n^{2})$ four-cycles. Hence, $\Gamma_{0}$
has $N=Cn^{3/2}$ vertices and at least $\Omega(C^{4}n^{2})=\Omega(N^{4/3})$
edges. Observe that a cycle of length $2k+1$ in $\Gamma_{0}$ corresponds to a
copy of $C^{\textrm{dia}}_{4k+2}$ in $G$ if the vertices of the cycle
correspond to pairwise disjoint edges in $G$; otherwise, we obtain a
_degenerate_ copy of $C^{\textrm{dia}}_{4k+2}$ in $G$. Thus, our goal is to
embed an _odd_ cycle in $\Gamma_{0}$ which corresponds to a non-degenerate
copy of $C^{\textrm{dia}}_{4k+2}$ in $G$; call such an odd cycle in
$\Gamma_{0}$, _proper_. To find such an embedding, it is very helpful if we
can find paths connecting pairs of vertices in $\Gamma_{0}$ in a robust manner
i.e., avoiding a given set of already embedded vertices in $G$. Using
expansion is a standard way of achieving this, so it is natural to take a
subgraph $\Gamma\subseteq\Gamma_{0}$ which is an expander, and try to embed an
odd cycle in $\Gamma$.

We, however, encounter a fundamental difficulty with the above strategy. Note
that since the extremal number of the four-cycle is less than
$n^{3/2}=N/C=v(\Gamma_{0})/C,$ there is no independent set of size $N/C$ in
$\Gamma_{0}$ i.e., $\Gamma_{0}$ is far from being bipartite in some sense. So
there are odd cycles in $\Gamma_{0}$ but when we pass to the expander subgraph
$\Gamma\subseteq\Gamma_{0}$, it is quite possible that $v(\Gamma)$ is much
smaller than $v(\Gamma_{0})$ and $\Gamma$ can even be bipartite, in which
case, there is no hope for finding an odd cycle in $\Gamma$ (let alone, a
proper odd cycle).

To overcome the above difficulty, we prove the following lemma (Lemma 2.1). We
believe this lemma is of independent interest and similar ideas may have other
applications (see Lemma 4.7 for its formal statement). Note that since every
graph contains an expander, without loss of generality, we may assume the host
graph $G$ is an expander. In our proof we actually need that $G$ has very
strong edge expansion; for this, we adopt the notion of $\alpha$-maximality
from Tomon [38] (see Definition 3.1). Moreover, we also need that the maximum
degree of $G$ is close to its average degree and to guarantee this, we remove
a carefully chosen set of vertices from a $1/2$-maximal subgraph: this affects
the expansion of very small sets but all large enough sets (of size up to
$v(G)/2$) in $G$ still expand extremely well (see Lemma 3.3).

######  Lemma 2.1.

If $G$ is an edge-expander, then its $C_{4}$-graph $\Gamma_{0}$ contains an
almost-spanning (robust) expander $\Gamma$.

More precisely, Lemma 2.1 shows that we obtain an excellent robust (vertex)
expander $\Gamma$ by removing only a small proportion of vertices and edges
from $\Gamma_{0}$ i.e., $v(\Gamma)\geq(1-\varepsilon)v(\Gamma_{0})$ for some
small $\varepsilon>0$. This ensures that the independence number of $\Gamma$
is at most $v(\Gamma_{0})/C\leq v(\Gamma)/2C$, so it is now feasible to find a
proper odd cycle in $\Gamma$.

Before outlining the proof of Lemma 2.1, let us sketch how to complete the
proof assuming the lemma holds. Since Lemma 2.1 ensures
$v(\Gamma)\geq(1-\varepsilon)v(\Gamma_{0})=(1-\varepsilon)N\geq Cn^{3/2}/2$, a
simple supersaturation argument implies that $\Gamma$ is _locally-dense_ in
the following sense: For any $U\subseteq V(\Gamma)$ with $|U|\geq N/100,$ we
have $e(\Gamma[U])\geq\Omega(C^{4}n^{2}).$ Since $\Gamma$ is a robust
expander, starting at any given vertex in $\Gamma$, almost all other vertices
of $\Gamma$ can be reached by a short _proper_ path. Moreover, the set of
these reachable vertices contains many edges of $\Gamma$ because $\Gamma$ is
locally-dense. Using this, we obtain that most pairs of vertices $x,y$ in
$\Gamma$ are connected by a short odd proper path $P_{o}(x,y)$ as well as a
short even proper path $P_{e}(x,y)$ in a robust manner i.e., avoiding a small
set of vertices in $G$ but it is still possible that $P_{o}(x,y)$ and
$P_{e}(x,y)$ have a common vertex in $G$ (and to establish this robustness
property, we actually show that the edges of the expander $\Gamma$ correspond
to four cycles in $G$ in which any opposite pair of vertices has small
codegree, see the last paragraph of the proof overview for more details).
Combining this with ideas from Letzter [32], we obtain a pair $x,y$ in
$\Gamma$ such that there are linearly many proper paths $\\{Q_{i}(x,y)\\}_{i}$
connecting $x$ and $y$, $P_{o}(x,y)$ and $P_{e}(x,y)$ are defined, and
moreover, every vertex of $G$ in $P_{o}(x,y)$ and $P_{e}(x,y)$ does not appear
on too many of the paths $\\{Q_{i}(x,y)\\}_{i}$. This implies that there is a
proper path $Q_{j}(x,y)$ such that either $Q_{j}(x,y)\cup P_{o}(x,y)$ or
$Q_{j}(x,y)\cup P_{e}(x,y)$ is the desired proper odd cycle in $\Gamma$.

Let us now sketch the proof of Lemma 2.1 (ignoring robustness for simplicity).
We first argue that all sets of size at least $\varepsilon N$ and at most
$0.99N$ in $\Gamma_{0}$ expand well. Suppose for a contradiction that there is
a set $E_{b}\subseteq V(\Gamma_{0})$ with $\varepsilon N\leq|E_{b}|\leq 0.99N$
that does not expand i.e., $N_{\Gamma_{0}}(E_{b})<\delta|E_{b}|$ for some
$\delta>0$. Let $E_{p}\coloneqq N_{\Gamma_{0}}(E_{b})$ and let $E_{r}\coloneqq
V(\Gamma_{0})\setminus(E_{b}\cup E_{p})$. Note that $E_{b},E_{p},E_{r}$ are
vertex sets in $\Gamma_{0}$, so they are edge sets in $G$. For convenience,
call the edges of $G$ in $E_{b},E_{p},E_{r}$, _blue_ , _purple_ and _red_
respectively. We now partition the vertices of $G$ into four sets $P,R,B,U$ as
follows: Roughly speaking, a vertex $v\in V(G)$ is in $P$ if at least half of
the edges incident to $v$ are purple; $v$ is in $R$ if most of the edges
incident to $v$ are red; $v$ is in $B$ if most of the edges incident to $v$
are blue; $v$ is in $U$ if there are sufficiently many blue edges as well as
red edges incident to $v$. Now, we claim that $B$ does not (edge) expand very
well in $G$. Indeed, the number of purple edges in $G$ is small (because we
assumed $|E_{p}|<\delta|E_{b}|$), and there are very few blue and red edges
between $B$ and $R$ (by the definition of $B$ and $R$), thus $e_{G}(B,R)$ is
very small. The number of edges incident to $P$ is at most four times the
number of purple edges, which is assumed to be small. This implies
$e_{G}(B,P)$ is small. Moreover, crucially, the size of $U$ must be very
small, because each vertex of $U$ provides many blue-red paths (by definition)
and if $U$ is large, we obtain a _red-red-blue-blue_ four-cycle (i.e., a four-
cycle of the form $xuyv$ where $xu,xv$ are red and $uy,vy$ are blue). However,
such a four-cycle in $G$ corresponds to an edge in $\Gamma_{0}$ between
$E_{b}$ and $E_{r}$ which is impossible. This implies that $e_{G}(B,U)$ is
also small. In total, we obtain that
$e_{G}(B,\overline{B})=e_{G}(B,R)+e_{G}(B,P)+e_{G}(B,U)$ is very small, i.e.,
$B$ does not expand well in $G$, as claimed. On the other hand we know that
all large enough sets (of size at most $v(G)/2$) in $G$ expand very well, so
either $|B|$ or $|\overline{B}|$ is very small, which in turn implies that
either $|E_{b}|$ or $|E_{r}|$ is very small, a contradiction. Hence, all sets
of size at least $\varepsilon N$ and at most $0.99N$ in $\Gamma_{0}$ expand
well, as desired. Now, removing a maximal non-expanding set among the sets of
size at most $0.99N$ in $\Gamma_{0}$, we obtain a (vertex) expander $\Gamma$.
Since such a maximal set must have size at most $\varepsilon N$, $\Gamma$ is
an almost-spanning expander of $\Gamma_{0}$, as required by Lemma 2.1.

Let us highlight that we actually need that sets in $\Gamma$ vertex-expand
robustly i.e., while also avoiding a given set $B\subseteq V(G)$ of size, say,
$|B|=\Omega(\log n)$. This is not straightforward to achieve. If we simply
remove all vertices in $\Gamma$ corresponding to the edges of $G$ incident to
$B$, we may lose more than $\Theta(\sqrt{n}\log n)$ vertices from $\Gamma$
which makes it impossible for small sets in $\Gamma$ to expand robustly (in
which case, starting at a vertex, we cannot robustly reach other vertices and
our proof fails). To overcome this difficulty, we prove that $\Gamma$ actually
satisfies two crucial properties: $\mathrm{(i)}$ $\Gamma$ is a robust expander
in a very strong sense (that ties vertex and edge expansion together) as
follows: every set $S$ (which is not too large) in $\Gamma$ expands well even
after the removal of any small set $F$ of edges in $\Gamma$, see Definition
4.5. $\mathrm{(ii)}$ Every edge in $\Gamma$ corresponds to a four-cycle $xyzw$
in $G$ for which both $d_{G}(x,z)$ and $d_{G}(y,w)$ are small enough. Then,
$\mathrm{(ii)}$ ensures that the number of edges in $\Gamma$ incident to a set
$S$ which have an endpoint in $B$ are small enough, so that the notion of
robustness in $\mathrm{(i)}$ can be used to show that $S$ expands well while
also avoiding $B$.

##  3 Expansion

In this section we show that every graph contains a subgraph with maximum
degree close to its average degree and with very strong edge-expansion (see
Lemma 3.3). For this we need the following notion of $\alpha$-maximal graphs.
The idea of taking a subgraph maximizing some density function dates back to
the work of Komlós and Szemerédi [29] and the definition we are going to use
has recently appeared in the work of Tomon [38].

######  Definition 3.1 ($\alpha$-maximal graphs).

Let $\alpha>0$. A graph $G$ is $\alpha$-maximal if for every subgraph $H$ of
$G$, we have

$\frac{e(H)}{v(H)^{1+\alpha}}\leq\frac{e(G)}{v(G)^{1+\alpha}}.$

In other words, if $e(G)=Cv(G)^{1+\alpha}$, then $e(H)\leq Cv(H)^{1+\alpha}$
for every subgraph $H$ of $G$.

In [38] it is shown that $\alpha$-maximal graphs are excellent edge-expanders.
This is made precise in the following simple lemma. We include its short proof
here for completeness.

######  Lemma 3.2 (Lemma 2.5 in [38]).

Let $0<\alpha<1$, let $G$ be an $\alpha$-maximal graph on $n$ vertices, and
let $e(G)=Cn^{1+\alpha}$. Then $G$ satisfies the following properties.

  * $\mathrm{(i)}$

If $G$ is non-empty, then $C\geq 1/4$.

  * $\mathrm{(ii)}$

Let $S\subset V(G)$, and let $|S|\leq n/2$. Then $e(S,V(G)\setminus
S)\geq|S|\frac{\alpha Cn^{\alpha}}{4}$.

###### Proof.

Since $G$ is non-empty, it contains an edge. Let $H$ be the subgraph of $G$
consisting of this edge. Since $G$ is $\alpha$-maximal, we have $e(H)\leq
Cv(H)^{1+\alpha}$, so $1\leq C2^{1+\alpha}$ i.e., $C\geq 1/4$, showing (i)
holds.

Now we show (ii). We have $e(S,\overline{S})=e(G)-e(S)-e(\overline{S})\geq
C(|S|+|\overline{S}|)^{1+\alpha}-C|S|^{1+\alpha}-C|\overline{S}|^{1+\alpha}$
since $G$ is $\alpha$-maximal. Moreover, since
$\left(1+\frac{|S|}{|\overline{S}|}\right)^{1+\alpha}\geq
1+(1+\alpha)\frac{|S|}{|\overline{S}|}$, $|\overline{S}|\geq n/2$, and
$|S|\leq|\overline{S}|$ we have

$C(|S|+|\overline{S}|)^{1+\alpha}-C|\overline{S}|^{1+\alpha}-C|S|^{1+\alpha}\geq
C((1+\alpha)|S||\overline{S}|^{\alpha}-|S|^{1+\alpha})=C|S|((1+\alpha)|\overline{S}|^{\alpha}-|S|^{\alpha})\geq\alpha
C|S|(n/2)^{\alpha}.$

Noting that $(n/2)^{\alpha}\geq n^{\alpha}/4$, this proves (ii). ∎

Note that every graph $G$ contains an $\alpha$-maximal subgraph since a
subgraph $H$ of $G$ maximising the quantity $e(H)/v(H)^{1+\alpha}$ (over all
subgraphs) is $\alpha$-maximal. Thus Lemma 3.2 shows that every graph contains
a subgraph which is an excellent edge-expander. In our proof, we will also
need that the maximum degree of this subgraph is not too large. In the next
lemma we show that every graph contains a subgraph $H$ whose maximum degree is
close to its average degree, and all large enough sets in the subgraph $H$
expand very well. For convenience, we only state the lemma for $\alpha=1/2$
but it holds more generally, and may be of independent interest.

######  Lemma 3.3.

Let $C_{1},D$ be constants satisfying $1000\leq D\leq C_{1}/1000$ and let $G$
be an $n$-vertex graph with $C_{1}n^{3/2}$ edges. Then, $G$ contains an
$m$-vertex subgraph $H$ satisfying the following properties for some $C>0$.

  1. $\mathrm{(P1)}$

$e(H)=Cm^{3/2},$ where $C\geq C_{1}/2,$

  2. $\mathrm{(P2)}$

$\Delta(H)\leq CDm^{1/2},$

  3. $\mathrm{(P3)}$

for every $S\subseteq V(H)$, $e(S)\leq 2C|S|^{3/2},$

  4. $\mathrm{(P4)}$

for every $S\subseteq V(H),\frac{1000m}{D}\leq|S|\leq\frac{m}{2},$
$e_{H}(S,V(H)\setminus S)\geq|S|\frac{Cm^{1/2}}{16}$.

###### Proof.

Let $H_{0}$ be a $1/2$-maximal subgraph of $G$ and let $v(H_{0})=m$ and
$e(H_{0})=2C_{0}m^{3/2}$. Then $2C_{0}\geq C_{1}$ (since $H_{0}$ is
$1/2$-maximal). Let $U$ be the set of vertices in $H_{0}$ with degree at least
$C_{0}Dm^{1/2}$ and let $t$ denote the number of edges in $H_{0}$ incident to
$U$. Note that $|U|\leq\frac{2t}{C_{0}Dm^{1/2}}\eqqcolon s<\frac{m}{2},$ where
in the last inequality we used $D\geq 1000$. Let $W$ be a random subset of
$V(H_{0})\setminus U$ of size $s$. Then,
$\operatorname{\mathbb{E}}[H_{0}[U\cup W]]\geq ts/m.$ Indeed, any edge of
$H_{0}$ with both endpoints in $U$ is also in $H_{0}[U\cup W]$ and an edge of
$H_{0}$ with a single endpoint in $U$ appears in $H_{0}[U\cup W]$ with
probability at least $s/m.$ So there is a set $Q$ of size at most $2s<m$
vertices spanning at least $ts/m$ edges. Since $H_{0}$ is $1/2$-maximal, we
have $ts/m\leq e(H_{0}[Q])\leq 2C_{0}(2s)^{3/2}$. Rearranging and using the
definition of $s$ yields $t\leq\frac{64C_{0}m^{3/2}}{D}.$ Remove from $H_{0}$
all the $t$ edges incident to $U$, and call this new graph $H$ (which is still
on $m$ vertices) and denote $e(H)=Cm^{3/2}=2C_{0}m^{3/2}-t\geq
2C_{0}m^{3/2}-\frac{64C_{0}m^{3/2}}{D}$. Then, since $D\geq 1000$, we have
$2C_{0}\geq C\geq C_{0}\geq C_{1}/2,$ so $\mathrm{(P1)}$ holds.

Since we removed all edges incident to vertices of degree at least
$C_{0}Dm^{1/2}$ when defining $H$, we have $\Delta(H)\leq C_{0}Dm^{1/2}\leq
CDm^{1/2}$, so $\mathrm{(P2)}$ holds. Moreover, since $H_{0}$ is
$1/2$-maximal, we have $e_{H_{0}}(S)\leq 2C_{0}|S|^{3/2}$, so $e_{H}(S)\leq
2C_{0}|S|^{3/2}\leq 2C|S|^{3/2}$, so $\mathrm{(P3)}$ holds.

By Lemma 3.2 (ii), for every set $S$ satisfying $|S|\leq\frac{m}{2},$ we have
$e_{H_{0}}(S,V(H_{0})\setminus S)\geq|S|\frac{C_{0}m^{1/2}}{4}$, so
$e_{H}(S,V(H)\setminus
S)\geq|S|\frac{C_{0}m^{1/2}}{4}-t\geq|S|\frac{C_{0}m^{1/2}}{4}-\frac{64C_{0}}{D}m^{3/2}$.
Moreover, if $|S|\geq\frac{1000m}{D}$, we have
$|S|\frac{C_{0}m^{1/2}}{4}-\frac{64C_{0}}{D}m^{3/2}\geq|S|\frac{C_{0}m^{1/2}}{8}\geq|S|\frac{Cm^{1/2}}{16}.$
Thus $\mathrm{(P4)}$ holds. ∎

##  4 Proof of Theorem 1.1

In this section, we prove Theorem 1.1. Throughout the proof, we fix small
positive constants $\delta,\eta,\varepsilon$ and large constants $C_{1},D$
such that

$1\gg\varepsilon\gg\eta\gg\delta\gg 1/D\gg 1/C_{1}>0.$

Take a graph $G_{0}$ with $e(G_{0})\geq 4C_{1}v(G_{0})^{3/2}.$ Our goal is to
show that $G_{0}$ contains a cycle with all diagonals. It is convenient for us
to work with a suitable subgraph of $G_{0}$ instead of $G_{0}$. Let $G_{1}$ be
a bipartite subgraph of $G_{0}$ with $e(G_{1})\geq e(G_{0})/2\geq
2C_{1}v(G_{0})^{3/2}$, and let $G$ be the (expander) subgraph obtained by
applying Lemma 3.3 to $G_{1}$. For convenience, denote $v(G)=n$. Then
$\mathrm{(P1)}$ and $\mathrm{(P2)}$ of Lemma 3.3 ensure that $e(G)=Cn^{3/2}$
and $\Delta(G)\leq CDn^{1/2}$ for some $C\geq C_{1}$. It suffices to show that
$G$ contains a cycle with all diagonals. We introduce an auxiliary graph as
follows.

######  Definition 4.1 ($C_{4}$-graph).

For a bipartite graph $G$ with the bipartition $\\{X,Y\\}$, its $C_{4}$-graph
$\Gamma(G)$ is defined as a graph with the vertex set $V(\Gamma(G))=E(G)$ and
$xy,x^{\prime}y^{\prime}\in V(\Gamma(G))$ are adjacent in $\Gamma(G)$ if and
only if $xyx^{\prime}y^{\prime}$ is a four-cycle in $G,$ where
$x,x^{\prime}\in X,y,y^{\prime}\in Y.$ Note that every $4$-cycle in $G$
contributes $2$ edges to $\Gamma(G)$.

Let $\Gamma_{0}\coloneqq\Gamma_{0}(G)$ be the $C_{4}$-graph of $G$. A four-
cycle $xyx^{\prime}y^{\prime}$ in $G$ is called _thick_ if
$\max\\{d_{G}(x,x^{\prime}),d_{G}(y,y^{\prime})\\}\geq 10\sqrt{CD}n^{1/4},$
otherwise it is called _thin_. Let $F_{T}$ be the set of edges of $\Gamma_{0}$
corresponding to the thick four-cycles in $G$. By the following simple claim
we will be able to assume that there are not many thick four-cycles in $G$. A
similar idea is used by Gao, Janzer, Liu and Xu in [20].

######  Claim 4.2.

If $|F_{T}|\geq 100C^{2}Dn^{2}$, then $G$ contains $C^{\textrm{dia}}_{6}$.

The proof of Claim 4.2 uses the following well-known bound for the asymmetric
Zarankiewicz problem.

######  Theorem 4.3 (Kővári, Sós and Turán [30]).

A bipartite graph with parts of size $m$ and $n$ and no four-cycle has at most
$m\sqrt{n}+n$ edges.

###### Proof of Claim 4.2.

Suppose that $|F_{T}|\geq 100C^{2}Dn^{2}.$ By averaging there is an edge $uv$
in $G$ which is contained in at least $|F_{T}|/(2Cn^{3/2})\geq 50CDn^{1/2}$
thick four-cycles and without loss of generality, at least $25CDn^{1/2}$ of
those four-cycles are of the form $uvxy$ such that $d_{G}(u,x)\geq
10\sqrt{CD}n^{1/4}.$ Let $\\{x_{1},\dots,x_{t}\\}$ denote the set of all
vertices $x\in N(v)$ such that $d_{G}(u,x)\geq 10\sqrt{CD}n^{1/4}.$ Consider
the bipartite graph $H=G[N(u),\\{x_{1},\dots,x_{t}\\}].$ Every thick four-
cycle of the form $uvxy$ with $d_{G}(u,x)\geq 10\sqrt{CD}n^{1/4}$ corresponds
to an edge $xy$ in $H$. Hence we have $e(H)\geq 25CDn^{1/2}$ and by the
definition of the set $\\{x_{1},\dots,x_{t}\\}$, we have $e(H)\geq t\cdot
10\sqrt{CD}n^{1/4}.$ So,

$e(H)>10CDn^{1/2}+5t\sqrt{CD}n^{1/4}>\Delta(G)+t\sqrt{\Delta(G)}\geq|N(u)|+\sqrt{|N(u)|}t.$

Thus, by Theorem 4.3, $H$ contains a four-cycle. The four vertices of this
four-cycle along with $\\{u,v\\}$ form a $K_{3,3}.$ Finally, note that
$K_{3,3}$ is isomorphic to $C^{\textrm{dia}}_{6}$, the $6$-cycle with all
diagonals, finishing the proof of the claim. ∎

From now on we assume $|F_{T}|<100C^{2}Dn^{2}$ since, otherwise, we are done
by Claim 4.2. We shall use the following well-known supersaturation theorem
for four-cycles.

######  Theorem 4.4 (Erdős and Simonovits [18]).

Let $C\geq 10$ and let $G$ be an $n$-vertex graph with $Cn^{3/2}$ edges. Then,
$G$ contains at least $C^{4}n^{2}/2$ four-cycles.

###  4.1 Finding an almost-spanning expander $\Gamma$ in the $C_{4}$-graph of
$G$

In this subsection, we prove our main lemma, Lemma 4.7, which shows that we
can turn $\Gamma_{0}$ into an excellent (robust) expander $\Gamma$ by removing
very few edges and vertices from $\Gamma_{0}$. As explained in the proof
overview, the following notion of robust expansion of vertex sets in the
$C_{4}$-graph is crucial to our proof. Related notions of robust expansion
(but for _sublinear_ expansion) were recently used in [21, 6, 37, 32].

######  Definition 4.5 (Robust expansion).

Let $\Gamma$ be an arbitrary subgraph of $\Gamma_{0}$. We say that a set
$E_{b}\subseteq V(\Gamma)$ is _$\delta$ -robustly-expanding_ in $\Gamma$ if
for any set $F\subseteq E(\Gamma)$ with $|F|\leq|E_{b}|\cdot\delta
C^{3}\sqrt{n},$ we have $|N_{\Gamma-F}(E_{b})|\geq\delta|E_{b}|.$ If all sets
of size at most $0.98|V(\Gamma)|$ are $\delta$-robustly expanding in $\Gamma,$
then we say $\Gamma$ is a $\delta$-robust-expander.

Denote $N_{0}\coloneqq|V(\Gamma_{0})|=Cn^{3/2}=e(G).$ By Theorem 4.4, we have
$e(\Gamma_{0})\geq C^{4}n^{2}/2.$ The following claim shows that all large
enough vertex-sets of size up to $0.99N_{0}$ in $\Gamma_{0}$ are robustly
expanding in the sense defined above.

######  Claim 4.6.

Any set $E_{b}\subseteq V(\Gamma_{0})$ with $\varepsilon N_{0}\leq|E_{b}|\leq
0.99N_{0}$ is $2\delta$-robustly-expanding in $\Gamma_{0}$.

###### Proof of Claim 4.6.

Let $E_{b}\subseteq V(\Gamma_{0})$ be a set with $\varepsilon
N_{0}\leq|E_{b}|\leq 0.99N_{0}$ and suppose for the sake of contradiction that
there is a set $F\subseteq E(\Gamma_{0})$ such that $|F|\leq|E_{b}|\cdot
2\delta C^{3}\sqrt{n}$ and $|N_{\Gamma_{0}-F}(E_{b})|<2\delta|E_{b}|.$ Let
$E_{p}=N_{\Gamma_{0}-F}(E_{b})$ and $E_{r}=V(\Gamma_{0})\setminus(E_{b}\cup
E_{p}).$ Note that $|E_{p}|<2\delta|E_{b}|$. We shall call the edges in
$E_{b},E_{p},E_{r}\subseteq E(G)$ blue, purple and red, respectively. Note
that these are edges in $G$ and thus vertices in $\Gamma_{0}.$ For each $v\in
V(G)$, let $d_{b}(v),d_{p}(v),d_{r}(v)$ denote the number of blue, purple and
red edges incident to $v$, respectively. We will partition the vertex set of
$G$ into four sets $P,R,B,U$ such that for any $v\in V(G)$ we have:

$\displaystyle v\in\begin{cases}P,&\text{if }d_{p}(v)\geq d(v)/2,\\\
R,&\text{if }d_{p}(v)<d(v)/2\text{ and }d_{b}(v)<\eta d(v),\\\ B,&\text{if
}d_{p}(v)<d(v)/2\text{ and }d_{r}(v)<\eta d(v),\\\ U,&\text{if
}d_{p}(v)<d(v)/2\text{ and }d_{b}(v),d_{r}(v)\geq\eta d(v).\end{cases}$

Note that since $\eta<1/4,$ $P\cup R\cup B\cup U$ is a partition of $V(G).$
First, we will show that there are few edges of $G$ incident to $U$. To this
end, let $e_{U}=\sum_{v\in U}d(v).$ Note that for any $v\in U,$ the number of
2-paths $xvy$ such that $xv\in E_{r},vy\in E_{b}$ is at least
$d_{r}(v)d_{b}(v)\geq\eta d(v)(1/2-\eta)d(v)\geq\frac{\eta}{4}d(v)^{2}.$ By
Jensen’s inequality, the total number of 2-paths $xvy$ with $v\in U,$ $xv\in
E_{r},vy\in E_{b}$ (i.e., $xv$ is red and $vy$ is blue) is at least

$\frac{\eta}{4}|U|\left(\frac{e_{U}}{|U|}\right)^{2}=\frac{\eta}{4}\frac{e_{U}^{2}}{|U|}\geq\frac{\eta}{4}\frac{e_{U}^{2}}{n}.$

Hence, on average, for a pair $x,y$ there are at least
$\frac{\eta}{4}\frac{e_{U}^{2}}{n^{3}}$ choices for $v\in U$ such that $xv\in
E_{r},vy\in E_{b}$. If $e_{U}\geq\frac{20}{\eta^{1/2}}n^{3/2}$, then
$\frac{\eta}{4}\frac{e_{U}^{2}}{n^{3}}\geq 10$, so by Jensen’s inequality,
there are at least

$\binom{n}{2}\binom{\frac{\eta}{4}\frac{e_{U}^{2}}{n^{3}}}{2}\geq\frac{\eta^{2}}{100}\frac{e_{U}^{4}}{n^{4}}$

four-cycles in $G$ of the form $xuyv$ where $xu,xv$ are red and $uy,vy$ are
blue. Let us call such four-cycles _red-red-blue-blue_ four-cycles. Note that
any red-red-blue-blue four-cycle in $G$ yields an edge between $E_{r}$ and
$E_{b}$ in $\Gamma_{0}.$ By definition, $\Gamma_{0}-F$ has no edges between
$E_{b}$ and $E_{r},$ therefore all of these red-red-blue-blue four-cycles in
$G$ correspond to edges in $F.$ Therefore, we obtain

$\frac{\eta^{2}}{100}\frac{e_{U}^{4}}{n^{4}}\leq|F|\leq|E_{b}|\cdot 2\delta
C^{3}\sqrt{n}\leq 2\delta C^{4}n^{2},$

which implies $e_{U}\leq(2\delta)^{1/5}Cn^{3/2}$, where we used
$\delta\ll\eta.$ Thus, using that $\frac{1}{C}\ll\delta,\eta,$ we have

$e_{U}=\sum_{v\in
U}d(v)\leq\max\\{(2\delta)^{1/5}Cn^{3/2},\frac{20}{\eta^{1/2}}n^{3/2}\\}=(2\delta)^{1/5}Cn^{3/2}.$

Furthermore, the number of edges incident to $P$ is at most

$e_{P}\coloneqq\sum_{v\in P}d(v)\leq 2\sum_{v\in P}d_{p}(v)\leq 4|E_{p}|\leq
8\delta|E_{b}|.$

Finally, let us bound the number of edges between the vertex sets $B$ and $R$.
There are at most $2\eta e(G)$ blue edges between $B$ and $R$. Indeed,
otherwise, there is a vertex $v\in R$ incident to at least $\eta d(v)$ blue
edges, a contradiction. Analogously, there are at most $2\eta e(G)$ red edges
between $B$ and $R$. Trivially, there are at most $|E_{p}|$ purple edges
between $B$ and $R$. Thus, $e_{G}(B,R)\leq 4\eta e(G)+|E_{p}|\leq 4\eta
e(G)+2\delta|E_{b}|.$

Since $e_{G}(B,\overline{B})\leq e_{U}+e_{P}+e_{G}(B,R)$, putting all of the
above bounds together, we have

$e_{G}(B,\overline{B})\leq(2\delta)^{1/5}Cn^{3/2}+8\delta|E_{b}|+(4\eta
e(G)+2\delta|E_{b}|)\leq 5\eta e(G),$

where we used that $\delta\ll\eta$ and $e(G)=Cn^{3/2}.$ Hence, since $G$
satisfies $\mathrm{(P4)}$ of Lemma 3.3, we have either
$|B|\leq\frac{1000n}{D}$ or $|\overline{B}|\leq\frac{1000n}{D}$ or

$\min\\{|B|,|\overline{B}|\\}\leq\frac{16e_{G}(B,\overline{B})}{Cn^{1/2}}\leq
80\eta n.$

Since $D^{-1}\ll\eta,$ this implies $|B|\leq 80\eta n$ or
$|B|\geq(1-80\eta)n.$ Suppose first $|B|\leq 80\eta n.$ Since $G$ satisfies
$\mathrm{(P3)}$ of Lemma 3.3, we have $e_{G}(B)\leq 2C|B|^{3/2}$. Therefore,
we have

$\displaystyle|E_{b}|$ $\displaystyle\leq e_{G}(B)+\sum_{v\in
R}d_{b}(v)+\sum_{v\in P}d(v)+\sum_{v\in U}d(v)$ $\displaystyle\leq
2C|B|^{3/2}+2\eta e(G)+8\delta|E_{b}|+(2\delta)^{1/5}Cn^{3/2}$
$\displaystyle\leq(2(80\eta)^{3/2}+2\eta+8\delta+(2\delta)^{1/5})Cn^{3/2}<\varepsilon
N_{0},$

where we used that $\varepsilon\gg\eta,\delta.$ This contradicts our
assumption that $|E_{b}|\geq\varepsilon N_{0}.$

Therefore, we have $|B|\geq(1-80\eta)n$ and thus $|R|\leq 80\eta n.$ Note that
since $G$ satisfies $\mathrm{(P3)}$ of Lemma 3.3, we have $e_{G}(R)\leq
2C|R|^{3/2}\leq 2C(80\eta n)^{3/2}$. Thus, we can bound $|E_{r}|$ as follows.

$\displaystyle|E_{r}|$ $\displaystyle\leq e_{G}(R)+\sum_{v\in
B}d_{r}(v)+\sum_{v\in P}d(v)+\sum_{v\in U}d(v)$ $\displaystyle\leq 2C(80\eta
n)^{3/2}+2\eta e(G)+8\delta e(G)+(2\delta)^{1/5}Cn^{3/2}$
$\displaystyle\leq(2(80\eta)^{3/2}+2\eta+8\delta+(2\delta)^{1/5})e(G)\leq
3\eta e(G),$

where we used $1\gg\eta\gg\delta.$ Thus,

$|E_{b}|+|E_{p}|+|E_{r}|\leq 0.99e(G)+2\delta e(G)+3\eta e(G)<e(G),$

a contradiction. This proves the claim. ∎

Now our aim is to show that $\Gamma_{0}$ contains an almost-spanning robust
expander $\Gamma$. To that end, let
$\Gamma^{\prime}\coloneqq\Gamma_{0}-F_{T},$ where $F_{T}$ is the set of edges
of $\Gamma_{0}$ corresponding to the thick four-cycles of $G$. Let $E_{0}$ be
a maximal set of size at most $0.99N_{0}$ which is not $\delta$-robustly-
expanding in $\Gamma^{\prime}$. Then there exists a set $F_{0}$ of edges in
$\Gamma^{\prime}$ such that $|N_{\Gamma^{\prime}-F_{0}}(E_{0})|<\delta|E_{0}|$
and $|F_{0}|\leq|E_{0}|\cdot\delta C^{3}\sqrt{n}$. Let
$\Gamma\coloneqq\Gamma^{\prime}\setminus E_{0}$ and $N\coloneqq|V(\Gamma)|.$
In the next lemma, we show that $\Gamma$ is a robust expander containing all
but at most $\varepsilon$-proportion of the vertices of $\Gamma_{0}$.

######  Lemma 4.7 (Main lemma).

We have $|V(\Gamma)|=N\geq(1-\varepsilon)N_{0}$ and moreover, $\Gamma$ is a
$\delta$-robust-expander.

###### Proof.

Suppose for a contradiction that $N<(1-\varepsilon)N_{0},$ i.e.,
$|E_{0}|>\varepsilon N_{0}$ (since $N_{0}-|E_{0}|=N$). Then,
$N_{\Gamma_{0}-(F_{0}\cup F_{T})}(E_{0})<\delta|E_{0}|.$ However, by Claim
4.2, $|F_{0}\cup F_{T}|\leq\delta C^{3}\sqrt{n}|E_{0}|+100C^{2}Dn^{2}\leq
2\delta C^{3}\sqrt{n}|E_{0}|,$ where we also used that $1/C\ll
1/D\ll\delta,\varepsilon$ and $N_{0}=Cn^{3/2}.$ This means that $E_{0}$ is not
$2\delta$-robustly-expanding in $\Gamma_{0}$ and $\varepsilon
N_{0}<|E_{0}|\leq 0.99N_{0},$ contradicting Claim 4.6. Thus
$|E_{0}|\leq\varepsilon N_{0}$, so $N\geq(1-\varepsilon)N_{0}$, proving the
first part of the lemma.

Now suppose for a contradiction that there is a non-empty set $E_{b}$ of size
at most $0.98N$ which is not $\delta$-robustly-expanding in $\Gamma$. Then
there is a set $F_{b}$ of edges in $\Gamma$ such that $|N_{\Gamma-
F_{b}}(E_{b})|=|N_{\Gamma^{\prime}\setminus
E_{0}-F_{b}}(E_{b})|<\delta|E_{b}|$ and $|F_{b}|\leq\delta
C^{3}\sqrt{n}|E_{b}|$. Let $E=E_{0}\cup E_{b}$ and $F=F_{0}\cup F_{b}.$ We
have $|E|=|E_{0}|+|E_{b}|\leq\varepsilon N_{0}+0.98N\leq 0.99N_{0},$
$|F|\leq|F_{0}|+|F_{b}|\leq\delta C^{3}\sqrt{n}|E_{0}|+\delta
C^{3}\sqrt{n}|E_{b}|=\delta C^{3}\sqrt{n}|E|$ and
$|N_{\Gamma^{\prime}-F}(E)|\leq|N_{\Gamma^{\prime}-F_{0}}(E_{0})|+|N_{\Gamma^{\prime}\setminus
E_{0}-F_{b}}(E_{b})|<\delta|E_{0}|+\delta|E_{b}|=\delta|E|.$ Thus, $E$ is not
$\delta$-robustly-expanding in $\Gamma^{\prime}$, $|E|\leq 0.99N_{0},$ and
$|E|=|E_{0}|+|E_{b}|>|E_{0}|$ contradicting the maximality of $E_{0}.$ This
proves the lemma. ∎

###  4.2 Finding an odd path and an even path connecting most pairs of
vertices in $\Gamma$

In this subsection, our main goal is to show that most pairs of vertices in
$\Gamma$ are connected by an odd path as well as an even path avoiding a small
set of vertices in $G$ (see Lemma 4.13). We do this by exploiting the fact
that $\Gamma$ is an almost-spanning expander of the $C_{4}$-graph of $G$.

Let $\phi\colon V(\Gamma)\rightarrow E(G)$ be the bijection mapping vertices
of $\Gamma$ to the corresponding edges in $G$. Note that, by Lemma 4.7, we
have $N=|V(\Gamma)|\geq(1-\varepsilon)N_{0}\geq\frac{C}{2}n^{3/2}$, and
$\Gamma$ is a $\delta$-robust-expander.

The next claim shows that in order to find a cycle with all diagonals in $G$,
it suffices to find an odd cycle in $\Gamma$ satisfying a certain property
made precise in the following definition.

######  Definition 4.8 (Proper path/cycle).

A path or a cycle $x_{1},\dots,x_{\ell}$ in $\Gamma$ is called _proper_ if
$\phi(x_{i})\cap\phi(x_{j})=\emptyset,$ for all $1\leq i<j\leq\ell$, i.e., the
edges of $G$ corresponding to $x_{i}$’s are disjoint.

######  Claim 4.9.

A proper odd cycle in $\Gamma$ corresponds to a cycle with all diagonals in
$G$.

###### Proof.

Let $x_{1},\dots,x_{\ell}$ be a proper odd cycle in $\Gamma,$ and denote
$\phi(x_{i})=u_{i}v_{i}\in E(G)$ for any $i\in[\ell],$ where the vertices
$u_{1},\dots,u_{\ell}$ are in the same part of the bipartition of $G$. Since
$x_{1},\dots,x_{\ell}$ is a cycle, it follows that
$u_{i}v_{i+1},u_{i+1}v_{i}\in E(G)$ for all $i\in[\ell],$ where we denote
$v_{\ell+1}=v_{1}$ and $u_{\ell+1}=u_{1}$.

For $i\in[2\ell],$ denote

$w_{i}=\begin{cases}u_{i},&\text{if }i\leq\ell\text{ and }i\text{ is odd};\\\
v_{i},&\text{if }i\leq\ell\text{ and }i\text{ is even};\\\
v_{i-\ell},&\text{if }i>\ell\text{ and }i\text{ is even};\\\
u_{i-\ell},&\text{if }i>\ell\text{ and }i\text{ is odd}.\end{cases}$

Because $x_{1},\dots,x_{\ell}$ is a proper cycle, all the vertices
$w_{1},\dots,w_{2\ell}$ are distinct. It is straightforward to check that
$w_{i}w_{i+1}\in E(G)$ for all $i\in[2\ell]$ (with $w_{2\ell+1}=w_{1}$) and
$w_{i}w_{i+\ell}\in E(G)$ for all $i\in[\ell].$ In other words, the vertices
$w_{1},\dots,w_{2\ell}$ form a copy of $C^{\textrm{dia}}_{2\ell}$ in $G$. This
proves the claim. ∎

Slightly abusing notation, for a path $P=x_{1},\dots,x_{\ell}$ in $\Gamma,$ we
denote $\phi(P)=\bigcup_{i=1}^{\ell}\phi(x_{i})$ i.e., $\phi(P)$ is the set of
vertices in $G$ which are contained in the edges of $G$ corresponding to the
vertices of $P$ in $\Gamma$. We say that a vertex $v\in V(G)$ appears on $P$
if $v\in\phi(P).$ The following notion of a nice fan and Lemma 4.11 are
inspired by the ideas of Letzter [32] (see also [25, 26]).

######  Definition 4.10 (Fan).

Given $x\in V(\Gamma)$, a _fan_ $\mathcal{P}$ rooted at $x$ is a collection
$\\{Q(y)\\}_{y\in Y}$ of proper paths in $\Gamma$, where $Y\subseteq
V(\Gamma)$ and for each $y\in Y$, $Q(y)$ is a proper path starting at $x$ and
ending at $y$. The _size_ of a fan is the number of paths in it. A fan
$\mathcal{P}$ is _nice_ if every $v\in V(G)\setminus\phi(x)$ appears on at
most $t\coloneqq C^{1.1}n^{5/4}\log n$ paths in $\mathcal{P}$.

The following lemma shows that by starting at any given vertex in $\Gamma$, we
can reach almost all other vertices of $\Gamma$ via proper paths that are not
too long while also avoiding a small set $B$ of vertices in $G$. Our notion of
robust expansion (guaranteeing vertex expansion in $\Gamma$ even after the
removal of any relatively small set of edges) is crucial for the proof of the
lemma.

######  Lemma 4.11.

Let $x_{0}\in V(\Gamma)$ be arbitrary and let $B\subseteq V(G)$ be a set of at
most $n^{1/4}$ vertices in $G$ such that $\phi(x_{0})\cap B=\emptyset.$ Then,
there is a nice fan $\mathcal{P}$ rooted at $x_{0}$ of size at least $0.98N$
such that every $P\in\mathcal{P}$ is a proper path of length at most
$\frac{2\log N}{\delta}$ and $\phi(P)\cap B=\emptyset$.

###### Proof.

Let $\mathcal{P}$ be a nice fan rooted at $x_{0}$ of maximum size such that
every path in $\mathcal{P}$ is a proper path of length at most $\frac{2\log
N}{\delta}\leq\frac{100\log n}{\delta}$ and, for the sake of contradiction,
assume that $|\mathcal{P}|<0.98N.$ Let $T$ be the set of vertices in $G$
appearing on precisely $t$ paths in $\mathcal{P}$ and note that
$|T|\leq\frac{200N\log n}{\delta t}<n^{1/4},$ where we used
$\delta\gg\frac{1}{C}.$ Denote $B^{\prime}=T\cup B,$ so $|B^{\prime}|\leq
2n^{1/4}.$ We recursively define a sequence of subsets $U_{0}\subseteq
U_{1}\subseteq U_{2}\ldots$ of $V(\Gamma)$ as follows. Let
$U_{0}\coloneqq\\{x_{0}\\},$ and suppose we have already defined
$U_{0},U_{1},\ldots U_{i}$ with the property that for every $x\in U_{i}$,
there is a proper path $P(x)$ in $\Gamma$ from $x_{0}$ to $x$ of length at
most $i$ such that $\phi(P(x))\cap B^{\prime}=\emptyset$ and moreover, suppose
$|U_{j}|\geq(1+\delta)|U_{j-1}|$ for every $1\leq j\leq i$. If
$|U_{i}|<0.98N,$ we define $U_{i+1}$ as follows. Otherwise, we stop the
procedure.

Let $U_{i+1}\coloneqq U_{i}\bigcup\\{y\in V(\Gamma)\setminus U_{i}\mid\exists
x\in U_{i},xy\in E(\Gamma),\phi(y)\cap(\phi(P(x))\cup
B^{\prime})=\emptyset\\}$. Note that for every vertex $y\in U_{i+1}$, there
exists a proper path $P(y)$ in $\Gamma$ from $x_{0}$ to $y$ of length at most
$i+1$ such that $\phi(P(y))\cap B^{\prime}=\emptyset$.

We claim that $|U_{i+1}|\geq(1+\delta)|U_{i}|.$ Indeed, consider an arbitrary
$x\in U_{i}$, and an arbitrary $b\in\phi(P(x))\cup B^{\prime}$. Let
$\phi(x)=\\{x_{1},x_{2}\\}\in E(G)$. Without loss of generality, assume that
$x_{1}$ and $b$ are on the same side of the bipartition of $G$. Then, since no
edge in $\Gamma$ corresponds to a thick four-cycle in $G$, there are at most
$10\sqrt{CD}n^{1/4}$ edges in $\Gamma$ of the form $xy$ where $b\in y.$ Let
$F_{i}\coloneqq\\{xy\in E(\Gamma)\mid x\in U_{i},\phi(y)\cap(\phi(P(x))\cup
B^{\prime})\not=\emptyset\\}$. For any $x\in U_{i}$, since $P(x)$ has length
at most $i$, we have $|\phi(P(x))|\leq 2i$. Moreover, since
$|U_{j}|\geq(1+\delta)|U_{j-1}|$ for every $1\leq j\leq i$, we have
$N\geq|U_{i}|\geq(1+\delta)^{i}\geq e^{\frac{\delta i}{2}},$ implying that
$i\leq\frac{2\log N}{\delta}\leq\frac{5\log n}{\delta}$. Hence, by the above
discussion, we have

$|F_{i}|\leq|U_{i}|\cdot(2i+|B^{\prime}|)\cdot
10\sqrt{CD}n^{1/4}\leq|U_{i}|\left(\frac{10\log
n}{\delta}+2n^{1/4}\right)10\sqrt{CD}n^{1/4}\leq|U_{i}|\cdot
30\sqrt{CD}n^{1/2}<|U_{i}|\cdot\delta C^{3}n^{1/2},$

where we used $\frac{1}{C}\ll\delta,\frac{1}{D}$. Since $\Gamma$ is
$\delta$-robustly-expanding, this implies that $|N_{\Gamma-
F_{i}}(U_{i})|\geq\delta|U_{i}|$. Moreover, crucially, notice that $N_{\Gamma-
F_{i}}(U_{i})=\\{y\in V(\Gamma)\setminus U_{i}\mid\exists x\in U_{i},xy\in
E(\Gamma),\phi(y)\cap(\phi(P(x))\cup B^{\prime})=\emptyset\\}$. Thus,
$|U_{i+1}|\geq|U_{i}|+\delta|U_{i}|=(1+\delta)|U_{i}|,$ as claimed.

Suppose the above procedure stops after $\ell$ steps having defined the sets
$U_{0}\subseteq U_{1},\ldots\subseteq U_{\ell}\subseteq V(\Gamma)$. Then,
again since $N\geq|U_{\ell}|\geq(1+\delta)^{\ell}\geq
e^{\frac{\delta\ell}{2}},$ we have $\ell\leq\frac{2\log N}{\delta}$ and since
the procedure has stopped, we must have $|U_{\ell}|\geq 0.98N.$ Hence, there
is a vertex $y\in U_{\ell}$ such that there is no path in $\mathcal{P}$ from
$x_{0}$ to $y$, but since $y\in U_{\ell}$, there is a proper path $P(y)$ in
$\Gamma$ from $x_{0}$ to $y$ of length at most $\frac{2\log N}{\delta}$ such
that $\phi(P(y))\cap B^{\prime}=\emptyset$. However, then we could add the
path $P(y)$ to $\mathcal{P},$ while still guaranteeing that
$\mathcal{P}\cup\\{P(y)\\}$ is a nice fan (as $\phi(P(y))\cap T=\emptyset$),
and ensuring that $\phi(P(y))\cap B=\emptyset$. This contradicts the
maximality of the fan $\mathcal{P}$ and completes the proof of the lemma. ∎

The fact that $\Gamma$ is an almost-spanning expander of the $C_{4}$-graph of
$G$ is crucial to the following claim.

######  Claim 4.12.

For any set $U\subseteq V(\Gamma)$ with $|U|\geq N/100,$ it holds that
$e(\Gamma[U])\geq 10^{-11}C^{4}n^{2}.$

###### Proof.

Let $U\subseteq V(\Gamma)$ be a subset of vertices such that $|U|\geq
N/100\geq Cn^{3/2}/200$. Note that $U$ corresponds to a set of at least
$Cn^{3/2}/200$ edges in $G$. Using that $C$ is large enough, by Theorem 4.4,
these edges induce at least $10^{-10}C^{4}n^{2}$ four-cycles. Since
$|F_{T}|\leq 100C^{2}Dn^{2}$ by Claim 4.2, and $1/C\ll 1/D$, at least
$10^{-10}C^{4}n^{2}-100C^{2}Dn^{2}\geq 10^{-11}C^{4}n^{2}$ of these four-
cycles correspond to edges in $\Gamma[U],$ proving the claim. ∎

Using the claim above and Lemma 4.11, we prove the following lemma which shows
that by starting at any vertex in our almost-spanning expander $\Gamma$, we
can reach almost all other vertices of $\Gamma$ via a short proper path of odd
length as well as a short proper path of even length (simultaneously) while
also avoiding a small set of vertices in $G$.

######  Lemma 4.13.

Let $x_{0}\in V(\Gamma)$ be arbitrary and let $B\subseteq V(G)$ be a set of at
most $n^{1/4}$ vertices in $G$ such that $\phi(x_{0})\cap B=\emptyset.$ Then,
there is a set $Y\subseteq V(\Gamma)$ of size $|Y|\geq 0.94N$ such that for
every $y\in Y,$ there exists a proper path $P_{o}(y)$ of odd length in
$\Gamma$ and a proper path $P_{e}(y)$ of even length in $\Gamma$, both of
which start at $x_{0}$ and end at $y$ and have length at most $\frac{2\log
N}{\delta}+1$, and $(\phi(P_{o}(y))\cup\phi(P_{e}(y)))\cap B=\emptyset$.

###### Proof.

By Lemma 4.11, there is a nice fan $\mathcal{P}$ rooted at $x_{0}$ of size at
least $0.98N$ such that every $P\in\mathcal{P}$ is a proper path of length at
most $\frac{2\log N}{\delta}$ and $\phi(P)\cap B=\emptyset$. Let $U\subseteq
V(\Gamma)$ be the set of endpoints of the paths in $\mathcal{P}$ and for each
$y\in U,$ denote by $P(y)$ the path in $\mathcal{P}$ from $x_{0}$ to $y$. Let
$U_{0}$ and $U_{1}$ be the set of vertices $y\in U$ for which the length of
the path $P(y)\in\mathcal{P}$ is even and odd respectively. Then
$|U|=|U_{0}|+|U_{1}|\geq 0.98N$.

Suppose $|U_{0}|\geq N/50$. Let $\Gamma^{\prime}$ be a graph obtained from
$\Gamma[U_{0}]$ by repeatedly removing vertices of degree at most
$C^{2.5}n^{1/2}$. Note that $|V(\Gamma^{\prime})|\geq|U_{0}|-N/100.$ Indeed,
otherwise, in $\Gamma$ there is a vertex set of size $N/100$ spanning at most
$N/100\cdot C^{2.5}n^{1/2}=C^{3.5}n^{2}/100<10^{-11}C^{4}n^{2}$ edges (since
$C$ is large enough) contradicting Claim 4.12. Thus, in particular,
$\Gamma^{\prime}$ is non-empty and $\delta(\Gamma^{\prime})\geq
C^{2.5}n^{1/2}$.

Note that for any edge $yz\in E(\Gamma^{\prime})$ with
$\phi(z)\cap(\phi(P(y))\cup B)=\emptyset$, we can extend the path $P(y)$ from
$x_{0}$ to $y$ using the edge $yz$ to obtain a proper path $P_{o}(z)$ in
$\Gamma$ of odd length at most $\frac{2\log N}{\delta}+1$ from $x_{0}$ to $z$
such that $\phi(P_{o}(z))\cap B=\emptyset$.

Let us show that such a path $P_{o}(z)$ of odd length can be obtained for all
but at most $N/100$ vertices $z\in V(\Gamma^{\prime}).$ To that end, we bound
the number of edges $yz\in E(\Gamma^{\prime})$ such that
$\phi(z)\cap(\phi(P(y))\cup B)\neq\emptyset$ as follows.

For each $y\in V(\Gamma^{\prime})$ and $v\in\phi(P(y))\cup B,$ there are at
most $10\sqrt{CD}n^{1/4}$ possible vertices $z\in V(\Gamma^{\prime})$ such
that $v\in\phi(z)$ and $yz\in E(\Gamma^{\prime}).$ Indeed, otherwise the
vertex $u\in\phi(y)$ which is in the same part of $G$ as $v$ satisfies
$d_{G}(u,v)>10\sqrt{CD}n^{1/4},$ so any such edge $yz\in E(\Gamma^{\prime})$
would correspond to a thick four-cycle in $\Gamma_{0}$ and hence would not be
in $\Gamma$, a contradiction. Since for any $y\in V(\Gamma^{\prime})$, the
path $P(y)\in\mathcal{P}$ has length at most $\frac{2\log N}{\delta}$ (so,
$\phi(P(y))\leq\frac{4\log N}{\delta}$) we conclude that the number of edges
$yz\in E(\Gamma^{\prime})$ such that $\phi(z)\cap(\phi(P(y))\cup
B)\neq\emptyset$ is at most $N\cdot(\frac{4\log N}{\delta}+n^{1/4})\cdot
10\sqrt{CD}n^{1/4}<C^{1.6}n^{2},$ where we used $\frac{1}{C}\ll\frac{1}{D}$.

On the other hand, for a vertex $z\in V(\Gamma^{\prime}),$ if we cannot find a
path $P_{o}(z)$ of odd length from $x_{0}$ to $z$ as described above, then
$\phi(z)\cap(\phi(P(y)\cup B)\neq\emptyset$ for all $y$ with $yz\in
E(\Gamma^{\prime}).$ Hence, the number of such vertices $z$ is at most
$C^{1.6}n^{2}/\delta(\Gamma^{\prime})\leq n^{3/2}/C^{0.9}<N/100,$ as required.

In summary, if $|U_{0}|\geq N/50$, we obtain a proper odd path $P_{o}(z)$ of
length at most $\frac{2\log N}{\delta}+1$ from $x_{0}$ to $z$ with
$\phi(P_{o}(z))\cap B=\emptyset$ for all but at most $N/50$ vertices $z\in
U_{0}.$ If $|U_{0}|<N/50$, then this statement is also vacuously true. An
analogous argument yields an even proper path $P_{e}(z)$ of length at most
$\frac{2\log N}{\delta}+1$ from $x_{0}$ to $z$ with $\phi(P_{e}(z))\cap
B=\emptyset$ for all but at most $N/50$ vertices $z\in U_{1}.$

Now, for each $z\in U_{0}$, let $P_{e}(z)\coloneqq P(z)\in\mathcal{P}$ and for
each $z\in U_{1}$, let $P_{o}(z)\coloneqq P(z)\in\mathcal{P}$. Hence, the
desired paths $P_{e}(z),P_{o}(z)$ exist for at least $|U|-2(N/50)\geq
0.98N-2(N/50)=0.94N$ vertices $z\in V(\Gamma)$, as required. This completes
the proof of the lemma. ∎

In the next subsection, we combine Lemma 4.13, Lemma 4.11 and ideas in [32] to
construct a proper odd cycle in $\Gamma$, giving us the required cycle with
all diagonals in $G$.

###  4.3 Constructing a proper odd cycle in $\Gamma$ and finding a cycle with
all diagonals

By Claim 4.9, in order to find a cycle with all diagonals in $G$, it suffices
to find a proper cycle of odd length in $\Gamma$. To that end, we apply Lemma
4.11 with $B=\emptyset$ to obtain for every $x\in V(\Gamma),$ a nice fan
$\mathcal{P}(x)\coloneqq\\{P(x,y)\\}_{y\in Y(x)}$ rooted at $x$ of size at
least $0.98N$, where $Y(x)\subseteq V(\Gamma)$ and for every $y\in Y(x)$,
$P(x,y)$ is the proper path in $\mathcal{P}(x)$ starting at $x$ and ending at
$y$.

Now, for every $y\in V(\Gamma),$ let $F(y)$ be the set of vertices in
$V(G)\setminus\phi(y)$ appearing on at least $t$ of the paths among
$\\{P(x,y)\\}_{x\in V(\Gamma)}$. Since $t=C^{1.1}n^{5/4}\log n,$ and for every
$x\in V(\Gamma)$, the path $P(x,y)$ has length at most $\frac{2\log
N}{\delta}\leq\frac{5\log n}{\delta}$, we have

$|F(y)|\leq N\cdot\frac{10\log n}{\delta}\cdot\frac{1}{t}\leq
Cn^{3/2}\cdot\frac{10\log n}{\delta}\cdot\frac{1}{C^{1.1}n^{5/4}\log
n}\leq\frac{10}{\delta C^{0.1}}n^{1/4}<n^{1/4},$

where we used $\frac{1}{C}\ll\delta.$

Thus, applying Lemma 4.13 with $F(y)$ playing the role of $B$, we obtain for
every $y\in V(\Gamma),$ a set $S(y)\subseteq V(\Gamma)$ of size $|S(y)|\geq
0.94N$ such that for every $x\in S(y),$ there is a proper path $P_{o}(y,x)$ of
odd length and a proper path $P_{e}(y,x)$ of even length in $\Gamma$, both of
which start at $y$ and end at $x$ and are of length at most $\frac{2\log
N}{\delta}+1$ such that $(\phi(P_{o}(y,x))\cup\phi(P_{e}(y,x)))\cap
F(y)=\emptyset$.

We claim that if there is a pair of vertices $x,y\in V(\Gamma)$ satisfying the
properties $\mathrm{(i)}$ and $\mathrm{(ii)}$ below, then there is a proper
cycle of odd length in $\Gamma$, as desired.

  * (i)

there is a set $Z\subseteq V(\Gamma)$ of size $|Z|\geq 0.7N$ such that for
every $z\in Z$, we have proper paths $P(x,z)\in\mathcal{P}(x)$,
$P(z,y)\in\mathcal{P}(z)$ and $\phi(P(x,z))\cap\phi(P(z,y))=\phi(z)$,

  * (ii)

$x\in S(y)$.

Let us first prove the claim above. Indeed, since $\mathrm{(ii)}$ holds, there
are proper paths $P_{o}(y,x),$ $P_{e}(y,x)$ from $y$ to $x$ as defined above.
Since the paths are proper, note that in particular
$\phi(x)\cap\phi(y)=\emptyset$. Let
$T\coloneqq\phi(P_{o}(y,x))\cup\phi(P_{e}(y,x))\setminus(\phi(x)\cup\phi(y))$
and note that $|T|\leq 4\left(2\frac{\log N}{\delta}+1\right)<20\frac{\log
n}{\delta}.$ Since $\mathcal{P}(x)$ is a nice fan and
$T\cap\phi(x)=\emptyset$, every vertex $v\in T$ appears on at most $t$ of the
paths $\\{P(x,z)\\}_{z\in Z}$. Moreover, since
$T\cap(F(y)\cup\phi(y))=\emptyset$, every vertex $v\in T$ appears on at most
$t$ of the paths $\\{P(z,y)\\}_{z\in Z}$. Then it follows that there are at
least $|Z|-2|T|\cdot t\geq 0.7N-2\left(20\frac{\log
n}{\delta}\right)C^{1.1}n^{5/4}\log n\geq 0.6N$ vertices $z\in Z$ such that
$(\phi(P(x,z))\cup\phi(P(z,y)))\cap T=\emptyset$. Fix one such vertex $z\in
Z.$ Then since $\phi(P(x,z))\cap\phi(P(z,y))=\phi(z)$ by $\mathrm{(i)}$,
either $P(x,z)P(z,y)P_{e}(y,x)$ or $P(x,z)P(z,y)P_{o}(y,x)$ is a proper odd
cycle in $\Gamma,$ proving the claim.

Hence, to complete the proof, it suffices to find a pair of vertices $x,y\in
V(\Gamma)$ satisfying the properties $\mathrm{(i)}$ and $\mathrm{(ii)}$.

To that end, let us consider the ordered triples $(x,z,y)\in V(\Gamma)\times
V(\Gamma)\times V(\Gamma)$ such that $P(x,z)\in\mathcal{P}(x)$,
$P(z,y)\in\mathcal{P}(z)$ and $\phi(P(x,z))\cap\phi(P(z,y))=\phi(z)$, and call
such triples $(x,z,y)$ _admissible_. Let us give a lower bound on the number
of admissible triples $(x,z,y)$. For a given $x\in V(\Gamma)$, the number of
choices of $z\in V(\Gamma)$ such that $P(x,z)\in\mathcal{P}(x)$ is at least
$0.98N$. Fixing a choice of $x,z\in V(\Gamma)$ with $P(x,z)\in\mathcal{P}(x)$,
every vertex $v\in\phi(P(x,z))\setminus\phi(z)$ appears on at most $t$ of the
paths in $\mathcal{P}(z)$ because $\mathcal{P}(z)$ is a nice fan. Hence, the
number of choices for $y\in V(\Gamma)$ such that $P(z,y)\in\mathcal{P}(z)$ and
$\phi(P(z,y))\cap(\phi(P(x,z))\setminus\phi(z))=\emptyset$ is at least
$|\mathcal{P}(z)|-|\phi(P(x,z))|t\geq 0.98N-\frac{4\log N}{\delta}\cdot
C^{1.1}n^{5/4}\log n\geq 0.97N$. Hence the number of admissible triples
$(x,z,y)$ is at least $N\cdot(0.98N)\cdot(0.97N)$. If an ordered pair
$(x,y)\in V(\Gamma)\times V(\Gamma)$ does not satisfy $\mathrm{(i)}$, then
there are more than $N-0.7N$ vertices $z$ such that $(x,z,y)$ is not an
admissible tuple. Thus the number of ordered pairs $(x,y)\in V(\Gamma)\times
V(\Gamma)$ which do not satisfy $\mathrm{(i)}$ is at most $\frac{(1-0.98\cdot
0.97)N^{3}}{(1-0.7)N}<\frac{N^{2}}{3}$. The number of ordered pairs $(x,y)\in
V(\Gamma)\times V(\Gamma)$ such that $x\not\in S(y)$ (i.e., which do not
satisfy $\mathrm{(ii)}$) is at most $N(N-0.94N)=0.06N^{2}.$ In total, the
number of ordered pairs $(x,y)\in V(\Gamma)\times V(\Gamma)$ not satisfying
either $\mathrm{(i)}$ or $\mathrm{(ii)}$ is at most
$\frac{N^{2}}{3}+0.06N^{2}<N^{2},$ so there is a pair $(x,y)$ satisfying
$\mathrm{(i)}$ or $\mathrm{(ii)}$, as required. This completes the proof of
Theorem 1.1.

##  5 Concluding remarks

In this paper we proved that any graph with at least $Cn^{3/2}$ edges contains
a cycle with all diagonals (where $C$ is a large enough constant). A key lemma
in our proof is Lemma 4.7, which states that, roughly speaking, if $G$ is an
expander, then its $C_{4}$-graph contains an almost-spanning robust expander.
Here the $C_{4}$-graph of $G$ is the graph defined on the edge-set of $G$ in
which two edges are adjacent if they are opposite edges of a four-cycle in
$G$. We believe that similar arguments applied to different auxiliary graphs
could be useful for other problems.

Let us mention a couple of problems related to our result. As noted in the
introduction, if $\ell=3$, then $C^{\textrm{dia}}_{2\ell}$ is isomorphic to
the complete bipartite graph $K_{3,3}$, so
$\mathrm{ex}(n,C^{\textrm{dia}}_{2\ell})=\mathrm{ex}(n,K_{3,3})=\Omega(n^{5/3})$
using Brown’s well-known construction [5]. On the other hand, our proof shows
that every $n$-vertex graph with $Cn^{3/2}$ edges contains a copy of
$C^{\textrm{dia}}_{2\ell}$ for some $\ell=O(\log n)$. This suggests the
following question.

######  Problem 5.1.

Is it true that if $\ell\in\mathbb{N}$ is large enough, then
$\mathrm{ex}(n,C^{\textrm{dia}}_{2\ell})=O(n^{3/2})$?

Next, we propose a possible generalization of our result. For a natural number
$k$, consider an even cycle with every $k$–th diagonal and note that the
graphs $C^{\textrm{dia}}_{2\ell}$ correspond to taking $k=1$. It is easy to
see that if $k$ is even, such a graph cannot be bipartite. For odd $k,$ much
like in Figure 1, this graph can be viewed as an “odd cycle of
$2(k+1)$-cycles" where two consecutive cycles share exactly one edge. Hence,
can we ask the following question. For any odd $k\geq 3,$ is there is a
constant $C=C(k)$ such that every $n$-vertex graph with at least
$Cn^{1+1/(k+1)}$ edges contains a cycle with every $k$–th diagonal? We believe
that the methods developed in this paper might be useful in resolving this
problem. More precisely, one would require an analogue of Claim 4.6 for the
auxiliary graph $\Gamma_{0}$ defined on the edge-set of $G$ in which two edges
of $G$ are adjacent in the auxiliary graph if they are opposite edges in a
$2(k+1)$-cycle. Additionally, one would need a way to upper bound the number
of $2(k+1)$-cycles containing a given edge and vertex. This would be analogous
to Claim 4.2.

Acknowledgements. We are extremely grateful to Jun Gao, Oliver Janzer, Tao
Jiang, Hong Liu and Zixiang Xu for valuable discussions.

## References

  * [1] N. Alon, L. Rónyai, and T. Szabó.  Norm-graphs: variations and applications.  Journal of Combinatorial Theory, Series B, 76(2):280–290, 1999\.
  * [2] B. Bollobás.  Nested cycles in graphs.  In Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), volume 260 of Colloq. Internat. CNRS, pages 49–50. CNRS, Paris, 1978.
  * [3] J. A. Bondy and M. Simonovits.  Cycles of even length in graphs.  Journal of Combinatorial Theory, Series B, 16(2):97–105, 1974.
  * [4] D. Bradač, O. Janzer, B. Sudakov, and I. Tomon.  The Turán number of the grid.  Bulletin of the London Mathematical Society, 55(1):194–204, 2023\.
  * [5] W.G. Brown.  On graphs that do not contain a Thomsen graph.  Canadian Mathematical Bulletin, 9(3):281–285, 1966.
  * [6] M. Bucić and R. Montgomery.  Towards the Erdős-Gallai Cycle Decomposition Conjecture.  arXiv preprint arXiv:2211.07689, 2022.
  * [7] B. Bukh.  Extremal graphs without exponentially-small bicliques.  Duke Mathematical Journal, to appear.
  * [8] G. Chen, P. Erdős, and W. Staton.  Proof of a conjecture of Bollobás on Nested Cycles.  Journal of Combinatorial Theory, Series B, 66(1):38–43, 1996.
  * [9] K. Corradi and A. Hajnal.  On the maximal number of independent circuits in a graph.  Acta Mathematica Hungarica, 14(3-4):423–439, 1963.
  * [10] N. Draganić, A. Methuku, D. Munhá Correia, and B. Sudakov.  Cycles with many chords.  arXiv preprint arXiv:2306.09157, 2023.
  * [11] Y. Egawa.  Vertex-disjoint cycles of the same length.  Journal of Combinatorial Theory, Series B, 66(2):168–200, 1996\.
  * [12] P. Erdős.  On a problem of Sidon in Additive Number Theory and on Some Related Problems Addendum.  Journal of the London Mathematical Society, 19(76_Part_4):208–208, 1944.
  * [13] P. Erdős and M. Simonovits.  A limit theorem in graph theory.  Studia Sci. Math. Hungar, 1(51-57):51, 1966.
  * [14] P. Erdős and A.H. Stone.  On the structure of linear graphs.  Bull, Amer. Math. Soc, 52:1089–1091, 1946.
  * [15] P. Erdős.  Problems and Results in Graph Theory and Combinatorial Analysis.  Proc. British Combinatorial Conj., 5th, pages 169–192, 1975.
  * [16] P. Erdős.  Some recent progress on extremal problems in graph theory.  Congr. Numer, 14:3–14, 1975.
  * [17] P. Erdős, A. Rényi, and V.T. Sós.  On a problem of graph theory.  Studia Sci. Math. Hungar., 1:215–235, 1966.
  * [18] P. Erdős and M. Simonovits.  Supersaturated graphs and hypergraphs.  Combinatorica, 3:181–192, 1983.
  * [19] I. Fernández, J. Kim, Y. Kim, and H. Liu.  Nested cycles with no geometric crossings.  Proceedings of the American Mathematical Society, Series B, 9(3):22–32, 2022.
  * [20] J. Gao, O. Janzer, H. Liu, and Z. Xu.  Extremal number of graphs from geometric shapes.  Israel Journal of Mathematics, to appear.
  * [21] J. Haslegrave, J. Kim, and H. Liu.  Extremal density for sparse minors and subdivisions.  International Mathematics Research Notices, 2022(20):15505–15548, 2022.
  * [22] X. He, Y. Li, and L. Feng.  Extremal graphs for the odd prism.  arXiv preprint arXiv:2302.03278, 2023.
  * [23] O. Janzer.  Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles.  Israel Journal of Mathematics, 253(2):813–840, 2023.
  * [24] O. Janzer and B. Sudakov.  Resolution of the Erdős-Sauer problem on regular subgraphs.  Forum of Mathematics, Pi, 11:e19, 2023.
  * [25] T. Jiang, S. Letzter, A. Methuku, and L. Yepremyan.  Rainbow clique subdivisions and blow-ups.  arXiv preprint arXiv:2108.08814, 2021.
  * [26] T. Jiang, S. Longbrake, and J. Ma.  Bipartiteness under smooth conditions.  Combinatorics, Probability and Computing, 32(4):546–558, 2023.
  * [27] T. Jiang and A. Newman.  Small dense subgraphs of a graph.  SIAM Journal on Discrete Mathematics, 31(1):124–142, 2017.
  * [28] J. Kollár, L. Rónyai, and T. Szabó.  Norm-graphs and bipartite Turán numbers.  Combinatorica, 16(3):399–406, 1996.
  * [29] J. Komlós and E. Szemerédi.  Topological cliques in graphs II.  Combinatorics, Probability and Computing, 5(1):79–90, 1996.
  * [30] T. Kővári, V. T. Sós, and P. Turán.  On a problem of Zarankiewicz.  In Colloquium Mathematicum, volume 3, pages 50–57. Polska Akademia Nauk, 1954.
  * [31] A. Kupavskii, A. Polyanskii, I. Tomon, and D. Zakharov.  The extremal number of surfaces.  International Mathematics Research Notices, 2022(17):13246–13271, 2022.
  * [32] S. Letzter.  Hypergraphs with no tight cycles.  Proceedings of the American Mathematical Society, 151(02):455–462, 2023.
  * [33] H. Liu and R. Montgomery.  A solution to Erdős and Hajnal’s odd cycle problem.  Journal of the American Mathematical Society, 36:1191–1234, 2023\.
  * [34] W. Mantel.  Vraagstuk xxviii.  Wiskundige Opgaven met de Oplossingen, 10(2):60–61, 1907.
  * [35] R. Pinchasi and M. Sharir.  On graphs that do not contain the cube and related problems.  Combinatorica, 25(5):615–623, 2005.
  * [36] L. Pyber, V. Rödl, and E. Szemerédi.  Dense graphs without $3$-regular subgraphs.  Journal of Combinatorial Theory, Series B, 63(1):41–54, 1995.
  * [37] B. Sudakov and I. Tomon.  The extremal number of tight cycles.  International Mathematics Research Notices, 2022:9663–9684, 2022\.
  * [38] I. Tomon.  Robust (rainbow) subdivisions and simplicial cycles.  arXiv preprint arXiv:2201.12309, 2022.
  * [39] J. Verstraëte.  On arithmetic progressions of cycle lengths in graphs.  Combinatorics, Probability and Computing, 9(4):369–373, 2000.
  * [40] J. Verstraëte.  Extremal problems for cycles in graphs.  In Recent trends in Combinatorics, pages 83–116. Springer, 2016\.
  * [41] R. Wenger.  Extremal graphs with no $C^{4}$’s, $C^{6}$’s, or $C^{10}$’s.  Journal of Combinatorial Theory, Series B, 52(1):113–116, 1991\.