# Hypergraphs with infinitely many extremal constructions

Jianfeng Hou Research was supported by National Natural Science Foundation of
China (Grant No. 12071077). Email<EMAIL_ADDRESS>Center for Discrete
Mathematics, Fuzhou University, Fujian, 350003, China  Heng Li Email:
<EMAIL_ADDRESS>Center for Discrete Mathematics, Fuzhou University,
Fujian, 350003, China  Xizhi Liu Research was supported by ERC Advanced Grant
101020255. Email<EMAIL_ADDRESS>Department of Mathematics,
Statistics, and Computer Science, University of Illinois, Chicago, IL, 60607
USA.  Mathematics Institute and DIMAP, University of Warwick, Coventry, CV4
7AL, UK  Dhruv Mubayi Research was supported by NSF awards DMS-1763317 and
DMS-1952767. Email<EMAIL_ADDRESS>Department of Mathematics, Statistics, and
Computer Science, University of Illinois, Chicago, IL, 60607 USA.  Yixiao
Zhang Email<EMAIL_ADDRESS>Center for Discrete Mathematics, Fuzhou
University, Fujian, 350003, China

###### Abstract

We give the first exact and stability results for a hypergraph Turán problem
with infinitely many extremal constructions that are far from each other in
edit-distance. This includes an example of triple systems with Turán density
$2/9$, thus answering some questions posed by the third and fourth authors and
Reiher about the feasible region of hypergraphs. Our results also provide
extremal constructions whose shadow density is a transcendental number.

Our novel approach is to construct certain multilinear polynomials that attain
their maximum (in the standard simplex) on a line segment and then to use
these polynomials to define an operation on hypergraphs that gives extremal
constructions.

##  1 Introduction

###  1.1 Turán number and stability

For $r\geq 2$ an $r$-uniform hypergraph (henceforth $r$-graph) $\mathcal{H}$
is a collection of $r$-subsets of some finite set $V$. Given a family
$\mathcal{F}$ of $r$-graphs we say $\mathcal{H}$ is $\mathcal{F}$-free if it
does not contain any member of $\mathcal{F}$ as a subgraph. The Turán number
$\mathrm{ex}(n,\mathcal{F})$ of $\mathcal{F}$ is the maximum number of edges
in an $\mathcal{F}$-free $r$-graph on $n$ vertices. The Turán density
$\pi(\mathcal{F})$ of $\mathcal{F}$ is defined as
$\pi(\mathcal{F})=\lim_{n\to\infty}\mathrm{ex}(n,\mathcal{F})/{n\choose r}$. A
family $\mathcal{F}$ is called _nondegenerate_ if $\pi(\mathcal{F})>0$. The
study of $\mathrm{ex}(n,\mathcal{F})$ is perhaps the central topic in extremal
graph and hypergraph theory.

Much is known about $\mathrm{ex}(n,\mathcal{F})$ when $r=2$, and one of the
most famous results in this regard is Turán’s theorem, which states that for
every integer $\ell\geq 2$ the Turán number $\mathrm{ex}(n,K_{\ell+1})$ is
uniquely achieved by the balanced $\ell$-partite graph on $n$ vertices, which
is called the Turán graph $T(n,\ell)$.

For $r\geq 3$ determining $\pi(\mathcal{F})$ for a family $\mathcal{F}$ of
$r$-graphs is known to be notoriously hard in general. Indeed, the problem of
determining $\pi(K_{\ell}^{r})$ raised by Turán [30], where $K_{\ell}^{r}$ is
the complete $r$-graph on $\ell$ vertices, is still wide open for all
$\ell>r\geq 3$. Erdős offered $\$500$ for the determination of any
$\pi(K_{\ell}^{r})$ with $\ell>r\geq 3$ and $\$1000$ for the determination of
all $\pi(K_{\ell}^{r})$ with $\ell>r\geq 3$.

######  Conjecture 1.1 (Turán [30]).

For every integer $\ell\geq 3$ we have $\pi(K_{\ell+1}^{3})=1-{4}/{\ell^{2}}$.

The case $\ell=3$ above, which states that $\pi(K_{4}^{3})=5/9$ has generated
a lot of interest and activity over the years. Many constructions (e.g. see
[3, 16, 8]) are known to achieve the value in Conjecture 1.1 for $\ell=3$. In
particular, Kostochka [16] showed that there are at least $2^{n-2}$
nonisomorphic extremal $K_{4}^{3}$-free constructions on $3n$ vertices
(assuming Turán’s Tetrahedron conjecture is true). This is perhaps one of the
reasons why it is so challenging. On the other hand, successively better upper
bounds for $\pi(K_{4}^{3})$ were obtained by de Caen [5], Giraud (see [4]),
Chung and Lu [4], and Razborov [27]. The current record is $\pi(K_{4}^{3})\leq
0.561666$, which was obtained by Razborov [27] using the Flag Algebra
machinery.

In this work, we continue the research on hypergraph Turán problems with the
flavour of trying to show that certain phenomena impossible for graphs are
possible for $r$-graphs when $r\geq 3$. There are several results that belong
to this category. For instance, the well known work of Frankl and Rödl on
jumps [12], and Pikhurko’s theorem that for $r\geq 3$ there exist uncountably
many Turán densities of infinite families of $r$-graphs [26]. More
specifically, we will show that there are infinitely many finite families
$\mathcal{F}$ with similar properties as $K_{4}^{3}$ (assuming Turán’s
conjecture) in terms of the number of extremal constructions.

Many families $\mathcal{F}$ have the property that there is a unique
$\mathcal{F}$-free hypergraph $\mathcal{G}$ on $n$ vertices achieving
$\mathrm{ex}(n,\mathcal{F})$, and moreover, any $\mathcal{F}$-free hypergraph
$\mathcal{H}$ of size close to $\mathrm{ex}(n,\mathcal{F})$ can be transformed
to $\mathcal{G}$ by deleting and adding very few edges. Such a property is
called the stability of $\mathcal{F}$. The first stability theorem, which says
that $K_{\ell}$ is stable for all integers $\ell\geq 3$, was proved
independently by Erdős and Simonovits [29]. Their result motivated the third
author [25] to make the following definition.

######  Definition 1.2 ($t$-stable).

Let $r\geq 2$ and $t\geq 1$ be integers. A family $\mathcal{F}$ of $r$-graphs
is $t$-stable if for every $m\in\mathbb{N}$ there exist $r$-graphs
$\mathcal{G}_{1}(m),\ldots,\mathcal{G}_{t}(m)$ on $m$ vertices such that the
following holds. For every $\delta>0$ there exist $\epsilon>0$ and $N_{0}$
such that for all $n\geq N_{0}$ if $\mathcal{H}$ is an $\mathcal{F}$-free
$r$-graph on $n$ vertices with
$|\mathcal{H}|>(1-\epsilon)\mathrm{ex}(n,\mathcal{F})$ then $\mathcal{H}$ can
be transformed to some $\mathcal{G}_{i}(n)$ by adding and removing at most
$\delta n^{r}$ edges. Say $\mathcal{F}$ is stable if it is $1$-stable.

Denote by $\xi(\mathcal{F})$ the minimum integer $t$ such that $\mathcal{F}$
is $t$-stable, and set $\xi(\mathcal{F})=\infty$ if there is no such $t$. Call
$\xi(\mathcal{F})$ _the stability number_ of $\mathcal{F}$.

The classical Erdős–Stone–Simonovits theorem [7, 6] and Erdős–Simonovits
stability theorem [29] imply that every nondegenerate family of graphs is
stable. For hypergraphs there are many families (whose Turán densities are
unknown) which are conjecturally not stable. Two famous examples are Turán’s
conjecture on tetrahedra (i.e. $K_{4}^{3}$) mentioned above (e.g. see [28, 16,
21]), and the Erdős–Sós conjecture on triple systems with bipartite links
(e.g. see [9, 21]). In fact, families that are not stable and whose Turán
densities can be determined were constructed only very recently. In [21], the
third and fourth authors constructed the first finite $2$-stable family of
$3$-graphs. Later in [23], together with Reiher, they further constructed the
first finite $t$-stable family of $3$-graphs for every integer $t\geq 3$. In
[22], using a similar method that was used for the hypergraph jump problem
(see e.g. [11]) their constructions were extended to every integer $r\geq 4$.

Using Kostochka’s constructions the authors proved in [21] that
$\xi(K_{4}^{3})=\infty$ (assuming Turán’s conjecture). However, the methods
used in [21] and [23] for constructing the $2$-stable family and $t$-stable
families cannot be extended further to construct a finite family whose
stability number is infinite, and this was left as an open question in both
papers.

Our main result in this work is to give a novel method to construct (finite)
families $\mathcal{F}$ with $\xi(\mathcal{F})=\infty$. Our method is based on
a simple property of multilinear polynomials, which will be stated in Section
1.4. We will use this method to give infinitely many (finite) families of
$3$-graphs whose number of extremal constructions grows with the number of
vertices. Further, using the machinery provided in [24] we also prove an
Andrásfai–Erdős–Sós type [1] stability theorem for these families.

We identify an $r$-graph $\mathcal{H}$ with its edge set, use $V(\mathcal{H})$
to denote its vertex set, and denote by $v(\mathcal{H})$ the size of
$V(\mathcal{H})$. An $r$-graph $\mathcal{H}$ is a _blowup_ of an $r$-graph
$\mathcal{G}$ if there exists a map $\psi\colon V(\mathcal{H})\to
V(\mathcal{G})$ so that $\psi(E)\in\mathcal{G}$ iff $E\in\mathcal{H}$. We say
$\mathcal{H}$ is _$\mathcal{G}$ -colorable_ if there exists a map $\phi\colon
V(\mathcal{H})\to V(\mathcal{G})$ so that $\phi(E)\in\mathcal{G}$ for all
$E\in\mathcal{H}$, and we call such a map $\phi$ a _homomorphism_ from
$\mathcal{H}$ to $\mathcal{G}$. In other words, $\mathcal{H}$ is
$\mathcal{G}$-colorable if and only if $\mathcal{H}$ occurs as a subgraph in
some blowup of $\mathcal{G}$.

######  Theorem 1.3.

For every integer $t\geq 3$ there exists a finite family $\mathcal{F}_{t}$ of
$3$-graphs such that the following statements hold.

  1. (a)

We have $\mathrm{ex}(n,\mathcal{F}_{t})\leq\frac{(t-2)(t-1)}{6t^{2}}n^{3}$ for
all $n\in\mathbb{N}$, and equality holds whenever $t\mid n$.

  2. (b)

If $t\mid n$, then the number of nonisomorphic maximum $\mathcal{F}_{t}$-free
$3$-graphs on $n$ vertices is at least ${n}/{2t}$.

  3. (c)

We have $\xi(\mathcal{F}_{t})=\infty$.

  4. (d)

For every integer $t\geq 4$ there exist constants $\epsilon=\epsilon(t)>0$ and
$N_{0}=N_{0}(t)$ such that the following holds for every integer $n\geq
N_{0}$. Every $n$-vertex $\mathcal{F}_{t}$-free $3$-graph with minimum degree
at least $\left(\frac{(t-2)(t-1)}{2t^{2}}-\epsilon\right)n^{2}$ is
$\Gamma_{t}$-colorable, where $\Gamma_{t}$ is some fixed $3$-graph on $t+2$
vertices.

Remarks.

  * •

Part (b) says that there are many extremal $\mathcal{F}_{t}$-free $3$-graphs
on $n$ vertices for $t\mid n$. This phenomenon already showed up in Graph
theory. For example, it follows from an old result of Simonovits [29, Theorem
5] that a maximum $K_{1,3,3}$-free graph on $n$ vertices can be obtained from
an $n$-vertex balanced bipartite graph by adding graphs of maximum degree $2$
into both parts. It is clear that there are many nonisomorphic maximum graphs
with maximum degree $2$ on a fixed number of vertices, so there are many
nonisomorphic maximum $K_{1,3,3}$-free graph on $n$ vertices.

For hypergraphs, Balogh and Clemen111Personal communication. claim that there
exists a single $3$-graph $F$ such that for special integers $n$ the maximum
$F$-free $3$-graphs on $n$ vertices are $3$-graphs that can obtained from the
balanced $n$-vertex $3$-partite $3$-graph by adding Steiner triple systems
into all three parts. Thus it follows from a result of Keevash [15] that there
are exponentially many such maximum $F$-free $3$-graphs on $n$ vertices.

These examples are different from our result in the sense that they all have
stability number $1$, i.e. all extremal constructions have a small edit-
distance to each other.

  * •

Motivated by the hypergraph jump problem222Our results in this paper are not
very related to the Jump problem, so we omit the related definitions here. We
refer the interested reader to e.g. [12, 11, 2] for related results., the
authors asked in [23] whether there exists a finite family whose Turán density
is $2/9$ that is not stable? By letting $t=3$ in Theorem 1.3 we see that the
finite family $\mathcal{F}_{3}$ of $3$-graphs has Turán density $2/9$ but
$\xi(\mathcal{F}_{3})=\infty$, thus answering this question.

###  1.2 Multilinear polynomials

In this short section, we state a simple result about polynomials. Later we
will see that our main theorem reduces to this result.

Denote by $\Delta_{m-1}$ the standard $(m-1)$-dimensional simplex, i.e.

$\displaystyle\Delta_{m-1}=\left\\{(x_{1},\ldots,x_{m})\in[0,1]^{m}\colon
x_{1}+\cdots+x_{m}=1\right\\}.$

Given an $m$-variable continuous function $f$ we define

$\displaystyle\lambda(f)=\max\left\\{f(x_{1},\ldots,x_{m})\colon(x_{1},\ldots,x_{m})\in\Delta_{m-1}\right\\},$

and

$\displaystyle Z(f)=\left\\{(x_{1},\ldots,x_{m})\in\Delta_{m-1}\colon
f(x_{1},\ldots,x_{m})-\lambda(f)=0\right\\}.$

Since $\Delta_{m-1}$ is compact, a well known theorem of Weierstraß implies
that the restriction of $f$ to $\Delta_{m-1}$ attains a maximum value. Thus
$\lambda(f)$ and $Z(f)$ are well-defined.

Let $p(X_{1},\ldots,X_{m})$ be a polynomial, where $X_{1},\ldots,X_{m}$ are
indeterminates. We say $p$ is _multilinear_ if for every $\alpha\in\mathbb{R}$
and for every $i\in[m]$ we have $p(X_{1},\ldots,\alpha\cdot
X_{i},\ldots,X_{m})=\alpha\cdot p(X_{1},\ldots,X_{i},\ldots,X_{m})$. Note that
this is equivalent to the fact that each term of $p$ is of the form
$\prod_{i\in S}x_{i}$ for some $S$. We say $p$ is _nonnegative_ (or
_nonpositive_) if $p(x_{1},\ldots,x_{m})\geq 0$ (or $p(x_{1},\ldots,x_{m})\leq
0$) for all $(x_{1},\ldots,x_{m})\in\Delta_{m-1}$. For a pair
$\\{i,j\\}\subset[m]$ we say $p$ is symmetric with respect to $X_{i}$ and
$X_{j}$ if

$p(X_{1},\ldots,X_{i},\ldots,X_{j},\ldots,X_{m})=p(X_{1},\ldots,X_{j},\ldots,X_{i},\ldots,X_{m}).$

An easy observation is that a multilinear polynomial $p(X_{1},\ldots,X_{m})$
is symmetric with respect to $X_{i}$ and $X_{j}$ iff there exist polynomials
$p_{1},p_{2},p_{3}$ without indeterminates $X_{i}$ and $X_{j}$ such that
$p=p_{1}+p_{2}(X_{i}+X_{j})+p_{3}X_{i}X_{j}$.

Given two vectors $\vec{x},\vec{y}\in\mathbb{R}^{m}$ define the line segment
$L(\vec{x},\vec{y})$ with endpoints $\vec{x}$ and $\vec{y}$ as

$\displaystyle
L(\vec{x},\vec{y})=\left\\{\alpha\cdot\vec{x}+(1-\alpha)\cdot\vec{y}\colon\alpha\in[0,1]\right\\}.$

We will later prove the following result about multilinear polynomials.

######  Proposition 1.4.

Let $p(X_{1},\ldots,X_{m})=p_{1}+p_{2}(X_{i}+X_{j})+p_{3}X_{i}X_{j}$ be an
$m$-variable multilinear polynomial that is symmetric with respect to $X_{i}$
and $X_{j}$. Suppose that $p_{3}$ is nonnegative, and $p_{4},p_{5}$ are
nonnegative polynomials satisfying $p_{4}+p_{5}=p_{3}$. Then the
$(m+2)$-variable polynomial

$\displaystyle\hat{p}(X_{1},\ldots,X_{i},X_{i}^{\prime},\ldots,X_{j},X_{j}^{\prime},\ldots,X_{m})$
$\displaystyle=p_{1}+p_{2}(X_{i}+X^{\prime}_{i}+X_{j}+X^{\prime}_{j})+p_{4}(X_{i}+X^{\prime}_{i})(X_{j}+X^{\prime}_{j})+p_{5}(X_{i}+X_{j})(X^{\prime}_{i}+X^{\prime}_{j})$

satisfies $\lambda(\hat{p})=\lambda(p)$, and moreover, for every
$(x_{1},\ldots,x_{m})\in Z(p)$ we have $L(\vec{y},\vec{z})\subset Z(\hat{p})$,
where $\vec{y},\vec{z}\in\Delta_{m+1}$ are defined by

$\displaystyle\vec{y}$
$\displaystyle=\left(x_{1},\ldots,x_{i-1},(x_{i}+x_{j})/2,0,x_{i+1},\ldots,x_{j-1},0,(x_{i}+x_{j})/2,x_{j+1},\ldots,x_{m}\right),$
$\displaystyle\vec{z}$
$\displaystyle=\left(x_{1},\ldots,x_{i-1},0,(x_{i}+x_{j})/2,x_{i+1},\ldots,x_{j-1},(x_{i}+x_{j})/2,0,x_{j+1},\ldots,x_{m}\right).$

###  1.3 Nonminimal hypergraphs

Now we return to hypergraphs. Our constructions are closely related to the so-
called nonminimal hypergraphs. To define them properly we need some
definitions related to the Lagrangian of a hypergraph, which was introduced by
Frankl and Rödl in [12].

For an $r$-graph $\mathcal{G}$ on $m$ vertices (let us assume for notational
transparency that $V(\mathcal{G})=[m]$) the multilinear polynomial
$p_{\mathcal{G}}$ is defined by

$\displaystyle
p_{\mathcal{G}}(X_{1},\ldots,X_{m})=\sum_{E\in\mathcal{G}}\prod_{i\in
E}X_{i}.$

The _Lagrangian_ of $\mathcal{G}$ is defined by
$\lambda(\mathcal{G})=\lambda(p_{\mathcal{G}})$. Define

$\displaystyle
Z(\mathcal{G})=Z(p_{\mathcal{G}})=\left\\{(x_{1},\ldots,x_{n})\in\Delta_{m-1}\colon
p_{\mathcal{G}}(x_{1},\ldots,x_{m})=\lambda(\mathcal{G})\right\\}.$

For a vertex set $S\subset V(\mathcal{G})$ we use $\mathcal{G}-S$ to denote
the induced subgraph of $\mathcal{G}$ on $V(\mathcal{G})\setminus S$.

######  Definition 1.5.

An $r$-graph $\mathcal{G}$ is minimal if
$\lambda(\mathcal{G}-v)<\lambda(\mathcal{G})$ for every vertex
$v\in\mathcal{G}$. Otherwise, it is nonminimal.

A substantial amount of research on hypergraph Turán problems is about minimal
hypergraphs. Indeed, for every nondegenerate family $\mathcal{F}$ of
hypergraphs that was studied before this work, the extremal $\mathcal{F}$-free
constructions are either minimal or blowups of minimal hypergraphs or close to
them in edit-distance. Conversely, in [26], Pikhurko proved that for every
minimal hypergraph $\mathcal{G}$ there exists a finite family $\mathcal{F}$
whose unique extremal construction is a blowup of $\mathcal{G}$ 333Pikhurko’s
results are much more general than what we stated here, and we refer the
reader to [26] for more details.. In contrast, there was very little
literature about nonminimal hypergraphs.

Parallel to Pikhurko’s result about minimal hypergraphs we have the following
result about nonminimal hypergraphs.

######  Proposition 1.6.

Let $r\geq 3$ be an integer. For every nonminial $r$-graph $\mathcal{G}$ there
exists a finite family $\mathcal{F}$ of $r$-graphs such that for every integer
$n\in\mathbb{N}$ there exists a maximum $\mathcal{F}$-free $r$-graph on
$n$-vertices which is a blowup of $\mathcal{G}$.

Next, we introduce an operation motivated by Proposition 1.4. It shows that
for a certain class of $3$-graphs $\mathcal{G}$ we can produce a nonminimal
$3$-graph containing $\mathcal{G}$.

For a $3$-graph $\mathcal{G}$ and a pair of vertices $\\{u,v\\}\subset
V(\mathcal{G})$ the _neighborhood_ $N_{\mathcal{G}}(u,v)$ and _codegree_
$d_{\mathcal{G}}(u,v)$ of $\\{u,v\\}$ are defined as

$N_{\mathcal{G}}(u,v)=\\{w\in\mathcal{G}\colon\\{u,v,w\\}\in\mathcal{G}\\}\quad\text{and}\quad
d_{\mathcal{G}}(u,v)=|N_{\mathcal{G}}(u,v)|.$

We say $\mathcal{G}$ is _$2$ -covered_ if $d_{\mathcal{G}}(u,v)\geq 1$ for
every pair $\\{u,v\\}\subset V(\mathcal{G})$. For a vertex $u\in
V(\mathcal{G})$ the _link_ of $v$ is defined as

$L_{\mathcal{G}}(u)=\\{\\{v,w\\}\subset\mathcal{G}\colon\\{u,v,w\\}\in\mathcal{G}\\}.$

Vertices $u$ and $u^{\prime}$ in $\mathcal{G}$ are clones if
$L_{\mathcal{G}}(u)=L_{\mathcal{G}}(v)$.

######  Definition 1.7 (Crossed blowup).

Let $\mathcal{G}$ be a $3$-graph and $\\{v_{1},v_{2}\\}\subset\mathcal{G}$ be
a pair of vertices with $d(v_{1},v_{2})=k\geq 2$. Fix an ordering of vertices
in $N_{\mathcal{G}}(v_{1},v_{2})$, say
$N_{\mathcal{G}}(v_{1},v_{2})=\\{u_{1},\ldots,u_{k}\\}$. The crossed blowup
$\mathcal{G}\boxplus\\{v_{1},v_{2}\\}$ of $\mathcal{G}$ on $\\{v_{1},v_{2}\\}$
is defined as follows.

  1. (a)

Remove all edges containing the pair $\\{v_{1},v_{2}\\}$ from $\mathcal{G}$,

  2. (b)

add two new vertices $v_{1}^{\prime}$ and $v_{2}^{\prime}$, make
$v_{1}^{\prime}$ a clone of $v_{1}$ and $v_{2}^{\prime}$ a clone of $v_{2}$,

  3. (c)

for every $i\in[k-1]$ add the edge set
$\\{u_{i}v_{1}v_{2},u_{i}v_{1}v_{2}^{\prime},u_{i}v_{1}^{\prime}v_{2},u_{i}v_{1}^{\prime}v_{2}^{\prime}\\}$,
and for $i=k$ add the edge set
$\\{u_{k}v_{1}v_{1}^{\prime},u_{k}v_{1}v_{2}^{\prime},u_{k}v_{2}v_{1}^{\prime},u_{k}v_{2}v_{2}^{\prime}\\}$.

Remark. If in Step (c) we add the edge set
$\\{u_{k}v_{1}v_{2},u_{k}v_{1}v_{2}^{\prime},u_{k}v_{1}^{\prime}v_{2},u_{k}v_{1}^{\prime}v_{2}^{\prime}\\}$
instead of
$\\{u_{k}v_{1}v_{1}^{\prime},u_{k}v_{1}v_{2}^{\prime},u_{k}v_{2}v_{1}^{\prime},u_{k}v_{2}v_{2}^{\prime}\\}$,
then we obtain an ordinary blowup of $\mathcal{G}$.

$u_{1}$$u_{2}$$u_{3}$$v_{1}$$v_{2}$$u_{1}$$u_{2}$$u_{3}$$v_{1}$$v_{2}$$v^{\prime}_{1}$$v^{\prime}_{2}$
Figure 1: $\\{u_{1}v_{1}v_{2},u_{2}v_{1}v_{2},u_{3}v_{1}v_{2}\\}$ and
$\\{u_{1}v_{1}v_{2},u_{2}v_{1}v_{2},u_{3}v_{1}v_{2}\\}\boxplus\\{v_{1},v_{2}\\}$.
The link of red vertices is the red $K_{2,2}$, the link of the yellow vertex
is the yellow $K_{2,2}$. 34$3^{\prime}$$4^{\prime}$132412 Figure 2:
$K_{4}^{3}$ and $K_{4}^{3}\boxplus\\{3,4\\}$.

######  Definition 1.8.

Let $\mathcal{G}$ be a $3$-graph. A pair $\\{v_{1},v_{2}\\}\subset
V(\mathcal{G})$ is symmetric in $\mathcal{G}$ if

$L_{\mathcal{G}}(v_{1})-v_{2}=L_{\mathcal{G}}(v_{2})-v_{1}.$

The crossed blowup of a $3$-graph has the following properties.

######  Proposition 1.9.

Suppose that $\mathcal{G}$ is an $m$-vertex $3$-graph and
$\\{v_{1},v_{2}\\}\subset V(\mathcal{G})$ is a pair of vertices with
$d(v_{1},v_{2})\geq 2$. Then the following statements hold.

  1. (a)

The $3$-graph $\mathcal{G}$ is contained in
$\mathcal{G}\boxplus\\{v_{1},v_{2}\\}$ as an induced subgraph. In particular,
$\lambda(\mathcal{G})\leq\lambda(\mathcal{G}\boxplus\\{v_{1},v_{2}\\})$.

  2. (b)

The $3$-graph $\mathcal{G}\boxplus\\{v_{1},v_{2}\\}$ is $2$-covered iff
$\mathcal{G}$ is $2$-covered.

  3. (c)

If $\\{v_{1},v_{2}\\}$ is symmetric in $\mathcal{G}$, then
$\lambda(\mathcal{G}\boxplus\\{v_{1},v_{2}\\})=\lambda(\mathcal{G})$. If, in
addition, there exists $(x_{1},\ldots,x_{m})\in Z(\mathcal{G})$ with
$x_{1}+x_{2}>0$, then the set $Z(\mathcal{G}\boxplus\\{v_{1},v_{2}\\})$
contains a one-dimensional simplex (i.e. a nontrivial line segment).

Remarks.

  * •

It is easy to see that Proposition 1.9 (b) does not necessarily hold for the
ordinary blowup of $\mathcal{G}$.

  * •

The requirement that $\\{v_{1},v_{2}\\}$ is symmetric in Proposition 1.9 (c)
cannot be removed since some calculations show that $\lambda(C_{5}^{3})=1/25$
while $\lambda(C_{5}^{3}\boxplus\\{4,5\\})=4/81$, where
$C_{5}^{3}=\\{123,234,345,451,512\\}$.

23154$5^{\prime}$$4^{\prime}$23145 Figure 3: $C_{5}^{3}$ and
$C_{5}^{3}\boxplus\\{4,5\\}$.

Using Propositions 1.6 and 1.9 and some further argument we obtain the
following theorem.

######  Theorem 1.10.

Let $\mathcal{G}$ be a minimal $3$-graph. Suppose that
$\\{v_{1},v_{2}\\}\subset V(\mathcal{G})$ is symmetric in $\mathcal{G}$ and
$d(v_{1},v_{2})\geq 1$. Then there exists a finite family $\mathcal{F}$ of
$3$-graphs with $\xi(\mathcal{F})=\infty$ such that
$\pi(\mathcal{F})=6\lambda(\mathcal{G})$, and for every $n\in\mathbb{N}$ there
exists a maximum $\mathcal{F}$-free $3$-graph on $n$-vertices which is a
blowup of $\mathcal{G}$.

###  1.4 Feasible region

Theorem 1.3 has some interesting application to the so-called feasible region
of hypergraphs.

Given an $r$-graph $\mathcal{H}$ the _shadow_ of $\mathcal{H}$ is defined as

$\displaystyle\partial\mathcal{H}=\left\\{A\in\binom{V(\mathcal{H})}{r-1}\colon\text{there
is }B\in\mathcal{H}\text{ such that }A\subseteq B\right\\}.$

The _edge density_ of $\mathcal{H}$ is defined as
$\rho(\mathcal{H})=|\mathcal{H}|/\binom{v(\mathcal{H})}{r}$, and the _shadow
density_ of $\mathcal{H}$ is defined as
$\rho(\partial\mathcal{H})=|\partial\mathcal{H}|/\binom{v(\mathcal{H})}{r-1}$.

For a family $\mathcal{F}$ the _feasible region_ $\Omega(\mathcal{F})$ of
$\mathcal{F}$ is the set of points $(x,y)\in[0,1]^{2}$ such that there exists
a sequence of $\mathcal{F}$-free $r$-graphs
$\left(\mathcal{H}_{k}\right)_{k=1}^{\infty}$ with

$\lim_{k\to\infty}v(\mathcal{H}_{k})=\infty,\quad\lim_{k\to\infty}\rho(\partial\mathcal{H}_{k})=x,\quad\text{and}\quad\lim_{k\to\infty}\rho(\mathcal{H}_{k})=y.$

The feasible region unifies and generalizes many classical problems such as
the Kruskal–Katona theorem [17, 13] and the Turán problem. It was introduced
in [20] to understand the extremal properties of $\mathcal{F}$-free
hypergraphs beyond just the determination of $\pi(\mathcal{F})$. The general
shape of $\Omega(\mathcal{F})$ was analyzed in [20] as follows: For some
constant $c(\mathcal{F})\in[0,1]$ the projection to the first coordinate,

${\rm proj}\Omega(\mathcal{F})=\left\\{x\colon\text{there is $y\in[0,1]$ such
that $(x,y)\in\Omega(\mathcal{F})$}\right\\},$

is the interval $[0,c(\mathcal{F})]$ . Moreover, there is a left-continuous
almost everywhere differentiable function $g(\mathcal{F})\colon{\rm
proj}\Omega(\mathcal{F})\to[0,1]$ such that

$\Omega(\mathcal{F})=\bigl{\\{}(x,y)\in[0,c(\mathcal{F})]\times[0,1]\colon
0\leq y\leq g(\mathcal{F})(x)\bigr{\\}}\,.$

Let us call $g(\mathcal{F})$ the _feasible region function_ of $\mathcal{F}$.
It was shown in [20] that $g(\mathcal{F})$ is not necessarily continuous, and
in [18], it was shown that $g(\mathcal{F})$ can have infinitely many local
maxima even for some simple and natural families $\mathcal{F}$.

The stability number of $\mathcal{F}$ can give information about the number of
global maxima of $g(\mathcal{F})$ (e.g. see [23]). The family $\mathcal{M}$ of
triple systems from [21] for which $\xi(\mathcal{M})=2$ has the following
additional property: not only are the two near extremal constructions for
$\mathcal{M}$ far from each other in edit-distance, but the same is true of
their shadows. As a consequence, in addition to $\xi(\mathcal{M})=2$, the
function $g(\mathcal{M})$ has exactly two global maxima. Similarly, it was
proved in [23] that for the $t$-stable family $\mathcal{M}_{t}$ the function
$g(\mathcal{M}_{t})$ has exactly $t$ global maxima for every positive integer
$t$.

It was left as an open question in [23] whether there exists a finite family
$\mathcal{F}$ so that the function $g(\mathcal{F})$ has infinitely many global
maxima. Here we would like to remind the reader that even though there are
infinitely many extremal constructions for Turán’s tetrahedron conjecture (if
it is true), the shadow of all these constructions is complete. Hence, solving
Turán’s tetrahedron conjecture will not answer the question asked in [23].

Our next result shows that the same family $\mathcal{F}_{t}$ as in Theorem 1.3
has the property that $g(\mathcal{F}_{t})$ attains its maximum on a nontrivial
interval, thus giving a positive answer to the question in [23].

######  Theorem 1.11.

For every integer $t\geq 3$ we have
$\mathrm{proj}\Omega(\mathcal{F}_{t})=\left[0,\frac{t+1}{t+2}\right]$, and
$g(\mathcal{F}_{t},x)\leq{(t-2)(t-1)}/{t^{2}}$ for all
$x\in\mathrm{proj}\Omega(\mathcal{F}_{t})$. Moreover, if $t\geq 4$, then
$g(\mathcal{F}_{t},x)={(t-2)(t-1)}/{t^{2}}$ iff
$x\in\left[\frac{t-1}{t},\frac{t-1}{t}+\frac{1}{t^{2}}\right]$.

Remark. Fox (see [26]) asked whether there exists a finite family
$\mathcal{F}$ of $r$-graphs for some $r\geq 3$ such that the Turán density
$\pi(\mathcal{F})$ is a transcendental number. Though we did not answer his
question, Theorem 1.11 does imply that there exists a sequence of (near)
extremal $\mathcal{F}_{t}$-free $3$-graphs whose shadow densities approach a
transcendental number (because the interval
$\left[\frac{t-1}{t},\frac{t-1}{t}+\frac{1}{t^{2}}\right]$ contains a
transcendental number).

$1$$0$$y$$x$$\frac{(t-2)(t-1)}{t^{2}}$$\frac{t-1}{t}$$\frac{t-1}{t}+\frac{1}{t^{2}}$$\frac{t+1}{t+2}$$(1,1)$
Figure 4: The function $g(\mathcal{F}_{t})$ attains its maximum on the
interval $\left[\frac{t-1}{t},\frac{t-1}{t}+\frac{1}{t^{2}}\right]$.

The remainder of this paper is organized as follows. In Section 2 we introduce
some preliminary definitions and results. In Section 3 we prove Proposition
1.4. In Section 4 we prove Propositions 1.6 and 1.9 and Theorem 1.10. In
Section 5 we prove Theorem 1.3 (a), (b), and (c). In Section 6 we prove
Theorem 1.3 (d). In Section 7 we prove Theorem 1.11. The final section
conatins some concluding remarks.

##  2 Preliminaries

We present some definitions and useful results in this section.

Recall that the shadow of an $r$-graph $\mathcal{H}$ is

$\displaystyle\partial\mathcal{H}=\left\\{A\in\binom{V(\mathcal{H})}{r-1}\colon\text{there
is }B\in\mathcal{H}\text{ such that }A\subseteq B\right\\}.$

By setting $\partial_{1}\mathcal{H}=\partial\mathcal{H}$ for every $i\in[r-1]$
we define $\partial_{i}\mathcal{H}$ inductively as
$\partial_{i}\mathcal{H}=\partial\partial_{i-1}\mathcal{H}$. In particular,
$\partial_{r-2}\mathcal{H}$ is a graph.

Given an $r$-graph $\mathcal{H}$ and a vertex $v\in V(\mathcal{H})$ the
_neighborhood_ of $v$ is defined as

$N_{\mathcal{H}}(v)=\left\\{u\in V(\mathcal{H})\setminus\\{v\\}\colon\exists
E\in\mathcal{H}\text{ such that }\\{u,v\\}\subset E\right\\}.$

Recall that the _link_ of $v$ in $\mathcal{H}$ is
$L_{\mathcal{H}}(v)=\left\\{e\in\partial\mathcal{H}\colon
e\cup\\{v\\}\in\mathcal{H}\right\\}.$ The _degree_ of $v$ is
$d_{\mathcal{H}}(v)=|L_{\mathcal{H}}(v)|$. Denote by $\delta(\mathcal{H})$ and
$\Delta(\mathcal{H})$ the minimum degree and maximum degree of $\mathcal{H}$,
respectively. Recall that the neighborhood of $\\{u,v\\}\subset
V(\mathcal{H})$ in $\mathcal{H}$ is $N_{\mathcal{H}}(u,v)=\left\\{w\in
V(\mathcal{H})\colon\\{u,v,w\\}\in\mathcal{H}\right\\}.$ The codegree of
$\\{u,v\\}$ is $d_{\mathcal{H}}(u,v)=|N_{\mathcal{H}}(u,v)|$. Denote by
$\delta_{2}(\mathcal{H})$ and $\Delta_{2}(\mathcal{H})$ the minimum degree and
maximum codegree of $\mathcal{H}$, respectively. We will omit the subscript
$\mathcal{H}$ from our notations if it is clear from the context.

Let $\mathcal{G}$ be an $r$-graph with the vertex set $[m]$, and
$V_{1},\ldots,V_{m}$ be $m$ disjoint sets (each $V_{i}$ is allowed to be
empty). The blowup $\mathcal{G}[V_{1},\ldots,V_{m}]$ of $\mathcal{G}$ is
obtained from $\mathcal{G}$ by replacing each vertex $i$ with the set $V_{i}$
and replacing each edge $i_{1}\cdots i_{r}$ with the complete $r$-partite
$r$-graph with parts $V_{i_{1}},\ldots,V_{i_{r}}$.

For a hypergraph $\mathcal{G}$ the maximum number of edges in a blowup of
$\mathcal{G}$ is related to $\lambda(\mathcal{G})$ (e.g. see Frankl and Füredi
[10] or Keevash’s survey [14, Section 3]).

######  Lemma 2.1 ([12, 14]).

Suppose that $\mathcal{G}$ is an $r$-graph and $V_{1},\ldots,V_{m}$ are $m$
disjoint sets with $\sum_{i\in[m]}|V_{i}|=n$. Then
$|\mathcal{G}[V_{1},\ldots,V_{m}]|=p_{\mathcal{G}}\left(|V_{1}|/n,\ldots,|V_{m}|/n\right)n^{r}$.
In particular, $|\mathcal{G}[V_{1},\ldots,V_{m}]|\leq\lambda(G)n^{r}$.

Given an $r$-graph $F$ we say $\mathcal{H}$ is _$F$ -hom-free_ if there is no
homomorphism from $F$ to $\mathcal{H}$. This is equivalent to say that every
blowup of $\mathcal{H}$ is $F$-free. For a family $\mathcal{F}$ of $r$-graphs
we say $\mathcal{H}$ is _$\mathcal{F}$ -hom-free_ if it is $F$-hom-free for
all $F\in\mathcal{F}$. An easy observation is that if an $r$-graph $F$ is
$2$-covered, then $\mathcal{H}$ is $F$-free iff it is $F$-hom-free.

######  Definition 2.2 (Blowup-invariance).

A family $\mathcal{F}$ of $r$-graphs is blowup-invariant if every
$\mathcal{F}$-free $r$-graph is also $\mathcal{F}$-hom-free.

Let $\mathcal{H}$ be an $r$-graph and $\\{u,v\\}\subset V(\mathcal{H})$ be two
non-adjacent vertices (i.e., no edge contains both $u$ and $v$). We say $u$
and $v$ are _equivalent_ if $L_{\mathcal{H}}(u)=L_{\mathcal{H}}(v)$. Otherwise
we say they are _non-equivalent_. An equivalence class of $\mathcal{H}$ is a
maximal vertex set in which every pair of vertices are equivalent. We say
$\mathcal{H}$ is _symmetrized_ if it does not contain non-equivalent pairs of
vertices. In [24], the authors summarized the well known method of Zykov [31]
symmetrization for solving Turán problems into the following statement.

######  Theorem 2.3 (see e.g. [24]).

Suppose that $\mathcal{F}$ is a blowup-invariant family of $r$-graphs. If
$\mathfrak{H}$ denotes the class of all symmetrized $\mathcal{F}$-free
$r$-graphs, then ex$(n,\mathcal{F})=\mathfrak{h}(n)$ holds for every
$n\in\mathbb{N}^{+}$, where
$\mathfrak{h}(n)=\max\\{|\mathcal{H}|\colon\mathcal{H}\in\mathfrak{H}\text{
and }v(\mathcal{H})=n\\}$.

##  3 Multilinear polynomials

We prove Proposition 1.4 in this section. First, we need the following simple
lemma.

######  Lemma 3.1.

Suppose that $p(X_{1},\ldots,X_{m})=p_{1}+p_{2}(X_{i}+X_{j})+p_{3}X_{i}X_{j}$
is an $m$-variable multilinear polynomial that is symmetric with respect to
$X_{i}$ and $X_{j}$, and $p_{3}$ is nonnegative. Then for every
$(x_{1},\ldots,x_{m})\in Z(p)$ we have
$(x_{1},\ldots,x_{i-1},(x_{i}+x_{j})/2,x_{i+1},\ldots,x_{j-1},(x_{i}+x_{j})/2,x_{j+1},\ldots,x_{m})\in
Z(p)$. In particular,

$\max\\{p(y_{1},\ldots,y_{m})\colon(y_{1},\ldots,y_{m})\in\Delta_{m-1}\text{
and }y_{i}=y_{j}\\}=\lambda(p).$

###### Proof.

Using the AM-GM inequality we obtain

$\displaystyle
p(x_{1},\ldots,x_{i-1},\frac{x_{i}+x_{j}}{2},x_{i+1},\ldots,x_{j-1},\frac{x_{i}+x_{j}}{2},x_{j+1},\ldots,x_{m})$
$\displaystyle=p_{1}+p_{2}\left(\frac{x_{i}+x_{j}}{2}+\frac{x_{i}+x_{j}}{2}\right)+p_{3}\left(\frac{x_{i}+x_{j}}{2}\right)^{2}$
$\displaystyle\geq p_{1}+p_{2}(x_{i}+x_{j})+p_{3}x_{i}x_{j}=\lambda(p),$

where the last equality follows from our assumption that
$(x_{1},\ldots,x_{m})\in Z(p)$. By the definition of $\lambda(p)$, the
inequality above is actually an equality, so we have
$(x_{1},\ldots,x_{i-1},(x_{i}+x_{j})/2,x_{i+1},\ldots,x_{j-1},(x_{i}+x_{j})/2,x_{j+1},\ldots,x_{m})\in
Z(p)$.

Now we are ready to prove Proposition 1.4.

###### Proof of Proposition 1.4.

Let $p,p_{1},p_{2},p_{3},p_{4},p_{5},\hat{p}$ be polynomials that satisfy the
assumptions in Proposition 1.4. By symmetry, we may assume that
$\\{i,j\\}=\\{1,2\\}$. Let $\widehat{X}_{1}=X_{1}+X_{1}^{\prime}$ and
$\widehat{X}_{2}=X_{2}+X_{2}^{\prime}$. It follows from the AM-GM inequality
that

$\displaystyle\hat{p}(X_{1},X^{\prime}_{1},X_{2},X^{\prime}_{2},X_{3},\ldots,X_{m})$
$\displaystyle=p_{1}+p_{2}(X_{1}+X^{\prime}_{1}+X_{2}+X^{\prime}_{2})+p_{4}(X_{1}+X^{\prime}_{1})(X_{2}+X^{\prime}_{2})+p_{5}(X_{1}+X_{2})(X^{\prime}_{1}+X^{\prime}_{2})$
$\displaystyle\leq
p_{1}+p_{2}(\widehat{X}_{1}+\widehat{X}_{2})+p_{4}\left(\frac{\widehat{X}_{1}+\widehat{X}_{2}}{2}\right)^{2}+p_{5}\left(\frac{\widehat{X}_{1}+\widehat{X}_{2}}{2}\right)^{2}$
$\displaystyle=p_{1}+p_{2}(\widehat{X}_{1}+\widehat{X}_{2})+p_{3}\left(\frac{\widehat{X}_{1}+\widehat{X}_{2}}{2}\right)^{2}$
$\displaystyle=p((\widehat{X}_{1}+\widehat{X}_{2})/2,(\widehat{X}_{1}+\widehat{X}_{2})/2,X_{3},\ldots,X_{m}).$
(1)

This implies that $\lambda(\hat{p})\leq\lambda(p)$.

Let $\alpha\in[0,1]$ and

$\displaystyle\vec{y}=\alpha\cdot(\frac{x_{1}+x_{2}}{2},0,0,\frac{x_{1}+x_{2}}{2},x_{3},\ldots,x_{m})+(1-\alpha)\cdot(0,\frac{x_{1}+x_{2}}{2},\frac{x_{1}+x_{2}}{2},0,x_{3},\ldots,x_{m}).$

Then it follows from Equation (3) that

$\displaystyle\hat{p}(\vec{y})=p((x_{1}+x_{2})/2,(x_{1}+x_{2})/2,x_{3},\ldots,x_{m}).$

By Lemma 3.1, we have

$\displaystyle
p((x_{1}+x_{2})/2,(x_{1}+x_{2})/2,x_{3},\ldots,x_{m})=p(x_{1},x_{2},x_{3},\ldots,x_{m})=\lambda(p).$

Therefore, $\vec{y}\in Z(\hat{p})$.

##  4 Nonmininal hypergraphs

In this section, we prove results that were stated in Section 1.3.

###  4.1 Proof for Proposition 1.6

In this subsection we prove Proposition 1.6.

For every $r$-graph $\mathcal{G}$ let $\mathcal{F}_{\infty}(\mathcal{G})$ be
the (infinite) family of all $r$-graphs that are not $\mathcal{G}$-colorable,
i.e.

$\displaystyle\mathcal{F}_{\infty}(\mathcal{G})=\left\\{\text{$r$-graph
$F$}\colon\text{ and $F$ is not $\mathcal{G}$-colorable}\right\\}.$

For every positive integer $M$ define the family
$\mathcal{F}_{M}(\mathcal{G})$ of $r$-graphs as

$\displaystyle\mathcal{F}_{M}(\mathcal{G})=\left\\{F\in\mathcal{F}_{\infty}(\mathcal{G})\colon
v(F)\leq M\right\\}.$

It is clear that $\mathcal{F}_{M}(\mathcal{G})$ is nonempty if $M\geq
v(\mathcal{G})+1$ since it contains all $r$-graphs $F$ with at most $M$
vertices and $K_{v(\mathcal{G})+1}\subset\partial_{r-2}F$. It is also clear
from the definition that
$\mathcal{F}_{M}(\mathcal{G})\subset\mathcal{F}_{M^{\prime}}(\mathcal{G})$ for
all $M^{\prime}\geq M$.

It follows easily from the definition that every
$\mathcal{F}_{\infty}(\mathcal{G})$-free $r$-graph is $\mathcal{G}$-colorable.
In particular, every maximum $\mathcal{F}_{\infty}(\mathcal{G})$-free
$r$-graph on $n$ vertices is $\mathcal{G}$-colorable. One of the main result
in [26] implies the following compactness result. For every minimum $r$-graph
$\mathcal{G}$ there exists a constant $M_{0}\in\mathbb{N}$ such that every
maximum $\mathcal{F}_{\infty}(\mathcal{G})$-free $r$-graph on $n$ vertices is
$\mathcal{G}$-colorable. Proposition 1.6 actually shows that a similar
compactness result holds for all $r$-graphs $\mathcal{G}$.

The following simple lemma is a special case of Lemma 8 in [26].

######  Lemma 4.1 ([26]).

For every $r$-graph $\mathcal{G}$ and every positive integer $M$ the family
$\mathcal{F}_{M}(\mathcal{G})$ is blowup-invariant.

The following lemma extends Observation 2.3 (a) in [19].

######  Lemma 4.2.

Let $\mathcal{G}$ be an $r$-graph. Let $m$ denote the order of a maximum
complete subgraph in $\partial_{r-2}\mathcal{G}$ and let
$M=m+1+(r-2)\binom{m+1}{2}$. Suppose that an $r$-graph $\mathcal{H}$ is
$\mathcal{F}_{M}(\mathcal{G})$-free. Then $\partial_{r-2}\mathcal{H}$ is
$K_{m+1}$-free.

###### Proof.

Suppose to the contrary that there exists a set $C\subset V(\mathcal{H})$ of
size $m+1$ such that the induced subgraph of $\partial\mathcal{H}$ on $C$ is
complete. For every pair $\\{u,v\\}\subset C$ let $E_{u,v}\in\mathcal{H}$ be
an edge that contains $\\{u,v\\}$. Let $F=\\{E_{u,v}\colon\\{u,v\\}\subset
C\\}$. It is clear that $v(F)\leq m+1+(r-2)\binom{m+1}{2}=M$. So it follows
from our assumption that $F$ is $\mathcal{G}$-colorable. In other words, there
exists a homomorphism $\phi\colon V(F)\to V(\mathcal{G})$ from $F$ to
$\mathcal{G}$. Since every pair $\\{u,v\\}\subset C$ is contained in an edge
of $F$, we have $\phi(u)\neq\phi(v)$. Therefore, $|\phi(C)|=|C|=m+1$. However,
$u\sim v$ in $\partial_{r-2}F$ implies that $\phi(u)\sim\phi(v)$ in
$\partial_{r-2}\mathcal{G}$, which means that the induced subgraph of
$\partial_{r-2}\mathcal{G}$ on $\phi(C)$ is complete, a contradiction.

We will prove the following statement which implies Proposition 1.6.

######  Proposition 4.3.

Suppose that $r\geq 3$, $\mathcal{G}$ is an $r$-graph, and
$M=v(\mathcal{G})+1+(r-2)\binom{v(\mathcal{G})+1}{2}$. Then
$\mathrm{ex}(n,\mathcal{F}_{M}(\mathcal{G}))=\max\\{|\mathcal{H}|\colon\text{$v(\mathcal{H})=n$
and $\mathcal{H}$ is $\mathcal{G}$-colorable}\\}$ for every $n\in\mathbb{N}$.

###### Proof.

Let $\mathcal{G}$ be an $r$-graph and let $m=v(\mathcal{G})$. Let
$\mathfrak{G}$ be the collection of all $\mathcal{G}$-colorable $r$-graphs.
Define
$\mathfrak{g}(n)=\max\\{|\mathcal{H}|\colon\mathcal{H}\in\mathfrak{H}\text{
and }v(\mathcal{H})=n\\}$. Let $M=m+1+(r-2)\binom{m+1}{2}$ and
$\mathcal{F}=\mathcal{F}_{M}(\mathcal{G})$. It follows from Lemma 4.1 that
$\mathcal{F}$ is blowup-invariant. Therefore, by Theorem 2.3, it suffices to
prove the following claim.

######  Claim 4.4.

Every symmetrized $\mathcal{F}$-free $r$-graph is contained in $\mathfrak{G}$.

###### Proof.

Let $\mathcal{H}$ be a symmetrized $\mathcal{F}$-free $r$-graph. Let $C\subset
V(\mathcal{H})$ be a set that contains exactly one vertex from each
equivalence class of $\mathcal{H}$ and let $\mathcal{T}$ denote the induced
subgraph of $\mathcal{H}$ on $C$. It is clear from the definition of
symmetrized hypergraphs that $\mathcal{H}$ is a blowup of $\mathcal{T}$. Since
$\partial_{r-2}\mathcal{T}\cong K_{|C|}$, it follows from Lemma 4.2 that
$|C|\leq m$. Since $\mathcal{T}\not\in\mathcal{F}$, we know that $\mathcal{T}$
is $\mathcal{G}$-colorable. This implies that $\mathcal{H}$ is also
$\mathcal{G}$-colorable. Therefore, $\mathcal{H}\in\mathfrak{G}$.

This completes the proof of Proposition 4.3.

###  4.2 Proofs for Proposition 1.9 and Theorem 1.10

In this subsection we prove Proposition 1.9 and Theorem 1.10.

Let us assume that the vertex set of $\mathcal{G}$ is
$\\{v_{1},v_{2},\ldots,v_{m}\\}$. Let $v_{1}^{\prime},v_{2}^{\prime}$ denote
the clones of $v_{1},v_{2}$ in $\mathcal{G}\boxplus\\{v_{1},v_{2}\\}$,
respectively. Let $U_{1}=\\{v_{1},v_{2}^{\prime},v_{3},\ldots,v_{m}\\}$ and
$U_{2}=\\{v_{1}^{\prime},v_{2},v_{3},\ldots,v_{m}\\}$. It is easy to see from
the definition that the induced subgraph of
$\mathcal{G}\boxplus\\{v_{1},v_{2}\\}$ on $U_{1}$ and $U_{2}$ are both
isomorphic to $\mathcal{G}$, this proves (a). Statement (b) follows easily
from the definition of crossed blowup. So we may focus on (c).

We will prove the following statement which implies Proposition 1.9 (c).

######  Proposition 4.5.

Suppose that $\mathcal{G}$ is an $m$-vertex $3$-graph and
$\\{v_{1},v_{2}\\}\subset\mathcal{G}$ is a pair of vertices with
$d(v_{1},v_{2})\geq 2$. Suppose that $\\{v_{1},v_{2}\\}$ is symmetric in
$\mathcal{G}$. Then
$\lambda(\mathcal{G}\boxplus\\{v_{1},v_{2}\\})=\lambda(\mathcal{G})$.
Moreover, for every $(z_{1},\ldots,z_{m})\in Z(\mathcal{G})$ we have

$L\left((\bar{z},0,0,\bar{z},z_{3},\ldots,z_{m}),(0,\bar{z},\bar{z},0,z_{3},\ldots,z_{m})\right)\subset
Z(\mathcal{G}\boxplus\\{v_{1},v_{2}\\}),$

where $\bar{z}=(z_{1}+z_{2})/2$.

###### Proof.

Let $k=d(v_{1},v_{2})$ and assume that
$N(v_{1},v_{2})=\\{v_{i_{1}},\ldots,v_{i_{k}}\\}$. Let
$W=\\{v_{3},\ldots,v_{m}\\}$. Define polynomials $p_{1},\ldots,p_{5}$ as

$\displaystyle p_{1}$
$\displaystyle=\sum_{v_{i}v_{j}v_{k}\in\mathcal{G}[W]}X_{i}X_{j}X_{k},$
$\displaystyle p_{2}$ $\displaystyle=\sum_{v_{i}v_{j}\in
L_{\mathcal{G}}(v_{1})[W]}X_{i}X_{j}=\sum_{v_{i}v_{j}\in
L_{\mathcal{G}}(v_{2})[W]}X_{i}X_{j},$ $\displaystyle p_{3}$
$\displaystyle=X_{i_{1}}+\cdots+X_{i_{k}},\quad
p_{4}=X_{i_{1}}+\cdots+X_{i_{k-1}},\quad\text{and}\quad p_{5}=X_{k}.$

It is easy to see that
$p_{\mathcal{G}}(X_{1},\ldots,X_{m})=p_{1}+p_{2}(X_{1}+X_{2})+p_{3}X_{1}X_{2}$.
On the other hand, it follows from the definition of crossed blowup that

$\displaystyle
p_{\mathcal{G}\boxplus\\{v_{1},v_{2}\\}}(X_{1},X_{1}^{\prime},X_{2},X_{2}^{\prime},X_{3}\ldots,X_{m})$
$\displaystyle=p_{1}+p_{2}(X_{1}+X_{2}+X_{1}^{\prime}+X_{2}^{\prime})+p_{4}(X_{1}+X_{1}^{\prime})(X_{2}+X_{2}^{\prime})+p_{5}(X_{1}+X_{2})(X_{1}^{\prime}+X_{2}^{\prime}).$

So by Proposition 1.4 we have

$L\left((\bar{z},0,0,\bar{z},z_{3},\ldots,z_{m}),(0,\bar{z},\bar{z},0,z_{3},\ldots,z_{m})\right)\subset
Z(\mathcal{G}\boxplus\\{v_{1},v_{2}\\}).$

Now we are ready to prove Theorem 1.10.

###### Proof of Theorem 1.10.

If $d_{\mathcal{G}}(v_{1},v_{2})\geq 2$, then we let
$\mathcal{G}^{\prime}=\mathcal{G}\boxplus\\{v_{1},v_{2}\\}$, and it follows
from Proposition 1.9 (c) that
$\lambda(\mathcal{G}^{\prime})=\lambda(\mathcal{G})$.

If $d_{\mathcal{G}}(v_{1},v_{2})=1$, then we let
$\\{w\\}=N_{\mathcal{G}}(v_{1},v_{2})$ and let $\mathcal{G}^{\prime}$ be
obtained as follows. First, we take two vertex-disjoint copies of
$\mathcal{G}$ and identify them on the set $V(\mathcal{G})\setminus\\{w\\}$
(i.e. we blowup $w$ into two vertices). Denote by $\mathcal{G}^{2}$ the
resulting $3$-graph. For example, if $\mathcal{G}=\\{125,345\\}$ and
$\\{v_{1},v_{2}\\}=\\{1,2\\}$, then $\mathcal{G}^{2}=\\{125,345,126,346\\}$.
Let $\mathcal{G}^{\prime}=\mathcal{G}^{2}\boxplus\\{v_{1},v_{2}\\}$. Since
$\mathcal{G}^{2}$ is $\mathcal{G}$-colorable and
$\mathcal{G}\subset\mathcal{G}^{2}$, we have
$\lambda(\mathcal{G}^{2})=\lambda(\mathcal{G})$. Notice that
$\\{v_{1},v_{2}\\}$ is still symmetric in $\mathcal{G}^{2}$, so it follows
from Proposition 1.9 (c) that
$\lambda(\mathcal{G}^{\prime})=\lambda(\mathcal{G}^{2})=\lambda(\mathcal{G})$.

Let $m=v(\mathcal{G}^{\prime})$ and $M=m+1+(r-2)\binom{m+1}{2}$. Let
$\mathcal{F}=\mathcal{F}_{M}(\mathcal{G}^{\prime})$. It follows from
Proposition 4.3 that
$\mathrm{ex}(n,\mathcal{F})=\max\\{|\mathcal{H}|\colon\text{$v(\mathcal{H})=n$
and $\mathcal{H}$ is $\mathcal{G}^{\prime}$-colorable}\\}$. Then by Lemma 2.1,
we have $\pi(\mathcal{F})\leq
6\lambda(\mathcal{G}^{\prime})=6\lambda(\mathcal{G})$. The converse of this
inequality follows from the fact that every blowup of $\mathcal{G}^{\prime}$
is $\mathcal{F}$-free. Therefore, we have
$\pi(\mathcal{F})=6\lambda(\mathcal{G})$.

Now we prove that $\xi(\mathcal{F})=\infty$. Suppose to the contrary that
$\xi(\mathcal{F})=t$ for some $t\in\mathbb{N}^{+}$. For every $n\in\mathbb{N}$
let $\mathcal{S}_{1}(n),\ldots,\mathcal{S}_{t}(n)$ be the $n$-vertex
$3$-graphs that witness the $t$-stability of $\mathcal{F}$. For every
$i\in[t]$ and $n\in\mathbb{N}$ let
$\rho_{i,n}=\rho(\mathcal{G}^{\prime},\mathcal{S}_{i}(n))=N(\mathcal{G}^{\prime},\mathcal{S}_{i}(n))/\binom{n}{m}$
, where $N(\mathcal{G}^{\prime},\mathcal{S}_{i}(n))$ is the number of copies
of $\mathcal{G}^{\prime}$ in $\mathcal{S}_{i}(n)$.

We will get a contradiction by first showing that for all sufficiently large
$n$ there exists a blowup $\widehat{\mathcal{G}}$ of $\mathcal{G}$ on $n$
vertices whose edge density is close to $\pi(\mathcal{F})$ but whose shadow
density is far from $\rho_{i,n}$ for every $i\in[t]$. Then we argue that since
every shadow edge is contained $\Omega(n)$ edges in $\widehat{\mathcal{G}}$,
the edit-distance of $\widehat{\mathcal{G}}$ and $\mathcal{S}_{i}(n)$ is
$\Omega(n^{3})$ for all $i\in[t]$. This contradicts the definition of
$t$-stable.

Notice that $v(\mathcal{G})=m-2$ if $d_{\mathcal{G}}(v_{1},v_{2})\geq 2$ and
$v(\mathcal{G}^{2})=m-2$ if $d_{\mathcal{G}}(v_{1},v_{2})=1$. Let
$(z_{1},z_{2},z_{3},\ldots,z_{m-2})\in Z(\mathcal{G})$ (or
$Z(\mathcal{G}^{2})$ if $d_{\mathcal{G}}(v_{1},v_{2})=1$) be a vector such
that $\zeta:=\min\\{z_{1},z_{2},z_{3},\ldots,z_{m-2}\\}$ is maximized. By
Lemma 3.1, we may assume that $z_{1}=z_{2}$ since otherwise we can replace
$z_{1}$ and $z_{2}$ by $(z_{1}+z_{2})/2$.

######  Claim 4.6.

We have $\zeta>0$.

###### Proof.

If $d(v_{1},v_{2})\geq 2$, then the minimality of $\mathcal{G}$ implies that
every vector in $Z(\mathcal{G})$ has only positive coordinate. Therefore,
$\zeta>0$.

Suppose that $d(v_{1},v_{2})=1$. Without loss of generality let us assume that
$N_{\mathcal{G}}(v_{1},v_{2})=\\{v_{3}\\}$ and
$N_{\mathcal{G}^{2}}(v_{1},v_{2})=\\{v_{3},v_{4}\\}$. Since $v_{4}$ is a clone
of $v_{3}$ in $\mathcal{G}^{2}$, $(z_{1},z_{2},z_{3},z_{4},\ldots,z_{m-2})\in
Z(\mathcal{G}^{2})$ implies that
$(z_{1},z_{2},(z_{3}+z_{4})/2,(z_{3}+z_{4})/2,\ldots,z_{m-2})\in
Z(\mathcal{G}^{2})$. For the same reason,
$(z_{1},z_{2},z_{3},z_{4},\ldots,z_{m-2})\in Z(\mathcal{G}^{2})$ implies that
$(z_{1},z_{2},z_{3}+z_{4},z_{5},\ldots,z_{m-2})\in Z(\mathcal{G})$. The
minimality of $\mathcal{G}$ implies that each coordinate of
$(z_{1},z_{2},z_{3}+z_{4},z_{5},\ldots,z_{m-2})$ is positive. Therefore, every
coordinate in $(z_{1},z_{2},(z_{3}+z_{4})/2,(z_{3}+z_{4})/2,\ldots,z_{m-2})$
is positive, and hence, $\zeta>0$.

Let
$\vec{x}_{\alpha}=\alpha\cdot(z_{1},0,0,z_{2},z_{3},\ldots,z_{m-2})+(1-\alpha)\cdot(0,z_{1},z_{2},0,z_{3},\ldots,z_{m-2})$
for $\alpha\in[0,1]$. Let
$\widehat{\mathcal{G}}_{\alpha}(n)=\mathcal{G}^{\prime}[V_{1},V_{1}^{\prime},V_{2},V_{2}^{\prime},V_{3},\cdots,V_{m-2}]$
be a blowup of $\mathcal{G}^{\prime}$, where $|V_{1}|=\lfloor\alpha
z_{1}n\rfloor$, $|V_{1}^{\prime}|=\lfloor(1-\alpha)z_{1}n\rfloor$,
$|V_{2}|=\lfloor\alpha z_{2}n\rfloor$,
$|V_{2}^{\prime}|=\lfloor(1-\alpha)z_{2}n\rfloor$, and $|V_{i}|=\lfloor
z_{i}n\rfloor$ for $i\in[3,m-2]$. Let $W=\\{v_{3},\ldots,v_{m-2}\\}$. Then

$\displaystyle|\partial\widehat{\mathcal{G}}_{\alpha}(n)|$
$\displaystyle=\sum_{v_{i}v_{j}\in\partial\mathcal{G}\cap\binom{W}{2}}|V_{i}||V_{j}|+\sum_{v_{i}\in
N_{\mathcal{G}}(v_{1})}|V_{i}|\left(|V_{1}|+|V_{1}|^{\prime}\right)+\sum_{v_{i}\in
N_{\mathcal{G}}(v_{2})}|V_{i}|\left(|V_{2}|+|V_{2}|^{\prime}\right)$
$\displaystyle\quad+\left(|V_{1}|+|V_{1}^{\prime}|\right)\left(|V_{2}|+|V_{2}^{\prime}|\right)+|V_{1}||V_{1}^{\prime}|+|V_{2}||V_{2}^{\prime}|.$

Taking the limit we obtain

$\displaystyle\lim_{n\to\infty}\rho\left(\partial\widehat{\mathcal{G}}_{\alpha}(n)\right)$
$\displaystyle=2\alpha(1-\alpha)(z_{1}+z_{2})+2C,$

where

$\displaystyle C$
$\displaystyle=\sum_{v_{i}v_{j}\in\partial\mathcal{G}\cap\binom{W}{2}}z_{i}z_{j}+\sum_{v_{i}\in
N_{\mathcal{G}}(v_{1})}z_{i}z_{1}+\sum_{v_{i}\in
N_{\mathcal{G}}(v_{2})}z_{i}z_{2}+z_{1}z_{2}$

is independent of $\alpha$.

For $i\in[t+1]$ let $\alpha_{i}=\frac{i}{2(t+1)}$. Since $z_{1}+z_{2}>0$ and
$\alpha(1-\alpha)$ is increasing in $\alpha$ for $\alpha\in[0,1/2]$, there
exists $\epsilon>0$ and $N_{0}$ such that

$\displaystyle\left|\partial\widehat{\mathcal{G}}_{\alpha_{j}}(n)\right|-\left|\partial\widehat{\mathcal{G}}_{\alpha_{i}}(n)\right|>\frac{6\epsilon
n^{2}}{\zeta}$

for all $1\leq i<j\leq t+1$. Fix such an $\epsilon>0$. By the definition of
$t$-stable there exists $\delta=\delta(\epsilon)$ and $N_{1}=N_{1}(\epsilon)$
such that every $n$-vertex $\mathcal{F}$-free $3$-graph $\mathcal{H}$ with
$|\mathcal{H}|\geq(1-\delta)\mathrm{ex}(n,\mathcal{F})$, satisfies
$|\mathcal{H}\triangle\mathcal{S}_{i}(n)|\leq\epsilon n^{3}$ for some
$i\in[t]$. Since
$\lim_{n\to\infty}\rho\left(\widehat{\mathcal{G}}_{\alpha}(n)\right)=\pi(\mathcal{F})$,
there exists $N_{2}$ such that
$\left|\widehat{\mathcal{G}}_{\alpha}(n)\right|\geq(1-\delta)\mathrm{ex}(n,\mathcal{F})$
for all $\alpha\in[0,1]$ and $n\geq N_{2}$. Therefore, for every $j\in[t+1]$
there exists $i\in[t]$ such that
$|\widehat{\mathcal{G}}_{\alpha_{j}}(n)\triangle\mathcal{S}_{i}(n)|\leq\epsilon
n^{3}$ for all $n\geq\max\\{N_{0},N_{1},N_{2}\\}$. By the Pigeonhole
principle, there exists a pair $\\{j,k\\}$ such that
$|\widehat{\mathcal{G}}_{\alpha_{j}}(n)\triangle\mathcal{S}_{i}(n)|\leq\epsilon
n^{3}$ and
$|\widehat{\mathcal{G}}_{\alpha_{k}}(n)\triangle\mathcal{S}_{i}(n)|\leq\epsilon
n^{3}$. By the triangle inequality, we have
$|\widehat{\mathcal{G}}_{\alpha_{j}}(n)\triangle\widehat{\mathcal{G}}_{\alpha_{k}}(n)|\leq
2\epsilon n^{3}$.

Without loss of generality we may assume that $\alpha_{j}<\alpha_{k}$. Observe
that every edge
$e\in\partial\widehat{\mathcal{G}}_{\alpha_{j}}(n)\triangle\partial\widehat{\mathcal{G}}_{\alpha_{k}}(n)$
is contained in the set $V_{1}\cup V_{1}^{\prime}\cup V_{2}\cup
V_{2}^{\prime}$. Let $\\{\ell_{1},\ell_{2}\\}\subset[3,m-2]$ be the pair such
that $N_{\mathcal{G}^{2}}=\\{\ell_{1},\ell_{2}\\}$. Then we have
$N_{\widehat{\mathcal{G}}_{\alpha}(n)}(e)\geq\min\\{|V_{\ell_{1}}|,|V_{\ell_{2}}|\\}\geq\lfloor\zeta
n\rfloor>\zeta n/2$. Therefore, in order to transform
$\widehat{\mathcal{G}}_{\alpha_{k}}(n)$ into
$\widehat{\mathcal{G}}_{\alpha_{k}}(n)$ we need to remove at least

$\displaystyle\left(|\partial\widehat{\mathcal{G}}_{\alpha_{k}}(n)|-|\partial\widehat{\mathcal{G}}_{\alpha_{j}}(n)|\right)\frac{\zeta
n}{2}>\frac{6\epsilon n^{2}}{\zeta}\frac{\zeta n}{2}>2\epsilon n^{3}$

edges, a contradiction. Therefore, $\xi(\mathcal{F})=\infty$.

##  5 Proof of Theorem 1.3 (a), (b), and (c)

In this section we prove Theorem 1.3 (a), (b), and (c). First let us define
$\Gamma_{t}$ and $\mathcal{F}_{t}$ that were mentioned in Theorem 1.3. For
convenience, we will use $t+2$ instead $t$ in the rest of this paper.

######  Definition 5.1.

Let $t\geq 1$ be an integer.

  1. (a)

Let

$\displaystyle\Gamma_{t+2}=\begin{cases}\\{134,234\\}\boxplus\\{3,4\\}&\text{if
}t=1,\\\ K_{t+2}^{3}\boxplus\\{t+1,t+2\\}&\text{if }t\geq 2.\end{cases}$

  2. (b)

Let $\mathfrak{\Gamma}_{t+2}$ be the collection of all
$\Gamma_{t+2}$-colorable $3$-graphs.

  3. (c)

Let $\gamma_{t+2}(n)=\max\\{|\mathcal{H}|\colon v(\mathcal{H})=n\text{ and
}\mathcal{H}\in\mathfrak{\Gamma}_{t+2}\\}$.

  4. (d)

Let $\mathcal{F}_{t+2}=\left\\{F\colon v(F)\leq 4(t+4)^{2}\text{ and
}F\not\in\mathfrak{\Gamma}_{t+2}\right\\}$.

Remark. In the rest of the paper, we always assume that for $t\geq 2$ the
vertex set of $\Gamma_{t+2}$ is $[t+4]$, and $t+3,t+4$ are clones of
$t+1,t+2$, respectively.

It follows from Proposition 1.9 and Lemma 2.1 that
$\gamma_{t+2}(n)\sim\lambda(K_{t+2}^{3})n^{3}=\frac{t(t+1)}{6(t+2)^{2}}n^{3}$
(for $t=1$ we also used $\lambda(\\{134,234\\})=\lambda(K_{3}^{3})$).

Theorem 1.3 (a) follows easily from Proposition 1.6. Theorem 1.3 (c) follows
easily from Theorem 1.10. So we just need to prove Theorem 1.3 (b).

###### Proof of Theorem 1.3 (b).

Let $t\geq 2$ and $n$ be an integer satisfying $(t+2)\mid n$. It is easy to
see that $\mathrm{ex}(n,\mathcal{F}_{t+2})=\frac{t(t+1)}{6(t+2)^{2}}n^{3}$.
Let $\mathcal{H}=\Gamma_{t+2}[V_{1},\cdots,V_{t+4}]$ be a blowup of
$\Gamma_{t+2}$ with $|V_{1}|=\cdots=|V_{t}|=\frac{n}{t+2}$,
$|V_{t+1}|=|V_{t+4}|=\frac{\alpha n}{t+2}$, and
$|V_{t+2}|=|V_{t+3}|=\frac{(1-\alpha)n}{t+2}$, where $\alpha\in[0,1/2]$
satisfies that $\frac{\alpha n}{t+2}\in\mathbb{N}$. It is easy to see that
$|\mathcal{H}|=\frac{t(t+1)}{6(t+2)^{2}}n^{3}$. So it suffices to show that
the set $S=\left\\{\alpha\in[0,1/2]\colon\frac{\alpha
n}{t+2}\in\mathbb{N}\right\\}$ has size at least $\frac{n}{2(t+2)}$. Indeed,
suppose that $\alpha=\frac{p}{q}\in[0,1/2]$, where $p\leq q/2$ are integers
that are coprime. Notice that $\frac{p}{q}\frac{n}{t+2}\in\mathbb{N}$ if
$q\mid\frac{n}{t+2}$. Since $p$ is coprime with $q$ iff $q-p$ is coprime with
$q$, we have $|\\{p\colon(p,q)=1,\ p\leq q/2\\}|\geq\varphi(q)/2$, where
$\varphi(q)$ is the Euler totient function that denotes the number of positive
integers $p\leq q$ that are coprime with $q$. Therefore,
$|S|\geq\frac{1}{2}\sum_{q\mid\frac{n}{t+2}}\varphi(q)$. It follows from a
well known result of Gauss that
$\sum_{q\mid\frac{n}{t+2}}\varphi(q)=\frac{n}{t+2}$. Therefore,
$|S|\geq\frac{n}{2(t+2)}$. This implies that there are at least
$\frac{n}{2(t+2)}$ nonisomorphic extremal $\mathcal{F}_{t}$-free $3$-graphs on
$n$ vertices. The proof for the case $t=1$ is similar, so we omit it here.

##  6 Stability

###  6.1 Preparations

In this section we present some useful theorems and lemmas that will be used
later in the proof of Theorem 1.3 (d).

######  Definition 6.1 (Vertex-extendibility).

Let $\mathcal{F}$ be a family of $r$-graphs and let $\mathfrak{H}$ be a class
of $\mathcal{F}$-free $r$-graphs. We say that $\mathcal{F}$ is _vertex-
extendable_ with respect to $\mathfrak{H}$ if there exist $\zeta>0$ and
$N_{0}\in\mathbb{N}$ such that for every $\mathcal{F}$-free $r$-graph
$\mathcal{H}$ on $n\geq N_{0}$ vertices satisfying
$\delta(\mathcal{H})\geq\bigl{(}\pi(\mathcal{F})/(r-1)!-\zeta\bigr{)}n^{r-1}$
the following holds: if $\mathcal{H}-v$ is a subgraph of a member of
$\mathfrak{H}$ for some vertex $v\in V(\mathcal{H})$, then $\mathcal{H}$ is a
subgraph of a member of $\mathfrak{H}$ as well.

In [24], the authors developed a machinery that reduces the proof of stability
of certain families $\mathcal{F}$ to the simpler question of checking that an
$\mathcal{F}$-free hypergraph $\mathcal{H}$ with large minimum degree is
vertex-extendable.

######  Theorem 6.2 ([24]).

Suppose that $\mathcal{F}$ is a blowup-invariant nondegenerate family of
$r$-graphs and that $\mathfrak{H}$ is a hereditary class of $\mathcal{F}$-free
$r$-graphs. If $\mathfrak{H}$ contains all symmetrized $\mathcal{F}$-free
$r$-graphs and $\mathcal{F}$ is vertex-extendable with respect to
$\mathfrak{H}$, then the following statement holds. There exist $\epsilon>0$
and $N_{0}$ such that every $\mathcal{F}$-free $r$-graph on $n\geq N_{0}$
vertices with minimum degree at least
$\left(\pi(\mathcal{F})/(r-1)!-\epsilon\right)n^{r-1}$ is contained in
$\mathfrak{H}$.

The following lemma will be used extensively in the proof of Theorem 1.3 (d).

######  Lemma 6.3 (see e.g. [23]).

Fix a real $\eta\in(0,1)$ and integers $m,n\geq 1$. Let $\mathcal{G}$ be a
$3$-graph with vertex set $[m]$ and let $\mathcal{H}$ be a further $3$-graph
with $v(\mathcal{H})=n$. Consider a vertex partition
$V(\mathcal{H})=\bigcup_{i\in[m]}V_{i}$ and the associated blow-up
$\widehat{\mathcal{G}}=\mathcal{G}[V_{1},\ldots,V_{m}]$ of $\mathcal{G}$. If
two sets $T\subseteq[m]$ and $S\subseteq\bigcup_{j\not\in T}V_{j}$ have the
properties

  1. (a)

$|V_{j}|\geq(|S|+1)|T|\eta^{1/3}n$ for all $j\in T$,

  2. (b)

$|\mathcal{H}[V_{j_{1}},V_{j_{2}},V_{j_{3}}]|\geq|\widehat{\mathcal{G}}[V_{j_{1}},V_{j_{2}},V_{j_{3}}]|-\eta
n^{3}$ for all $\\{j_{1},j_{2},j_{3}\\}\in\binom{T}{3}$, and

  3. (c)

$|L_{\mathcal{H}}(v)[V_{j_{1}},V_{j_{2}}]|\geq|L_{\widehat{\mathcal{G}}}(v)[V_{j_{1}},V_{j_{2}}]|-\eta
n^{2}$ for all $v\in S$ and $\\{j_{1},j_{2}\\}\in\binom{T}{2}$,

then there exists a selection of vertices $u_{j}\in V_{j}$ for all $j\in[T]$
such that $U=\\{u_{j}\colon j\in T\\}$ satisfies
$\widehat{\mathcal{G}}[U]\subseteq\mathcal{H}[U]$ and
$L_{\widehat{\mathcal{G}}}(v)[U]\subseteq L_{\mathcal{H}}(v)[U]$ for all $v\in
S$. In particular, if $\mathcal{H}\subseteq\widehat{\mathcal{G}}$, then
$\widehat{\mathcal{G}}[U]=\mathcal{H}[U]$ and
$L_{\widehat{\mathcal{G}}}(v)[U]=L_{\mathcal{H}}(v)[U]$ for all $v\in S$.

Next we prove some basic properties about $\Gamma_{t+2}$.

######  Observation 6.4.

The following statements hold.

  1. (a)

If a set $U\subset[t+4]$ satisfies that $\Gamma_{t+2}[U]\cong K_{t+2}^{3}$,
then either $U=[t]\cup\\{t+1,t+4\\}$ or $U=[t]\cup\\{t+2,t+3\\}$.

  2. (b)

We have $L_{\Gamma_{t+2}}(1)\cong\cdots\cong L_{\Gamma_{t+2}}(t)$, and
$L_{\Gamma_{t+2}}(t+1)\cong\cdots\cong L_{\Gamma_{t+2}}(t+4).$

  3. (c)

We have

$\displaystyle d_{\Gamma_{t+2}}(i,j)=\begin{cases}t+2&\text{if
}\\{i,j\\}\in\binom{[t]}{2},\\\ t+1&\text{if }i\in[t]\text{ and
}j\in[t+1,t+4],\\\ t&\text{if
}\\{i,j\\}\in\\{\\{t+1,t+4\\},\\{t+2,t+3\\}\\},\\\ t-1&\text{if
}\\{i,j\\}\in\\{\\{t+1,t+3\\},\\{t+2,t+4\\}\\},\\\ 1&\text{if
}\\{i,j\\}\in\\{\\{t+1,t+2\\},\\{t+3,t+4\\}\\}.\end{cases}$

Using Observation 6.4 (a) we prove the following lemma.

######  Lemma 6.5.

Suppose that $\mathcal{G}$ is a blowup of $\Gamma_{t+2}$ and
$U,U^{\prime}\subset V(\mathcal{G})$ are two vertex sets of size $t+2$ with
$|U\cap U^{\prime}|=t+1$. If $\mathcal{G}[U]\cong\mathcal{G}[U^{\prime}]\cong
K_{t+2}^{3}$, then the set $U\triangle U^{\prime}$ is not contained in any
edge of $\mathcal{G}$.

###### Proof.

Suppose that $U=\\{u_{1},\ldots,u_{t+1},u\\}$ and
$U^{\prime}=\\{u_{1},\ldots,u_{t+1},u^{\prime}\\}$. Let $\phi\colon U\cup
U^{\prime}\to V(\Gamma_{t+2})$ be a map such that $\phi|_{U}$ and
$\phi|_{U^{\prime}}$ are homomorphisms from $\mathcal{G}[U]$ and
$\mathcal{G}[U^{\prime}]$ to $\Gamma_{t+2}$, respectively. Since $|U\cap
U^{\prime}|=t+1$, it follows from Observation 6.4 (a) that either
$\phi(U)=\phi(U^{\prime})=[t]\cup\\{t+1,t+4\\}$ or
$\phi(U)=\phi(U^{\prime})=[t]\cup\\{t+2,t+3\\}$. In either case, we have
$\phi(u)=\phi(u^{\prime})$, which implies that $u$ and $u^{\prime}$ lie in the
same part of $\mathcal{G}$. So $\\{u,u^{\prime}\\}$ is not contained in any
edge of $\mathcal{G}$.

The following lemma follows easily from Observation 6.4 (c).

######  Lemma 6.6.

Suppose that $\phi\colon V(\Gamma_{t+2})\to V(\Gamma_{t+2})$ is a homomorphism
from $\Gamma_{t+2}$ to $\Gamma_{t+2}$. Then $\phi$ is bijective,
$\phi([t])=[t]$, and

$\left\\{\phi(\\{t+1,t+4\\}),\phi(\\{t+2,t+3\\})\right\\}=\left\\{\\{t+1,t+4\\},\\{t+2,t+3\\}\right\\}.$

If $t\geq 3$, then additionally, $\phi([t-1])=[t-1]$.

Using Observation 6.4 (c) we further prove the following lemma.

######  Lemma 6.7.

Suppose that $\phi\colon V(\Gamma_{t+2})\setminus\\{t+3\\}\to V(\Gamma_{t+2})$
is a homomorphism from $\Gamma_{t+2}\setminus\\{t+3\\}$ to $\Gamma_{t+2}$.
Then $\phi$ is injective, $\phi([t])=[t]$,
$\phi(\\{t+1,t+2,t+4\\})\subset[t+1,t+4]$, and
$\\{\phi(t+1),\phi(t+4)\\}\in\\{\\{t+1,t+4\\},\\{t+2,t+3\\}\\}$. If $t\geq 3$,
then additionally, $\phi([t-1])=[t-1]$.

###### Proof.

Let $F=\Gamma_{t+2}\setminus\\{t+3\\}$. Since $\phi$ is an embedding, we have
$d_{F}(i,j)\leq d_{\Gamma_{t+2}}(\phi(i),\phi(j))$ for all pairs of vertices
in $F$. Observe that

$\displaystyle d_{F}(i,j)=\begin{cases}t+1&\text{if
}\\{i,j\\}\in\binom{[t]}{2}\text{ or }(i,j)\in[t-1]\times\\{t+4\\}\text{ or
}(i,j)=(t,t+1),\\\ t&\text{if }(i,j)\in[t-1]\times\\{t+1,t+2\\}\text{ or
}(i,j)\in\\{t\\}\times\\{t+2,t+4\\}\\\ &\text{or }\\{i,j\\}=\\{t+1,t+4\\},\\\
t-1&\text{if }\\{i,j\\}=\\{t+2,t+4\\},\\\ 1&\text{if
}\\{i,j\\}=\\{t+1,t+2\\}.\end{cases}$

Since the induced subgraph of $F$ on $[t]\cup\\{t+1,t+4\\}$ is isomorphic to
$K_{t+2}^{3}$, it follows from from Observation 6.4 (a) that
$\phi([t]\cup\\{t+1,t+4\\})\in\\{[t]\cup\\{t+1,t+4\\},[t]\cup\\{t+2,t+3\\}\\}$.
By symmetry we may assume that
$\phi([t]\cup\\{t+1,t+4\\})=[t]\cup\\{t+1,t+4\\}$. Then we have
$\phi(t+2)\in[t+1,t+4]\setminus\phi([t]\cup\\{t+1,t+4\\})=\\{t+2,t+3\\}$ By
symmetry we may assume that $\phi(t+2)=t+2$. Since
$d_{\Gamma_{t+2}}(\phi(t+2),t+1)=1$ and $d_{\Gamma_{t+2}}(\phi(t+2),t+4)=t-1$,
we have $\phi(t+1)=t+1$ and $\phi(t+4)=t+4$ (otherwise we would have
$\phi(i)\in\\{t+1,t+4\\}$ for some $i\in[t]$, but this implies that
$t=d_{F}(i,t+2)\leq d_{\Gamma_{t+2}}(\phi(i),\phi(t+2))\leq t-1$, a
contradiction). Consequently, $\phi([t])=[t]$.

Suppose that $t\geq 3$. Let $S=\\{t+1,t+2,t+4\\}$ Observe that
$L_{F}(i)[S]=L_{F}(j)[S]\neq L_{F}(t)(S)$ and
$L_{\Gamma_{t+2}}(i)[\phi(S)]=L_{\Gamma_{t+2}}(j)[\phi(S)]\neq
L_{\Gamma_{t+2}}(t)(\phi(S))$ and for all $i,j\in[t-1]$. So, we should have
$\phi([t-1])=[t-1]$ and $\phi(t)=\phi(t)$.

The following lemma characterizes the vectors
$(x_{1},\ldots,x_{t+4})\in\Delta_{t+3}$ for which the value
$p_{\Gamma_{t+2}}(x_{1},\ldots,x_{t+4})$ is close to the maximum.

######  Lemma 6.8.

For every integer $t\geq 2$ and every real number $\epsilon>0$ there exists a
constant $\delta>0$ such that if a vector $\vec{x}\in\Delta_{t+3}$ satisfies
$p_{\Gamma_{t+2}}(x_{1},\ldots,x_{t+4})\geq\lambda(K_{t+2}^{3})-\delta$, then
there exists a real number $\alpha\in[0,1]$ such that

$\displaystyle x_{i}=\begin{cases}\frac{1}{t+2}\pm\epsilon&\text{if
}i\in[t],\\\ \frac{\alpha}{t+2}\pm\epsilon&\text{if }i\in\\{t+1,t+4\\},\\\
\frac{1-\alpha}{t+2}\pm\epsilon&\text{if }i\in\\{t+2,t+3\\}.\end{cases}$ (2)

###### Proof.

We will use

$\displaystyle
xy=\left(\frac{x+y}{2}\right)^{2}-\left(\frac{x-y}{2}\right)^{2},$ (3)

and the following inequalities (see Lemma 2.2 in [24]),

$\displaystyle
p_{K_{t+2}^{3}}(y_{1},\ldots,y_{t+2})\leq\frac{t(t+1)}{2(t+2)^{2}}-\frac{t}{6(t+2)}\sum_{i=1}^{t+2}\left(y_{i}-\frac{1}{t+2}\right)^{2}$
(4)

for all $(y_{1},\ldots,y_{t+2})\in\Delta_{t+1}$.

Let $\delta=\left(\frac{\epsilon}{30t}\right)^{2}$ and note that
$\epsilon=30t\delta^{1/2}$. Let $p=p_{\Gamma_{t+2}}(x_{1},\ldots,x_{t+4})$ and
$\sigma_{i}=\sigma_{i}(x_{1},\ldots,x_{t})=\sum_{E\in\binom{[t]}{i}}\prod_{j\in
E}x_{j}$ for $i\in\\{1,2,3\\}$. Let $y_{12}=x_{t+1}+x_{t+2}$,
$y_{34}=x_{t+3}+x_{t+4}$, $y_{13}=x_{t+1}+x_{t+3}$, $y_{24}=x_{t+2}+x_{t+4}$,
and $y_{t+1}=y_{t+2}=(x_{t+1}+x_{t+2}+x_{t+3}+x_{t+4})/2$. Note that
$y_{t+1}=y_{t+2}=(y_{12}+y_{34})/2=(y_{13}+y_{24})/2$. By Equation
$(\ref{INEQU:Maclaurin-r=2})$, we have

$\displaystyle p$
$\displaystyle=\sigma_{3}+\sigma_{2}\left(1-\sigma_{1}\right)+\sum_{i=1}^{t-1}x_{i}y_{12}y_{34}+x_{t}y_{13}y_{24}$
$\displaystyle\leq\sigma_{3}+\sigma_{2}\left(1-\sigma_{1}\right)+\sigma_{1}y_{t+1}y_{t+2}-(\sigma_{1}-x_{t})\left(\frac{y_{12}-y_{34}}{2}\right)^{2}-x_{t}\left(\frac{y_{13}-y_{24}}{2}\right)^{2}$
$\displaystyle=p_{K_{t+2}^{3}}(x_{1},\ldots,x_{t},y_{t+1},y_{t+2})-(\sigma_{1}-x_{t})\left(\frac{y_{12}-y_{34}}{2}\right)^{2}-x_{t}\left(\frac{y_{13}-y_{24}}{2}\right)^{2}.$

Since $p\geq\frac{t(t+1)}{2(t+2)^{2}}-\delta$, it follows from Equation
$(\ref{INEQU:Maclaurin-r=3})$ and the inequality above that

$\displaystyle\delta$
$\displaystyle\geq\frac{t}{6(t+2)}\sum_{i=1}^{t}\left(x_{i}-\frac{1}{t+2}\right)^{2}+\sum_{i=t+1}^{t+2}\left(y_{i}-\frac{1}{t+2}\right)^{2}$
$\displaystyle+(\sigma_{1}-x_{t})\left(\frac{y_{12}-y_{34}}{2}\right)^{2}+x_{t}\left(\frac{y_{13}-y_{24}}{2}\right)^{2}.$
(5)

First, it follows that

$\displaystyle\left|x_{i}-\frac{1}{t+2}\right|$
$\displaystyle\leq\sqrt{\frac{6(t+2)}{t}\delta}\leq
6\delta^{1/2}\quad\text{for }i\in[t],\text{ and}$
$\displaystyle\left|y_{i}-\frac{1}{t+2}\right|$
$\displaystyle\leq\sqrt{\frac{6(t+2)}{t}\delta}\leq
6\delta^{1/2}\quad\text{for }i\in\\{t+1,t+2\\}.$

In particular, the first inequality implies that $x_{t}\geq
1/(t+2)-6\delta^{1/2}\geq 1/4t^{2}$ and
$\sigma_{1}-x_{t}=\sum_{i=1}^{t-1}x_{i}\geq 1/4t^{2}$. So it follows from
Inequality $(\ref{equ:delta})$ implies that

$\max\\{|y_{12}-y_{34}|,|y_{13}-y_{24}|\\}\leq\max\left\\{2\sqrt{\delta/x_{t}},2\sqrt{\delta/(\sigma_{1}-x_{t})}\right\\}\leq
4t\delta^{1/2}.$

Since $y_{12}+y_{34}=y_{13}+y_{24}=2y_{t+1}$, we obtain

$\displaystyle\max\left\\{\left|y_{12}-\frac{1}{t+2}\right|,\left|y_{23}-\frac{1}{t+2}\right|,\left|y_{13}-\frac{1}{t+2}\right|,\left|y_{24}-\frac{1}{t+2}\right|\right\\}\leq
4t\delta^{1/2}+6\delta^{1/2}\leq 10t\delta^{1/2}.$

Consequently,

$\displaystyle|x_{t+1}-x_{t+4}|$ $\displaystyle=|y_{12}-y_{24}|\leq
20t\delta^{1/2},\quad\text{and}\quad|x_{t+2}-x_{t+3}|$
$\displaystyle=|y_{12}-y_{13}|\leq 20t\delta^{1/2}.$

Since $x_{t+1}+x_{t+2}=y_{12}=\frac{1}{t+2}\pm 10t\delta^{1/2}$, there exists
$\alpha\in[0,1]$ such that

$\displaystyle x_{t+1}=\frac{\alpha}{t+2}\pm
10t\delta^{1/2},\quad\text{and}\quad x_{t+2}=\frac{1-\alpha}{t+2}\pm
10t\delta^{1/2}.$

Consequently,

$\displaystyle x_{t+3}=\frac{1-\alpha}{t+2}\pm
30t\delta^{1/2},\quad\text{and}\quad x_{t+4}=\frac{\alpha}{t+2}\pm
30t\delta^{1/2}.$

This proves Lemma 6.8.

###  6.2 Proof of Theorem 1.3 (d)

We prove Theorem 1.3 (d) in this section. Recall from Lemma 4.1 that
$\mathcal{F}_{t+2}$ is blowup-invariant, and from Claim 4.4 that the
hereditary family $\mathfrak{\Gamma}_{t+2}$ contains all symmetrized
$\mathcal{F}_{t+2}$-free $3$-graphs. Therefore, by Theorem 6.2, it suffices to
show that $\mathcal{F}_{t+2}$ is vertex-extendable with respect to
$\mathfrak{\Gamma}_{t+2}$.

###### Proof of Theorem 1.3 (d).

Let $\epsilon>0$ be a sufficiently small constant and $n$ be a sufficiently
large integer. Let $\delta>0$ be the constant guaranteed by Lemma 6.8. We may
assume that $\delta\leq\epsilon$. Let $\mathcal{H}$ be an $(n+1)$-vertex
$\Gamma_{t+2}$-colorable $3$-graph with minimum degree at least
$3(\lambda-\delta/2)(n+1)^{2}$, where
$\lambda=\lambda(\Gamma_{t+2})=\frac{t(t+1)}{6(t+2)^{2}}$.

Suppose that there exists a vertex $v\in V(\mathcal{H})$ such that
$\mathcal{H}\setminus\\{v\\}\in\mathfrak{\Gamma}_{t+2}$. Let
$V=V(\mathcal{H})\setminus\\{v\\}$ and
$\mathcal{H}^{\prime}=\mathcal{H}\setminus\\{v\\}$. Let $V=V_{1}\cup\cdots\cup
V_{t+4}$ be a partition such that the map $\phi\colon
V(\mathcal{H}^{\prime})\to V(\Gamma_{t+2})$ defined by $\phi(V_{i})=i$ for
$i\in[t+4]$ induces a homomorphism from $\mathcal{H}^{\prime}$ to
$\Gamma_{t+2}$. Let $\mathcal{G}=\Gamma_{t+2}[V_{1},\ldots,V_{t+4}]$ be a
blowup of $\Gamma_{t+2}$. It is possible that some set $V_{i}$ is empty. So it
will be convenient later to define the following graphs.

Let $w_{1},\ldots,w_{t+4}$ be $t+4$ new vertices and let
$W_{i}=V_{i}\cup\\{w_{i}\\}$ for $i\in[t+4]$. Let
$\widehat{\mathcal{G}}=\Gamma_{t+2}[W_{1},\ldots,W_{t+4}]$ be a blowup of
$\Gamma_{t+2}$. For every $i\in[t+4]$ define
$L_{\mathcal{G}}(i)=L_{\widehat{\mathcal{G}}}(w_{i})[V]$ and
$N_{\mathcal{G}}(i)=V\setminus V_{i}$. Notice that $L_{\mathcal{G}}(i)$ is a
graph on $N_{\mathcal{G}}(i)$.

We will $N(u)$ and $L(u)$ to denote $N_{\mathcal{H}}(u)$ and
$L_{\mathcal{H}}(u)$ respectively for every vertex $u\in V(\mathcal{H})$ if it
does not cause any confusion.

######  Claim 6.9.

It suffices to prove that there exists some $i_{0}\in[t+4]$ such that
$L(v)\subset L_{\mathcal{G}}(i_{0})$.

###### Proof.

Suppose that there exists some $i_{0}\in[t+4]$ such that $L(v)\subset
L_{\mathcal{G}}(i_{0})$. First notice that since $N_{\mathcal{G}}(i_{0})\cap
V_{i_{0}}=\emptyset$, we have $N(v)\cap V_{i_{0}}=\emptyset$ as well. Let
$\widehat{V}_{i_{0}}=V_{i_{0}}\cup\\{v\\}$ and $\widehat{V}_{i}=V_{i}$ for
$i\in[t+4]\setminus\\{i_{0}\\}$. It is clear that
$\mathcal{H}\subset\Gamma_{t+2}[\widehat{V}_{1},\ldots,\widehat{V}_{t+4}]$.
Therefore, $\mathcal{F}_{t+2}$ is vertex-extendable with respect to
$\mathfrak{\Gamma_{t+2}}$. This proves Theorem 1.3 (d).

Let $x_{i}=|V_{i}|/n$ for $i\in[t+4]$. By assumption, we have

$\delta(\mathcal{H}^{\prime})\geq\delta(\mathcal{H})-n\geq
3(\lambda-\delta/2)(n+1)^{2}-n\geq 3(\lambda-\delta)n^{2},$

and hence
$|\mathcal{H}^{\prime}|\geq\delta(\mathcal{H}^{\prime})n/3\geq(\lambda-\delta)n^{3}$.
Since
$p_{\Gamma_{t+2}}(x_{1},\ldots,x_{t+4})\geq|\mathcal{H}^{\prime}|/n^{3}\geq\lambda-\delta$,
it follows from Lemma 6.8 that there exists a real number $\alpha\in[0,1]$
such that Equation $(\ref{equ:weight-stable})$ holds.

######  Claim 6.10.

For every vertex $u\in V$ we have $|L_{\mathcal{G}}(u)\setminus L(u)|\leq
4t\epsilon n^{2}$.

###### Proof.

Let us assume that $u\in V_{i}$ where $i\in[t+4]$.

If $i\in\\{1,\ldots,t\\}$, then it follows from $(\ref{equ:weight-stable})$
that

$\displaystyle|L_{\mathcal{G}}(u)|/n^{2}$
$\displaystyle\leq\binom{t-1}{2}\left(\frac{1}{t+2}+\epsilon\right)^{2}+(t-1)\left(\frac{1}{t+2}+\epsilon\right)\left(\frac{2}{t+2}+4\epsilon\right)$
$\displaystyle\quad+\left(\frac{1}{t+2}+2\epsilon\right)\left(\frac{1}{t+2}+2\epsilon\right)$
$\displaystyle\leq\frac{t(t+1)}{2(t+2)^{2}}+\frac{t(t+3)}{t+2}\epsilon+\frac{t^{2}+5t+2}{2}\epsilon^{2}\leq\frac{t(t+1)}{2(t+2)^{2}}+2t\epsilon.$

If $i\in\\{t+1,\ldots,t+4\\}$, then it follows from $(\ref{equ:weight-
stable})$ that

$\displaystyle|L_{\mathcal{G}}(u)|/n^{2}$
$\displaystyle\leq\binom{t}{2}\left(\frac{1}{t+2}+\epsilon\right)^{2}+t\left(\frac{1}{t+2}+\epsilon\right)\left(\frac{1}{t+2}+2\epsilon\right)$
$\displaystyle\leq\frac{t(t+1)}{2(t+2)^{2}}+t\epsilon+\frac{t(t+3)}{2}\epsilon^{2}\leq\frac{t(t+1)}{2(t+2)^{2}}+2t\epsilon.$

Recall that $\lambda=\frac{t(t+1)}{6(t+2)^{2}}$ and $\delta\leq\epsilon$.
Therefore,

$\displaystyle|L_{\mathcal{G}}(u)\setminus
L(u)|/n^{2}\leq\frac{t(t+1)}{2(t+2)^{2}}+2t\epsilon-3\left(\lambda-\delta\right)\leq\frac{t(t+1)}{2(t+2)^{2}}+2t\epsilon-\frac{t(t+1)}{2(t+2)^{2}}+3\epsilon\leq
4t\epsilon.$

######  Claim 6.11.

For every $i\in[t+4]$ and every $u\in V_{i}$ we have $|V_{j}\setminus
N(u)|\leq 12t\epsilon n$ for all $j\in[t+4]\setminus\\{i\\}$.

###### Proof.

Fix $i\in[t+4]$ and let $u\in V_{i}$. If $i\in[t]$, then it follows from Lemma
6.8 that

$\displaystyle\delta(L_{\mathcal{G}}(u))/n$
$\displaystyle\geq\min\left\\{(t-2)\left(\frac{1}{t+2}-\epsilon\right)+2\left(\frac{\alpha}{t+2}-\epsilon+\frac{1-\alpha}{t+2}-\epsilon\right),\right.$
$\displaystyle\quad\left.(t-1)\left(\frac{1}{t+2}-\epsilon\right)+\frac{\alpha}{t+2}-\epsilon+\frac{1-\alpha}{t+2}-\epsilon\right\\}\geq\frac{t}{t+2}-(t+2)\epsilon\geq\frac{1}{3}.$

If $i\in[t+1,t+4]$, then it follows from Lemma 6.8 that

$\displaystyle\delta(L_{\mathcal{G}}(u))/n$
$\displaystyle\geq\min\left\\{(t-1)\left(\frac{1}{t+2}-\epsilon\right)+\frac{\alpha}{t+2}-\epsilon+\frac{1-\alpha}{t+2}-\epsilon,t\left(\frac{1}{t+2}-\epsilon\right)\right\\}$
$\displaystyle\geq\frac{t}{t+2}-(t+2)\epsilon\geq\frac{1}{3}.$

Since each vertex in $V_{j}\setminus N(u)$ contributes at least
$\delta(L_{\Gamma_{t+2}}(u))$ edges to $L_{\mathcal{G}}(u)\setminus L(u)$, it
follows from Claim 6.10 that

$\displaystyle|V_{j}\setminus N(u)|\leq\frac{4t\epsilon
n^{2}}{n/3}=12t\epsilon n.$

By symmetry, we may assume that $\alpha\geq 1/2$. Since $\epsilon$ is
sufficiently small, we have
$\min\\{x_{1},\ldots,x_{t},x_{t+1},x_{t+4}\\}\geq\frac{1}{4(t+2)}$.

######  Claim 6.12.

We have $L(v)\cap\binom{V_{i}}{2}=\emptyset$ for all $i\in[t+4]$.

###### Proof.

Suppose to the contrary that there exists $i\in[t+4]$ such that
$L(v)\cap\binom{V_{i}}{2}\neq\emptyset$. Let us assume that
$\\{u_{i},u_{i}^{\prime}\\}\in L(v)\cap\binom{V_{i}}{2}$.

First let us assume that $i\in\\{1,\ldots,t,t+1,t+4\\}$. Applying Lemma 6.3
with $\eta=4t\epsilon$ and $T=\\{1,\ldots,t,t+1,t+4\\}\setminus\\{i\\}$ we
obtain $u_{j}\in V_{j}$ for every $j\in T$ such that sets $U=\\{u_{j}\colon
j\in T\\}\cup\\{u_{i}\\}$ and $U^{\prime}=\\{u_{j}\colon j\in
T\\}\cup\\{u_{i}^{\prime}\\}$ satisfy

$\mathcal{H}[U]=\mathcal{G}[U]\cong
K_{t+2}^{3}\quad\text{and}\quad\mathcal{H}[U^{\prime}]=\mathcal{G}[U^{\prime}]\cong
K_{t+2}^{3}.$

Let $F=\mathcal{H}[U\cup U^{\prime}]\cup\\{\\{v,u_{i},u_{i}^{\prime}\\}\\}$.
It is clear that $v(F)=t+4\leq 4(t+4)^{2}$. Therefore, $F$ is contained as a
subgraph in some blowup of $\Gamma_{t+2}$. Since $\mathcal{H}[U]\cong
K_{t+2}^{3}$, $\mathcal{H}[U^{\prime}]\cong K_{t+2}^{3}$, and $|U\cap
U^{\prime}|=t+1$, it follows from Lemma 6.5 that $\\{u_{i},u_{i}^{\prime}\\}$
is not contained in any edge of $F$, a contradiction.

Now let us assume that $i\in\\{t+2,t+3\\}$. Applying Lemma 6.3 with
$\eta=4t\epsilon$ and $T=\\{1,\ldots,t,t+1,t+4\\}$ we obtain $u_{j}\in V_{j}$
for every $j\in T$ such that the set $U=\\{u_{j}\colon j\in T\\}$ satisfies

$\displaystyle\mathcal{H}[U]=\mathcal{G}[U]\cong
K_{t+2}^{3}\quad\text{and}\quad
L(u_{i})[U]=L_{\mathcal{G}}(u_{i})[U]=L_{\mathcal{G}}(u_{i}^{\prime})[U]=L(u_{i}^{\prime})[U].$

Let
$F=\mathcal{H}[U\cup\\{u_{i},u_{i}^{\prime}\\}]\cup\\{\\{v,u_{i},u_{i}^{\prime}\\}\\}$.
It is clear that $v(F)=t+5\leq 4(t+4)^{2}$. So there exists a homomorphism
$\phi\colon V(F)\to V(\Gamma_{t+2})$ from $F$ to $\Gamma_{t+2}$. Since
$F[U]\cong K_{t+2}^{3}$, it follows from Observation 6.4 (a) that either
$\phi(U)=[t]\cup\\{t+1,t+4\\}$ or $\phi(U)=[t]\cup\\{t+2,t+3\\}$. By symmetry
we may assume that $\phi(U)=[t]\cup\\{t+1,t+4\\}$. Since
$U\cup\\{u_{i},u_{i}^{\prime}\\}$ is $2$-covered in $F$, we have
$\\{\phi(u_{i}),\phi(u_{i}^{\prime})\\}=[t+4]\setminus\phi(U)=\\{t+2,t+3\\}$.
However, notice that $|L_{F}(u_{i})[U]\cap
L_{F}(u_{i}^{\prime})[U]|=\binom{t}{2}+t$, while
$|L_{\Gamma_{t+2}}(t+2)[\phi(U)]\cap
L_{\Gamma_{t+2}}(t+3)[\phi(U)]|=\binom{t}{2}<\binom{t}{2}+t$, a contradiction.

Define

$\displaystyle I_{small}=\left\\{i\in[t+4]\colon|N(v)\cap
V_{i}|\leq\epsilon^{1/4}n\right\\},\quad\text{and}\quad
I_{\emptyset}=\left\\{i\in[t+4]\colon N(v)\cap V_{i}=\emptyset\right\\}.$

It follows from the definition that $I_{\emptyset}\subset I_{small}$.

Next we will consider two cases depending on the sizes of $V_{t+2}$ and
$V_{t+3}$: either $V_{t+2}$ and $V_{t+3}$ are both large (i.e. at least
$50t^{2}\epsilon^{1/4}$) or $V_{t+2}$ and $V_{t+3}$ are both small. The first
case is quite easy to handle while the second case needs more work.

Case 1: $\alpha\leq 1-101t^{3}\epsilon^{1/4}$.

Note that in this case we have

$\min\left\\{|V_{t+1}|,|V_{t+2}|,|V_{t+3}|,|V_{t+4}|\right\\}\geq\frac{101t^{3}\epsilon^{1/4}}{t+2}n\geq
50t^{2}\epsilon^{1/4}n.$

Define an auxiliary graph $R$ on $[t+4]$ in which two vertices $i$ and $j$ are
adjacent iff there exists $e\in L(v)$ such that $e\cap V_{i}\neq\emptyset$ and
$e\cap V_{j}\neq\emptyset$. An easy observation is that $L(v)\subset
R[V_{1},\ldots,V_{t+4}]$.

######  Claim 6.13.

We have $L(v)\subset L_{\mathcal{G}}(i)$ for some $i\in I_{small}$.

###### Proof.

For each edge $ij\in R$ let $e_{ij}\in L(v)$ be an edge with one endpoint in
$V_{i}$ and the other endpoint in $V_{j}$. Let $U_{1}=\bigcup_{ij\in R}e_{ij}$
be a vertex subset of $V$ and note that $|U_{1}|\leq 2\binom{t+4}{2}$. Define

$\displaystyle V_{i}^{\prime}=\begin{cases}V_{i}\cap
N(v)\cap\left(\bigcap_{u\in U_{1}\setminus V_{i}}N(u)\right)&\text{for
}i\in[t+4]\setminus I_{small},\\\ V_{i}\cap\left(\bigcap_{u\in U_{1}\setminus
V_{i}}N(u)\right)&\text{for }i\in I_{small}.\end{cases}$

It follows from Claim 6.11 and our assumption that

$\displaystyle|V_{i}^{\prime}|\geq\min\left\\{\epsilon^{1/4}n-\left(|U_{1}|+1\right)\times
12t\epsilon n,\ 50t^{2}\epsilon^{1/4}n-|U_{1}|\times 12t\epsilon
n\right\\}\geq 4(t+4)^{3}\epsilon^{1/3}n.$

Applying Lemma 6.3 with $\eta=4t\epsilon$ and $T=[t+4]$ we obtain $u_{i}\in
V_{i}^{\prime}$ for $i\in T$ such that the set $U_{2}=\\{u_{i}\colon i\in
T\\}$ satisfies

  1. (a)

$\mathcal{H}[U_{2}]=\mathcal{G}[U_{2}]\cong\Gamma_{t+2}$, and

  2. (b)

$L(u)[U_{2}]=L_{\mathcal{G}}(u)[U_{2}]$ for all $u\in U_{1}$.

Let $F=\mathcal{H}[U_{1}\cup U_{2}\cup\\{v\\}]$. Note that $v(F)\leq
2\binom{t+4}{2}+t+5\leq 3(t+4)^{2}$. By assumption there exists a homomorphism
$\phi\colon V(F)\to V(\Gamma_{t+2})$ from $F$ to $\Gamma_{t+2}$ (otherwise we
would have $F\in\mathcal{F}_{t+2}$, a contradiction). Since
$F[U_{2}]\cong\Gamma_{t+2}$, it follows from Lemma 6.6 that
$\phi(u_{i})\in[t]$ for $i\in[t]$ (and $\phi(u_{t})=t$ if $t\geq 3$), and

$\displaystyle\left\\{\phi(\\{u_{t+1},u_{t+4}\\}),\phi(\\{u_{t+2},u_{t+3}\\})\right\\}=\left\\{\\{t+1,t+4\\},\\{t+2,t+3\\}\right\\}.$

By symmetry we may assume that $\phi(u_{i})=i$ for $i\in[t+4]$. For every
$i\in[t+4]$ and $u\in V_{i}\cap U_{1}$ since $u$ is adjacent to all vertices
in $U_{2}\setminus\\{u_{i}\\}$ in $\partial F$, we have $\phi(u)=i$. Finally,
since $v$ is adjacent to all vertices in $\\{u_{i}\colon i\in[t+4]\setminus
I_{small}\\}$, we have $\phi(v)\not\in\phi([t+4]\setminus I_{small})$. In
other words, $\phi(v)\in\phi(I_{small})$. This means that there exists some
$i\in I_{small}$ such that $\phi(R)\subset L_{\Gamma_{t+2}}(\phi(i))$, and
hence $L(v)\subset L_{\mathcal{G}}(i)$.

Case 2: $\alpha\geq 1-101t^{3}\epsilon^{1/4}$.

Note that in this case we have

$\displaystyle\max\left\\{|V_{t+2}|,|V_{t+3}|\right\\}$
$\displaystyle\leq\frac{101t^{3}\epsilon^{1/4}}{t+2}n+\epsilon n\leq
102t^{2}\epsilon^{1/4}n,\quad\text{and}$
$\displaystyle\min\left\\{|V_{t+1}|,|V_{t+4}|\right\\}$
$\displaystyle\geq\frac{1-100t^{3}\epsilon^{1/4}}{t+2}n-\epsilon
n\geq\frac{n}{t+2}-50t^{2}\epsilon^{1/4}n.$

For convenience, let $S=[t]\cup\\{t+1,t+4\\}$.

######  Claim 6.14.

We have $|I_{small}\cap S|\leq 1$.

###### Proof.

Suppose to the contrary that $|I_{small}\cap S|\geq 2$. Then it follows from
Lemma 6.8 that

$\displaystyle|L(v)|/n^{2}$
$\displaystyle\leq\binom{t}{2}\left(\frac{1}{t+2}+\epsilon\right)^{2}+2\times
102t^{2}\epsilon^{1/4}+2\epsilon^{1/4}$
$\displaystyle=\frac{t(t+1)}{2(t+2)^{2}}-\frac{t}{(t+2)^{2}}+\frac{t(t-1)}{t+2}\epsilon+\frac{t(t-1)}{2}\epsilon^{2}+204t^{2}\epsilon^{1/4}+2\epsilon^{1/4}$
$\displaystyle<3(\lambda-\delta),$

a contradiction.

Next we will consider two cases depending on the value of $|I_{small}\cap S|$:
either $|I_{small}\cap S|=1$ or $|I_{small}\cap S|=0$.

Case 2.1: $|I_{small}\cap S|=1$.

We may assume that $I_{small}=\\{1\\}$. The proof for other cases follows
analogously. Let $W=\bigcup_{i\in S\setminus I_{small}}V_{i}$. It follows from
our assumption that

$\displaystyle|L(v)[W]|/n^{2}\geq\delta(\mathcal{H})/n^{2}-2\times
102t^{2}\epsilon^{1/4}-\epsilon^{1/4}\geq\frac{t(t+1)}{2(t+2)^{2}}-205t^{2}\epsilon^{1/4}.$

Notice that the induced subgraph of $L_{\mathcal{G}}(1)$ on $W$ is the blowup
$K_{t+1}[V_{2},\ldots,V_{t},V_{t+1},V_{t+4}]$ of $K_{t+1}$. Using the same
argument as in the proof of Claim 6.10, we get

$\displaystyle|L_{\mathcal{G}}(1)\setminus
L(v)[W]|/n^{2}\leq\frac{t(t+1)}{2(t+2)^{2}}+2t\epsilon-\left(\frac{t(t+1)}{2(t+2)^{2}}-205t^{2}\epsilon^{1/4}\right)\leq
206t^{2}\epsilon^{1/4}.$

Also, using the same argument as in the proof of Claim 6.11, we get

$\displaystyle|N(v)\cap
V_{i}|\geq|V_{i}|-\frac{206t^{2}\epsilon^{1/4}n^{2}}{n/3}\geq\frac{n}{t+2}-50t^{2}\epsilon^{1/4}n-700t^{2}\epsilon^{1/4}n\geq\frac{n}{2(t+2)}.$

######  Claim 6.15.

We have $N(v)\cap V_{1}=\emptyset$.

###### Proof.

Suppose to the contrary that there exists a vertex $u_{1}\in N(v)\cap V_{1}$.
Let $V_{i}^{\prime}=V_{i}\cap N(v)\cap N(u_{1})$ for $i\in S\setminus\\{1\\}$.
Notice that $|V_{i}^{\prime}|\geq\frac{n}{2(t+2)}-12t\epsilon
n>206(t+4)^{4}\epsilon^{1/12}n$. Applying Lemma 6.8 with
$\eta=206t^{2}\epsilon^{1/4}$ and $T=S\setminus\\{1\\}$, we obtain a vertex
$u_{i}\in V_{i}^{\prime}$ for every $i\in T$ such that the set
$U=\\{u_{i}\colon i\in T\\}$ satisfies

$\displaystyle\mathcal{H}[U\cup\\{u_{1}\\}]=\mathcal{G}[U\cup\\{u_{1}\\}]\cong
K_{t+2}^{3}\quad\text{and}\quad\mathcal{H}[U\cup\\{v\\}]=\mathcal{G}[U\cup\\{v\\}]\cong
K_{t+2}^{3}.$

Let $e\in\mathcal{H}$ be an edge that contains $\\{v,u_{1}\\}$ and let
$F=\mathcal{H}[U\cup\\{v,u_{1}\\}]\cup\\{e\\}$. By assumption, $F$ should be
contained in some blowup of $\Gamma_{t+2}$, but this would contradict Lemma
6.5 since $\\{v,u_{1}\\}$ is contained in $e$.

######  Claim 6.16.

We have $L(v)\subset L_{\mathcal{G}}(1)$.

###### Proof.

Suppose to the contrary that there exists an edge $e\in
L_{\mathcal{G}}(1)\setminus L(v)$. By symmetry we may assume that
$e=\\{u_{t+1},u_{t+2}\\}$ and $(u_{t+1},u_{t+2})\in V_{t+1}\times V_{t+2}$.
Let

$\displaystyle V_{i}^{\prime}=\begin{cases}V_{i}\cap N(u_{t+1})\cap
N(u_{t+2})&\text{if }i=1,\\\ V_{i}\cap N(v)\cap N(u_{t+2})&\text{if }i=t+1,\\\
V_{i}\cap N(v)\cap N(u_{t+1})\cap N(u_{t+2})&\text{if
}i\in[2,t]\cup\\{t+4\\}.\end{cases}$

Notice that $|V_{i}^{\prime}|\geq\frac{n}{2(t+2)}-2\times
12t\epsilon>206(t+4)^{4}\epsilon^{1/12}$. Applying Lemma 6.8 with
$\eta=206t^{2}\epsilon^{1/4}$ and $T=S$, we obtain a vertex $u_{i}^{\prime}\in
V_{i}^{\prime}$ for every $i\in T$ such that the set
$U=\\{u_{i}^{\prime}\colon i\in T\\}$ satisfies

  1. (a)

$\mathcal{H}[U]=\mathcal{G}[U]\cong K_{t+2}^{3}$,

  2. (b)

$L(v)[U\setminus\\{u_{1}\\}]\cong K_{t+1}$, and

  3. (c)

$L(u_{i})[U]=L_{\mathcal{G}}(u_{i})[U]$ for $i\in\\{t+1,t+2\\}$.

Let $F=\mathcal{H}[U\cup\\{v,u_{t+1},u_{t+2}\\}]$ and
$U^{\prime}=\left(U\cup\\{u_{t+1}\\}\right)\setminus\\{u_{t+1}^{\prime}\\}$.
Since $v(F)=t+5\leq 4(t+4)^{2}$, by assumption, there is a homomorphism
$\phi\colon V(F)\to V(\Gamma_{t+2})$ from $F$ to $\Gamma_{t+2}$. Since
$\mathcal{H}[U]\cong\mathcal{H}[U^{\prime}]\cong K_{t+2}^{3}$, we have
$\Gamma_{t+2}[\phi(U)]\cong\Gamma_{t+2}[\phi(U^{\prime})]\cong K_{t+2}^{3}$.
Since $|\phi(U)\cap\phi(U^{\prime})|=|U\cap U^{\prime}|=t+1$, it follows from
Lemma 6.5 that $\phi(U)=\phi(U^{\prime})$ and
$\phi(u_{t+1})=\phi(u_{t+1}^{\prime})$.

Let $U_{1}=U\cup\\{u_{t+2}\\}$. Since
$F[U_{1}]\cong\Gamma_{t+2}\setminus\\{t+3\\}$, it follows from Lemma 6.7 that
$\phi(\\{u_{i}^{\prime}\colon i\in[t]\\})=[t]$ (and $\phi(u^{\prime}_{t})=t$
if $t\geq 3$),
$\phi(\\{u_{t+1}^{\prime},u_{t+2},u_{t+4}^{\prime}\\})\subset[t+1,t+4]$, and
$\phi(\\{u_{t+1}^{\prime},u_{t+4}^{\prime}\\})\in\\{\\{t+1,t+4\\},\\{t+2,t+3\\}\\}$.
By symmetry we may assume that $\phi(u_{i}^{\prime})=i$ for $i\in S$ and
$\phi(u_{t+2})=t+2$. Hence $\phi(u_{t+1}^{\prime})=\phi(u_{t+1})=t+1$. Since
$v$ is adjacent to all vertices in $U_{1}\setminus\\{u_{1}\\}$, we have
$\phi(v)\in[t+4]\setminus\phi(U_{1}\setminus\\{u_{1}\\})=\\{1,t+3\\}$. If
$\phi(v)=t+3$, then $\\{v,u_{t+1},u_{t+2}\\}\in F$ implies that
$\\{t+1,t+2,t+3\\}=\\{\phi(v),\phi(u_{t+1}),\phi(u_{t+2})\\}\in\Gamma_{t+2}$,
a contradiction. Therefore, we may assume that $\phi(v)=1$. Then
$\left\\{\\{u_{1}^{\prime},u_{t+1}^{\prime},u_{t+4}^{\prime}\\},\\{u_{1}^{\prime},u_{t+2},u_{t+4}^{\prime}\\},\\{v,u_{t+1},u_{t+2}\\}\\}\right\\}\subset
F$ implies that

$\displaystyle\left\\{\\{1,t+1,t+4\\},\\{1,t+2,t+4\\},\\{1,t+1,t+2\\}\\}\right\\}$
$\displaystyle=$
$\displaystyle\left\\{\\{\phi(u_{1}^{\prime}),\phi(u_{t+1}^{\prime}),\phi(u_{t+4}^{\prime})\\},\\{\phi(u_{1}^{\prime}),\phi(u_{t+2}),\phi(u_{t+4}^{\prime})\\},\\{\phi(v),\phi(u_{t+1}),\phi(u_{t+2})\\}\\}\right\\}\subset\Gamma_{t+2}.$

This means that the triangle $\\{t+1,t+2,t+4\\}$ is contained in the induced
subgraph of $L_{\Gamma_{t+2}}(1)$ on $\\{t+1,t+2,t+3,t+4\\}$, contradicts the
fact that the induced subgraph of $L_{\Gamma_{t+2}}(1)$ on
$\\{t+1,t+2,t+3,t+4\\}$ is a copy of $C_{4}$.

Recall that $S=[t]\cup\\{t+1,t+2\\}$

Case 2.2: $I_{small}\cap S=\emptyset$.

Recall that $R$ is a graph on $[t+4]$ in which two vertices $i$ and $j$ are
adjacent iff there exists $e\in L(v)$ such that $e\cap V_{i}\neq\emptyset$ and
$e\cap V_{j}\neq\emptyset$. Recall the observation that $L(v)\subset
R[V_{1},\ldots,V_{t+4}]$.

######  Claim 6.17.

If $V_{t+2}\cup V_{t+3}\neq\emptyset$, then either $L(v)\subset
L_{\mathcal{G}}(t+2)$ or $L(v)\subset L_{\mathcal{G}}(t+3)$.

###### Proof.

For every $ij\in R$ let $e_{ij}\in L(v)$ be an edge such that $e_{ij}\cap
V_{i}\neq\emptyset$ and $e_{ij}\cap V_{j}\neq\emptyset$. Let
$U_{1}=\bigcup_{ij\in R_{2}}e_{ij}$ be a vertex subset of $V$. Note that
$|U_{1}|\leq 2\binom{t+4}{2}$.

By symmetry we may assume that $V_{t+2}\neq\emptyset$. Fix a vertex
$u_{t+2}\in V_{t+2}$ (it is possible that $u_{t+2}\in U_{1}$ as well). For
every $i\in S$ let $V_{i}^{\prime}=V_{i}\cap N(v)\cap
N(u_{t+2})\cap\left(\bigcap_{u\in U_{1}\setminus V_{i}}N(u)\right)$. Notice
that
$|V_{i}^{\prime}|\geq\frac{n}{2(t+2)}-(2\binom{t+4}{2}+1)12t\epsilon>4(t+4)^{3}\epsilon^{1/3}n$.
Applying Lemma 6.3 with $\eta=4t\epsilon$ and $T=S$ we obtain $u_{i}\in
V^{\prime}_{i}$ for every $i\in T$ such that the set $U=\\{u_{i}\colon i\in
T\\}$ satisfies

  1. (a)

$\mathcal{H}[U]=\mathcal{G}[U]\cong K_{t+2}^{3}$,

  2. (b)

$L(u)[U]=L_{\mathcal{G}}(u)[U]$ for all $u\in U_{1}$, and

  3. (c)

$L(u_{t+2})[U]=L_{\mathcal{G}}(u_{t+2})[U]$.

Let $F=\mathcal{H}[U\cup U_{1}\cup\\{v,u_{t+2}\\}]$. Since $v(F)\leq
2\binom{t+4}{2}+t+5\leq 4(t+4)^{3}$, by assumption there is a homomorphism
$\phi\colon V(F)\to V(\Gamma_{t+2})$ from $F$ to $\Gamma_{t+2}$. Since
$F[U\cup\\{u_{t+2}\\}]\cong\Gamma_{t+2}\setminus\\{t+3\\}$, it follows from
Lemma 6.7 that $\phi(\\{u_{i}\colon i\in[t]\\})=[t]$ (and $\phi(u_{t})=t$ if
$t\geq 3$), $\phi(\\{u_{t+1},u_{t+2},u_{t+4}\\})\subset[t+1,t+4]$, and
$\phi(\\{u_{t+1},u_{t+4}\\})\in\\{\\{t+1,t+4\\},\\{t+2,t+3\\}\\}$. By
symmetry, we may assume that $\phi(u_{i})=i$ for
$i\in[t]\cup\\{t+1,t+2,t+4\\}$. For every $i\in[t]\cup\\{t+1,t+4\\}$ and every
$u\in U_{1}\cap V_{i}$, since $L(u)[U]=L(u_{i})[U]=L_{\mathcal{G}}(u_{i})[U]$
and $u$ is adjacent to all vertices in $U\setminus\\{u_{i}\\}$, we have
$\phi(u)=\phi(u_{i})=i$. Finally, since $v$ is adjacent to all vertices in
$\\{u_{i}\colon i\in[t]\cup\\{t+1,t+3\\}\\}$, we have
$\phi(v)\in[t+4]\setminus\phi(\\{u_{i}\colon
i\in[t]\cup\\{t+1,t+3\\}\\})=\\{t+2,t+3\\}$. If $\phi(v)=t+2$, then
$\phi(R)\subset L_{\Gamma_{t+2}}(\phi(v))=L_{\Gamma_{t+2}}(t+2)$, which means
that $L(v)\subset L_{\mathcal{G}}(t+2)$. If $\phi(v)=t+3$, then
$\phi(R)\subset L_{\Gamma_{t+2}}(\phi(v))=L_{\Gamma_{t+2}}(t+3)$, which means
that $L(v)\subset L_{\mathcal{G}}(t+3)$.

Now we may assume that $V_{j+2}\cup V_{j+3}=\emptyset$.

######  Claim 6.18.

We have either $L(v)\subset L_{\mathcal{G}}(t+2)$ or $L(v)\subset
L_{\mathcal{G}}(t+3)$.

###### Proof.

For each edge $ij\in R$ let $e_{i,j}\in L(v)$ be an edge with one endpoint in
$V_{i}$ and the other endpoint in $V_{j}$. Let $U_{1}=\bigcup_{ij\in
R}e_{i,j}$ be a vertex subset of $V$ and note that $|U_{1}|\leq
2\binom{t+2}{2}$. Define

$\displaystyle V_{i}^{\prime}=V_{i}\cap N(v)\cap\left(\bigcap_{u\in
U_{1}\setminus V_{i}}N(u)\right)\quad\text{for }i\in[t]\cup\\{t+1,t+4\\}.$

Notice that
$|V_{i}^{\prime}|\geq\frac{n}{2(t+2)}-(2\binom{t+4}{2}+1)12t\epsilon>4(t+4)^{3}\epsilon^{1/3}n$.
Applying Lemma 6.3 with $\eta=4t\epsilon$ and $T=[t]\cup\\{t+1,t+4\\}$ we
obtain $u_{i}\in V_{i}^{\prime}$ for $i\in T$ such that the set
$U_{2}=\\{u_{i}\colon i\in T\\}$ satisfies

  1. (a)

$\mathcal{H}[U_{2}]=\mathcal{G}[U_{2}]\cong K_{t+2}^{3}$, and

  2. (b)

$L(u)[U_{2}\setminus\\{u_{i}\\}]=L_{\mathcal{G}}(u)[U_{2}\setminus\\{u_{i}\\}]\cong
K_{t+1}$ for all $u\in U_{1}\cap V_{i}$ and $i\in S$.

Let $F=\mathcal{H}[U_{1}\cup U_{2}\cup\\{v\\}]$. Suppose that there exists a
homomorphism $\phi\colon V(F)\to V(\Gamma_{t+2})$ from $F$ to $\Gamma_{t+2}$.
Since the set $F[U_{2}]\cong K_{t+2}^{3}$ we have either
$\phi(U_{2})=[t]\cup\\{t+1,t+4\\}$ or $\phi(U_{2})=[t]\cup\\{t+2,t+3\\}$. By
symmetry we may assume that the former case holds and $\phi(u_{i})=i$ for
$i\in[t]\cup\\{t+1,t+4\\}$. Since $L_{\Gamma_{t+2}}(t+2)$ and
$L_{\Gamma_{t+2}}(t+3)$ do not contain $K_{t+1}$ as a subgraph, it follows
from $(b)$ that for every $u\in V_{i}\cap U_{1}$ and
$i\in[t]\cup\\{t+1,t+4\\}$ we have $\phi(u)\not\in\\{t+2,t+3\\}$. Moreover,
since $u$ is adjacent to all vertices in $U_{2}\setminus\\{u_{i}\\}$ in
$\partial F$, we have $\phi(u)\not\in\phi(U_{2}\setminus\\{u_{i}\\})$ as well.
Therefore, $\phi(u)=\phi(u_{i})=i$. Finally, since $U_{2}\cup\\{v\\}$ is
$2$-covered in $F$, we have $\phi(v)\in\\{t+2,t+3\\}$. If $\phi(v)=t+2$, then
we have $L(v)\subset L_{\mathcal{G}}(t+2)$. If $\phi(v)=t+3$, then we have
$L(v)\subset L_{\mathcal{G}}(t+3)$.

This completes the proof of Theorem 1.3 (d).

##  7 Feasible region

We prove Theorem 1.11 in this section. First we need the following simple
corollary of Theorem 1.3 (d). For convenience, we will keep using $t+2$
instead of $t$ in this section.

Recall that for an $n$-vertex $r$-graph $\mathcal{H}$ the edge density of
$\mathcal{H}$ is $\rho(H)=|\mathcal{H}|/\binom{n}{r}$, and the shadow density
of $\mathcal{H}$ is $|\partial\mathcal{H}|/\binom{n}{r-1}$.

######  Corollary 7.1.

For every integer $t\geq 2$ there exist constants $\epsilon_{0}>0$ and $N_{0}$
such that the following statement holds for all $\epsilon\leq\epsilon_{0}$ and
$n\geq N_{0}$. Suppose that $\mathcal{H}$ is an $n$-vertex
$\mathcal{F}_{t+2}$-free $3$-graph with
$\rho(\mathcal{H})\geq\frac{t(t+1)}{2(t+2)^{2}}-\epsilon$. Then there exists a
set $Z_{\epsilon}\subset V(\mathcal{H})$ of size at most $\epsilon^{1/2}n$
such that $\mathcal{H}\setminus Z_{\epsilon}$ is $\Gamma_{t+2}$-colorable and
$\delta(\mathcal{H})\geq\left(\frac{t(t+1)}{2(t+2)^{2}}-3\epsilon^{1/2}\right)n^{2}$.

The idea for proving Corollary 7.1 is to show that after removing a few
vertices with small degree from $\mathcal{H}$ the remaining $3$-graph has
large minimum degree, and hence, by Theorem 1.3 (d), it is
$\Gamma_{t+2}$-colorable. We refer the reader to the proof of Theorem 4.1 in
[23] for detailed calculations.

######  Lemma 7.2.

Suppose that $\mathcal{H}$ is an $n$-vertex $\Gamma_{t+2}$-colorable $3$-graph
with $|\mathcal{H}|\geq\left(\frac{t(t+1)}{6(t+2)^{2}}-\epsilon\right)n^{3}$.
Then
$\left(\frac{t+1}{2(t+2)}-100t^{4}\epsilon^{1/2}\right)n^{2}\leq|\partial\mathcal{H}|\leq\left(\frac{t^{2}+3t+3}{2(t+2)^{2}}+5000t^{4}\epsilon^{1/2}\right)n^{2}$.

###### Proof.

Let $V=V_{1}\cup\cdots\cup V_{t+4}$ be a partition such that
$\mathcal{H}\subset\Gamma_{t+2}[V_{1},\ldots,V_{t+4}]$. Let
$\mathcal{G}=\Gamma_{t+2}[V_{1},\ldots,V_{t+4}]$. Let $x_{i}=|V_{i}|/n$ for
$i\in[t+4]$. By Lemma 6.8, there exists some $\alpha\in[0,1]$ such that

$\displaystyle x_{i}=\begin{cases}\frac{1}{t+2}\pm 30t\epsilon^{1/2}&\text{if
}i\in[t],\\\ \frac{\alpha}{t+2}\pm 30t\epsilon^{1/2}&\text{if
}i\in\\{t+1,t+4\\},\\\ \frac{1-\alpha}{t+2}\pm 30t\epsilon^{1/2}&\text{if
}i\in\\{t+2,t+3\\}.\end{cases}$

Notice that for every pair $\\{u,v\\}\in\partial\mathcal{G}$ the number of
edges in $\mathcal{G}$ containing $\\{u,v\\}$ is at least
$\left(\frac{1}{t+2}-30t\epsilon^{1/2}\right)n\geq\frac{n}{2(t+2)}$.
Therefore, it follows from a simple double counting that

$\displaystyle|\partial\mathcal{G}\setminus\partial\mathcal{H}|\leq\frac{3|\mathcal{G}\setminus\mathcal{H}|}{n/2(t+2)}\leq\frac{3\epsilon
n^{3}}{n/2(t+2)}\leq 6\epsilon(t+2)n^{2}.$

Therefore,

$\displaystyle|\partial\mathcal{H}|/n^{2}$
$\displaystyle\geq|\partial\mathcal{G}|/n^{2}-6\epsilon(t+2)=p_{\partial\mathcal{G}}(x_{1},\ldots,x_{t+4})-6(t+2)\epsilon$
$\displaystyle\geq\binom{t}{2}\left(\frac{1}{t+2}-30t\epsilon^{1/2}\right)^{2}+t\left(\frac{1}{t+2}-30t\epsilon^{1/2}\right)\left(\frac{2}{t+2}-4\times
30t\epsilon^{1/2}\right)$
$\displaystyle\quad+\left(\frac{\alpha}{t+2}-30t\epsilon^{1/2}\right)^{2}+\left(\frac{1-\alpha}{t+2}-30t\epsilon^{1/2}\right)^{2}$
$\displaystyle\quad+4\left(\frac{\alpha}{t+2}-30t\epsilon^{1/2}\right)\left(\frac{1-\alpha}{t+2}-30t\epsilon^{1/2}\right)-6(t+2)\epsilon$
$\displaystyle\geq\frac{t+1}{2(t+2)}+\frac{2\alpha(1-\alpha)}{(t+2)^{2}}-30t(t+3)\epsilon^{1/2}+450t^{2}\left(t^{2}+7t+12\right)\epsilon-6(t+2)\epsilon$
$\displaystyle\geq\frac{t+1}{2(t+2)}-100t^{4}\epsilon^{1/2}.$

On the other hand, we have

$\displaystyle|\partial\mathcal{H}|/n^{2}$
$\displaystyle\leq|\partial\mathcal{G}|/n^{2}=p_{\partial\mathcal{G}}(x_{1},\ldots,x_{t+4})$
$\displaystyle\leq\binom{t}{2}\left(\frac{1}{t+2}+30t\epsilon^{1/2}\right)^{2}+t\left(\frac{1}{t+2}+30t\epsilon^{1/2}\right)\left(\frac{2}{t+2}+4\times
30t\epsilon^{1/2}\right)$
$\displaystyle\quad+\left(\frac{\alpha}{t+2}+30t\epsilon^{1/2}\right)^{2}+\left(\frac{1-\alpha}{t+2}+30t\epsilon^{1/2}\right)^{2}$
$\displaystyle\quad+4\left(\frac{\alpha}{t+2}+30t\epsilon^{1/2}\right)\left(\frac{1-\alpha}{t+2}+30t\epsilon^{1/2}\right)$
$\displaystyle\leq\frac{t+1}{2(t+2)}+\frac{2\alpha(1-\alpha)}{(t+2)^{2}}+30t(t+3)\epsilon^{1/2}+450t^{2}\left(t^{2}+7t+12\right)\epsilon$
$\displaystyle\leq\frac{t+1}{2(t+2)}+\frac{1}{2(t+2)^{2}}+5000t^{4}\epsilon^{1/2}=\frac{t^{2}+3t+3}{2(t+2)^{2}}+5000t^{4}\epsilon^{1/2}.$

Now we are ready to prove Theorem 1.11.

###### Proof of Theorem 1.11.

First, we prove that
$\mathrm{proj}\Omega(\mathcal{F}_{t+2})=\left[0,\frac{t+3}{t+4}\right]$. By a
result in [20], this is equivalent to show that
$\frac{t+3}{t+4}\in\mathrm{proj}\Omega(\mathcal{F}_{t+2})$ and
$\mathrm{proj}\Omega(\mathcal{F}_{t+2})\subset\left[0,\frac{t+3}{t+4}\right]$.
Let $\mathcal{H}$ be an $n$-vertex $\mathcal{F}_{t+2}$-free $3$-graph. By
Lemma 4.2, the graph $\partial\mathcal{H}$ is $K_{t+5}$-free. Thus, by Turán’s
theorem, we have $\rho(\partial\mathcal{H})\leq\frac{t+3}{t+4}$. Therefore, we
have
$\mathrm{proj}\Omega(\mathcal{F}_{t+2})\subset\left[0,\frac{t+3}{t+4}\right]$.
On the other hand, since the balanced blowup of $\Gamma_{t+2}$ on $n$ vertices
has edge density $\frac{t+3}{t+4}$ as $n\to\infty$, we have
$\frac{t+3}{t+4}\in\mathrm{proj}\Omega(\mathcal{F}_{t+2})$. Therefore,
$\mathrm{proj}\Omega(\mathcal{F}_{t+2})=\left[0,\frac{t+3}{t+4}\right]$.

Let $I_{t}=\left[\frac{t+1}{t+4},\frac{t^{2}+3t+3}{(t+2)^{2}}\right]$. Next,
we show that
$I_{t}\times\left\\{\frac{t(t+1)}{(t+2)^{2}}\right\\}\subset\Omega(\mathcal{F}_{t+2})$.
This is done by constructing for every $x\in I_{t}$ a sequence of
$\mathcal{F}_{t+2}$-free $3$-graphs whose shadow densities approach $x$, and
whose edge densities approach $\frac{t(t+1)}{(t+2)^{2}}$. Let
$\alpha\in[0,1/2]$ be a real number. Let $x_{1}=\cdots=x_{t}=\frac{1}{t+2}$,
$x_{t+1}=x_{t+4}=\frac{\alpha}{t+2}$, and
$x_{t+2}=x_{t+3}=\frac{1-\alpha}{t+2}$. For every $n\in\mathbb{N}$ let
$\mathcal{H}_{n}(\alpha)=\Gamma_{t+2}[V_{1},\ldots,V_{t+4}]$ be a blowup of
$\Gamma_{t+2}$ such that $|V_{i}|=\lfloor x_{i}n\rfloor$ for $i\in[t+4]$. It
is easy to see that

$\displaystyle\lim_{n\to\infty}\rho\left(\partial\mathcal{H}_{n}(\alpha)\right)=2\cdot
p_{K_{t+4}}(x_{1},\ldots,x_{t+4})=\frac{t^{2}+3t+2+4\alpha(1-\alpha)}{(t+2)^{2}},$

and

$\displaystyle\lim_{n\to\infty}\rho\left(\mathcal{H}_{n}(\alpha)\right)=6\cdot
p_{\Gamma_{t+2}}(x_{1},\ldots,x_{t+4})=\frac{t(t+1)}{(t+2)^{2}}.$

Letting $\alpha$ vary from $0$ to $1/2$, the function
$\frac{t^{2}+3t+2+4\alpha(1-\alpha)}{2(t+2)^{2}}$ grows from $\frac{t+1}{t+4}$
to $\frac{t^{2}+3t+3}{(t+2)^{2}}$. Therefore,
$I_{t}\times\left\\{\frac{t(t+1)}{6(t+2)^{2}}\right\\}\subset\Omega(\mathcal{F}_{t+2})$.

Finally, we show that the feasible region function $g(\mathcal{F}_{t+2})$
attains its maximum only on the interval $I_{t}$. Suppose that
$\left(\mathcal{H}_{n}\right)_{n=1}^{\infty}$ is a sequence of
$\mathcal{F}_{t+2}$-free $3$-graphs with
$\lim_{n\to\infty}\rho(\partial\mathcal{H}_{n})=x$ and
$\lim_{n\to\infty}\rho(\mathcal{H}_{n})=\frac{t(t+1)}{(t+2)^{2}}$. To keep our
notations simple, let us assume that $v(\mathcal{H}_{n})=n$ for all $n\geq 1$.
Let $\epsilon>0$ be a sufficiently small constant. Then there exists $N_{0}$
such that $\rho(\partial\mathcal{H}_{n})=x\pm\epsilon$ and
$\rho(\mathcal{H}_{n})\geq\frac{t(t+1)}{(t+2)^{2}}-\epsilon$ for all $n\geq
N_{0}$. It follows from Corollary 7.1 that there exists a set $Z_{n}\subset
V(\mathcal{H}_{n})$ of size $\epsilon^{1/2}n$ such that the $3$-graph
$\mathcal{H}^{\prime}_{n}$ obtained from $\mathcal{H}_{n}$ by removing all
edges that have nonempty intersection with $Z_{n}$ is $\Gamma_{t+2}$-colorable
with minimum degree at least
$\delta(\mathcal{H})\geq\left(\frac{t(t+1)}{2(t+2)^{2}}-3\epsilon^{1/2}\right)n^{2}$.
Fixing a $\Gamma_{t+2}$-coloring
$V(\mathcal{H}_{n}^{\prime})=V_{n,1}\cup\cdots\cup V_{n,t+4}$ of
$\mathcal{H}_{n}^{\prime}$ and let
$\mathcal{G}_{n}=\Gamma_{t+2}[V_{n,1}\cup\cdots\cup V_{n,t+4}]$ be the blowup
of $\Gamma_{t+2}$.

Since
$\rho(\mathcal{H}_{n}^{\prime})\geq\rho(\mathcal{H}_{n})-|Z_{\epsilon}|n^{2}/\binom{n}{3}\geq\rho(\mathcal{H}_{n})-6\epsilon^{1/2}\geq\frac{t(t+1)}{(t+2)^{2}}-7\epsilon^{1/2}$,
it follows from Lemma 7.2 that

$\frac{t+1}{t+2}-2800t^{4}\epsilon^{1/4}\leq\rho(\partial\mathcal{H}_{n}^{\prime})\leq\rho(\partial\mathcal{G}_{n})\leq\frac{t^{2}+3t+3}{(t+2)^{2}}+140000t^{4}\epsilon^{1/4}.$

By Claim 6.12, for every $v\in Z_{n}$ we have $L_{\mathcal{H}_{n}}(v)\cap
V_{n,i}=\emptyset$ 444Note that in the proof of Claim 6.12 we do not require
$d_{\mathcal{H}_{n}}(v)$ to be large. for all $i\in[t+4]$. Therefore,
$\rho(\partial\mathcal{H}_{n})\leq\rho(\partial\mathcal{G}_{n})+|Z_{n}|n/\binom{n}{2}\leq\rho(\partial\mathcal{G}_{n})+3\epsilon^{1/2}$.
So,

$\displaystyle\frac{t+1}{t+2}-2800t^{4}\epsilon^{1/4}\leq\rho(\partial\mathcal{H}^{\prime}_{n})\leq\rho(\partial\mathcal{H}_{n})\leq\rho(\partial\mathcal{G}_{n})+3\epsilon^{1/2}\leq\frac{t^{2}+3t+3}{(t+2)^{2}}+140001t^{4}\epsilon^{1/4}.$

Consequently,

$\displaystyle\frac{t+1}{t+2}-2800t^{4}\epsilon^{1/4}-\epsilon\leq
x\leq\frac{t^{2}+3t+3}{(t+2)^{2}}+140001t^{4}\epsilon^{1/4}+\epsilon.$

Letting $\epsilon\to 0$, we have

$\displaystyle\frac{t+1}{t+2}\leq x\leq\frac{t^{2}+3t+3}{(t+2)^{2}}.$

This completes the proof of Theorem 1.11.

##  8 Concluding remarks

$\bullet$ We defined the crossed blowup and used it to construct finite family
of triple systems with infinitely many extremal constructions. One could
extended this operation in the following way.

Instead of replacing a pair of vertices (i.e. $\\{v_{1},v_{2}\\}$) by four
vertices (i.e. $\\{v_{1},v_{1}^{\prime},v_{2},v_{2}^{\prime}\\}$), one could
replace it by $2^{k}$ vertices for $k\geq 2$.

Let $Q_{k}$ denote the vertex set of the $k$-dimensional hypercube (each
vertex is represented by a length-$k$ binary string). For $i\in[k]$ let
$Q_{k}(i,0)\subset Q_{k}$ and $Q_{k}(i,1)\subset Q_{k}$ denote the collection
of vertices whose $i$-th coordinate is $0$ and $1$, respectively.

######  Definition 8.1 ($k$-crossed blowup).

Let $k\geq 2$ be an integer. Let $\mathcal{G}$ be a $3$-graph and
$\\{v_{1},v_{2}\\}\subset V(\mathcal{H})$ be a pair with
$d_{\mathcal{G}}(v_{1},v_{2})=d\geq k$. Assume that
$N_{\mathcal{G}}(v_{1},v_{2})=\\{u_{1},\ldots,u_{d}\\}$. The $k$-crossed
blowup $\mathcal{G}\boxplus^{k}\\{v_{1},v_{2}\\}$ of $\mathcal{G}$ on
$\\{v_{1},v_{2}\\}$ is obtained in the following way.

  1. (a)

Remove all edges in $\mathcal{G}$ that contain $\\{v_{1},v_{2}\\}$,

  2. (b)

replace $\\{v_{1},v_{2}\\}$ by $2^{k}$ new vertices $Q_{k}$ so that every
vertex in $Q(1,0)$ is a clone of $v_{1}$ and every vertex in $Q(1,1)$ is a
colon of $v_{2}$,

  3. (c)

for $i\in[k-1]$ we add a set $\mathcal{E}_{i}$ of triples containing $u_{i}$
so that $L_{\mathcal{E}_{i}}(u_{i})$ is the complete bipartite graph
$B[Q(i,0),Q(i,1)]$ with two parts $Q(i,0),Q(i,1)$,

  4. (d)

for $i\in[k,d]$ we add a set $\mathcal{E}_{i}$ of triples containing $u_{i}$
so that $L_{\mathcal{E}_{i}}(u_{i})$ is the complete bipartite graph
$B[Q(k,0),Q(k,1)]$ with two parts $Q(k,0),Q(k,1)$.

123000010100110001011101111 Figure 5:
$\\{145,245,345\\}\boxplus^{3}\\{4,5\\}$, in which $L(1)$ is the complete
bipartite graph with parts $\\{000,001,010,011\\}$ and $\\{100,101,110,111\\}$
(these two squares are perpendicular to the yellow axis). Similarly to $L(2)$
and $L(3)$.

Notice that the crossed blowup we defined in Section 1 is $2$-crossed blowup.
Using a similar argument, one could extend Proposition 1.9 to $k$-crossed
blowups for all $k\geq 2$.

There is also a natural extension to $r$-graphs for every $r\geq 4$. We omit
the definition here.

$\bullet$ There are two ways to extend Theorem 1.3 to $r$-graphs for every
$r\geq 4$. One is to use $\Gamma_{t+2}$ to construct an $r$-graph in the
following way: take $r-3$ new vertices $\\{u_{1},\ldots,u_{r-3}\\}$ and let

$\displaystyle\Gamma_{t+2}^{r}=\left\\{\\{u_{1},\ldots,u_{r-3}\\}\cup E\colon
E\in\Gamma_{t+2}\right\\}.$

Following the argument as in [22] one could extend Theorem 1.3 to $r$-graphs.

Another way is to consider the crossed blowup of the $r$-uniform complete
graph $K_{t+2}^{r}$. Following the argument as in the present paper one could
extend Theorem 1.3 to $r$-graphs as well.

$\bullet$ For $t=1$ one could use the fact that the set $Z(\Gamma_{1})$ is a
two-dimensional simplex

$\displaystyle\left\\{\alpha\vec{x}_{1}+\beta\vec{x}_{2}+(1-\alpha-\beta)\vec{x}_{3}\colon\alpha\geq
0,\beta\geq 0,\alpha+\beta\leq 1\right\\},$

where $\vec{x}_{1}=\left(\frac{1}{3},0,\frac{1}{3},0,0,\frac{1}{3}\right)$,
$\vec{x}_{2}=\left(0,\frac{1}{3},\frac{1}{3},0,0,\frac{1}{3}\right)$, and
$\vec{x}_{3}=\left(0,\frac{1}{3},0,\frac{1}{3},\frac{1}{3},0,\right)$, to
improve Theorem 1.3 (b) to show that the number of maximum
$\mathcal{F}_{1}$-free $3$-graphs on $n$ vertices is $\Theta(n^{2})$.

## References

  * [1] B. Andrásfai, P. Erdős, and V. T. Sós.  On the connection between chromatic number, maximal clique and minimal degree of a graph.  Discrete Math., 8:205–218, 1974.
  * [2] R. Baber and J. Talbot.  Hypergraphs do jump.  Combin. Probab. Comput., 20(2):161–171, 2011.
  * [3] W. G. Brown.  On an open problem of Paul Turán concerning 3-graphs.  In Studies in pure mathematics, pages 91–93. Springer, 1983.
  * [4] F. Chung and L. Lu.  An upper bound for the Turán number $t_{3}(n,4)$.  J. Comb. Theory, Ser. A, 87(2):381–389, 1999.
  * [5] D. de Caen.  On upper bounds for $3$-graphs without tetrahedra.  volume 62, pages 193–202. 1988.  Seventeenth Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, MB, 1987).
  * [6] P. Erdős and M. Simonovits.  A limit theorem in graph theory.  Studia Sci. Math. Hungar., 1:51–57, 1966.
  * [7] P. Erdős and A. H. Stone.  On the structure of linear graphs.  Bull. Amer. Math. Soc., 52:1087–1091, 1946.
  * [8] D. G. Fon-Der-Flaass.  On a method of construction of $(3,4)$-graphs.  Mat. Zametki, 44(4):546–550, 1988.
  * [9] P. Frankl and Z. Füredi.  An exact result for 3-graphs.  Discrete Math., 50:323–328, 1984.
  * [10] P. Frankl and Z. Füredi.  Extremal problems whose solutions are the blowups of the small Witt-designs.  J. Combin. Theory Ser. A, 52(1):129–147, 1989.
  * [11] P. Frankl, Y. Peng, V. Rödl, and J. Talbot.  A note on the jumping constant conjecture of Erdős.  J. Combin. Theory Ser. B, 97(2):204–216, 2007.
  * [12] P. Frankl and V. Rödl.  Hypergraphs do not jump.  Combinatorica, 4(2-3):149–159, 1984.
  * [13] G. Katona.  A theorem of finite sets.  In Theory of graphs (Proc. Colloq., Tihany, 1966), pages 187–207, 1968.
  * [14] P. Keevash.  Hypergraph Turán problems.  In Surveys in combinatorics 2011, volume 392 of London Math. Soc. Lecture Note Ser., pages 83–139. Cambridge Univ. Press, Cambridge, 2011.
  * [15] P. Keevash.  Counting Steiner triple systems.  In European Congress of Mathematics, pages 459–481. Eur. Math. Soc., Zürich, 2018.
  * [16] A. V. Kostochka.  A class of constructions for Turán’s (3,4)-problem.  Combinatorica, 2:187–192, 1982.
  * [17] J. B. Kruskal.  The number of simplices in a complex.  In Mathematical optimization techniques, pages 251–278. Univ. of California Press, Berkeley, Calif., 1963.
  * [18] X. Liu.  Cancellative hypergraphs and steiner triple systems.  arXiv preprint arXiv:1912.11917, 2019.
  * [19] X. Liu.  New short proofs to some stability theorems.  European J. Combin., 96:Paper No. 103350, 8, 2021.
  * [20] X. Liu and D. Mubayi.  The feasible region of hypergraphs.  J. Comb. Theory, Ser. B, 148:23–59, 2021.
  * [21] X. Liu and D. Mubayi.  A hypergraph Turán problem with no stability.  Combinatorica, pages 1–30, 2022.
  * [22] X. Liu, D. Mubayi, and C. Reiher.  Hypergraphs with many extremal configurations II.  In preparation.
  * [23] X. Liu, D. Mubayi, and C. Reiher.  Hypergraphs with many extremal configurations.  arXiv preprint arXiv:2102.02103, 2021.
  * [24] X. Liu, D. Mubayi, and C. Reiher.  A unified approach to hypergraph stability.  arXiv preprint arXiv:2104.00167, 2021.
  * [25] D. Mubayi.  Structure and stability of triangle-free set systems.  Trans. Amer. Math. Soc., 359(1):275–291, 2007.
  * [26] O. Pikhurko.  On possible Turán densities.  Israel J. Math., 201(1):415–454, 2014.
  * [27] A. Razborov.  On 3-hypergraphs with forbidden 4-vertex configurations.  SIAM J. Discrete Math., 24(3):946–963, 2010.
  * [28] A. Sidorenko.  What we know and what we do not know about Turán numbers.  Graphs Combin., 11(2):179–199, 1995.
  * [29] M. Simonovits.  A method for solving extremal problems in graph theory, stability problems.  In Theory of Graphs (Proc. Colloq., Tihany, 1966), pages 279–319. Academic Press, New York, 1968.
  * [30] P. Turán.  On an extermal problem in graph theory.  Mat. Fiz. Lapok, 48:436–452, 1941.
  * [31] A. A. Zykov.  On some properties of linear complexes.  Mat. Sbornik N.S., 24(66):163–188, 1949.