###### Proof.

###### The Turán density of tight cycles in three-uniform hypergraphs

###### Abstract

The _Turán density_ of an $r$-uniform hypergraph $\mathcal{H}$, denoted
$\pi(\mathcal{H})$, is the limit of the maximum density of an $n$-vertex
$r$-uniform hypergraph not containing a copy of $\mathcal{H}$, as
$n\to\infty$.

Denote by $\mathcal{C}_{\ell}$ the $3$-uniform tight cycle on $\ell$ vertices.
Mubayi and Rödl conjectured that the Turán density of $\mathcal{C}_{5}$ is
$2\sqrt{3}-3\approx 0.464$, and gave an “iterated blow-up” construction
showing that this is tight. Their construction also does not contain
$\mathcal{C}_{\ell}$ for larger $\ell$ not divisible by $3$, which suggests
that it might be the extremal construction for these hypergraphs as well.
Here, we determine the Turán density of $\mathcal{C}_{\ell}$ for all large
$\ell$ not divisible by $3$, showing that indeed
$\pi(\mathcal{C}_{\ell})=2\sqrt{3}-3$. To our knowledge, this is the first
example of a Turán density being determined where the extremal construction is
an iterated blow-up construction.

A key component in our proof, which may be of independent interest, is a
$3$-uniform analogue of the statement “a graph is bipartite if and only if it
does not contain an odd cycle”.

##  1 Introduction

For an $r$-uniform hypergraph $\mathcal{H}$, the _Turán number_ of
$\mathcal{H}$, denoted $\operatorname{ex}(n,\mathcal{H})$, is defined as the
maximum number of edges an $n$-vertex $r$-uniform hypergraph can have without
containing a copy of $\mathcal{H}$ as a subgraph. For ($2$-uniform) graphs, we
have a fairly good understanding of Turán numbers. The first theorem proved
about them is Mantel’s theorem [23], which says that, for the triangle, we
have $\operatorname{ex}(n,K_{3})=\left\lfloor n^{2}/4\right\rfloor$. This was
generalised by Turán [32] who showed that
$\operatorname{ex}(n,K_{r})\approx(1-\frac{1}{r-1})\binom{n}{2}$. For non-
complete graphs we know less, and usually only know what the Turán number of a
graph is asymptotically, up to $o(n^{2})$ terms. Because of this, we study the
_Turán density_ of an $r$-uniform hypergraph $\mathcal{H}$, denoted
$\pi(\mathcal{H})$, and defined as
$\pi(\mathcal{H})=\lim_{n\to\infty}\frac{\operatorname{ex}(n,\mathcal{H})}{\binom{n}{r}}$.
This limit is known to exist, and, moreover, it is clear that
$\pi(\mathcal{H})\in[0,1]$ for every $H$. The Turán densities of ($2$-uniform)
graphs were completely determined by Erdős and Stone [8], who showed that
every graph $H$ satisfies $\pi(H)=1-\frac{1}{\chi(H)-1}$.

The special case of the Erdős–Stone theorem for bipartite graphs can be
generalised to higher uniformities, as follows (see [7]): every $r$-partite
$r$-uniform hypergraph $\mathcal{H}$ satisfies $\pi(\mathcal{H})=0$. (An
$r$-uniform hypergraph $\mathcal{H}$ is said to be _$r$ -partite_ if its
vertices can be $r$-coloured so that every edge has one vertex of each
colour.) Nevertheless, in general, our understanding of Turán numbers in
higher uniformities is very limited, and there is only a small number of
hypergraphs whose Turán densities are known; see Keevash [18] for a
comprehensive survey of the topic listing a number of such hypergraphs. A
notable, relatively early example is a result of de Caen and Füredi [6]
showing that the Turán density of the Fano plane is $3/4$ (see also [13, 19]).
More recently, the impactful computer-assisted “flag-algebra” technique has
been used to obtain a number of sharpest known upper bounds on Turán densities
(see [1, 18, 29] and the references therein).

Given the sporadicity of hypergraphs whose Turán densities are known, it is
unsurprising that there are many conjectures about Turán densities of specific
hypergraphs. The most famous of these is Turán’s conjecture [33], that the
Turán density of the tetrahedron $K_{4}^{(3)}$ is $5/9$. Frankl and Füredi
[12] conjectured that the the Turán density of the 3-edge subgraph of
$K_{4}^{(3)}$ (usually denoted $K_{4}^{-}$) is $2/7$. A particularly relevant
conjecture for us concerns tight cycles. The _$r$ -uniform tight cycle_ of
length $\ell$, denoted $\mathcal{C}_{\ell}^{r}$, is defined to be the
hypergraph with vertex set $\\{1,\dots,\ell\\}$ and hyperedges all sets of the
form $\\{x,x+1,\dots,x+r-1\\!\pmod{\ell}\\}$. The following conjecture,
usually attributed to Mubayi and Rödl, appears for instance in [10, 24].

######  Conjecture 1.1.

$\pi(\mathcal{C}_{5}^{3})=2\sqrt{3}-3$.

The lower bound $\pi(\mathcal{C}_{5}^{3})\geq 2\sqrt{3}-3\approx 0.464$ was
found by Mubayi and Rödl (see Example 1.2 below for a description of their
example) and the best upper bound is due to Razborov [27], who showed
$\pi(\mathcal{C}_{5}^{3})\leq 0.468$.

One basic reason why hypergraphs are more difficult than graphs is that the
extremal $\mathcal{H}$-free hypergraphs can be much more complicated than the
extremal graphs. In the 2-uniform case, the Erdős–Stone theorem shows that all
optimal graphs are close to being complete multipartite. For higher-uniformity
hypergraphs there have been numerous papers discovering more complicated
possible extremal hypergraphs, for instance [3, 12, 2], as well as Conjectures
1.1 and 7.1. For some hypergraphs, such as $K_{4}^{(3)}$, the conjectured
extremal constructions are even non-unique and very different from each other
[3, 20, 11, 28].

One class of extremal examples, which does not occur for graphs, is an
“iterated blow-up construction”. The conjectured extremal example for
Conjecture 1.1 is an instance of such a construction.

######  Example 1.2 (Iterated blow-up construction with no copies of
$\mathcal{C}_{5}^{3}$).

Consider nested vertex sets $V_{1}\supseteq\ldots\supseteq V_{t}$ with
$|V_{i}|=x_{i}$. Let $\mathcal{H}(x_{1},\ldots,x_{t})$ be a 3-uniform
hypergraph on the vertex set $V_{1}$, where $xyz$ is an edge whenever $x,y\in
V_{i}$ and $z\in V_{i+1}$ for some $i$ (see Figure 1).

We claim that there is no copy of $\mathcal{C}_{5}^{3}$. To see this, say that
an edge with two vertices in $V_{i}\setminus V_{i+1}$ and one vertex in
$V_{i+1}$ has _type $i$_, and observe that if two edges $e$ and $f$ intersect
in two vertices, they are of the same type. Thus, if $C=(u_{1}\ldots u_{5})$
is a cycle, then its edges all have the same type, say $i$. Without loss of
generality, $u_{1}\in V_{i}\setminus V_{i+1}$ and $u_{2},u_{3}\in V_{i+1}$. It
follows that $u_{4}\in V_{i}\setminus V_{i+1}$, and thus $u_{5}\in V_{i+1}$.
But then $u_{4}u_{5}u_{1}$ is not an edge of
$\mathcal{H}(x_{1},\ldots,x_{t})$, a contradiction.

Thus $\pi(\mathcal{C}_{5}^{3})\geq
e(\mathcal{H}(x_{1},\ldots,x_{t}))/\binom{n}{3}$ for all choices of
$x_{1},\ldots,x_{t}$. Let $f(n)$ denote the maximum number of edges that such
a hypergraph on $n$ vertices can have i.e
$f(n):=\max(e(\mathcal{H}(x_{1},\ldots,x_{t}):x_{t}\leq\dots\leq x_{1}=n)$. It
is possible to show $\lim_{n\to\infty}f(n)/\binom{n}{3}=2\sqrt{3}-3$ (see
Section 4 for details), which gives $\pi(\mathcal{C}_{5}^{3})\geq
2\sqrt{3}-3$.

Let $\mathcal{G}_{n}=\mathcal{H}(x_{1},\ldots,x_{t})$ for a choice of
$n=x_{1}\geq\ldots\geq x_{t}$ such that $e(\mathcal{G}_{n})=f(n)$.

$V_{1}$$V_{2}$$V_{3}$$V_{4}$ Figure 1: An illustration of the hypergraph
$\mathcal{H}(x_{1},x_{2},x_{3},x_{4})$.

Note that in the above construction, $\mathcal{G}_{n}$ has no tight cycles of
lengths $\ell\equiv 1$ or $2\\!\pmod{3}$ either. So it is plausible that
Conjecture 1.1 could be strengthened to say that
$\pi(\mathcal{C}_{\ell}^{3})=2\sqrt{3}-3$ for all $\ell\geq 5$ with
$\ell\equiv 1$ or $2\pmod{3}$ (notice that $\mathcal{C}_{4}^{3}=K_{4}^{(3)}$,
and there are known examples of $K_{4}^{(3)}$-free $3$-uniform graphs with
density at least $5/9>2\sqrt{3}-3$). The main result of our paper is to show
that this is true for sufficiently large $\ell$.

######  Theorem 1.3.

Let $\ell$ be sufficiently large with $\ell\equiv 1$ or $2\\!\pmod{3}$. Then
$\pi(\mathcal{C}_{\ell}^{3})=2\sqrt{3}-3$.

To our knowledge, this is the first example of a Turán density being
determined where the extremal construction is an iterated blow-up
construction, and could be a step towards Conjecture 1.1. This is also one of
the few examples of hypergraphs with irrational Turán densities. Such
hypergraphs were recently found by Yan and Peng [35], as well as Wu [34],
motivated by the work of Chung and Graham [5], Baber and Talbot [1], and
Pikhurko [26]. We remark that Conjecure 1.1 would imply Theorem 1.3 via
Theorem 2.1 below (using the same argument as in the proof of Theorem 1.3 in
Section 6).

One of our main tools, which may be of independent interest, is a 3-uniform
analogue of the statement “a graph is bipartite if and only if it does not
contain an odd cycle”; see Theorem 2.4. Thus, we characterise 3-uniform
hypergraphs $\mathcal{H}$ which do not contain homomorphic images of cycles
$\mathcal{C}^{3}_{\ell}$ with $3\nmid\ell$, in terms of certain colourings of
$V(\mathcal{H})^{2}$, as explained in the proof overview.

Throughout the paper we will informally refer to 3-uniform cycles of length
$\ell\equiv 1$ or $2\pmod{3}$ as “odd cycles”, and we will often refer to
$3$-uniform hypergraphs as 3-graphs.

### Related results

As we mentioned, there are very few hypergraphs with a known Turán density,
but let us state some recent results on Turán-type problems for tight cycles.
A well-studied hypergraph parameter is the so-called _uniform Turán density_ ,
the infimum over all $d$ for which any sufficiently large hypergraph with the
property that all its linear-size subhyperghraphs have density at least $d$
contains $\mathcal{H}$. This line of research was initiated by Erdős and Sós
[9] and, parallel to the classical Turán densities, the motivating questions
in the area are determining the uniform Turán densities of the tetrahedron
$K_{4}^{(3)}$ and its 3-edge subgraph $K_{4}^{-}$. The latter was found to be
$1/4$ by Glebov, Kráľ, and Volec [14] and later by Reiher, Rödl, and Schacht
[30] with a different proof. In 2022, Bucić, Cooper, Kráľ, Mohr, and Munha
Correia showed that for $\ell\geq 5$ and not divisible by 3, the uniform Turán
density of $\mathcal{C}_{\ell}^{3}$ is $\frac{4}{27}$ [4].

Another question that has attracted a lot of interest in the last few years is
this: what is the extremal number of tight cycles (the maximum number of edges
in an $n$-vertex $r$-uniform hypergraph containing no tight cycles)? For
$r=2$, the answer is of course $n-1$, but it turns out that the behaviour is
rather different for $r\geq 3$. More specifically, after a series of results
[16, 17, 31, 21], we know that the extremal number of tight $r$-uniform cycles
lies between $\Omega\left(n^{r-1}\log n/\log\log n\right)$ and
$O\left(n^{r-1}\log^{5}n\right)$.

##  2 Proof overview

For an $r$-uniform hypergraph $\mathcal{H}$, the _$t$ -blow-up_ of
$\mathcal{H}$, denoted $\mathcal{H}[t]$, is defined to be the $r$-uniform
hypergraph with vertex set $V(\mathcal{H})\times[t]$ and edges all $r$-tuples
$\\{(x_{1},i_{1}),\dots,(x_{r},i_{r})\\}$ with $\\{x_{1},\dots,x_{r}\\}\in
E(\mathcal{H})$. The starting point of our proof is the following theorem,
which asserts that the blow-up of a hypergraph $\mathcal{H}$ has the same
Turán density as $\mathcal{H}$.

######  Theorem 2.1 ([18], Theorem 2.2).

Let $t$ be an integer and let $\mathcal{H}$ be an $r$-uniform hypergraph. Then
$\pi(\mathcal{H}[t])=\pi(\mathcal{H})$.

It shows that, rather than focusing on the Turán density
$\pi(\mathcal{C}_{k}^{3})$ for an odd cycle $C_{k}^{3}$, we can instead work
out the Turán density of $\pi(\mathcal{H})$ for any hypergraph $\mathcal{H}$
whose blow-up $\mathcal{H}[t]$ contains $\mathcal{C}_{k}^{3}$ for some $t$. We
refer to such hypergraphs $\mathcal{H}$ as pseudocycles, and they can be
equivalently defined as follows.

######  Definition 2.2.

A _pseudocycle_ of length $\ell$ in a 3-uniform hypergraph $\mathcal{H}$ is a
sequence of (not necessarily distinct) vertices $v_{1},\ldots,v_{\ell}$, such
that for each $i\in[\ell]$, we have that
$\\{v_{i},v_{i+1\\!\pmod{\ell}},v_{i+2\\!\pmod{\ell}}\\}$ is an edge of
$\mathcal{H}$. A _pseudopath_ of order $\ell$ is defined analogously.

It is easy to show that for a hypergraph $\mathcal{H}$, the properties
“$\mathcal{H}[t]$ contains a $\mathcal{C}_{k}^{3}$ for some $t$” and
“$\mathcal{H}$ contains a length $k$ pseudocycle” are equivalent.

Thus, the next question is — what is the maximum number of edges that a
3-uniform hypergraph can have without containing an odd pseudocycle? To
understand our approach to this, consider the analogous question about graphs
— what is the maximum number of edges in a (2-uniform) graph with no odd
circuits? This is easy to answer using Kotzig’s Lemma — a graph has no odd
circuit if, and only if, it is bipartite. The maximum number of edges in an
$n$-vertex bipartite graph is $\left\lfloor\frac{n^{2}}{4}\right\rfloor$.

Our approach to the 3-uniform case is analogous to this. We first find the
relevant generalisation of bipartite graphs, and then maximise the number of
edges over this class of graphs. To define this generalisation, recall that a
graph is bipartite if, and only if, it has a proper 2-vertex-colouring. In our
context, we will be colouring the shadow of a 3-uniform hypergraph. The
_shadow_ of a hypergraph $\mathcal{H}$, denoted $\partial\mathcal{H}$, is the
graph on vertices $V(\mathcal{H})$ whose edges are pairs $xy$ that are
contained in an edge in $\mathcal{H}$.

######  Definition 2.3.

A _good colouring_ of a 3-uniform hypergraph $\mathcal{H}$ is a colouring of
its shadow, such that each edge $xy$ in the shadow is either coloured blue or
coloured red and given an orientation, and every edge $e$ in $\mathcal{H}$ can
be written as $xyz$ where $xy$ and $xz$ are red and directed from $x$ and $yz$
is blue.

The key first step of our proof is to show that the notion of “good colouring”
is exactly equivalent to $\mathcal{H}$ not containing an odd pseudocycle.

######  Theorem 2.4.

A 3-uniform hypergraph $\mathcal{H}$ has a good colouring if, and only if,
$\mathcal{H}$ has no pseudocycle of length $\ell$ with $3\nmid\ell$.

This theorem is proved in Section 3. Having established the above theorem, we
next wish to maximise the number of edges in a hypergraph with a good
colouring. To this end, we define a _coloured graph_ to be a complete graph
whose edges are either coloured blue or coloured red and oriented. A _cherry_
in a coloured graph $G$ is a triple $xyz$ such that $xy$ and $xz$ are red and
directed from $x$ and $yz$ is blue. Denote by $c(G)$ the number of cherries in
$G$. Notice that if we have a good colouring of the shadow of $\mathcal{H}$
(and the remaining vertex pairs can be coloured arbitrarily), then all edges
of $\mathcal{H}$ will be cherries in the resulting coloured graph. Thus, let
$m_{\mathrm{cherry}}(n)$ be the maximum number of cherries in an $n$-vertex
coloured graph. The quantity $m_{\mathrm{cherry}}(n)$ has been studied before
by Falgas-Ravry and Vaughan [10], who used flag algebras to show that
$\lim_{n\to\infty}m_{\mathrm{cherry}}/\binom{n}{3}=2\sqrt{3}-3$. Huang [15]
worked on the area further and determined the maximum number of “induced out-
stars” of size $t$ in an $n$-vertex coloured graph. The following special case
of their results is relevant for us.

######  Theorem 2.5 (Falgas-Ravry–Vaughan [10]; Huang [15]).

Every coloured graph on $n$ vertices contains at most $f(n)$ cherries.

Combining Theorem 2.4 and Theorem 2.5 already yields the following weakening
of Theorem 1.3.

######  Corollary 2.6.

If $\mathcal{H}$ is a $3$-uniform hypergraph on $n$ vertices which contains no
pseudocycles of order $\ell$ with $3\nmid\ell$, then $e(\mathcal{H})\leq
f(n)$.

Thus, the next goal is to prove a version of the above corollary which holds
when forbidding _short pseudocycles_. This is done by controlling the diameter
of the hypergraph $\mathcal{H}$.

######  Definition 2.7.

The _diameter_ of a hypergraph $\mathcal{H}$ is the minimum $\ell$ such that
the following holds: for every $x,y,z,w\in V(\mathcal{H})$ (where $x,y$ are
distinct and $z,w$ are distinct) whenever there is a pseudopath from $xy$ to
$zw$, there is such a pseudopath of order at most $\ell$.

In Section 6, we show that, for $\ell\gg\epsilon^{-1}$, every 3-uniform
hypergraph $\mathcal{H}$ contains a subhypergraph $\mathcal{H}^{\prime}$ with
$e(\mathcal{H}^{\prime})\geq e(\mathcal{H})-\epsilon n^{3}$ such that
$\mathcal{H}^{\prime}$ has diameter at most $\ell$ (see Proposition 6.4). Then
we show that in every 3-uniform hypergraph of diameter $\ell$, if there is
some odd pseudocycle, then there is also an odd pseudocycle of length at most
$4\ell$ (see Proposition 6.3). Combining these with Corollary 2.6 shows the
following

######  Corollary 2.8.

Let $1/n\ll 1/\ell\ll\epsilon\ll 1$, and let $\mathcal{H}$ be an $n$-vertex
hypergraph with no odd pseudocycles of length at most $\ell$. Then
$e(\mathcal{H})\leq f(n)+\epsilon n^{3}$.

Note that this is still not strong enough to combine with Theorem 2.1 to yield
Theorem 1.3. The issue is that the length of the cycle $\ell$ depends on
$\epsilon$ — therefore, when combined with Theorem 2.1, we would only get that
$\lim_{m\to\infty}\pi(\mathcal{C}_{m}^{3})=2\sqrt{3}-3$. To go further, we
prove a “stability version” of Theorem 2.5. We show that if a coloured graph
$D$ on $n$ vertices contains more than $f(n)-\epsilon n^{3}$ cherries, then
$D$ must have a very constrained structure similar to the iterated blow-up
construction (see Theorem 5.2 for the precise statement). Once we have this,
we can obtain the following strengthening of Corollary 2.8

######  Theorem 2.9.

There exists $L>0$ such that the following holds. If $\mathcal{H}$ is a
$3$-uniform hypergraph on $n$ vertices which contains no pseudocycles of
length $\ell$, with $\ell\leq L$ and $3\nmid\ell$, then $e(\mathcal{H})\leq
f(n)+O(1)$.

This theorem easily combines with Theorem 2.1 in order to give our main
result, Theorem 1.3 (see Section 6).

##  3 Finding a good colouring

Recall that a _pseudocycle_ of order $m$ (or _$m$ -pseudocycle_) is a sequence
$v_{1}\ldots v_{m}$ such that $v_{i}v_{i+1}v_{i+2}$ is an edge for $i\in[m]$
(indices taken mod $3$). A _pseudopath_ of order $m$ is defined analogously. A
hypergraph is called tightly connected if there is a pseudopath between any
two edges. Given vertices $x,y,z,w$ (not necessarily distinct), a pseudopath
from $xy$ to $zw$ (where $xy$ and $zw$ are ordered pairs) is a pseudopath
whose first two vertices are $x$ and $y$ (in this order) and the last two
vertices are $z$ and $w$. The _shadow_ of a hypergraph $\mathcal{H}$, denoted
$\partial\mathcal{H}$, is the graph on vertices $V(\mathcal{H})$ whose edges
are pairs $xy$ that are contained in an edge in $\mathcal{H}$.

Recall that a _good colouring_ of a hypergraph $\mathcal{H}$ is a colouring of
its shadow, such that each edge $xy$ in the shadow is either coloured blue or
coloured red and given an orientation, and every edge $e$ in $\mathcal{H}$ can
be written as $xyz$ where $xy$ and $xz$ are red and directed from $x$ and $yz$
is blue. Such an edge is called a _cherry_ , and the the vertex $x$ is called
its _apex_.

Figure 2: A cherry $xyz$ with apex $x$

In this section, we will prove Theorem 2.4, restated here. See 2.4 It is easy
to see that a hypergraph with a good colouring has no psedocycles of length
$\ell$ with $3\nmid\ell$, so the main effort will be put into proving the “if”
direction. Namely, we need to show that every hypergraph with no odd
pseudocycles has a good colouring. Before specifying such a colouring, let us
give some intuition. Any proper path (that is, with no repetitions)
$v_{1}\ldots v_{k}$ has a good colouring, and this colouring is unique given
the colour of $v_{1}v_{2}$ (see Figure 3 for the three good colourings of a
path of order 9, and notice that each such colouring colours each edge in the
shadow differently).

Figure 3: The three good colourings of a path of order $9$

A proper cycle has a good colouring if and only if it is tripartite (i.e. the
number of vertices is divisible by 3). See Figure 4 for a good colouring of a
cycle of length 18 and notice that every third vertex is an apex.

Figure 4: A good colouring of a cycle whose length is divisible by $3$

Moreover, if there is a path $P=xy\ldots yx$, then the order of $P$ uniquely
determines the colour of $xy$. This fact will be used to construct a good
colouring of our hypergraph $\mathcal{H}$ – we will start from a specific pair
$xy$ and extend the colouring uniquely along pseudopaths. The difficulty is to
show that this colouring is well defined, so the actual colouring definition
will involve some more formalism. For a pseudopath $P=v_{1}\ldots v_{k}$,
define $\tilde{P}$ by

$\tilde{P}:=v_{k-1}v_{k}v_{k-2}v_{k-1}v_{k-3}\dots v_{4}v_{2}v_{3}v_{1}v_{2};$
(1)

note that $\tilde{P}$ is a pseudopath from $v_{k-1}v_{k}$ to $v_{1}v_{2}$ of
order $2k-2$ (because every vertex but $v_{1}$ and $v_{k}$ appears twice).

###### Proof of Theorem 2.4.

Whenever we talk about a path or cycle in this proof, we mean a pseudopath or
pseudocycle.

As we said above, it is easy to show that a hypergraph with a good colouring
has no odd cycles, so it suffices to show that if $\mathcal{H}$ has no odd
cycles then $\mathcal{H}$ has a good colouring. Note that we may assume that
$\mathcal{H}$ is tightly connected.

Let $P_{0}$ be a shortest path with the property that its first two vertices
are the same as the last two but in reversed order, if such a path exists.
Write $P_{0}:=v_{0}\ldots v_{k}$ and denote $x:=v_{0}=v_{k}$ and
$y:=v_{1}=v_{k-1}$.

Define $\sigma$ as follows.

$\sigma\equiv 2k\,(\mathrm{mod}\,\,3).$ (2)

Intuitively, $\sigma$ is defined so that if $P_{0}$ has a good colouring, then
the apexes in this colouring are at index $\sigma\pmod{3}$. If $P_{0}$ does
not exist, define $\sigma=2$.

Let $\\{z,w\\}$ be an edge in the shadow of $\mathcal{H}$, and let
$P=xyv_{2}v_{3}\ldots v_{k}$ be a path from $xy$ whose last three vertices
contain $z$ and $w$. Let $i_{w}\in\\{k-2,k-1,k\\}$ be the index of $w$
(namely, $v_{i_{w}}=w$), and define $i_{z}$ analogously. Define the index

$\eta(P,\\{z,w\\})=\begin{cases}w,&i_{w}\equiv\sigma\,(\mathrm{mod}\,\,3),\\\
z,&i_{z}\equiv\sigma\,(\mathrm{mod}\,\,3),\\\ *,&\text{otherwise}.\end{cases}$

In particular, this defines $\eta(xy,\\{x,y\\})$. We claim that
$\eta(P,\\{z,w\\})$ is independent of the choice of the path $P$.

######  Claim 3.1.

Let $z,w\in V(\mathcal{H})$ be distinct. Let $P=v_{0}\ldots v_{p}$ and
$Q=u_{0}\ldots u_{q}$ be two paths starting at $xy$ such that $z$ and $w$ are
among their last three vertices. Then

$\eta(P,\\{z,w\\})=\eta(Q,\\{z,w\\}).$

###### Proof.

Let $i_{z}\in\\{p-2,p-1,p\\}$ such that $v_{i_{z}}=z$, and define $j_{z}$
similarly with respect to $Q$. It suffices to prove that
$i_{z}\equiv\sigma\,(\mathrm{mod}\,\,3)$ if and only if
$j_{z}\equiv\sigma\,(\mathrm{mod}\,\,3)$. For, then the same equivalence holds
for $w$. But this implies that $\eta(P,\\{z,w\\})=*$ if and only if
$\eta(Q,\\{z,w\\})=*$.

First, we modify $P$ so as to assume that $P$ ends with $zw$ or $wz$. If this
is not the case, then up to swapping $z$ and $w$ we have that $P$ ends with
either $zw*$ or $z*w$. In the former case remove the last vertex of $P$, and
in the latter case append $z$ to $P$. It is easy to see that the statement of
the claim holds for the original $P$ if and only if it holds for the modified
path. Similarly, we may assume that $Q$ ends with $zw$ or $wz$.

Assume first that $P$ and $Q$ both end with $zw$. Then $\tilde{Q}$ (defined as
in (1)) is a path from $zw$ to $xy$ of order $2(q+1)-2=2q$. Hence
$v_{2}v_{3}\ldots v_{p-2}\tilde{Q}$ is a cycle, and by assumption its order is
divisible by 3. That is, $p-3+2q\equiv 0\,(\mathrm{mod}\,\,3)$, and thus
$p\equiv q\,(\mathrm{mod}\,\,3)$. Since $i_{z}=p-1$ and $j_{z}=q-1$, this
proves Claim 3.1. The same argument holds when $P$ and $Q$ both end with $wz$.

Secondly, assume that $P$ is a path from $xy$ to $zw$ and $Q$ is a path from
$xy$ to $wz$. Note that this case only arises if $P_{0}$ is defined, as
$v_{0}v_{1}\ldots v_{p-2}zwu_{q-2}\dots u_{0}$ is a path from $xy$ to $yx$.
Then consider the cycle $v_{2}\ldots v_{p-2}zwu_{q-2}\ldots
u_{2}\tilde{P_{0}}$. This is indeed a cycle because $u_{1}u_{0}=yx$,
$v_{0}v_{1}=xy$ and $\tilde{P_{0}}$ is a path from $yx$ to $xy$. The order of
this cycle is $p-3+2+q-3+2k\equiv p+q+2+\sigma\,(\mathrm{mod}\,\,3)$, using
(2). Now substitute $p=i_{z}+1$ and $q=j_{z}$. We have
$i_{z}+j_{z}+\sigma\equiv 0\,(\mathrm{mod}\,\,3)$, so
$i_{z}\equiv\sigma\,(\mathrm{mod}\,\,3)$ if and only if
$j_{z}\equiv\sigma\,(\mathrm{mod}\,\,3)$. ∎

Note that for every edge $\\{z,w\\}$ in the shadow of $\mathcal{H}$ there is a
path $P$ starting at $xy$ whose last three vertices contain $z$ and $w$.
Indeed, as $\mathcal{H}$ is tightly connected, there is a path $Q$ such that
$x$ and $y$ are among its first three vertices and $z$ and $w$ among its last
three vertices. Using a modification as in the proof of Claim 3.1 we may
assume that $Q$ starts with $xy$ or $yx$. If it starts with $xy$ we are done,
and otherwise the reverse of the path $\tilde{Q}$ satisfies the requirements.

Given an edge $\\{z,w\\}$ in the shadow of $\mathcal{H}$, define
$\eta(zw)=\eta(P,\\{zw\\})$, where $P$ is any path from $xy$ whose last three
vertices contain $z$ and $w$ (which exists by the previous paragraph). This
parameter is well defined by Claim 3.1. Now define $\chi$ as follows: let $zw$
be blue if $\eta(zw)=*$, and let it be red and oriented away from $\eta(zw)$
otherwise.

Finally, we show that $\chi$ is a good colouring. To see this, consider an
edge $uvw$ of $G$. Let $P$ be a path from $xy$ whose last three vertices are
$u,v,w$ (in some order); such a path exists by the paragraph above. Write
$P:=xyv_{2}v_{3}\ldots v_{p-2}v_{p-1}v_{p}$, let $i\in\\{p-2,p-1,p\\}$ with
$i\equiv\sigma\,(\mathrm{mod}\,\,3)$, and we may assume that $v_{i}=u$. Then
$\eta(uv)=\eta(uw)=u$ and $\eta(vw)=*$, which implies that $uvw$ is a cherry
with apex $u$. ∎

######  Remark.

Our proof actually shows that if $G$ does not contain a path $P_{0}$ starting
and ending with $xy$ and $yx$ respectively, then the graph is tripartite.

Notice that a good colouring of $\mathcal{H}$ can be extended from the shadow
of $\mathcal{H}$ to $K_{n}$ with no restrictions. Thus, in what follows it
will suffice to analyse colourings of complete graphs by blue edges and red
oriented edges (we will call such graphs _coloured graphs_).

##  4 Maximising the number of cherries

The results of the previous section establish a connection between maximising
the number of edges in an odd-pseudocycle-free hypergraph and maximising the
number of cherries in colourings of $K_{n}$ (formally defined below). It will
turn out that both problems have the same extremal construction which yields
the maximum $f(n)$. Recall that we have defined $f(n)$ as the maximum number
of edges in a hypergraph $\mathcal{H}(x_{1},\ldots,x_{k})$ with
$\sum_{i}{x_{i}}=n$. An explicit expression for $f$ is

$f(n)=\max_{k\geq 1}\max_{\begin{subarray}{c}x_{1},\ldots,x_{k}\geq 1:\\\
x_{1}+\ldots+x_{k}=n\end{subarray}}\left\\{\sum_{1\leq i<j\leq
k}\binom{x_{i}}{2}\cdot x_{j}\right\\}.$ (3)

Equivalently, we have the recursive characterisation

$\displaystyle\begin{split}&f(1)=0,\\\
&f(n)=\max_{k\in[n-1]}\binom{k}{2}(n-k)+f(n-k)\,\,\text{ for $n\geq
2$}.\end{split}$ (4)

Write

$\beta=\frac{3-\sqrt{3}}{2}\approx
0.634\qquad\text{and}\qquad\alpha=\frac{\beta(1-\beta)}{2(3-3\beta+3\beta^{2})}=\frac{\sqrt{3}}{3}-\frac{1}{2}\approx
0.077.$ (5)

The following proposition will be proved in Section 5.2.

######  Proposition 4.1.

$f(n)=\alpha n^{3}+o(n^{3})$.

We remark that the density of the corresponding hypergraph $\mathcal{H}_{n}$
is $6\alpha=2\sqrt{3}-3$, as already noted by Mubayi and Rödl [25].

As in Section 2, we call a graph $G$ _coloured_ if it is a complete graph
whose edges are either coloured blue or coloured red and oriented. A _cherry_
in a coloured graph $G$ is a triple $xyz$ such that $xy$ and $xz$ are red and
directed from $x$ and $yz$ is blue. Denote by $c(G)$ the number of cherries in
$G$. Theorem 2.5 states that $c(G)\leq f(n)$ for any $n$-vertex coloured graph
$G$. Recall that this was originally proved by Falgas-Ravry and Vaughan [10]
(who used flag algebras and also proved a similar result for out-directed
stars on four vertices) and by Huang [15] (who used a symmetrisation argument,
and proved a similar result for out-directed stars on $k$ vertices, for every
$k\geq 3$). Nevertheless, we provide a proof, both for completeness and
because we need most of the groundwork to prove a stability version of Theorem
2.5.

As mentioned in the proof overview (Section 2), Corollary 2.6, which is a weak
version of our main result and is restated here, follows directly from Theorem
2.5 (proved in the next section) and Theorem 2.4 (proved in the previous
section).

See 2.6

##  5 Stability with symmetrisation

Most of the work in this section will go into proving the following lemma,
providing a stability version of Theorem 2.5. It will then be iterated to
prove a stability result about cherries in coloured graphs; recall that
$\beta=(3-\sqrt{3})/2$ (see (5)).

We point out that this stability result is somewhat similar to a general
result due to Liu–Pikhurko–Sharifzadeh–Staden [22] which allows one to obtain
stability versions of a class of extremal results that can be proved using a
symmetrisation argument. However, while we indeed prove the extremal result in
Theorem 2.5 using a symmetrisation argument, the result in [22] does not apply
to automatically convert it into a stability result.

######  Lemma 5.1.

Let $1/n\ll\varepsilon\ll 1$ and let $G$ be a coloured graph on $n$ vertices
satisfying $c(G)\geq f(n)-\varepsilon^{2}n^{3}$. Then there is a coloured
graph $G^{\prime}$ on $V(G)$ satisfying: $c(G^{\prime})\geq c(G)$; the graphs
$G$ and $G^{\prime}$ differ on at most $800\varepsilon^{1/2}n^{2}$ edges;
moreover, there is a set $Q\subseteq V(G)$ satisfying $\big{|}|Q|-\beta
n\big{|}\leq 100\varepsilon n$; $Q$ is a blue clique in $G^{\prime}$; and all
other edges in $G^{\prime}$ that are incident with $Q$ are red and oriented
towards $Q$.

The proof consists of two main parts: first we show that $G$ has a blue
almost-clique on a vertex set $Q^{\prime}$ of size roughly $\beta n$. Then we
show that most $(V\setminus Q^{\prime},Q^{\prime})$ edges are red and point
towards $Q^{\prime}$. In both parts, we make use of a “symmetrisation
procedure” which builds blue cliques without decreasing the number of
cherries.

A _blue clone-clique_ in a coloured graph $G$ is a set of vertices $Q$ such
that $Q$ is a blue clique in $G$, and for any $v\notin Q$, either all edges
between $v$ and $Q$ are blue, or they are all red and have the same
orientation (namely, they all point towards $v$ or all point away from $v$). A
_full blue clone-clique_ is a blue clone-clique $Q$ such that all $(V\setminus
Q,Q)$ edges are red.

The symmetrisation procedure, which will be described in detail in the next
section, receives as input a vertex $x$ in a graph $G$, and produces a graph
$G^{\prime}$ on the same vertex set, which has at least as many cherries as
$G$ and has a full blue clone-clique $Q$ in $G^{\prime}$ that contains $x$.

The symmetrisation procedure can be applied repeatedly to a coloured graph $G$
to find a coloured graph $G^{\prime}$ with at least as many cherries as $G$,
and whose vertices can be partitioned into full blue clone-cliques. Some
calculus (detailed in Section 5.2) will show that such a $G^{\prime}$ contains
a full blue clone-clique $Q^{\prime}$ of size approximately $\beta n$.

To proceed we need two lemmas (Lemmas 5.6 and 5.7; see Section 5.3) that
together tell us the following. Suppose that a symmetrisation procedure on $G$
resulted in a full blue clone-clique $Q$, of size approximately $\beta n$.
Then (even before performing symmetrisation) almost all edges in
$G[Q,V\setminus Q]$ are red and point towards $Q$, and almost all edges in
$G[Q]$ are blue.

Applying these lemmas to the previously found blue clone-clique $Q^{\prime}$,
we conclude first that $G[Q^{\prime}]$ is almost fully blue. We then show that
there is a particular instance of the symmetrisation procedure that results in
a graph $G^{\prime}$ and full blue clone-clique $Q$ such that $Q$ and
$Q^{\prime}$ differ on only few vertices. Lemma 5.6 implies that almost all
$G[Q^{\prime},V\setminus Q^{\prime}]$ edges are red and point towards
$Q^{\prime}$. This essentially completes the proof. This part is detailed in
Section 5.4.

In Section 5.5, we iterate Lemma 5.1 to prove the following result.

######  Theorem 5.2.

Let $1/n\ll\varepsilon_{1}\ll\varepsilon_{2}\ll 1$. Let $G$ be a coloured
graph on $n$ vertices satisfying $c(G)\geq f(n)-\varepsilon_{1}n^{3}$. Then
there exists a coloured graph $G^{\prime}$ on the same vertex set, satisfying:

  1. (a)

$c(G^{\prime})\geq c(G)$,

  2. (b)

$G$ and $G^{\prime}$ differ on at most $\varepsilon_{2}n^{2}$ edges,

  3. (c)

the vertices of $G^{\prime}$ can be partitioned into $Q_{1},\ldots,Q_{t}$ such
that:

    1. (i)

$|Q_{1}|\geq\ldots\geq|Q_{t}|$,

    2. (ii)

all edges in $Q_{i}$ are blue, for $i\in[t]$,

    3. (iii)

all edges in $(Q_{i},Q_{j})$ are red and directed towards $Q_{i}$, for $1\leq
i<j\leq t$,

    4. (iv)

$\big{|}|Q_{i}|-\beta\cdot|Q_{i}\cup\ldots\cup
Q_{t}|\big{|}\leq\varepsilon_{2}n$ for $i\in[t]$.

In a coloured graph $G$, let $N^{-}_{G}(x)$ be the red in-neighbourhood of $x$
and let $N^{+}_{G}(x)$ be the red out-neighbourhood of $x$ (we sometimes omit
the subscript $G$).

###  5.1 The symmetrisation procedure

Given $x\in V(G)$, the _symmetrisation procedure_ $S_{G}(x)$ (or $S(x)$ in
short) builds a blue clone-clique containing $x$; see Figure 5 for a detailed
description. The result of the procedure depends on the choice of $x_{k+1}$ in
step 4, but we suppress this dependence in the notation $S_{G}(x)$.

The symmetrisation procedure $S_{G}(x)$

Input: a coloured graph $G$ on vertex set $V$ and a vertex $x\in V$.

Output: a graph $G^{\prime}$ and a full blue clone-clique $Q$ in $G^{\prime}$
containing $x$.

The process: the algorithm builds sequences $x_{1},\ldots,x_{t}$ and
$y_{1},\ldots,y_{t}$ of vertices in $V$ and $G_{1},\ldots,G_{t}$ of graphs on
$V$, for some $t$, as follows.

  1. 1.

Set $x_{1},y_{1}:=x$ and $G_{1}:=G$.

  2. 2.

Suppose $x_{1},\ldots,x_{k}$ and $G_{1},\ldots,G_{k}$ are given and
$\\{x_{1},\ldots,x_{k}\\}$ is a blue clone-clique in $G_{k}$.

  3. 3.

If there are no vertices in $V\setminus\\{x_{1},\ldots,x_{k}\\}$ whose edges
to $\\{x_{1},\ldots,x_{k}\\}$ are blue, put $Q:=\\{x_{1},\ldots,x_{k}\\}$ and
$G^{\prime}:=G_{k}$, and return $G^{\prime}$ and $Q$.

  4. 4.

Otherwise, let $x_{k+1}$ be a vertex in $V\setminus\\{x_{1},\ldots,x_{k}\\}$
which sends blue edges to $\\{x_{1},\ldots,x_{k}\\}$ ($x_{k+1}$ can be chosen
arbitrarily or judiciously).

  5. 5.

For $y\in V$, let $G_{k+1}(y)$ be the graph obtained by replacing
$\\{x_{1},\ldots,x_{k+1}\\}$ by $k+1$ copies of $y$ and letting the new
vertices form a blue clique.

If $c(G_{k+1}(x_{k+1}))-c(G_{k})\geq k\cdot(c(G_{k+1}(x_{1}))-c(G_{k}))$, set
$y_{k+1}=x_{k+1}$, and otherwise let $y_{k+1}=x_{1}$. Define
$G_{k+1}:=G_{k+1}(y_{k+1})$, and return to step 3.

Figure 5: Description of the symmetrisation process $S_{G}(x)$

We now show that the procedure $S_{G}(x)$ does not decrease the number of
cherries. In fact, we prove a stronger quantitative claim.

######  Claim 5.3.

Let $x_{1},\ldots,x_{t}$, $y_{1},\ldots,y_{t}$ and $G_{1},\ldots,G_{t}$ be
sequences produced by $S_{G}(x)$, let $k\in[t-1]$, and use $N^{-}(u)$ as a
shorthand for $N^{-}_{G_{k}}(u)$. Then, one of the following holds.

  1. (i)

$y_{k+1}=x_{1}$ and
$c(G_{k+1})-c(G_{k})\geq\frac{k+1}{4}\cdot\big{|}N^{-}(x_{1})\,\triangle\,N^{-}(x_{k+1})\big{|}$,

  2. (ii)

$y_{k+1}=x_{k+1}$ and
$c(G_{k+1})-c(G_{k})\geq\frac{k(k+1)}{4}\cdot\big{|}N^{-}(x_{1})\,\triangle\,N^{-}(x_{k+1})\big{|}$.

In particular, $c(G_{k+1})\geq c(G_{k})$.

###### Proof.

Let $c(x_{i})$ denote the number of cherries in $G_{k}$ containing $x_{i}$ and
no other vertices in $x_{1},\ldots,x_{k}$. Recall that for
$y\in\\{x_{1},\ldots,x_{k+1}\\}$ the graph $G_{k+1}(y)$ is obtained from
$G_{k}$ by replacing $x_{1},\ldots,x_{k+1}$ by copies of $y$ that form a blue
clique. Write $\Delta_{j}:=c(G_{k+1}(x_{j}))-c(G_{k})$. Then

$\Delta_{j}=(k+1)c(x_{j})-\sum_{i\in[k+1]}c(x_{i})+\binom{k+1}{2}\big{|}N^{-}(x_{j})\big{|}-\frac{1}{2}\sum_{i_{1}\neq
i_{2}}\big{|}N^{-}(x_{i_{1}})\cap N^{-}(x_{i_{2}})\big{|}.$

Summing over $j\in[k+1]$, we obtain

$\displaystyle\sum_{j}\Delta_{j}$
$\displaystyle=\binom{k+1}{2}\sum_{j}\big{|}N^{-}(x_{j})\big{|}-\frac{k+1}{2}\sum_{i\neq
j}\big{|}N^{-}(x_{i})\cap N^{-}(x_{j})\big{|}$
$\displaystyle=\frac{k+1}{2}\sum_{i\neq j}\big{|}N^{-}(x_{j})\setminus
N^{-}(x_{i})\big{|}.$

In particular, since $\\{x_{1},\dots x_{k}\\}$ is a blue clique-clone,

$\displaystyle k\Delta_{1}+\Delta_{k+1}$
$\displaystyle=\frac{k(k+1)}{2}\cdot\left(\big{|}N^{-}(x_{k+1})\setminus
N^{-}(x_{1})\big{|}+\big{|}N^{-}(x_{1})\setminus N^{-}(x_{k+1})\big{|}\right)$
$\displaystyle=\frac{k(k+1)}{2}\cdot\big{|}N^{-}(x_{1})\,\triangle\,N^{-}(x_{k+1})\big{|}.$

Now, $\max(k\Delta_{1},\Delta_{k+1})$ is at least one half of the RHS. Thus,
if $y_{k+1}=x_{k+1}$ then $\Delta_{k+1}\geq k\Delta_{1}$ and so
$\Delta_{k+1}=\max(k\Delta_{1},\Delta_{k+1})\geq\frac{k(k+1)}{4}\cdot\big{|}N^{-}(x_{1})\,\triangle\,N^{-}(x_{k+1})\big{|}$,
and if $y_{1}=x_{1}$ then $k\Delta_{1}>\Delta_{k+1}$ and so
$\Delta_{1}=\max(k\Delta_{1},\Delta_{k+1})\geq\frac{k+1}{4}\cdot|N^{-}(x_{1})\,\triangle\,N^{-}(x_{k+1})\big{|}$.
∎

Theorem 2.5 follows easily from the above claim.

###### Proof of Theorem 2.5.

Let $G$ be a coloured graph on $n$ vertices. Run the following process:
starting with $G^{\prime}=G$, as long as there is a vertex $x$ which is not in
a full blue clone-clique in $G^{\prime}$, run $S_{G^{\prime}}(x)$ and replace
$G^{\prime}$ by the resulting graph. Let $G_{\operatorname{final}}$ be the
graph $G^{\prime}$ at the end of the process (notice that the process will
indeed end, because $S_{G^{\prime}}(x)$ keeps full blue clone-cliques intact).
Then $c(G_{\operatorname{final}})\geq c(G)$ by Claim 5.3, and the vertices of
$G_{\operatorname{final}}$ can be partitioned into full blue clone-cliques
$Q_{1},\ldots,Q_{t}$; for convenience suppose that
$|Q_{1}|\geq\ldots\geq|Q_{t}|$. Replace $G_{\operatorname{final}}$ by the
graph $G_{\operatorname{final}}^{\prime}$ obtained by directing the red edges
between $Q_{i}$ and $Q_{j}$ towards $Q_{i}$, for $1\leq i<j\leq t$. It is
straightforward to verify that $c(G_{\operatorname{final}}^{\prime})\geq
c(G_{\operatorname{final}})$, as the number of cherries in $Q_{i}\cup Q_{j}$
is larger when the arcs in $(Q_{i},Q_{j})$ point towards the larger clique.
Finally, denoting $q_{i}:=|Q_{i}|$, observe that
$c(G_{\operatorname{final}}^{\prime})=\sum_{i\leq j}\binom{q_{i}}{2}q_{j}\leq
f(n)$ (see (3)). Thus $c(G)\leq f(n)$, as claimed. ∎

###  5.2 Optimising the clique size

Before proceeding to analyse the symmetrisation procedure, we prove the
following lemma regarding the structure of a graph whose vertices are
partitioned into full blue clone-cliques, mostly using calculus; recall that
$\alpha$ and $\beta$ are defined in (5).

######  Lemma 5.4.

Let $1/n\ll\varepsilon\ll 1$. Let $G$ be a coloured graph on $n$ vertices
whose vertices can be partitioned into full blue clone-cliques, and suppose
that $c(G)\geq f(n)-\varepsilon^{2}n^{3}$. Then $G$ has a full blue clone-
clique $Q$ satisfying $\big{|}|Q|-\beta n\big{|}\leq 100\varepsilon n$.

Define a function $g:[0,1]\to\mathbb{R}$ as follows.

$g(x)=\frac{x(1-x)}{2(3-3x+x^{2})}.$ (6)

It will be convenient to note the following equation.

$\left(1-(1-x)^{3}\right)\cdot g(x)=\frac{1}{2}\cdot x^{2}(1-x).$ (7)

One can check that $g^{\prime}$ is decreasing and $g^{\prime}(\beta)=0$,
showing that

$g(x)\leq g(\beta)=\alpha\qquad\text{for $x\in[0,1]$}.$ (8)

We first prove Proposition 4.1 regarding the value of $f(n)$.

###### Proof of Proposition 4.1.

We show that $f(n)\leq\alpha n^{3}$ by induction on $n$. This is true for
$n=1$. Suppose that $f(m)\leq\alpha m^{3}$ for $m<n$.

Given $k\in[n-1]$ that maximises the LHS in (4), write $x=k/n$. The recursive
definition of $f$ implies that $\frac{f(n)}{n^{3}}\leq\frac{1}{2}\cdot
x^{2}(1-x)+\alpha(1-x)^{3}$. Subtracting $\alpha$ and using (7), we obtain

$\frac{f(n)}{n^{3}}-\alpha\leq\frac{1}{2}\cdot
x^{2}(1-x)-\alpha(1-(1-x)^{3})=(1-(1-x)^{3})(g(x)-\alpha)\leq 0,$

as required.

To verify that $f(n)\geq(\alpha+o(1))n^{3}$, set
$x_{i}=\lfloor\beta(1-\beta)^{i}n\rfloor$ in (3). ∎

###### Proof of Lemma 5.4.

Let $Q_{1},\ldots,Q_{t}$ be the full blue clone-cliques in $G$, arranged in
descending order according to their sizes. Let $G^{\prime}$ be obtained from
$G$ by orienting the $(Q_{i},Q_{j})$ (red) edges towards $Q_{i}$, for $1\leq
i<j\leq t$. As explained before and by assumption on $G$, $c(G^{\prime})\geq
c(G)\geq f(n)-\varepsilon^{2}n^{3}$.

Notice that $|Q_{1}|\geq 0.01n$, because otherwise $c(G)\leq n^{2}|Q_{1}|\leq
0.01n^{3}<f(n)-\varepsilon^{2}n^{3}$ (recall that $f(n)\approx 0.077n^{3}$, by
Proposition 4.1).

Write $|Q_{1}|=\theta n$. Then, using $f(n)=\alpha
n^{3}+o(n^{3})=g(\beta)n^{3}+o(n^{3})$ (which follows from Proposition 4.1 and
the definition of $\alpha$ in (5)),

$c(G^{\prime})\leq\binom{|Q_{1}|}{2}(n-|Q_{1}|)+f(n-|Q_{1}|)\leq\frac{1}{2}\theta^{2}(1-\theta)n^{3}+g(\beta)(1-\theta)^{3}n^{3}+o(n^{3}).$

Thus, using (7),

$\displaystyle\varepsilon^{2}\geq\frac{f(n)-c(G^{\prime})}{n^{3}}$
$\displaystyle\geq
g(\beta)-g(\beta)(1-\theta)^{3}-\frac{1}{2}\theta^{2}(1-\theta)+o(1)$
$\displaystyle=\theta\cdot(3-3\theta+\theta^{2})\cdot(g(\beta)-g(\theta))+o(1)$
$\displaystyle\geq 0.02\cdot(g(\beta)-g(\theta))+o(1).$

For the last inequality we used $\theta\geq 0.01$, which implies
$\theta(3-3\theta+\theta^{2})\geq 0.02$. By bounding the $o(1)$ term by
$\varepsilon^{2}/2$ and using Claim 5.5 below, we get

$100\varepsilon^{2}\geq
g(\beta)-g(\theta)\geq\min\\{0.05(\beta-\theta)^{2},0.005\\}.$

Since $\varepsilon$ is very small, we get $100\varepsilon^{2}\geq
0.05(\beta-\theta)^{2}$, which implies $|\beta-\theta|\leq 100\varepsilon$. ∎

######  Claim 5.5.

For $x\in[0,1]$,

$g(\beta)-g(x)\geq\min\\{0.05(\beta-x)^{2},0.005\\}.$ (9)

###### Proof.

We use the following facts that can be checked easily.

  * •

The function $g(x)$ is increasing on $[0,\beta]$ and decreasing on
$[\beta,1]$. In particular, its maximum is attained at $\beta$, and
$g^{\prime}(\beta)=0$.

  * •

$g(\beta)-g(0.5)\geq 0.005$.

  * •

The second derivative $g^{\prime\prime}(x)$ (which is
$\frac{-x(2x^{2}-9x+9)}{(x^{2}-3x+3)^{3}}$) is non-negative and decreasing on
$[0,1]$. In particular $g^{\prime\prime}(x)\leq g^{\prime\prime}(0.5)\leq-0.4$
for $x\in[0.5,1]$.

  * •

By Taylor’s expansion:
$g(x)=g(\beta)+\frac{1}{2}g^{\prime}(\beta)(x-\beta)+\frac{1}{6}g^{\prime\prime}(c_{x})(x-\beta)^{2}$
for every $x\in[0,1]$ and some $c_{x}$ between $x$ and $\beta$.

By the first and second items (using $\beta>0.5$), if $x\in[0,0.5]$ then

$g(\beta)-g(x)\geq g(\beta)-g(0.5)\geq 0.005.$

By the first, third and fourth items, if $x\in[0.5,1]$, then

$g(\beta)-g(x)\geq\frac{0.4}{6}(x-\beta)^{2}\geq 0.05(x-\beta)^{2}.$

The two inequalities prove the claim. ∎

###  5.3 Blue clone-cliques before and after symmetrisation

The next two lemmas show that if a symmetrisation procedure on $G$ produces a
full blue clone-clique $Q$ of size apprximately $\beta n$, then almost all
edges in $G[Q,V\setminus Q]$ are red and oriented towards $Q$ and almost all
edges in $G[Q]$ are blue.

######  Lemma 5.6.

Let $1/n\ll\varepsilon\ll 1$. Let $G=(V,E)$ be a coloured graph on $n$
vertices with at least $f(n)-\varepsilon^{2}n^{3}$ cherries. Suppose that
$G^{\prime}$ and $Q$ are the output of a procedure $S_{G}(x)$, and suppose
that $|Q|\geq 0.55n$. Then all but at most $10\varepsilon n^{2}$ edges in
$G[Q,V\setminus Q]$ are red and directed towards $Q$.

###### Proof.

Set $U:=V\setminus Q$, let $V_{\operatorname{in}}$ be the set of vertices $u$
in $U$ for which $uq$ is a red arc in $G^{\prime}$ for every $q\in Q$, and let
$V_{\operatorname{out}}:=U\setminus V_{\operatorname{in}}$. We will show that
$V_{\operatorname{out}}$ is small, and that not many pairs incident to
$V_{\operatorname{in}}$ were recoloured during the symmetrisation procedure
$S_{G}(x)$.

First, we show $|V_{\operatorname{out}}|\leq 40\varepsilon^{2}n$. Let
$G^{\prime\prime}$ be obtained from $G^{\prime}$ by reorienting the edges in
$G^{\prime}[Q,V_{\operatorname{out}}]$ to point towards $Q$. Notice that the
cherries in $G^{\prime}$ that contain an edge in $(Q,V_{\operatorname{out}})$
consist of one vertex in $Q$ and two in $V_{\operatorname{out}}$, and thus
their number is at most $|Q|\binom{|V_{\operatorname{out}}|}{2}$. Also, every
set consisting of two vertices in $Q$ and one in $V_{\operatorname{out}}$ is a
cherry in $G^{\prime\prime}$ but not in $G^{\prime}$. Thus, using $|Q|\geq
0.55n$ which implies $|Q|-|V_{\operatorname{out}}|\geq 0.1n$,

$\displaystyle c(G^{\prime\prime})-c(G^{\prime})$
$\displaystyle\geq\binom{|Q|}{2}|V_{\operatorname{out}}|-\binom{|V_{\operatorname{out}}|}{2}|Q|=\frac{1}{2}|Q||V_{\operatorname{out}}|(|Q|-|V_{\operatorname{out}}|)$
$\displaystyle\geq\frac{1}{2}\cdot\frac{n}{2}\cdot\frac{n}{10}\cdot|V_{\operatorname{out}}|=\frac{n^{2}}{40}\cdot|V_{\operatorname{out}}|.$

Recall that $c(G)\geq f(n)-\varepsilon^{2}n^{3}$ by assumption,
$c(G^{\prime})\geq c(G)$ by Claim 5.3, and $c(G^{\prime\prime})\leq f(n)$ by
Theorem 2.5. Altogether, this implies
$c(G^{\prime\prime})-c(G^{\prime})\leq\varepsilon^{2}n^{3}$ and thus
$|V_{\operatorname{out}}|\leq 40\varepsilon^{2}n$, as claimed.

Let $R$ be the set of edges $qv$ in $(Q,V\setminus Q)$ that are red and
oriented towards $Q$ in $G^{\prime}$ but not in $G$. We now upper-bound $|R|$.
Notice that each such edge in $R$ was recoloured to a red arc oriented towards
$Q$ at some point during $S_{G}(x)$ (possibly more than once). Let
$G=G_{1},\ldots,G_{t}=G^{\prime}$ be the graphs obtained during the
symmetrisation process on $Q$ and let $x_{1},\ldots,x_{t}$ be the
corresponding sequence of vertices. For each $v\in V$ and $k\in[t]$, let
$A_{k}(v)$ be the set of ordered pairs $vq$ which changed to red arcs in step
$k$ (so they were recoloured from $G_{k-1}$ to $G_{k}$).

We claim that $\sum_{k\geq\varepsilon n}\sum_{v\in
V_{\operatorname{in}}}|A_{k}(v)|\leq 4\varepsilon n^{2}$. To see this, fix
$k\geq\varepsilon n$ and consider the $k$-th step. If $y_{k}=x_{1}$, then
$A_{k}(v)=\\{vx_{k}\\}$ for $v\in N^{-}(x_{1})\setminus N^{-}(x_{k})$ and
$A_{k}(v)=\emptyset$ otherwise, where $N^{-}(\cdot)$ refers to the in-
neighbourhood with respect to $G_{k-1}$. Thus, using Claim 5.3 (i),

$\sum_{v\in V_{\operatorname{in}}}|A_{k}(v)|\leq\big{|}N^{-}(x_{1})\setminus
N^{-}(x_{k})\big{|}\leq\frac{4}{k}\cdot\big{(}c(G_{k})-c(G_{k-1})\big{)}.$

If $y_{k}=x_{k}$, then $A_{k}(v)=\\{vx_{1},\ldots,vx_{k-1}\\}$ for $v\in
N^{-}(x_{k})\setminus N^{-}(x_{1})$ and $A_{k}(v)=\emptyset$ otherwise. Thus,
by Claim 5.3 (ii),

$\sum_{v\in
V_{\operatorname{in}}}|A_{k}(v)|\leq(k-1)\cdot\big{|}N^{-}(x_{1})\setminus
N^{-}(x_{k})\big{|}\leq\frac{4}{k}\cdot\big{(}c(G_{k})-c(G_{k-1})\big{)},$

In either case, we get that for $k\geq\varepsilon n$,

$\sum_{v\in V_{\operatorname{in}}}|A_{k}(v)|\leq\frac{4}{\varepsilon
n}\big{(}c(G_{k})-c(G_{k-1})\big{)}.$

Summing over $k\geq\varepsilon n$, we obtain the required inequality

$\sum_{k\geq\varepsilon n}\sum_{v\in
V_{\operatorname{in}}}|A_{k}(v)|\leq\frac{4}{\varepsilon
n}\big{(}c(G^{\prime})-c(G_{\varepsilon n})\big{)}\leq 4\varepsilon n^{2},$

Where the last equality holds since $c(G^{\prime})-c(G_{\varepsilon
n})\leq\varepsilon^{2}n^{2}$.

Note that $|R|\leq\varepsilon n^{2}+\sum_{k\geq\varepsilon n}\sum_{v\in
V_{\operatorname{in}}}|A_{k}(v)|\leq 5\varepsilon n^{2}$. In total, all but at
most $(40\varepsilon^{2}+5\varepsilon)n^{2}\leq 10\varepsilon n^{2}$ pairs in
$(Q,V\setminus Q)$ are red and oriented towards $Q$. ∎

######  Lemma 5.7.

Let $1/n\ll\varepsilon\ll 1$. Let $G$ be a coloured graph on $n$ vertices with
at least $f(n)-\varepsilon^{2}n^{3}$ cherries. Suppose that $G^{\prime}$ and
$Q$ are the graph and full blue clone-clique produced by the procedure
$S_{G}(x)$, and suppose that $0.55n\leq|Q|\leq 0.65n$. Then all but
$1200\varepsilon n^{2}$ edges in $G[Q]$ are blue.

###### Proof.

Let $F$ and $F^{\prime}$ be the graphs obtained from $G$ and $G^{\prime}$ by
colouring all $(Q,V\setminus Q)$ edges red and orienting them towards $Q$.
Notice that $F^{\prime}$ can be obtained from $F$ by colouring all edges in
$Q$ blue.

We will first derive an upper bound on $c(F^{\prime})-c(F)$. By Lemma 5.6, the
graphs $G$ and $F$ differ on at most $10\varepsilon n^{2}$ edges and thus
$|c(G)-c(F)|\leq 10\varepsilon n^{3}$. Similarly,
$|c(G^{\prime})-c(F^{\prime})|\leq 10\varepsilon n^{3}$ (the lemma is still
applicable, as $S_{G^{\prime}}(x)$ does not change the graph $G^{\prime}$). By
assumption on $G$ we also have $c(G^{\prime})-c(G)\leq\varepsilon^{2}n^{3}$.
Altogether,

$c(F^{\prime})-c(F)\leq c(G^{\prime})-c(G)+20\varepsilon
n^{3}\leq(\varepsilon^{2}+20\varepsilon)n^{3}\leq 30\varepsilon n^{3}.$ (10)

We now obtain a lower bound on the same quantity. Let $e$ be the number of red
edges in $G[Q]$. The number of cherries in $F$ that are not cherries in
$F^{\prime}$ is at most $\sum_{q\in Q}\binom{d^{+}(q)}{2}$, where $d^{+}(q)$
denotes the red in-degree of $q$ in $F[Q]$. Notice that

$\sum_{q\in Q}\binom{d^{+}(q)}{2}\leq\frac{1}{2}\sum_{q\in
Q}(d^{+}(q))^{2}\leq\frac{1}{2}e|Q|,$

because $d^{+}(q)\leq|Q|$ and $e=\sum_{q}d^{+}(q)$.

On the other hand, the number of cherries in $F^{\prime}$ that are not
cherries in $F$ is exactly $e(n-|Q|)$. Thus,

$c(F^{\prime})-c(F)\geq
e(n-|Q|)-\frac{1}{2}e|Q|=e\cdot\big{(}n-\frac{3}{2}|Q|\big{)}\geq\frac{en}{40},$
(11)

using $|Q|\leq 0.65n$.

By (10) and (11), we have $e\leq 1200\varepsilon n^{2}$, as claimed. ∎

###  5.4 Proof of Lemma 5.1

Finally, we start with the actual proof of Lemma 5.1. The first step is to
find a set $Q^{\prime}$ of the right size almost all of whose edges in $G$ are
blue.

######  Lemma 5.8.

Let $1/n\ll\varepsilon\ll 1$. Let $G$ be a coloured graph on $n$ vertices,
satisfying $c(G)\geq f(n)-\varepsilon^{2}n^{3}$. Then there is a set
$Q^{\prime}\subseteq V(G)$ such that $\big{|}|Q^{\prime}|-\beta n\big{|}\leq
100\varepsilon n$ and all but at most $1200\varepsilon n^{2}$ edges in
$G[Q^{\prime}]$ are blue.

###### Proof.

Similarly to the proof of Theorem 2.5, start with $G^{\prime}=G$, and, as long
as $G^{\prime}$ has a vertex $x$ which is not in a full blue clone-clique, run
the symmetrisation procedure $S_{G^{\prime}}(x)$, and replace $G^{\prime}$ by
the resulting graphs. Denote by $G_{\operatorname{final}}$ the graph at the
end of the process (as before, the process is guaranteed to end). Then the
vertices of $G_{\operatorname{final}}$ can be partitioned into full blue
clone-cliques $Q_{1},\ldots,Q_{t}$.

Let $Q^{\prime}$ be the vertex set of the largest clone-clique. By Lemma 5.4,
we have $\big{|}|Q^{\prime}|-\beta n\big{|}\leq 100\varepsilon n$. In
particular $|Q^{\prime}|\in[0.55n,0.65n]$.

Let $F_{1}$ be the graph created just before the symmetrisation procedure was
started on an element of $Q^{\prime}$, and let $F_{2}$ be the graph just after
$Q^{\prime}$ was built. Notice that $c(F_{2})\geq c(F_{1})\geq c(G)\geq
f(n)-\varepsilon^{2}n^{3}$. By Lemma 5.7, all but at most $1200\varepsilon
n^{2}$ edges in $F_{1}[Q^{\prime}]$ are blue. Notice that during the above
process, the edges in $Q^{\prime}$ remain untouched until right before a
symmetrisation process is started on an element of $Q^{\prime}$. It follows
that all but at most $1200\varepsilon n^{2}$ edges in $G[Q^{\prime}]$ are
blue. ∎

Now, we can complete the proof by running a symmetrisation procedure that
generates a blue clique $Q$ which will be close to $Q^{\prime}$.

###### Proof of Lemma 5.1.

Apply Lemma 5.8 to find $Q^{\prime}$ such that $\big{|}|Q^{\prime}|-\beta
n\big{|}\leq 100\varepsilon n$ and $G[Q^{\prime}]$ has at most
$\delta^{2}n^{2}$ red edges (with $\delta^{2}=1200\varepsilon$).

######  Claim 5.9.

We can run a symmetrisation procedure on $G$ which results in a graph
$G^{\prime}$ and a full blue clone-clique $Q$ satisfying $|Q^{\prime}\setminus
Q|\leq 3\delta n$.

###### Proof.

Let $A$ be the set of vertices in $Q^{\prime}$ with more than $\delta n$ red
(in- or out-) neighbours in $G[Q^{\prime}]$. The bound on the number of red
edges in $Q^{\prime}$ gives $|A|<2\delta n$. Define
$Q^{\prime\prime}:=Q^{\prime}\setminus A$.

We will run a symmetrisation procedure on $G$, but with a specific ordering of
vertices. We start with $x_{1}\in Q^{\prime\prime}$ (chosen arbitrarily).
Assuming that $\\{x_{1},\ldots,x_{k}\\}$ are defined and contained in
$Q^{\prime\prime}$, if possible we pick $x_{k+1}$ to also be in
$Q^{\prime\prime}$ (we can do this as long as there is a vertex in
$Q^{\prime\prime}\setminus\\{x_{1},\ldots,x_{k}\\}$ whose edges to
$\\{x_{1},\ldots,x_{k}\\}$ are blue). Once this is no longer possible, we
continue with the symmetrisation procedure using an arbitrary order of
vertices. Let $Q$ be the full blue clone-clique build by this procedure.

Let $k$ be largest such that $\\{x_{1},\ldots,x_{k}\\}\subseteq
Q^{\prime\prime}$. It is easy to see that throughout the procedure, until at
least step $k$, every vertex in $Q^{\prime\prime}$ has at most $\delta n$ non-
blue neighbours in $Q^{\prime\prime}\setminus\\{x_{1},\ldots,x_{k}\\}$. Thus
$k\geq|Q^{\prime\prime}|-\delta n\geq|Q|-3\delta n$, as otherwise we could
find a suitable $x_{k+1}$ in $Q^{\prime\prime}$, contradicting the choice of
$k$. It follows that $|Q^{\prime}\setminus Q|\leq 3\delta n$. ∎

Let $G^{\prime}$ and $Q$ be as in the above Claim. We claim that
$|Q|\leq(\beta+100\varepsilon)n$. Indeed, this follows from Lemma 5.4 by
running symmetrisation procedures repeatedly, starting from $G^{\prime}$,
until the vertices can be partitioned into full blue clone-cliques (one of
which is $Q$). It follows that $|Q\setminus Q^{\prime}|\leq 3\delta
n+|Q|-|Q^{\prime}|\leq(3\delta+200\varepsilon)n\leq 5\delta n$. In particular,
the number of red edges in $G[Q]$ is at most the number of red edges in
$G[Q^{\prime}]$ plus the number of edges incident with $Q\setminus
Q^{\prime}$, which amounts to a total of at most
$(\delta^{2}+5\delta)n^{2}\leq 10\delta n^{2}$ red edges in $G[Q]$.

By Lemma 5.6, all but at most $10\varepsilon n^{2}$ edges in $G[Q,V\setminus
Q]$ are red and oriented towards $Q$, and similarly for
$G^{\prime}[Q,V\setminus Q]$.

Since $Q$ is a full blue clone-clique, the vertices in $V\setminus Q$ can be
partitioned into $V_{\operatorname{in}}$ and $V_{\operatorname{out}}$, where
$vq$ is a red arc for every $v\in V_{\operatorname{in}}$ and $q\in Q$ and $qv$
is a red arc for $v\in V_{\operatorname{out}}$ and $q\in Q$. Thus, by the
previous paragraph and because $|Q|\geq n/2$, $|V_{\operatorname{out}}|\leq
20\varepsilon n$.

Let $G^{\prime\prime}$ be obtained from $G^{\prime}$ be reorienting all
$(Q,V\setminus Q)$ edges towards $Q$. Then

$c(G^{\prime\prime})-c(G^{\prime})\geq\binom{|Q|}{2}{|V_{\operatorname{out}}|}-\binom{|V_{\operatorname{out}}|}{2}|Q|=|Q||V_{\operatorname{out}}|\cdot(|Q|-|V_{\operatorname{out}}|)\geq
0.$

It follows that $c(G^{\prime\prime})\geq c(G^{\prime})\geq c(G)$. Moreover,
$G^{\prime\prime}$ and $G^{\prime}$ differ on at most
$|V_{\operatorname{out}}|n\leq 20\varepsilon n^{2}$ edges, and thus $G$ and
$G^{\prime\prime}$ differ on at most
$(20\varepsilon+10\varepsilon+10\delta)\leq 20\delta n^{2}$ edges. Since
$G^{\prime\prime}$ has the required structure, this proves Lemma 5.1. ∎

###  5.5 Full stability result

###### Proof of Theorem 5.2.

Let $\varepsilon_{1}\ll\eta\ll\varepsilon_{2}$. The idea is simply to iterate
Lemma 5.1. We will find graphs $G_{1},\ldots,G_{s}$ and sets
$Q_{1},\ldots,Q_{s}$, satisfying the following conditions, for $k\in[s]$ (for
convenience set $G_{0}:=G$, $Q_{0}:=\emptyset$ and $V:=V(G)$).

  1. (1)

$G_{k}$ is a coloured graph on vertex set $V\setminus(Q_{1}\cup\ldots\cup
Q_{k-1})$.

  2. (2)

$Q_{k}$ is a blue clique in $G_{k}$, all other edges incident with $Q_{k}$ in
$G_{k}$ are red and point towards $Q_{k}$.

  3. (3)

$\big{|}|Q_{k}|-\beta|G_{k}|\big{|}\leq\eta|G_{k}|$.

  4. (4)

$G_{k}$ and $G_{k-1}\setminus Q_{k-1}$ differ on at most $\eta|G_{k}|^{2}$
edges.

  5. (5)

$c(G_{k})\geq c(G_{k-1}\setminus Q_{k-1})$.

  6. (6)

$c(G_{k}\setminus Q_{k})\geq f(|G_{k}\setminus Q_{k}|)-\varepsilon_{1}n^{3}$.

To see how such a sequence can be built, suppose that $G_{1},\ldots,G_{k-1}$
and $Q_{1},\ldots,Q_{k-1}$ are defined and satisfy the above conditions. If
$|G_{k-1}\setminus Q_{k-1}|\leq\eta n$, we stop the process and set $s:=k-1$.
Otherwise, we apply Lemma 5.1 to the graph $G_{k-1}\setminus Q_{k-1}$. Notice
that by (6) and the assumption on $|G_{k-1}\setminus Q_{k-1}|$, we have
$c(G_{k}\setminus Q_{k})\geq f(|G_{k}\setminus
Q_{k})-\varepsilon_{1}\eta^{-3}|G_{k}\setminus Q_{k}|^{3}$. Since
$\varepsilon_{1}\eta^{-3}\ll\eta$, the lemma is applicable. The lemma produces
a graph $G_{k}$ on vertex set $V(G_{k-1})\setminus
Q_{k-1}=V\setminus(Q_{1}\cup\ldots\cup Q_{k-1})$ satisfying items (1) to (5).
It remains to verify (6). Note that

$\displaystyle c(G_{k})=\binom{|Q_{k}|}{2}\cdot|G_{k}\setminus
Q_{k}|+c(G_{k}\setminus Q_{k}).$

Also

$\displaystyle c(G_{k})\geq c(G_{k-1}\setminus Q_{k-1})$ $\displaystyle\geq
f(|G_{k-1}\setminus Q_{k-1}|)-\varepsilon_{1}n^{3}$
$\displaystyle=f(|G_{k}|)-\varepsilon_{1}n^{3}$
$\displaystyle\geq\binom{|Q_{k}|}{2}|G_{k}\setminus Q_{k}|+f(|G_{k}\setminus
Q_{k}|)-\varepsilon_{1}n^{3},$

where the last inequality follows from the definition of $f$. The two
inequalities imply (6).

To finish, run a symmetrisation procedure on $G_{s}\setminus Q_{s}$
repeatedly, to obtain a graph $H$ whose vertices are partitioned into full
blue clone-cliques $Q_{s+1},\ldots,Q_{t}$ (arranged in decreasing size); the
edges between any two of them point towards the larger clique; and $c(H)\geq
c(G_{t}\setminus Q_{t})$. Let $G^{\prime}$ be the graph on vertex set $V$,
such that $Q_{1},\ldots,Q_{t}$ are blue cliques and the edges between any two
of them are red and point towards the larger clique (note that
$Q_{1},\ldots,Q_{t}$ partition $V$).

To complete the proof of Theorem 5.2, we need to show that properties (a) to
(c) hold. For (a), define $G_{k}^{\prime}$ to be the graph on vertex set $V$,
obtained from $G^{\prime}$ by replacing $V\setminus(Q_{1}\cup\ldots\cup
Q_{k-1})$ by a copy of $G_{k}$ (this makes sense due to (1)). It is easy to
see that $c(G_{k}^{\prime})-c(G_{k-1}^{\prime})=c(G_{k})-c(G_{k-1}\setminus
Q_{k-1})\geq 0$ for $k\in[s]$, using (5). Similarly, $c(G^{\prime})\geq
c(G_{s}^{\prime})$. Altogether, $c(G^{\prime})\geq c(G_{1}^{\prime})=c(G)$, as
required for (a).

Before continuing, we derive an upper bound on $s$. By (3) we have
$|Q_{k}|\geq 0.55|G_{k}|$ for $k\in[s]$, so $|G_{k}|\leq 2^{-(k-1)}n$. Since
$|G_{t}|\leq\eta n$, this implies that $s\leq 2\log(1/\eta)\leq\eta^{-1/2}$,
say.

By (4) we find that $G^{\prime}$ and $G$ differ on at most
$((s\eta+\eta)n^{2}\leq 2\eta^{1/2}n^{2}\leq\varepsilon_{2}n^{2}$ edges.
Property (b) follows.

Notice that the estimate $|Q_{k}|\geq 0.55|G_{k}|$, which follows from (3)
implies $|Q_{1}|\geq\ldots\geq|Q_{s}|$. Thus (c)c(i) to (c)c(iii) clearly
hold. Finally, (c)c(iv) holds trivially for $k>s$ and, for $k\leq s$, it
follows from (3) and $\eta\leq\varepsilon_{2}$. ∎

##  6 Hypergraphs with no short odd pseudocycles

In this section we leverage the stability result about cherries, Theorem 5.2,
and the connection between hypergraphs with no odd pseudocycles to good
colourings (Theorem 2.4) to prove the following result regarding the structure
of a dense hypergraph with no short odd pseudocycles. In case of cycles and
pseudocycles, the length (number of edges) and order (number of vertices)
coincide, so, since there is no danger of confusion, we prefer the term
length. Given vertex sets $X_{1},X_{2},X_{3}\subset V(\mathcal{H})$, an
$X_{1}X_{2}X_{3}$-triple in $\mathcal{H}$ is an (unordered) edge
$x_{1}x_{2}x_{3}\in E(\mathcal{H})$ with $x_{i}\in X_{i}$ for $i\in[3]$.

######  Theorem 6.1.

Let $n\gg\ell\gg 1$. Let $\mathcal{H}$ be a $3$-uniform hypergraph on $n$
vertices which contains no odd pseudocycles of length at most $\ell$, and
which maximises the number of edges under these conditions. Then there is a
partition $\\{A,B\\}$ of the vertices of $\mathcal{H}$ into non-empty sets
such that all $AAB$ triples are edges of $\mathcal{H}$ (and there are no $AAA$
and $ABB$ triples).

By iterating the above result, we prove Theorem 2.9, restated here, which
gives an upper bound on the number of edges in a hypergraph with no short odd
pseudocycles. See 2.9

###### Proof of Theorem 2.9 using Theorem 6.1.

Let $L$ and $n_{0}$ be such that Theorem 6.1 holds for $\ell=L$ and $n\geq
n_{0}$. Denote by $g(n)$ the maximum number of edges in an $n$-vertex
hypergraph with no odd pseudocycles of length at most $L$. Then for every
$n\geq n_{0}$ there exists $a_{n}\in[n-1]$ such that
$g(n)\leq\binom{a_{n}}{2}(n-a_{n})+g(n-a_{n})$. Iterating this and recalling
the definition of $f(n)$ implies that $g(n)\leq f(n)+\binom{n_{0}}{3}$. ∎

Recall that Theorem 2.9 is tight, up to the additive $O(1)$ error term, as
evidenced by $\mathcal{H}(x_{1},\ldots,x_{k})$ for a suitable choice of
$x_{i}$’s.

We next show how Theorem 2.9 implies our main result, Theorem 1.3, restated
here. See 1.3 Recall that the _$t$ -blow-up_ of an $r$-uniform hypergraph
$\mathcal{H}$, denoted $\mathcal{H}[t]$, is the hypergraph with vertex set
$V(\mathcal{H})\times[t]$ and edges all $r$-sets
$\\{(x_{1},i_{1}),\ldots,(x_{r},i_{r})\\}$ such that
$\\{x_{1},\ldots,x_{r}\\}\in E(\mathcal{H})$. For a family $\mathcal{F}$ of
hypergraphs, we denote by $\mathcal{F}[t]$ the family of $t$-blow-ups of
members of $\mathcal{F}$. Recall that Theorem 2.1 (whose proof can be found in
[18]) asserts that taking the $t$-blow-up of a hypergraph does not change its
Turán density. The following generalisation for finite families of hypergraphs
can be proved similarly.

######  Theorem 6.2 ([18], Theorem 2.2).

Let $s$ and $t$ be integers, and let $\mathcal{F}$ be a family of $r$-graphs
with $|\mathcal{F}|\leq s$. Then $\pi(\mathcal{F}(t))=\pi(\mathcal{F})$.

To prove Theorem 1.3, we will note that an odd cycle $C^{(3)}_{m}$ is
contained in an $m$-blow-up of any odd pseudocycle of length at most $m/2$,
and apply the last theorem.

###### Proof of Theorem 1.3 using Theorem 2.9.

Let $m$ be an integer with $m\geq 2L$ and $3\nmid m$, where $L$ is the
constant from Theorem 2.9. Recall that $f(n)=(2\sqrt{3}-3+o(1))\binom{n}{3}$.
Let $\varepsilon>0$ and let $\mathcal{H}$ be an $n$-vertex 3-uniform
hypergraph with $e(\mathcal{H})\geq(2\sqrt{3}-3+\varepsilon)\binom{n}{3}$ and
$n$ sufficiently large. We claim that $\mathcal{H}$ contains a copy of
$C^{(3)}_{m}$.

Theorem 2.9 and Theorem 6.2 imply that $\mathcal{H}$ contains $F[m]$ for some
$\ell$-pseudocycle $F$ with $\ell\leq L$ and $3\nmid\ell$. It suffices to show
that $F$ contains an $m$-pseudocycle, because then $C_{m}^{(3)}$ will be
contained in $F[m]$. To see this, let $v_{1}\dots v_{\ell}$ be an ordering of
$V(F)$ such that $v_{i}v_{i+1}v_{i+2}\in E(F)$, with the indices taken modulo
$\ell$.

In case $m\equiv\ell\,(\mathrm{mod}\,\,3)$, consider the sequence

$(v_{1}v_{2}v_{3})^{\frac{m-\ell}{3}}v_{1}v_{2}\dots v_{\ell},$

where $(v_{1}v_{2}v_{3})^{x}$ stands for $x$ repetitions of the sequence
$v_{1}v_{2}v_{3}$. This is a sequence of order $m$ certifying that $F$
contains an $m$-pseudocycle.

Otherwise, if $m\equiv 2\ell\,(\mathrm{mod}\,\,3)$, the same is certified for
instance by the sequence

$(v_{1}v_{2}v_{3})^{\frac{m-2\ell}{3}}(v_{1}v_{2}\dots v_{\ell})^{2}.\qed$

All that remains now is to prove Theorem 6.1. We will state and prove some
preliminary results in the following subsection, and then prove the theorem in
Section 6.2.

###  6.1 Preparation

The _diameter_ of a hypergraph $\mathcal{H}$ is the minimum $\ell$ such that
the following holds: for every $x,y,z,w\in V(\mathcal{H})$ (where $x,y$ are
distinct and $z,w$ are distinct) whenever there is a pseudopath from $xy$ to
$zw$, there is such a pseudopath of order at most $\ell$.

We have already shown that $n$-vertex hypergraphs with no odd pseudocycles
have at most $f(n)$ edges. To prove the same for pseudocycles of bounded
length, we will pass to a subhypergraph with bounded diameter, which is the
purpose of the following two propositions.

######  Proposition 6.3.

Let $\mathcal{H}$ be a 3-uniform hypergraph of diameter $\ell\geq 4$. If
$\mathcal{H}$ has an odd pseudocycle, then it has an odd pseudocycle of length
at most $4\ell$.

###### Proof.

Let $C$ be the shortest odd pseudocycle in $\mathcal{H}$. Assuming that its
length is at least $3\ell+4$, we may index it by $xyv_{1}\ldots
v_{k}abu_{1}\ldots u_{t}$ with $t\geq 2\ell$, $k\geq\ell$. Note that the
length of $C$ is $k+t+4\not\equiv 0\pmod{3}$.

Since $\mathcal{H}$ contains a pseudopath from $xy$ to $ab$, it also contains
such a pseudopath $P=xyw_{1}\ldots w_{r}ab$ with $r\leq\ell-4$. The
pseudocycle $xyw_{1}\ldots w_{r}abu_{1}\ldots u_{t}$ is shorter than $C$, so
it must not be odd, that is, $r+t+4\equiv 0\,(\mathrm{mod}\,\,3)$.

Now consider the pseudocycle $C_{1}=v_{1}\ldots v_{k}\tilde{P}$. Recall that
$\tilde{P}$ is a $(2r+2)$-vertex pseudopath from $ab$ to $xy$ (see (1)), so
$C_{1}$ is indeed a pseudocycle. The length of $C_{1}$ is $k+2r+6\equiv
k-r\equiv k+t+4\not\equiv 0\pmod{3}$. Noting that $k+2r+6\leq k+2\ell-2\leq
k+t$, this contradicts the minimality of $C$. ∎

######  Proposition 6.4.

Let $1/\ell\ll\varepsilon\ll 1$, and let $\mathcal{H}$ be an $n$-vertex
hypergraph. Then there is a subgraph
$\mathcal{H}^{\prime}\subseteq\mathcal{H}$ with $e(\mathcal{H}^{\prime})\geq
e(\mathcal{H})-\varepsilon n^{3}$ whose diameter is at most $\ell$.

###### Proof.

First we form a subgraph $\mathcal{H}^{\prime}\subseteq\mathcal{H}$ in which
each vertex pair has codegree either $0$ or at least $\varepsilon n$, as
follows. If there are vertices $u,v$ whose codegree in the _current_
hypergraph is smaller than $\varepsilon n$, delete all edges containing $uv$.
Repeat this step until each pair has codegree degree either $0$ or at least
$\varepsilon n$. Denote the resulting hypergraph by $\mathcal{H}^{\prime}$.
Observe that the number of deleted edges is at most $\varepsilon
n\cdot\binom{n}{2}$ since the edges containing each pair were removed at most
once. Hence $e(\mathcal{H}^{\prime})\geq e(\mathcal{H})-\varepsilon n^{3}$.

Given ordered pairs $uv$ and $u^{\prime}v^{\prime}$ which have a pseudopath
connecting them, let $P=uvx_{0}x_{1}\dots x_{t}u^{\prime}v^{\prime}$ be a
shortest such pseudopath. For each $i$, let $B_{i}$ be the set of ordered
pairs $ab$ such that $x_{i}x_{i+1}ab$ is a tight path. We claim that the sets
$B_{10i}$ are mutually disjoint for $0\leq i<\frac{t}{10}$. Suppose not, and
take $ab\in B_{10i}\cap B_{10j}$ for some $0\leq i<j<\frac{t}{10}$. Then
$x_{i}x_{i+1}abx_{j+1}ax_{j}x_{j+1}$ is a pseudopath with only five vertices
between $x_{i}$ and $x_{j}$, which can be used to form a shorter pseudopath
than $P$ connecting $uv$ and $u^{\prime}v^{\prime}$, contradiction. Now since
$|B_{i}|\geq\varepsilon^{2}n^{2}/2$ for every $i$, using the codegree
condition, we have

$\left\lfloor\frac{t}{10}\right\rfloor\cdot\frac{\varepsilon^{2}n^{2}}{2}\leq
n^{2},$

so $t\leq\frac{20}{\varepsilon^{2}}$. Hence the diameter of
$\mathcal{H}^{\prime}$ is at most $\ell:=\frac{20}{\varepsilon^{2}}+4$, as
required. ∎

As alluded to in Section 2, we can already prove Corollary 2.8, restated here,
which is a weakening of Theorem 2.9, with only an asymptotic upper bound,
which depends on $\ell$, on the number of edges. See 2.8 This bound will be
used in the proof of Proposition 6.6. Note that the analogous bound on the
extremal number of proper odd tight cycles follows from Theorem 6.2.

###### Proof of Corollary 2.8.

Assume the opposite, that $e(\mathcal{H})\geq f(n)+\varepsilon n^{3}$.
Applying Proposition 6.4 with the parameters $\ell/4$ and $\varepsilon/2$, we
obtain a hypergraph $\mathcal{H}^{\prime}\subseteq\mathcal{H}$ with at least
$f(n)+\varepsilon n^{3}/2$ edges whose diameter is at most $\ell/4$.
$\mathcal{H}^{\prime}$ contains no odd pseudocycles of lenght at most $\ell$,
so by Proposition 6.3, it contains no odd pseudocycles. Hence we may apply
Theorem 2.4 to obtain a good colouring of $\partial\mathcal{H}^{\prime}$ with
$e(\mathcal{H}^{\prime})>f(n)$ cherries, contradicting Theorem 2.5. ∎

The following proposition shows that hypergraphs with no short odd cycles
whose number of edges is large are close to being regular.

######  Proposition 6.5.

Let $1/n\ll 1/\ell\ll\varepsilon\ll 1$, and let $\mathcal{H}$ be an $n$-vertex
hypergraph with no odd pseudocycles of length at most $\ell$, which maximises
the number of edges under these conditions. Then
$d(u)\geq(3\alpha-\varepsilon)n^{2}$ for every vertex $u$.

###### Proof.

Given vertices $u$ and $v$ in $\mathcal{H}$, consider the hypergraph
$\mathcal{H}_{uv}$ obtained from $\mathcal{H}$ by removing all edges
containing $v$ and then adding the edge $e-u+v$, for each edge $e$ that
contains $u$ but not $v$. Observe that $\mathcal{H}$ has no odd pseudocycles
of length at most $\ell$; indeed, if there were such a cycle then we could
replace each instance of $v$ by $u$ to obtain an odd pseudocycle of the same
length in $\mathcal{H}$ (whereby it is important that $\mathcal{H}_{uv}$ has
no edges containing both $u$ and $v$), a contradiction. Since
$e(\mathcal{H}_{uv})\geq e(\mathcal{H})-d(v)+d(u)-n$ and by maximality of
$\mathcal{H}$, we have $d(v)\geq d(u)-n$. Since $u$ and $v$ were arbitrary,
this implies that the maximum and minimum degrees of $\mathcal{H}$ differ by
at most $n$. In particular, using $e(\mathcal{H})\geq f(n)=\alpha
n^{3}+o(n^{3})$, which follows from the maximality of $\mathcal{H}$ and
Proposition 4.1,

$\delta(\mathcal{H})\geq\frac{3e(\mathcal{H})}{n}-n\geq\frac{3f(n)}{n}-n\geq(3\alpha-\varepsilon)n^{2}.\qed$

Next, we prove a stability version of the previous proposition.

######  Proposition 6.6.

Let $1/n\ll 1/\ell\ll\varepsilon_{1}\ll\varepsilon_{2}\ll 1$, and let
$\mathcal{H}$ be an $n$-vertex $3$-uniform hypergraph with no odd pseudocycles
of length at most $\ell$. If $e(\mathcal{H})\geq f(n)-\varepsilon_{1}n^{3}$
then $d(u)\leq(3\alpha+\varepsilon_{2})n^{2}$ for every vertex $u$.

###### Proof.

Let $\mu=\sqrt{\varepsilon_{1}}\leq\varepsilon_{2}/10$. Let $X$ be the set of
vertices $x$ with $d(x)\leq 3(\alpha+\mu)n^{2}$. Then
$e(\mathcal{H})\geq(n-|X|)(\alpha+\mu)n^{2}$. By Corollary 2.8 (and the
properties of $f(n)$) we also have
$e(\mathcal{H})\leq(\alpha+\varepsilon_{1})n^{3}$. Putting the two
inequalities together, we get

$\displaystyle(\alpha+\varepsilon_{1})n^{3}\geq(n-|X|)(\alpha+\mu)n^{2}$
$\displaystyle\Longrightarrow\quad$
$\displaystyle|X|\geq\frac{(\alpha+\mu)n-(\alpha+\varepsilon_{1})n}{\alpha+\mu}=\frac{\mu-\varepsilon_{1}}{\alpha+\mu}\cdot
n\geq\mu n.$

Let $u$ be a vertex of maximum degree in $\mathcal{H}$, and let $X^{\prime}$
be a subset of $X$ of size $t:=\mu n$. We may assume $u\notin X^{\prime}$
because otherwise
$d_{\mathcal{H}}(u)\leq(3\alpha+3\mu)n^{2}\leq(3\alpha+\varepsilon_{2})n^{2}$,
as required. Now consider the hypergraph $\mathcal{H}_{1}$ formed in two steps
as follows. First, define $\mathcal{H}_{0}=\mathcal{H}\setminus X^{\prime}$;
then $e(\mathcal{H}_{0})\geq e(\mathcal{H})-t\cdot 3(\alpha+\mu)n^{2}$ and
$d_{\mathcal{H}_{0}}(u)\geq d_{\mathcal{H}}(u)-tn$. Second, let
$\mathcal{H}_{1}$ be the hypergraph obtained by adding $|X^{\prime}|$ copies
of $u$ to $\mathcal{H}_{0}$. Then

$\displaystyle e(\mathcal{H}_{1})$ $\displaystyle\geq
e(\mathcal{H}_{0})+t\cdot d_{\mathcal{H}_{0}}(u)$ $\displaystyle\geq
e(\mathcal{H})-t\cdot 3(\alpha+\mu)n^{2}+t\cdot(d_{\mathcal{H}}(u)-tn)$
$\displaystyle\geq
f(n)-\varepsilon_{1}n^{3}+t\cdot(d_{\mathcal{H}}(u)-tn-3(\alpha+\mu)n^{2})$
$\displaystyle=f(n)-\varepsilon_{1}n^{3}+\mu
n\cdot(d_{\mathcal{H}}(u)-(3\alpha+4\mu)n^{2}).$

Notice that $\mathcal{H}_{1}$ has no odd pseudocycles of length at most
$\ell$. Thus, by Corollary 2.8, we have $e(\mathcal{H}_{1})\leq
f(n)+\varepsilon_{1}n^{3}$. Hence, using
$\mu=\sqrt{\varepsilon_{1}}\leq\varepsilon_{2}/10$,

$d_{\mathcal{H}}(u)\leq(3\alpha+4\mu)n^{2}+(2\varepsilon_{1}/\mu)n^{2}\leq(3\alpha+\varepsilon_{2})n^{2},$

as required. ∎

###  6.2 The structure of odd-pseudocycle-free graphs

We now prove the main result in the section, Theorem 6.1. The starting point
of the proof uses the relation between hypergraphs with no odd pseudocycles
and good colourings of $K_{n}$, as well the stability result about cherries
from the previous section, to conclude the following: there is a coloured
graph $G$ with a nice structure such that almost all cherries in $G$ are
triples in $\mathcal{H}$ and vice versa. This readily implies the existence of
a partition $\\{A,B\\}$ of the vertices such that $|A|\approx\beta n$ and for
almost every vertex $u$ in $\mathcal{H}$ the following holds: almost all
vertices in $A$ are joined to almost all $A\times B$ pairs, and almost all
vertices in $B$ are joined to almost all $A^{(2)}$ pairs. The main difficulty
of the proof lies in showing that there is such a partition for which every
vertex in $A$ is joined to almost all pairs in $A\times B$, and similarly for
vertices in $B$. This is achieved in Claim 6.7 and the main idea is to compare
several graphs obtained by modifying the triples containing a given vertex.
Given a partition as above, to conclude the proof, we argue (using the fact
that $\mathcal{H}$ has no short odd pseudocycles) that the number of $AAB$
“non-edges” exceeds the number of $AAA$ and $ABB$ edges, unless all of these
numbers are 0. The maximality of $\mathcal{H}$ implies that all these numbers
are indeed $0$, meaning that $\mathcal{H}$ has all $AAB$ edges and no $AAA$,
$ABB$ edges.

###### Proof of Theorem 6.1.

Let $\varepsilon_{7}=0.1$ and let $\varepsilon_{1},\ldots,\varepsilon_{6}$,
and $\ell$ satisfy

$0<1/\ell\ll\varepsilon_{1}\ll\ldots\ll\varepsilon_{7}.$

Let $\mathcal{H}^{\prime}$ be a subgraph of $\mathcal{H}$ on the same vertex
set with at least $e(\mathcal{H})-\varepsilon_{1}n^{3}$ edges, that has
diameter at most $\ell/4$; such $\mathcal{H}^{\prime}$ exists by Proposition
6.4. By Proposition 6.3, $\mathcal{H}^{\prime}$ has no odd pseudocycles, so by
Theorem 2.4, there is a good colouring of $\partial\mathcal{H}^{\prime}$.

Extending the good colouring of $\partial\mathcal{H}^{\prime}$ arbitrarily to
also cover vertex pairs which are not in the shadow, we obtain a coloured
graph (recall that this is a complete graph whose edges are either blue or
oriented and red) $G^{\prime}$ on vertex set $V:=V(\mathcal{H})$, such that
every edge in $\mathcal{H}^{\prime}$ is a cherry in $G^{\prime}$. By
maximality of $\mathcal{H}$, we have $c(G^{\prime})\geq
e(\mathcal{H}^{\prime})\geq e(\mathcal{H})-\varepsilon_{1}n^{3}\geq
f(n)-\varepsilon_{1}n^{3}$.

Thus, by Theorem 5.2, there is a graph $G$ satisfying (a)–(c) in Theorem 5.2
on vertex set $V$. That is, $G$ has at least as many cherries as $G^{\prime}$,
all but at most $\varepsilon_{2}n^{3}$ cherries in $G$ are cherries in
$G^{\prime}$, and $V$ can be partitioned into sets $X_{1},\ldots,X_{k}$ such
that: $G[X_{i}]$ is blue for $i\in[k]$;
$|X_{i}|=(\beta\pm\varepsilon_{2})n\cdot(|X_{i}|+\ldots+|X_{k}|)$ for
$i\in[k]$; and all $X_{i}\times X_{j}$ pairs in $G$ are red and oriented
towards $X_{i}$, for $1\leq i<j\leq k$. Recall that
$\beta=\frac{3-\sqrt{3}}{2}$ was defined in (5).

Define $X_{>i}:=X_{i+1}\cup\ldots\cup X_{k}$, and define $X_{\geq i}$
analogously. Let $H$ be the subgraph of $G$ whose edges are either pairs in
$X_{i}\times X_{i}$ that are in at least
$(|X_{i+1}|+\ldots+|X_{k}|)-\varepsilon_{3}n$ triples in $(X_{i}\times
X_{i}\times X_{>i})\cap E(\mathcal{H})$, or pairs in $X_{i}\times X_{j}$,
where $i<j$, that are in at least $|X_{i}|-\varepsilon_{3}n$ triples in
$(X_{i}\times X_{i}\times X_{j})\cap E(\mathcal{H})$.

Denoting the number of non-edges in $H$ by $\bar{e}(H)$, we have that the
number of cherries in $G$ that are not edges in $\mathcal{H}$ is at least
$\bar{e}(H)\cdot\varepsilon_{3}n/3$. Recall that $e(\mathcal{H}^{\prime})\geq
e(\mathcal{H})-\varepsilon_{1}n^{3}\geq f(n)-\varepsilon_{1}n^{3}$ and that
all edges in $\mathcal{H}^{\prime}$ are cherries in $G^{\prime}$. But
$c(G^{\prime})\leq f(n)$ (by Theorem 2.5), so all but $\varepsilon_{1}n^{3}$
cherries in $G^{\prime}$ are edges in $\mathcal{H}^{\prime}$ and thus in
$\mathcal{H}$. Since there are at most $\varepsilon_{2}n^{3}$ cherries in $G$
that are not cherries in $G^{\prime}$, it follows that all but at most
$(\varepsilon_{1}+\varepsilon_{2})n^{3}\leq 2\varepsilon_{2}n^{3}$ cherries in
$G$ are edges in $\mathcal{H}$. Hence $\bar{e}(H)\cdot\varepsilon_{3}n/3\leq
2\varepsilon_{2}n^{3}$, showing
$\bar{e}(H)\leq(6\varepsilon_{2}/\varepsilon_{3})n^{3}\leq\varepsilon_{3}n^{2}$.

Let $k_{0}$ be the maximum $i$ such that $|X_{i}|\geq\varepsilon_{4}n$. Define
subsets $X_{i}^{\prime}\subseteq X_{i}$ as follows: if $i<k_{0}$ let
$X_{i}^{\prime}$ be the set of vertices in $X_{i}$ that have degree at least
$|X_{i}|-\varepsilon_{4}n$ in $H[X_{i}]$ and degree at least
$|X_{>i}|-\varepsilon_{4}n$ in $H[X_{i},X_{>i}]$; if $i\geq k_{0}$, define
$X_{i}^{\prime}:=\emptyset$. Since
$(\varepsilon_{4}n/2)\sum_{i<k_{0}}|X_{i}\setminus
X_{i}^{\prime}|\leq\bar{e}(H)\leq\varepsilon_{3}n^{2}$ and $|X_{\geq
k_{0}}|\leq 10\varepsilon_{4}n$ (using (c)c(iv)), we have

$\sum_{i\in[k]}|X_{i}\setminus X_{i}^{\prime}|\leq
10\varepsilon_{4}n+(2\varepsilon_{3}/\varepsilon_{4})n\leq
20\varepsilon_{4}n.$

Let $X:=X_{1}^{\prime}\cup\ldots\cup X_{k}^{\prime}$ and $Y:=V\setminus X$. We
have seen that $|Y|\leq 20\varepsilon_{4}n\leq\varepsilon_{5}n$.

For $v\in V$, let $N(v)$ be the _link_ of $v$, namely the graph spanned by
pairs $uw$ such that $uvw\in E(\mathcal{H})$. Write $A:=X_{1}^{\prime}$ and
$B:=X\setminus X_{1}^{\prime}$.

######  Claim 6.7.

One of the graphs $N(u)[A]$ and $N(u)[A,B]$ has at most $\varepsilon_{6}n^{2}$
non-edges, for every $u\in V$.

###### Proof.

Let $\varepsilon_{5}\ll\mu\ll\varepsilon_{6}$. Note that the claim holds for
all $u\in X$, so it suffices to prove it for $u\in Y$. Fix such $u$.

Let $\mathcal{F}$ be the hypergraph on vertex set $X$ whose edges are all
$X_{i}^{\prime}X_{i}^{\prime}X_{j}^{\prime}$ triples with $1\leq i<j\leq
k_{0}$. We will construct two hypergraphs $\mathcal{F}_{i}^{+}$ (for
$i\in\\{1,2\\}$), that consist of $\mathcal{F}$ with one additional vertex
$u_{i}$, which is a suitable modification of $u$, and that have no odd
pseudocycles of length at most $\ell/10$. We will argue that if both $N(u)[A]$
and $N(u)[A,B]$ have at least $\varepsilon_{6}n^{2}$ non-edges then
$d_{\mathcal{F}_{i}^{+}}(u_{i})>(3\alpha+\mu)n^{2}$ for some $i\in[2]$,
contradicting Proposition 6.6.

Let $F_{0}$ be the graph on vertex set $X$ with edges $E(H)\cap E(N(u))$.
Recall that vertices in $X_{i}^{\prime}$ have at most $2\varepsilon_{4}n$ non-
neighbours in $H[X^{\prime}_{>i}]$. Thus, using Proposition 6.5 for a lower
bound on $d_{\mathcal{H}}(u)$, we have $e(F_{0})\geq
d_{\mathcal{H}}(u)-|Y|\cdot n-|X|\cdot
2\varepsilon_{4}n\geq(3\alpha-10\varepsilon_{5})n^{2}$. We modify $F_{0}$ as
follows, while possible: remove each edge $xy$ satisfying: $x,y\in A$ and $x$
has degree $1$ in $A$; or $x\in A$, $y\in B$, and $x$ has degree $1$ into $B$
or $y$ has degree $1$ into $A$. Call the resulting graph $F$ and notice that
$|E(F_{0})\setminus E(F)|\leq 2n$, implying that

$e(F)\geq(3\alpha-20\varepsilon_{5})n^{2}.$ (12)

Recall that $\mathcal{F}$ is the hypergraph on vertex set $X$ whose edges are
all $X_{i}^{\prime}X_{i}^{\prime}X_{j}^{\prime}$ triples with $1\leq i<j\leq
k_{0}$, and let $\mathcal{F}^{+}$ be the hypergraph obtained by adding the
vertex $u$ to $\mathcal{F}$ along with all edges $uvw$ such that $vw\in E(F)$.
We argue that $\mathcal{F}^{+}$ has no odd pseudocycles of length at most
$\ell/10$. To do so, we prove the following.

$\displaystyle\begin{split}&\text{Let $xy,vw\in E(H)$, and let $P$ be a
pseudopath in $\mathcal{F}$ from $xy$ to $vw$ on $t$ vertices. Then}\\\
&\text{there is a pseudopath $P^{\prime}$ in $\mathcal{H}$ from $xy$ to $vw$
of order $t$ (if $t\in\\{2,3\\}$) or $t+3$ (otherwise).}\end{split}$ (13)

We prove (13) by induction on $t$. If $t=2$ we can take $P^{\prime}=P$.
Suppose that $t=3$, so $P=xyw$. Let $i_{1},i_{2},i_{3}$ be such that $x\in
X_{i_{1}}^{\prime}$, $y\in X_{i_{2}}^{\prime}$ and $w\in X_{i_{3}}^{\prime}$.
Since $xy\in E(H)$, we know that for almost every $a\in X_{i_{3}}^{\prime}$
the following holds: $xya\in E(\mathcal{H})$ and $ya\in E(H)$; pick such an
$a$ with $a\neq w$. Similarly, $yab$ and $ywb$ are edges in $\mathcal{H}$ for
almost every $b\in X_{i_{1}}^{\prime}$; pick such $b$. The path $xyabyw$
satisfies the requirements.

Next, suppose that $t=4$, so $P=xyvw$. Let $i_{1},i_{2},i_{3},i_{4}$ be such
that $x\in X_{i_{1}}^{\prime}$, $y\in X_{i_{2}}^{\prime}$, $v\in
X_{i_{3}}^{\prime}$ and $w\in X_{i_{4}}^{\prime}$. As $xy\in E(H)$, almost all
$a\in X_{i_{3}}^{\prime}$ satisfy $xya\in E(\mathcal{H})$ and $ya\in E(H)$;
fix such $a$. Similarly, almost all $c\in X_{i_{2}}^{\prime}$ satisfy $cvw\in
E(\mathcal{H})$, $cv\in E(H)$ and $ac\in E(H)$; fix such $c$. Finally, almost
every $b\in X_{i_{3}}^{\prime}$ satisfies $yab,abc,bcv\in E(\mathcal{H})$; fix
such $b$. Then $P^{\prime}=xyabcvw$ satisfies the requirements.

Finally, suppose that $t\geq 5$, and write $P=v_{1}\ldots v_{t}$, so
$x=v_{1}$, $y=v_{2}$, $v=v_{t-1}$ and $w=v_{t}$. Let $i_{j}$ be such that
$v_{j}\in X_{i_{j}}^{\prime}$ for $j\in[t]$. As usual, since $xy=v_{1}v_{2}\in
E(H)$, almost all $a\in X_{i_{3}}^{\prime}$ satisfy: $v_{2}a\in E(H)$ and
$v_{1}v_{2}a\in E(\mathcal{H})$. Let $Q=v_{2}av_{4}\ldots v_{t}$. Then $Q$ is
a pseudopath in $\mathcal{F}$ of order $t-1$ that starts and ends with edges
in $H$. By induction, there is a pseudopath $Q^{\prime}$ in $\mathcal{H}$ from
$v_{2}a$ to $v_{t-1}v_{t}$ of order $t+2$. Then we can take
$P^{\prime}=v_{1}Q^{\prime}$, completing the proof of (13).

Now suppose that $C=v_{1}\ldots v_{t}$ is a pseudocycle in $\mathcal{F}^{+}$,
where $t\leq\ell/10$. We need to show that $t$ is divisible by $3$. If $C$
does not go through $u$, then $C$ is in $\mathcal{F}$, implying that $t$ is
indeed divisible by $3$. So we may assume that $C$ goes through $u$ at least
once. This shows that $C$ can be written as $uP_{1}u\ldots uP_{k}$, where
$P_{i}$ is a pseudopath in $\mathcal{F}$ whose first two vertices and last two
vertices form edges in $F$. It follows from (13) that for each $i\in[k]$ there
is a pseudopath $P_{i}^{\prime}$ in $\mathcal{H}$ whose first two vertices and
last two vertices match those of $P_{i}$ and whose order satisfies
$|P_{i}^{\prime}|-|P_{i}|\in\\{0,3\\}$. Then
$C^{\prime}:=vP_{1}^{\prime}v\ldots vP_{k}^{\prime}$ is a cycle in
$\mathcal{H}$ with $|C^{\prime}|\leq|C|+3k\leq 4|C|\leq\ell$ and
$|C^{\prime}|\equiv|C|\,(\mathrm{mod}\,\,3)$. By the properties of
$\mathcal{H}$, we have that $|C^{\prime}|$ is divisible by $3$, implying that
$|C|$ is divisible by $3$, as required.

Let $A_{0}$ and $A_{1}$ be the sets of vertices in $A$ incident with $AA$ and
$AB$ edges in $F$, respectively (that is, $a_{0}\in A_{0}$ if $F$ contains an
edge $a_{0}x$ with $x\in A$). We claim that $A_{0}$ and $A_{1}$ are disjoint.
Indeed, if $a_{1}\in A_{0}\cap A_{1}$, then there are vertices $b_{0}\in B$
and $a_{0},a_{2}\in A-a_{1}$ such that $a_{0}a_{1}b_{0}a_{2}$ is a path in
$F$. Let $a_{3}$ and $b_{1}$ be arbitrary vertices in $A$ and $B$,
respectively (distinct from previously chosen vertices). Then
$a_{0}a_{1}ub_{0}a_{2}a_{3}b_{1}$ is cycle of length 7 in $\mathcal{F}^{+}$, a
contradiction.

Let $B_{1}$ be the set of vertices in $B$ incident with $AB$ edges in $F$.
Using a similar argument to the above paragraph, we will show that $B_{1}$ is
independent in $F$. Indeed, otherwise there is a path $a_{1}b_{1}b_{2}a_{2}$
in $F$. Choosing $a_{3},a_{4}\in A$ and $b_{3}\in B$ to be arbitrary unused
vertices, we obtain a cycle $a_{1}b_{1}ub_{2}a_{2}a_{3}b_{3}a_{4}$ of length 8
in $\mathcal{F}^{+}$ and reach a contradiction.

Let $F_{1}$ and $F_{2}$ be graphs on vertex set $X$, defined as follows:
$E(F_{1})=A\times B$ and $E(F_{2})=A^{(2)}\cup E(F[B])$. Now define
$\mathcal{F}^{+}_{i}$ to be the graph obtained from $\mathcal{F}$ by adding a
new vertex $u_{i}$ and edges $u_{i}vw$ such that $vw\in E(F_{i})$, for
$i\in[2]$. Thus $\mathcal{F}^{+}_{i}$ and $\mathcal{F}^{+}$ differ only on
edges touching $u_{i}$ or $u$. We claim that $\mathcal{F}^{+}_{i}$ has no odd
pseudocycles of length at most $\ell/10$. Indeed, this is easy to see for
$i=1$, because we can think of $\mathcal{F}^{+}_{1}$ as obtained by extending
$X_{1}^{\prime}$ by one vertex. To see that this also holds for $i=2$, notice
that in $\mathcal{F}^{+}_{2}$, the $AAB$ and $BBB$ triples are in different
strong components, so any pseudocycle $C$ in $\mathcal{F}^{+}_{2}$ is either a
pseudocycle in $\mathcal{F}^{+}$ or consists only of edges containing exactly
two vertices from $A$.

Notice that $e(\mathcal{F}^{+}_{i})\geq c(G)-|Y|n^{2}\geq
f(n)-(\varepsilon_{1}+\varepsilon_{5})n^{3}\geq f(n)-2\varepsilon_{5}n^{3}$,
because all cherries in $G$ that do not touch $Y$ are edges in $\mathcal{F}$
and $c(G)\geq c(G^{\prime})\geq f(n)-\varepsilon_{1}n^{3}$. Using this lower
bound and the fact that $\mathcal{F}^{+}_{i}$ has no odd pseudocycles of
length at most $\ell/10$, Proposition 6.6 implies that
$d_{\mathcal{F}^{+}_{i}}(u_{i})\leq(3\alpha+\mu)n^{2}$. Since
$d_{\mathcal{F}^{+}}(u)=e(F)\geq(3\alpha-20\varepsilon_{5})n^{2}$ (see (12)),
we have
$e(F_{i})-e(F)=d_{\mathcal{F}^{+}_{i}}(u_{i})-d_{\mathcal{F}^{+}}(u)\leq(\mu+20\varepsilon_{5})n^{2}\leq
2\mu n^{2}$ for $i\in[2]$.

To finish, suppose first that $|A_{0}|\geq|B_{1}|$. Recalling that $F$ and
$F_{1}$ coincide on $B$, and that $F$ has no edges in $(A_{1}\cup B_{1})\times
A_{0}$ or $A_{1}^{(2)}$, we have

$\displaystyle 2\mu n^{2}\geq e(F_{2})-e(F)$
$\displaystyle\geq-|A_{1}||B_{1}|+|A_{0}||A_{1}|+\binom{|A_{1}|}{2}+\bar{e}(F[A_{0}])$
$\displaystyle\geq\frac{|A_{1}|^{2}}{2}+\bar{e}(F[A_{0}])+O(n).$

It follows that $|A_{1}|\leq 5\mu^{1/2}n$ and $\bar{e}(F[A_{0}])\leq 5\mu
n^{2}$. Altogether $\bar{e}(F[A])\leq|A_{1}|\,n+\bar{e}(F[A_{0}])\leq
10\mu^{1/2}n^{2}\leq\varepsilon_{6}n^{2}$. Since $F[A]\subseteq N(u)[A]$,
Claim 6.7 is proved in this case.

Now we consider the remaining case, namely that $|A_{0}|\leq|B_{1}|$. Let
$B_{0}=B\setminus B_{1}$, and recall that $F$ has no edges in $B_{1}^{(2)}$ or
in $A_{0}\times B_{1}$. Using $|A|\geq|B|=|B_{0}|+|B_{1}|$,

$\displaystyle 2\mu n^{2}$ $\displaystyle\geq
e(\mathcal{F}^{+}_{1})-e(\mathcal{F}^{+})$
$\displaystyle\geq-\binom{|A_{0}|}{2}-\binom{|B_{0}|}{2}-|B_{0}||B_{1}|+|A||B_{0}|+|A_{0}||B_{1}|+\bar{e}(F[A_{1},B_{1}])$
$\displaystyle\geq|A_{0}|(|B_{1}|-|A_{0}|)+|B_{0}|(|A|-|B_{0}|-|B_{1}|)+\frac{|A_{0}|^{2}}{2}+\frac{|B_{0}|^{2}}{2}+\bar{e}(F[A_{1},B_{1}])+O(n)$
$\displaystyle\geq\frac{|A_{0}|^{2}}{2}+\frac{|B_{0}|^{2}}{2}+\bar{e}(F[A_{1},B_{1}])+O(n).$

Thus, we have $|A_{0}|,|B_{0}|\leq 5\mu^{1/2}n$ and
$\bar{e}(F[A_{1},B_{1}])\leq 5\mu n^{2}$. This implies that
$\bar{e}(F[A,B])\leq|A_{0}|\,n+|B_{0}|\,n+\bar{e}(F[A_{1},B_{1}])\leq\varepsilon_{6}n^{2}$,
proving Claim 6.7. ∎

Let $A^{*}$ be the set of vertices $u$ such that $N(u)[A,B]$ has at most
$\varepsilon_{6}n^{2}$ non-edges, and let $B^{*}:=V\setminus A^{*}$. Note that
$A\subseteq A^{*}$, and by Claim 6.7, for every $u\in B^{*}$ the graph
$N(u)[A]$ has at most $\varepsilon_{6}n^{2}$ non-edges. Let $t_{1}$ be the
number of $A^{*}A^{*}A^{*}$ triples in $\mathcal{H}$, let $t_{2}$ be the
number of $A^{*}B^{*}B^{*}$ triples in $\mathcal{H}$, and let $s$ be the
number of $A^{*}A^{*}B^{*}$ triples that are not edges in $\mathcal{H}$. Let
$\mathcal{H}^{*}$ be the hypergraph obtained from $\mathcal{H}$ by removing
all $A^{*}A^{*}A^{*}$ and $A^{*}B^{*}B^{*}$ triples and adding all missing
$A^{*}A^{*}B^{*}$ triples. Then $\mathcal{H}^{*}$ has no odd pseudocycle of
length at most $\ell$; this follows from observing that every pseudocycle in
$\mathcal{H}^{*}$ is either a pseudocycle in $\mathcal{H}$ or each of its
edges has exactly two vertices in $A^{*}$. Moreover,
$e(\mathcal{H}^{*})-e(\mathcal{H})=s-(t_{1}+t_{2})$. By maximality of
$\mathcal{H}$ we have $s\leq t_{1}+t_{2}$.

######  Claim 6.8.

$t_{1}\leq\varepsilon_{7}s$.

###### Proof.

Let $\varepsilon_{6}\ll\mu\ll\varepsilon_{7}$.

We first show that for every distinct $u,v\in A^{*}$, there are at most $\mu
n$ vertices $w\in A^{*}$ such that $uvw\in E(\mathcal{H})$.

Suppose there exist $u,v\in A^{*}$ violating this. Let $W$ be the set of
vertices $w\in A^{*}$ such that $uvw\in E(\mathcal{H})$, so $|W|\geq\mu n$.
Consider the graph $(N(u)\cap N(v))[W,B]$; its edges are pairs $wb$ such that
$w\in W$, $b\in B$, and $uwb,vwb\in E(\mathcal{H})$. This graph has at most
$2\varepsilon_{6}n^{2}$ non-edges, by Claim 6.7. Thus there exists $b\in B$
with at least $\frac{1}{2}\mu n$ neighbours in the aforementioned graph;
denote its set of neighbours by $W^{\prime}$. Now, by Claim 6.7, $b$ is
adjacent in $\mathcal{H}$ to all but at most $\varepsilon_{6}n^{2}$ pairs in
$W^{\prime}$, so there exists a triple $w_{1}w_{2}b\in E(\mathcal{H})$ with
$w_{1},w_{2}\in W^{\prime}$. Thus $uvw_{1}bw_{2}$ is a pseudocycle of length
5, contradiction.

To finish the argument, we count the four-tuples

$Q:=\\{\\{u,v,w,z\\}:u,v,w\in A^{*},z\in B^{*},uvw\in E(\mathcal{H}),uvz\notin
E(\mathcal{H})\\}$

in two different ways. For each vertex $b\in B^{*}$ and $A^{*}A^{*}A^{*}$
triple $uvw\in E(\mathcal{H})$, at least one of the triples $uvb,uwb,vwb$ is
not in $E(\mathcal{H})$, so $|Q|\geq t_{1}|B^{*}|$. On the other hand, it
follows from the above paragraph that any $A^{*}A^{*}B^{*}$ triple $uvz\notin
E(\mathcal{H})$ extends to at most $\mu n$ elements of $Q$, so $|Q|\leq s\mu
n$. Hence

$t_{1}\leq\frac{|Q|}{|B^{*}|}\leq\frac{s\mu n}{|B^{*}|}\leq\varepsilon_{7}s,$

as claimed. ∎

######  Claim 6.9.

$t_{2}\leq 2s/3$.

###### Proof.

Let $\varepsilon_{6}\ll\mu\ll\varepsilon_{7}$.

To begin with, we show that if $uvw$ is an $A^{*}B^{*}B^{*}$ triple in
$\mathcal{H}$ (with $u\in A^{*}$) then one of the pairs $uv$ and $vw$ is in at
most $\mu n$ triples of form $A^{*}A^{*}B^{*}$ in $\mathcal{H}$. Fix an
$A^{*}A^{*}B^{*}$ triple $uvw\in E(\mathcal{H})$.

Let $W^{\prime}$ (resp. $V^{\prime}$) be set of vertices $a\in A^{*}$ such
that $uwa\in E(\mathcal{H})$ (resp. $uva\in E(\mathcal{H})$). Suppose that
$|W^{\prime}|,|V^{\prime}|\geq\mu n$. Consider the graph $(N(v)\cap
N(w))[W^{\prime},V^{\prime}]$. By Claim 6.7, this graph contains an edge
$a_{1}a_{2}$, i.e. we have $a_{1}a_{2}w$, $a_{1}a_{2}v\in E(\mathcal{H})$. By
definition of $W^{\prime}$ and $V^{\prime}$, the triples $uwa_{1}$ and
$uva_{2}$ are in $\mathcal{H}$. Hence $uwa_{1}a_{2}v$ is a cycle of length 5,
contradiction.

Let $F$ be an auxiliary bipartite graph with parts $A^{*}$ and $B^{*}$ such
that $uv$ is an edge of $F$ whenever (i) there is an $A^{*}B^{*}B^{*}$ triple
in $\mathcal{H}$ containing $uv$, and (ii) the number of $A^{*}A^{*}B^{*}$
triples containing $uv$ is at most $\mu n$. By the previous paragraph, each
$A^{*}B^{*}B^{*}$ triple in $\mathcal{H}$ contains an edge of $F$, so

$t_{2}\leq|B^{*}|\cdot e(F)\leq 0.4n\cdot e(F).$

Moreover, we claim that $d_{F}(v)\leq\mu n$ for every $v\in B^{*}$. Indeed, by
(ii), the graph $N(v)[A^{*}]$ has at least $d_{F}(v)(|A^{*}|-\mu n)/2$ non-
edges. If $d_{F}(v)>\mu n$ then this quantity is larger than
$2\varepsilon_{6}n^{2}$, contradicting Claim 6.7. Also using (ii), we conclude
that

$s\geq\sum_{v\in B^{*}}d_{F}(v)\cdot(|A^{*}|-d_{F}(v)-\mu n)\geq 0.6n\cdot
e(F).$

It follows that $t_{2}\leq 2s/3$, as claimed. ∎

The last two claims, and the choice $\varepsilon_{7}=0.1$, say, show that
$(t_{1}+t_{2})\leq 0.8s$. Since $s\leq t_{1}+t_{2}$ this implies that
$t_{1}=t_{2}=s=0$. That is, all $A^{*}A^{*}B^{*}$ triples are edges in
$\mathcal{H}$ (and there are no $A^{*}A^{*}A^{*}$ or $A^{*}B^{*}B^{*}$ edges).
This proves Theorem 6.1. ∎

##  7 Open problems

There are two natural extensions of our result. Firstly, one could prove
Conjecture 1.1, or perhaps determine the density of $C_{\ell}^{(3)}$ for
smaller values of $\ell$, say $\ell\leq 100$. Although we do not state our
bound on $\ell$ explicitly, this would not be too cumbersome, since it is a
polynomial in $\varepsilon_{7}$, and we set $\varepsilon_{7}=0.1$.

The second direction is determining the Turán density of $r$-uniform tight
cycles for $r\geq 4$. For this, we do not even know of a conjectured optimal
construction. Moreover, our characterisation of odd-pseudocycle-free
hypergraphs (Theorem 2.4) does not have an obvious extension, as the
straightforward extension of Definition 2.3 is too strong.

As mentioned in the introduction, there are many other specific 3-uniform
hypergraphs for which determining the Turán density would be very interesting.
Let us point out one conjecture which is perhaps less well known, and which
can be found for instance in [24].

######  Conjecture 7.1.

Let $\mathcal{C}_{5}^{-}$ be the 3-uniform hypergraph obtained from the tight
5-cycle $\mathcal{C}_{5}^{3}$ by removing one edge. The Turán density of
$\mathcal{C}_{5}^{-}$ is $\frac{1}{4}$.

As in our case, one conjectured extremal hypergraph is an iterated
construction; one may take a complete 3-partite 3-uniform hypergraph and then
repeat the same construction recursively within each of the three parts.

### Acknowledgements

We would like to thank Xizhi Liu, Yuejian Peng, and Oleg Pikhurko for bringing
to our attention several important references.

## References

  * [1] R. Baber and J. Talbot, _New Turán densities for 3-graphs_ , Electron. J. Combin. 19 (2012), Paper P40.
  * [2] B. Bollobás, I. Leader, and C. Malvenuto, _Daisies and other Turán problems_ , Combin. Probab. Comput. 20 (2011), no. 5, 743–747.
  * [3] W. G. Brown, _On an open problem of Paul Turán concerning $3$-graphs_, Studies in pure mathematics, Birkhäuser, Basel, 1983, pp. 91–93.
  * [4] M. Bucić, J. W. Cooper, D. Kráľ, S. Mohr, and D. Munhá Correia, _Uniform Turán density of cycles_ , arXiv:2112.01385 (2021).
  * [5] F. Chung and R. Graham, _Erdős on graphs_ , A K Peters, Ltd., Wellesley, MA, 1998, His legacy of unsolved problems.
  * [6] D. De Caen and Z. Füredi, _The maximum size of 3-uniform hypergraphs not containing a Fano plane_ , J. Combin. Theory Ser. B 78 (2000), no. 2, 274–276.
  * [7] P. Erdős, _On some extremal problems on $r$-graphs_, Discr. Math. 1 (1971), 1–6.
  * [8] P. Erdős and A. H. Stone, _On the structure of linear graphs_ , Bull. Am. Math. Soc. 52 (1946), no. 12, 1087–1091.
  * [9] P. Erdős and V. T. Sós, _On Ramsey—Turán type theorems for hypergraphs_ , Combinatorica 2 (1982), no. 3, 289–295.
  * [10] V. Falgas-Ravry and E. R. Vaughan, _Turán $H$-densities for 3-graphs_, Electron. J. Combin. (2012), P40.
  * [11] D. G. Fon-Der-Flaass, _A method for constructing $(3,4)$-graphs_, Mat. Zametki 44 (1988), no. 4, 546–550, 559.
  * [12] P. Frankl and Z. Füredi, _An exact result for $3$-graphs_, Discrete Math. 50 (1984), no. 2-3, 323–328.
  * [13] Z. Füredi and M. Simonovits, _Triple systems not containing a Fano configuration_ , Combin. Probab. Comput. 14 (2005), no. 4, 467–484.
  * [14] R. Glebov, D. Kráľ, and J. Volec, _A problem of Erdős and Sós on 3-graphs_ , Israel J. Math. 211 (2016), no. 1, 349–366.
  * [15] H. Huang, _On the maximum induced density of directed stars and related problems_ , SIAM J. Discr. Math. 28 (2014), no. 1, 92–98.
  * [16] H. Huang and J. Ma, _On tight cycles in hypergraphs_ , SIAM J. Discrete Math. 33 (2019), no. 1, 230–237.
  * [17] B. Janzer, _Large hypergraphs without tight cycles_ , Comb. Theory 1 (2021), Paper No. 12, 4.
  * [18] P. Keevash, _Hypergraph Turán problems_ , Surveys in combinatorics 2011, London Math. Soc. Lecture Note Ser., vol. 392, Cambridge Univ. Press, Cambridge, 2011, pp. 83–139.
  * [19] P. Keevash and B. Sudakov, _The Turán number of the Fano plane_ , Combinatorica 25 (2005), 561–574.
  * [20] A. V. Kostochka, _Lower bound of the Hadwiger number of graphs by their average degree_ , Combinatorica 4 (1984), no. 4, 307–316.
  * [21] S. Letzter, _Hypergraphs with no tight cycles_ , Proc. Am. Math. Soc. (to appear).
  * [22] H. Liu, O. Pikhurko, M. Sharifzadeh, and K. Staden, _Stability from graph symmetrisation arguments with applications to inducibility_ , arXiv:2012.10731 (2020).
  * [23] W. Mantel, _Problem 28_ , Wiskundige Opgaven 10 (1907), 60–61.
  * [24] D. Mubayi, O. Pikhurko, and B. Sudakov, _Hypergraph Turán problem: some open questions_ , AIM workshop problem lists, manuscript, homepages.warwick.ac.uk/~maskat/Papers/TuranQuestions.pdf.
  * [25] D. Mubayi and V. Rödl, _On the Turán number of triple systems_ , J. Combin. Theory Ser. A 100 (2002), no. 1, 136–152.
  * [26] O. Pikhurko, _On possible Turán densities_ , Israel J. Math. 201 (2014), 415–454.
  * [27] A. A. Razborov, _On 3-hypergraphs with forbidden 4-vertex configurations_ , SIAM J. Discr. Math. 24 (2010), no. 3, 946–963.
  * [28] A. A. Razborov, _On the Fon-der-Flaass interpretation of extremal examples for Turán’s $(3,4)$-problem_, Tr. Mat. Inst. Steklova 274 (2011), no. Algoritmicheskie Voprosy Algebry i Logiki, 269–290.
  * [29] A. A. Razborov, _Flag algebras: an interim report_ , The Mathematics of Paul Erdős II, Springer, 2013, pp. 207–232.
  * [30] C. Reiher, V. Rödl, and M. Schacht, _On a Turán problem in weakly quasirandom 3-uniform hypergraphs_ , J. Eur. Math. Soc. (JEMS) 20 (2018), no. 5, 1139–1159.
  * [31] B. Sudakov and I. Tomon, _The extremal number of tight cycles_ , Int. Math. Res. Not. IMRN (2022), no. 13, 9663–9684.
  * [32] P. Turán, _Eine Extremalaufgabe aus der Graphentheorie_ , Mat. Fiz. Lapok 48 (1941), 436–452.
  * [33] , _Research problem_ , Közl MTA Mat. Kutató Int. 6 (1961), 417–423.
  * [34] B. Wu, _An Irrational Turán Density via Hypergraph Lagrangian Densities_ , Electron. J. Combin. 29 (2022), no. 3, Paper No. 3.62–. MR 4486632
  * [35] Z. Yan and Y. Peng, _An irrational Lagrangian density of a single hypergraph_ , SIAM J. Discrete Math. 36 (2022), no. 1, 786–822. MR 4400421