# Ramsey and Turán numbers of sparse hypergraphs

Jacob Fox  ,  Maya Sankar  ,  Michael Simkin  Department of Mathematics,
Massachusetts Institute of Technology<EMAIL_ADDRESS>,  Jonathan Tidor  and
Yunkun Zhou  Department of Mathematics, Stanford University  {jacobfox,
mayars, jtidor<EMAIL_ADDRESS>
###### Abstract.

Degeneracy plays an important role in understanding Turán- and Ramsey-type
properties of graphs. Unfortunately, the usual hypergraphical generalization
of degeneracy fails to capture these properties. We define the skeletal
degeneracy of a $k$-uniform hypergraph as the degeneracy of its $1$-skeleton
(i.e., the graph formed by replacing every $k$-edge by a $k$-clique). We prove
that skeletal degeneracy controls hypergraph Turán and Ramsey numbers in a
similar manner to (graphical) degeneracy.

Specifically, we show that $k$-uniform hypergraphs with bounded skeletal
degeneracy have linear Ramsey number. This is the hypergraph analogue of the
Burr–Erdős conjecture (proved by Lee). In addition, we give upper and lower
bounds of the same shape for the Turán number of a $k$-uniform $k$-partite
hypergraph in terms of its skeletal degeneracy. The proofs of both results use
the technique of dependent random choice. In addition, the proof of our Ramsey
result uses the ‘random greedy process’ introduced by Lee in his resolution of
the Burr–Erdős conjecture.

Fox was supported a Packard Fellowship and by NSF Awards DMS-1800053 and
DMS-2154169. Sankar was supported by a Fannie and John Hertz Foundation
Fellowship and NSF Graduate Research Fellowship DGE-1656518. Simkin was
partially supported by the Center of Mathematical Sciences and Applications at
Harvard University. Tidor was supported by a Stanford Science Fellowship. Zhou
was supported by NSF Graduate Research Fellowship DGE-1656518.

##  1\. Introduction

Two central problems in extremal combinatorics are to better understand the
Turán and Ramsey numbers of graphs and hypergraphs. To recap the definitions,
let $H$ be a $k$-uniform hypergraph and $n,q$ be positive integers. The Turán
number $\operatorname{ex}(n,H)$ is the maximum number of edges in a
$k$-uniform hypergraph on $n$ vertices that is $H$-free. The Ramsey number
$r(H;q)$ is the minimum positive integer $N$ for which every coloring of the
edges of the complete $k$-uniform hypergraph $K_{N}^{(k)}$ using $q$ colors
contains a monochromatic copy of $H$.

Estimating Ramsey and Turán numbers has remained a challenging problem (see,
for example, the surveys [30, 12, 37] and the book [25]). It is therefore
natural to seek parameters of the hypergraph $H$ that control these numbers.
As we will explain, for $k=2$ (i.e., the graph case) the notion of degeneracy
has been central in this regard. The purpose of this paper is to propose an
analogue for hypergraphs, which we term skeletal degeneracy, and to prove that
it emulates the role of degeneracy for graphs, at least as it concerns Turán
and Ramsey numbers.

Among the earliest results in modern combinatorics are Turán’s theorem and
Ramsey’s theorem [41, 38]. Turán’s theorem determines
$\operatorname{ex}(n,K_{r})$ exactly, showing that among $K_{r}$-free graphs
on $n$ vertices the complete balanced $(r-1)$-partite graph has the most edges
(the case $r=3$ is due to Mantel [35] and goes back more than a century).
Ramsey’s theorem guarantees that Ramsey numbers exist. Besides their inherent
interest, Turán and Ramsey problems have served as strong motivations to
develop new methods and techniques. For instance, the early quantitative upper
bound $r(K_{r};2)\leq\binom{2r-2}{r-1}<4^{r}$ was proved by Erdős and Szekeres
[21]. Despite much effort, the exponent $4$ in the upper bound resisted
improvement for many decades until the very recent breakthrough of Campos,
Griffiths, Morris, and Sahasrabudhe [6].

Additionally, an early and extremely influential use of the probabilistic
method in combinatorics was Erdős’s lower bound on $r(K_{r};2)$ leveraging the
random graph $\mathbb{G}(n;1/2)$ [18]. To this day, newcomers to the field
often see this example before any other. In 1975, Spencer [39] slightly
improved the lower bound, in a paper that introduced a common form of the
Lovász local lemma, but this remains the state of the art.

With respect to Turán numbers, a consequence of the Erdős–Stone–Simonovits
theorem [17, 20] is that for a fixed graph $H$ with chromatic number
$\chi=\chi(H)$ the extremal number satisfies
$\operatorname{ex}(n,H)=(1-1/(\chi-1)+o(1))n^{2}\\!/2$. Thus, for non-
bipartite $H$, the asymptotics of $\operatorname{ex}(n,H)$ are determined
exactly by $\chi(H)$.

In contrast to the non-bipartite case, for bipartite $H$ the
Erdős–Stone–Simonovits theorem only says that
$\operatorname{ex}(n,H)=o(n^{2})$, and these numbers are far less understood.
In fact, even determining the order of magnitude of $\operatorname{ex}(n,H)$
is open in general. In the search for graphical parameters of $H$ that control
$\operatorname{ex}(n,H)$, a natural candidate is the degeneracy of $H$, the
smallest $d$ such that every subgraph of $H$ has minimum degree at most $d$. A
longstanding conjecture of Erdős [19] states that if $H$ is a $d$-degenerate
bipartite graph then the Turán number $\operatorname{ex}(n,H)$ has order at
most $n^{2-1/d}$. Despite much interest (see, for example, [22, 13, 14, 26,
27, 28, 29, 4, 40]), the conjecture remains open. Currently, the best lower
bound is $\operatorname{ex}(n,H)\geq\Omega(n^{2-2/d})$, achieved by a
straightforward probabilistic construction. The best known upper bound is due
to Alon, Krivelevich, and Sudakov [2]. In an early application of dependent
random choice (which also figures prominently in this paper) they proved the
following theorem.

######  Theorem 1.1 ([2, Theorem 3.5]).

For every $d$-degenerate bipartite graph $H$,

$\operatorname{ex}(n,H)\leq O_{H}\left(n^{2-\frac{1}{4d}}\right).$

In addition to controlling the Turán exponent, degeneracy plays an important
role in graph Ramsey theory. In 1973, Burr and Erdős [5] conjectured that
graphs with bounded degeneracy have Ramsey number linear in the number of
vertices. They also made the related, weaker, conjecture that bounded degree
graphs have linear Ramsey number. These conjectures garnered much interest
(see, for instance, [23, 24, 11] for the bounded degree case and [31, 33, 22]
for the bounded degeneracy case). Although the bounded degree case was
resolved by Chvatál, Rödl, Szemerédi, and Trotter [7] in 1983, it would take
until 2017 until the bounded degeneracy conjecture was proved by Lee [34].

######  Theorem 1.2 ([34, Theorem 1.1]).

For every $d$-degenerate $n$-vertex graph $H$,

$r(H;2)\leq O_{d}(n).$

In this paper, we seek hypergraph analogues of Theorems 1.1 and 1.2. A naïve
attempt would be to use the standard definition of hypergraph degeneracy: the
_degeneracy_ of a hypergraph $H$ is the least $d$ such that every
subhypergraph of $H$ has minimum degree at most $d$. This notion was studied
by Kostochka and Rödl [32], who showed that the natural analogue of the
Burr–Erdős conjecture fails for hypergraphs. Specifically, they described a
family of 1-degenerate 4-uniform hypergraphs $H$ on $n$ vertices satisfying
$r(H;2)\geq 2^{\Omega(n^{1/3})}$, as well as more complicated examples showing
that the conjecture fails for 3-uniform hypergraphs. (See also [8] for more
examples of this phenomenon.)

It is also straightforward to show that the hypergraph analogue of Erdős’s
conjecture regarding Turán numbers is false. Indeed, for every $\varepsilon>0$
there is a 1-degenerate $k$-uniform $k$-partite hypergraph $H$ with
$\operatorname{ex}(n,H)>n^{k-\varepsilon}$. We give the details of this simple
construction in Section 3 (see Corollary 3.5).

To overcome the issues above we introduce a new notion of degeneracy for
hypergraphs that we call skeletal degeneracy.

######  Definition 1.3.

Let $H$ be a $k$-uniform hypergraph. For $0\leq i<k$, its _$i$ -skeleton_
$H^{(i)}$ is the $(i+1)$-uniform hypergraph on the same vertex set with all
$(i+1)$-edges that are contained in some $k$-edge of $H$. The _$i$ -th
skeletal degeneracy_ of $H$, denoted $d_{i}(H)$, is the degeneracy of
$H^{(i)}$, i.e., the least $d$ such that every subhypergraph of $H^{(i)}$ has
minimum degree at most $d$. Equivalently, this is the smallest $d$ for which
there exists an ordering $v_{1},\ldots,v_{n}$ of $V(H)$ in which each vertex
$v_{j}$ is the highest-numbered vertex of at most $d$ of the $(i+1)$-edges of
$H^{(i)}$. We refer to $d_{1}(H)$ simply as the _skeletal degeneracy_ of $H$.

For a $k$-uniform hypergraph $H$ the $(k-1)$-st skeletal degeneracy
$d_{k-1}(H)$ agrees with the standard definition of degeneracy given above.
Moreover, although $d_{k-1}(H)$ is not a good predictor of the Turán and
Ramsey properties of $H$, we will show that the skeletal degeneracy $d_{1}(H)$
is.

Observe that the skeletal degeneracy can equivalently be defined as the
degeneracy of the graph formed by replacing every $k$-edge of a hypergraph $H$
by a $k$-clique. Although it may seem that this definition does not capture
the hypergraph structure of $G$, we show that it is nevertheless sufficient to
control the Turán and Ramsey properties of $H$. Our first of two main results
shows that this is the case for Turán numbers.

######  Theorem 1.4.

For every $k\geq 2$ there exist constants $C_{k},c_{k}>0$ such that the
following holds. For any $k$-uniform $k$-partite hypergraph $H$ with at least
two edges, the Turán number of $H$ satisfies

$\Omega_{k}\left(n^{k-\frac{C_{k}}{d_{1}(H)}}\right)\leq\operatorname{ex}(n,H)\leq
O_{H}\left(n^{k-\frac{c_{k}}{d_{1}(H)^{k-1}}}\right).$

Note that for $k=2$, the exponent in the upper and lower bounds are both of
the shape ${2-c/d_{1}(H)}$. However, as $k$ increases, the gap between the
upper and lower bounds in this theorem increases. In Section 3 we give
examples showing that (up to the values of the constants $C_{k},c_{k}$) both
growth rates are possible. We discuss this more and conjecture more precise
bounds in Section 6.

We remark that Theorem 1.4 focuses on the $k$-partite case because the
asymptotic order of magnitude in the non-partite case is easy to ascertain.
Indeed, if $H$ is not $k$-partite, then
$\operatorname{ex}(n,H)=\Theta_{H}(n^{k})$; the upper bound is trivial and the
lower bound is witnessed by the complete balanced $k$-partite hypergraph. This
is not to say that the non-partite case is fully understood. On the contrary,
even determining the leading asymptotics of $\operatorname{ex}(n,K_{4}^{(3)})$
(i.e., tetrahedra-free $3$-uniform hypergraphs) is a notable open problem.
Nevertheless, we restrict our attention to the $k$-partite case, where even
the order of magnitude is unknown.

Our second main result concerns Ramsey numbers. Conlon, Sudakov, and the first
author asked if the hypergraph analogue of the Burr–Erdős conjecture holds for
skeletal degeneracy [1, Problem 1.26]. We answer this question in the
affirmative.

######  Theorem 1.5.

Let $H$ be a $k$-uniform hypergraph on $n$ vertices with skeletal degeneracy
${d_{1}({H})}=d$. Then the $q$-color Ramsey number of $H$ satisfies

$r(H;q)\leq O_{k,d,q}(n).$

One nice application of this theorem is to triangulations of surfaces. Let
$\Sigma$ be a surface of genus $g$ and let $H$ be a 3-uniform $n$-vertex
hypergraph which triangulates $\Sigma$. It can be deduced from Euler’s formula
(see, e.g., [36, Theorem 4.4.4]) that $d_{1}(H)\leq O(\sqrt{g})$. Thus by
Theorem 1.5 we see that $r(H;q)\leq O_{g,q}(n)$ where the hidden constant only
depends on the genus and the number of colors. To the best of our knowledge,
this family of hypergraphs was not previously known to have linear Ramsey
number. One can also show that the dependence on genus in the constant in
front of the linear term is necessary due to an example based on embedding a
large clique into a surface of large genus.

The remainder of this paper is organized as follows. We prove the upper and
lower bounds on Theorem 1.4 in Sections 2 and 3, respectively. Using the same
techniques, we give a short proof of an almost-linear bound on the Ramsey
number in Section 4. In Section 5, we prove Theorem 1.5. Finally, in Section 6
we give some open problems.

Acknowledgements: We thank David Conlon for helpful discussions early in this
project’s development.

##  2\. Upper bounds on the Turán number

In this section we prove the upper bound in Theorem 1.4. We show how to find a
$k$-uniform $k$-partite hypergraph $H$ in any $k$-uniform $k$-partite host
hypergraph $G$ with sufficiently many edges. We do this by first pruning $G$
so that all small sets of $(k-1)$-edges in $G$ have many mutual extensions to
$k$-edges in $G$. We then show how this extending property suffices to embed
$H$ in $G$.

######  Notation.

For a $k$-partite $k$-uniform hypergraph $G$ with parts $V_{1},\dots,V_{k}$,
write $V_{-t}=\bigcup_{i\neq t}V_{i}$. For $S\subseteq V(G)$, we use the
notation $G^{(k-2)}[S]$ for the subhypergraph of the $(k-2)$-skeleton of $G$
induced on the vertices $S$. For example, $G^{(k-2)}[V_{-t}]$ is the
$(k-1)$-partite $(k-1)$-uniform hypergraph on $V_{-t}$ with edge set $\\{e\cap
V_{-t}:e\in E(G)\\}$.

######  Definition 2.1.

Let $G$ be a $k$-partite $k$-uniform hypergraph on vertex set $V_{1}\sqcup
V_{2}\sqcup\cdots\sqcup V_{k}$. For a set $F\subseteq E(G^{(k-2)})$, we say
that a vertex $v\in V(G)$ is a _mutual extension of $F$_ if $e\cup\\{v\\}\in
E(G)$ for each $e\in F$. For each $1\leq t\leq k$ and positive integers $a,d$,
we say that $G$ is $(a,d)$-vertex-extending to $V_{t}$ if for every set $S$ of
at most $d$ vertices in $V_{-t}$, the set $E(G^{(k-2)}[S])$ of $(k-1)$-edges
induced by $S$ has at least $a$ mutual extensions (in $V_{t}$).

######  Lemma 2.2.

Let $d\in\mathbb{N}$ and $k\geq 3$. There exist a constant $c_{k}>0$ and a
constant $n_{0}=n_{0}(k,d)$ such that the following holds. If $G$ is a
$k$-partite $k$-uniform hypergraph on vertex set $V_{1}\sqcup\cdots\sqcup
V_{k}$ with $n\geq n_{0}$ vertices in each part and at least
$n^{k-c_{k}/d^{k-1}}$ edges, then it contains a nonempty subhypergraph
$G^{\prime}\subseteq G$ which is $(n^{1/3},d)$-vertex-extending to each part.

This lemma builds on the following result, which uses the technique of
dependent random choice.

######  Lemma 2.3.

Let $d\geq 2$, $k\geq 3,t,h,n,\lambda$ be positive integers with $1\leq t\leq
k$, and let $p\in(0,1/2)$ be a real number. Suppose these parameters also
satisfy the following two inequalities:

$p^{(\lambda+1)d}n\geq 1\qquad\text{and}\qquad
n^{-1}\geq\left(\frac{h}{n}\right)^{\lambda
d}\binom{kn}{d}2^{\binom{d}{k-1}}.$

Then, given any $k$-partite $k$-uniform hypergraph $G$ on vertex set
$V_{1}\sqcup\cdots\sqcup V_{k}$ with $n$ vertices in each part and at least
$pn^{k}$ edges, the following holds. If $G$ is $(h,(\lambda+1)d)$-vertex-
extending to $V_{r}$ for all $r<t$ then there exists a subhypergraph
$G^{\prime}$ of $G$ on the same vertex set with at least
$p^{(\lambda+1)d}n^{k}$ edges that is $(h,d)$-vertex-extending to $V_{r}$ for
all $r\leq t$.

###### Proof.

Choose $u=\lambda d$ vertices uniformly at random from $V_{t}$ with
replacement and let $X_{t}$ be the resulting set of vertices. Let $G^{\prime}$
be the subhypergraph of $G$ containing only those edges
$e=\\{e_{1},\ldots,e_{k}\\}$ for which
$(e\setminus\\{e_{t}\\})\cup\\{x_{t}\\}$ is an edge of $G$ for each $x_{t}\in
X_{t}$.

For each $(k-1)$-edge $e\in E(G^{(k-2)}[V_{-t}])$, let $d_{G}(e)$ be the
number of vertices (in $V_{t}$) that are mutual extensions of $\\{e\\}$. Then
the probability that any such $e$ remains in $G^{\prime}$ is
$(d_{G}(e)/n)^{u}$. Since the number of edges of $G$ satisfies
$e(G)=\sum_{e\in E(G^{(k-2)}[V_{-t}])}d_{G}(e)\geq pn^{k}$, by convexity

$\mathbb{E}[e(G^{\prime})]=\sum_{e\in
E(G^{(k-2)}[V_{-t}])}d_{G}(e)\left(\frac{d_{G}(e)}{n}\right)^{u}\geq\frac{e(G)^{u+1}}{n^{u}e(G^{(k-2)}[V_{-t}])^{u}}\geq\frac{e(G)^{u+1}}{n^{ku}}\geq
p^{u+1}n^{k}.$

For a set of edges $F\subseteq E(G^{(k-2)}[V_{-t}])$ with fewer than $h$
mutual extensions in $G$, the probability that this subset remains in
$(G^{\prime})^{(k-2)}[V_{-t}]$ is less than
$\left(\frac{h}{n}\right)^{u}=\left(\frac{h}{n}\right)^{\lambda d}$.
Additionally, the total number of such sets $F\subseteq E(G^{(k-2)}[V_{-t}])$
that are spanned by at most $d$ vertices is less than $\binom{kn}{d}\cdot
2^{\binom{d}{k-1}}$. Let $P$ be the event that $G^{\prime}$ is $(h,d)$-vertex-
extending to $V_{t}$, i.e., the event that $G^{\prime}$ does not contain any
such set $F$. Because the parameters satisfy the inequality
$n^{-1}\geq\left(\frac{h}{n}\right)^{\lambda d}\binom{kn}{d}\cdot
2^{\binom{d}{k-1}}$,

$\mathbb{E}[e(G^{\prime})\mid
P]\geq\mathbb{E}[e(G^{\prime})]-\Pr[\overline{P}]\mathop{\mathbb{E}}[e(G^{\prime})\mid\overline{P}]\geq
p^{u+1}n^{k}-n^{k-1}.$

Because $p<1/2$ and $d\geq 2$, we have that $p^{u+1}n^{k}\geq 2p^{u+2}n^{k}$
and $n^{k-1}\leq p^{(\lambda+1)d}n^{k}\leq p^{u+2}n^{k}$. Hence,
$\mathop{\mathbb{E}}[e(G^{\prime})\mid P]\geq p^{u+2}n^{k}$. It follows that
there is a set $X_{t}$ of at most $u$ vertices such that the corresponding
hypergraph $G^{\prime}$ contains at least $p^{u+2}n^{k}\geq
p^{(\lambda+1)d}n^{k}$ edges and is $(h,d)$-vertex-extending to $V_{t}$.

It remains to argue that $G^{\prime}$ is also $(h,d)$-vertex-extending to
$V_{r}$ for each $1\leq r<t$. Let $S\subseteq V_{-r}$ be a set of at most $d$
vertices. Then $S\cup X_{t}$ is a set of at most $d+u\leq(\lambda+1)d$
vertices in $V_{-r}$. Because $G$ is $(h,(\lambda+1)d)$-vertex-extending to
$V_{r}$, there are at least $h$ vertices (in $V_{r}$) that are mutual
extensions in $G$ of $E(G^{(k-2)}[S\cup X_{t}])$. For each mutual extension
$v\in V_{r}$ and each edge $e\in E((G^{\prime})^{(k-2)}[S])$, we claim that
$e\cup\\{v\\}\in E(G^{\prime})$. Indeed, because $e\in
E((G^{\prime})^{(k-2)}[V_{-r}])$, there exists some $b_{r}\in V_{r}$ such that
$e\cup\\{b_{r}\\}\in E(G^{\prime})$. Writing $\\{e_{t}\\}=e\cap V_{t}$, this
implies that $(e\setminus\\{e_{t}\\})\cup\\{b_{r},x_{t}\\}\in E(G)$ for every
$x_{t}\in X_{t}$. Hence, $(e\setminus\\{e_{t}\\})\cup\\{x_{t}\\}\in
E(G^{(k-2)}[S\cup X_{t}])$, implying that
$(e\setminus\\{e_{t}\\})\cup\\{x_{t},v\\}\in E(G)$ for every $x_{t}\in X_{t}$.
By construction, it follows that $e\cup\\{v\\}\in E(G^{\prime})$. Thus, there
are at least $h$ vertices (in $V_{r}$) that are mutual extensions in
$G^{\prime}$ of $E((G^{\prime})^{(k-2)}[S])$, so $G^{\prime}$ is
$(h,d)$-vertex-extending to $V_{r}$. ∎

We state a corollary of the prior lemma that is easier to work with.

######  Corollary 2.4.

Let $d\geq 4$, $k\geq 3$, $t$ be positive integers with $1\leq t\leq k$. Then
for any $\varepsilon\in(0,\frac{1}{3d}]$ and all $n\geq
n_{0}=n_{0}(k,d,\varepsilon)$, the following holds. Let $G$ be a $k$-partite
$k$-uniform hypergraph on vertex set $V_{1}\sqcup\cdots\sqcup V_{k}$ with $n$
vertices in each part. Suppose that $G$ is $(n^{1/3},3d)$-vertex-extending to
$V_{r}$ for all $r<t$ and that $e(G)\geq n^{k-\varepsilon}$.

Then there exists a subhypergraph $G^{\prime}$ of $G$ on the same vertex set
and a nonempty subset $X_{t}\subseteq V_{t}$ such that $G^{\prime}$ is
$(n^{1/3},d)$-vertex-extending to $V_{r}$ for all $r\leq t$, we have
$e(G^{\prime})\geq n^{k-3d\varepsilon}$, and, moreover, the edges of
$G^{\prime}$ are exactly those edges $e\in E(G)$ satisfying $(e\setminus
V_{t})\cup\\{x_{t}\\}\in E(G)$ for each $x_{t}\in X_{t}$.

###### Proof.

We apply Lemma 2.3 with parameters $p=n^{-\varepsilon}$, $\lambda=2$, and
$h=n^{1/3}$. For $n$ sufficiently large, the assumption $p\in(0,1/2)$ is met.
Moreover, $e(G)\geq n^{k-\varepsilon}=pn^{k}$ and $G$ is
$(n^{1/3},3d)$-vertex-extending to $V_{r}$ for all $r<t$.

It remains to check that the two inequalities are satisfied. Because
$\varepsilon\leq\frac{1}{3d}$, it holds that
$p^{(\lambda+1)d}n=n^{1-3d\varepsilon}\geq 1$. Additionally,

$n\left(\frac{h}{n}\right)^{\lambda d}\binom{kn}{d}2^{\binom{d}{k-1}}\leq
n\cdot n^{-4d/3}(kn)^{d}2^{\binom{d}{k-1}}=n^{1-d/3}\cdot
k^{d}2^{\binom{d}{k-1}}.$

Because $d\geq 4$, the right side is less than $1$ for all sufficiently large
$n$. Thus, the hypotheses of Lemma 2.3 are satisfied.

Applying the lemma yields a subhypergraph $G^{\prime}$ with $e(G^{\prime})\geq
p^{(\lambda+1)d}n^{k}=n^{k-3d\varepsilon}$ satisfying the desired vertex-
extending property. ∎

Applying Corollary 2.4 repeated $k$ times, one may show that there is a
constant $c_{k}>0$ such that if $G$ is an $n$-vertex hypergraph with at least
$n^{k-c_{k}/d^{k}}$ edges and $n$ is sufficiently large in terms of $k$ and
$d$, then $G$ has a nonempty subhypergraph that is $(n^{1/3},d)$-vertex-
extending to every part. However, to reach $n^{k-c_{k}/d^{k-1}}$ (i.e., the
bound in Lemma 2.2), the last step must be handled slightly differently.

###### Proof of Lemma 2.2.

We apply Corollary 2.4 repeated $k-1$ times to produce a sequence of
hypergraphs $G=G_{0}\supseteq G_{1}\supseteq G_{2}\supseteq\cdots\supseteq
G_{k-1}$. In detail, for each $t=1,\ldots,k-1$, define $d_{t}=3^{k-t+1}d$.
Given sufficiently small $\varepsilon_{0}>0$, define

$\varepsilon_{i}=\left(\prod_{t=1}^{i}3d_{t}\right)\varepsilon_{0}.$

For $\varepsilon_{0}\leq
3^{-k}3^{-\frac{k(k+1)}{2}}d^{-k+1}=3^{-\frac{k(k+3)}{2}}d^{-k+1}$ we have
$\varepsilon_{i}\leq\tfrac{1}{3d}$ for all $1\leq i\leq k-2$ and
$\varepsilon_{k-1}\leq\tfrac{1}{3}<\tfrac{1}{2}$.

Suppose $n$ is sufficiently large in terms of $k,d$, and that $e(G)\geq
n^{k-\varepsilon_{0}}$. Let $G_{i}$ be the subhypergraph of $G_{i-1}$ obtained
by applying Corollary 2.4 with parameters
$(d,k,t,\varepsilon)=(d_{i},k,i,\varepsilon_{i})$. If $e(G_{i-1})\geq
n^{k-\varepsilon_{i-1}}$, then $e(G_{i})\geq
n^{k-3d_{i}\varepsilon_{i-1}}=n^{k-\varepsilon_{i}}$.

After $k-1$ iterations, this process produces a hypergraph $G_{k-1}$ with
$e(G_{k-1})\geq n^{k-\varepsilon_{k-1}}\geq n^{k-1/2}$ that is
$(n^{1/3},9d)$-vertex-extending to $V_{r}$ for every $1\leq r\leq k-1$.
Moreover, for each $1\leq r\leq k-1$, there exists a nonempty subset
$X_{r}\subseteq V_{r}$ such that each edge $e\in E(G_{r-1})$ is in $E(G_{r})$
if and only if $(e\setminus V_{r})\cup\\{x_{r}\\}\in E(G_{r-1})$ for every
$x_{r}\in X_{r}$.

######  Claim 2.5.

For every $e\in E(G_{k-1})$ we have $X_{1}\times\cdots\times
X_{k-1}\times(e\cap V_{k})\subseteq E(G_{k-1})$.

###### Proof.

For each $t$, let $\\{e_{t}\\}=e\cap V_{t}$. We first show that
$\\{e_{1}\\}\times\cdots\times\\{e_{t}\\}\times X_{t+1}\times\cdots\times
X_{k-1}\times\\{e_{k}\\}\subseteq E(G_{t})$, using induction on
$t=k-1,\dots,0$. When $t=k-1$, this trivially holds. Suppose that this is true
for $t\geq 1$, and we would like to show this for $t-1$.

Let $f\in\\{e_{1}\\}\times\cdots\times\\{e_{t}\\}\times
X_{t+1}\times\cdots\times X_{k-1}\times\\{e_{k}\\}$. Because $f\in E(G_{t})$,
it holds that $(f\setminus V_{t})\cup\\{x_{t}\\}\in E(G_{t-1})$ for all
$x_{t}\in X_{t}$. This means that
$\\{e_{1}\\}\times\cdots\times\\{e_{t-1}\\}\times X_{t}\times
X_{t+1}\times\cdots\times X_{k-1}\times\\{e_{k}\\}\subseteq E(G_{t-1})$,
completing the induction.

We have established that $X_{1}\times\cdots\times
X_{k-1}\times\\{e_{k}\\}\subseteq E(G_{0})$. We now use induction to prove
that $X_{1}\times\cdots\times X_{k-1}\times\\{e_{k}\\}\subseteq E(G_{t})$ for
all $0\leq t\leq k-1$. Suppose that this holds for $t-1$ where $t\geq 1$. We
would like to show this for $t$. Let $f\in X_{1}\times\cdots\times
X_{k-1}\times\\{e_{k}\\}$. By the inductive hypothesis, $(f\setminus
V_{t})\cup\\{x_{t}\\}\in X_{1}\times\cdots\times
X_{k-1}\times\\{e_{k}\\}\subseteq E(G_{t-1})$ for all $x_{t}\in X_{t}$. Hence,
by construction, we know that $f\in E(G_{t})$. When $t=0$, this inductive
argument establishes $X_{1}\times\cdots\times
X_{k-1}\times\\{e_{k}\\}\subseteq E(G_{k-1})$, as desired. ∎

Let $B_{k}\subseteq V_{k}$ be the set of vertices incident to at least one
edge of $G_{k-1}$. Then $n^{k-1}|B_{k}|\geq e(G_{k-1})\geq n^{k-1/2}$, so
$|B_{k}|\geq n^{1/2}$. Also, by Claim 2.5, we have that
$X_{1}\times\cdots\times X_{k-1}\times B_{k}\subseteq E(G_{k-1})$. Now choose
$8d$ vertices uniformly at random from $B_{k}$ with replacement and let
$X_{k}$ be the resulting set of vertices. Let $G_{k}$ be the subhypergraph of
$G_{k-1}$ containing only those edges $e=\\{e_{1},\dots,e_{k}\\}$ for which
$(e\setminus V_{k})\cup\\{x_{k}\\}$ is an edge of $G_{k-1}$ for each $x_{k}\in
X_{k}$. (This is identical to the previous procedure except that $X_{k}$ is
chosen from $B_{k}$ instead of from $V_{k}$.) We note that $X_{1}\times
X_{2}\times\cdots\times X_{k}\subseteq E(G_{k})$ by construction, so $G_{k}$
is not empty. To complete the proof we need to show that $G_{k}$ is
$(n^{1/3},d)$-vertex-extending to each part.

To show that $G_{k}$ is $(n^{1/3},d)$-vertex-extending to $V_{k}$ we rely on
the argument used to prove Lemma 2.3. There are fewer than $\binom{kn}{d}\cdot
2^{\binom{d}{k-1}}$ edge sets spanned by a size-$d$ vertex set in
$V(G)\setminus V_{k}$. For each such set with at most $n^{1/3}$ mutual
extensions in $G_{k-1}$, the probability that it is retained in $G_{k}$ is at
most $(n^{1/3}/|B_{k}|)^{8d}\leq n^{-4d/3}$. Applying a union bound, the
probability that $E(G_{k})$ contains such a subset is at most $O(n^{-d/3})$.
Hence, when $n$ is sufficiently large, $G_{k}$ is $(n^{1/3},d)$-vertex-
extending to $V_{k}$ with positive probability.

It remains to prove that $G_{k}$ is $(n^{1/3},d)$-vertex extending to $V_{r}$
for each $1\leq r<k$. Here too we mimic the proof of Lemma 2.3. Fix $1\leq
r<k$ and consider any $S\subseteq V(G)\setminus V_{r}$ of size $d$. Set
$S^{\prime}=S\cup X_{t}$ and observe that $|S^{\prime}|\leq 9d$. Recall that
$G_{k-1}$ is $(n^{1/3},9d)$-vertex-extending to $V_{r}$. Hence, there is a set
$A_{S}\subseteq V_{r}$ of size at least $n^{1/3}$ such that, for every $e\in
E(G_{k-1}^{(k-2)}[S^{\prime}])$ and every $v\in A_{S}$, we have
$e\cup\\{v\\}\in E(G_{k-1})$. We show that for every $e\in
E(G_{k}^{(k-2)}[S])$ and every $v\in A_{S}$ it is the case that
$e\cup\\{v\\}\in E(G_{k})$, thus witnessing the vertex extension property of
$G_{k}$. Let $e\in E(G_{k}^{(k-2)}[S])$. By definition, there exists a vertex
$b\in V_{r}$ such that $e\cup\\{b\\}\in E(G_{k})$. By construction, this
implies that $(e\setminus\\{e_{k}\\})\cup\\{b,x\\}\in E(G_{k-1})$, and hence
$(e\setminus\\{e_{k}\\})\cup\\{x\\}\in E(G_{k-1}^{(k-2)}[S^{\prime}])$, for
each $x\in X_{k}$. By the defining property of $A_{S}$, it holds that
$(e\setminus\\{e_{k}\\})\cup\\{x,v\\}\in E(G_{k-1})$ for each $v\in A_{S}$ and
$x\in X_{k}$, so $e\cup\\{v\\}\in E(G_{k})$ as desired. ∎

Finally we use the vertex-extending property guaranteed by Lemma 2.2 to embed
any given hypergraph with bounded skeletal degeneracy. This requires a small
trick since we only know that the $(k-1)$-edges extend to $k$-edges instead of
the stronger property that all $i$-edges extend to $(i+1)$-edges.

######  Theorem 2.6.

Let $H$ be a $k$-uniform $k$-partite hypergraph with $d_{1}(H)=d$. There exist
constants $c_{k}>0$ (depending only on $k$) and $C_{H}$ such that every
$n$-vertex $k$-uniform hypergraph on with at least $C_{H}n^{k-c_{k}/d^{k-1}}$
edges contains a copy of $H$.

###### Proof.

Because adding a constant number of vertices does not affect the statement up
to the choice of $C_{H}$, we may assume that $n$ is a multiple of $k$. We will
apply Lemma 2.2 with parameters $k,k+d$. Let $c_{k}$ and $n_{0}$ be the
constants produced by that result.

Let $H$ be a $k$-uniform $k$-partite hypergraph with $d_{1}(H)=d$. We may
assume that $H$ is nonempty, in which case $d\geq k-1$. Let $C_{H}$ be a
sufficiently large constant and set $c^{\prime}_{k}=3^{-k}c_{k}$. Let $G$ be a
$k$-uniform hypergraph with $n$ vertices and at least
$C_{H}n^{k-c^{\prime}_{k}/d^{k-1}}$ edges. By setting $C_{H}$ large enough we
may assume that the number of vertices of $H$ satisfies $n\geq k(v(H)+k)^{3}$
and $n\geq kn_{0}$. Indeed, the statement holds vacuously whenever
$C_{H}n^{k-c^{\prime}_{k}/d^{k-1}}>n^{k}$.

We claim that $G$ contains a nonempty $k$-partite subhypergraph
$G^{\prime\prime}$ with vertex partition $V(G)=V_{1}\sqcup\cdots\sqcup V_{k}$
that is $((n/k)^{1/3},d+k)$-vertex-extending to each part. Indeed, let
$V_{1}\sqcup\cdots\sqcup V_{k}$ be an equitable partition of $V(G)$ (i.e., a
partition in which $|V_{i}|=n/k$ for each $i$) chosen uniformly at random. Let
$G^{\prime}\subseteq G$ be the $k$-partite subhypergraph induced by this
partition. Assuming that $C_{H}$ is sufficiently large, we have the inequality

$\mathop{\mathbb{E}}[e(G^{\prime})]=\frac{k!(n/k)^{k}}{n(n-1)\cdots(n-k+1)}\geq\frac{k!}{k^{k}}e(G)\geq
n^{k-\frac{c^{\prime}_{k}}{d^{k-1}}}\geq n^{k-\frac{c_{k}}{(d+k)^{k-1}}}.$

Hence there is some choice of $G^{\prime}$, a $k$-partite subhypergraph of $G$
with at least $n^{k-c_{k}/(d+k)^{k-1}}$ edges. We then apply Lemma 2.2 to
$G^{\prime}$ to produce $G^{\prime\prime}$.

Define $\hat{H}$ to be the $k$-uniform $k$-partite hypergraph formed from $H$
by adding a single auxiliary vertex to each part. Call the vertex partition
$V(\hat{H})=W_{1}\sqcup\cdots\sqcup W_{k}$ and let $\hat{w}_{i}\in W_{i}$
denote the auxiliary vertices. Let the edges of $\hat{H}$ be of the form

$\\{\hat{w}_{i}:i\in I\\}\cup\left(e\cap\bigcup_{i\in[k]\setminus
I}W_{i}\right)$

for $e\in E(H)$ and $I\subseteq[k]$. In other words, the edges of $\hat{H}$
are formed from the edges of $H$ by replacing any number of vertices with the
corresponding auxiliary vertices. We note that $d_{1}(\hat{H})\leq
d_{1}(H)+k$, because every edge present in $\hat{H}^{(1)}$ but not in
$H^{(1)}$ contains at least one of the $k$ auxiliary vertices.

We now greedily construct an embedding $\phi\colon V(\hat{H})\to
V(G^{\prime\prime})$ according to the degeneracy order. Let
$v_{1},\ldots,v_{h}$ be an ordering of $V(\hat{H})$ in which
$v_{i}=\hat{w}_{i}$ for $1\leq i\leq k$ and each subsequent vertex in the
ordering is adjacent in $\hat{H}^{(1)}$ to at most $d+k$ previous vertices. We
will define $\phi$ iteratively so that it maps vertices of $W_{i}$ to vertices
of $V_{i}$ and edges of $\hat{H}$ to edges of $G^{\prime\prime}$.

First, define $\phi$ to map $\\{v_{1},\ldots,v_{k}\\}$ to an edge of
$G^{\prime\prime}$. We can do this because $G^{\prime\prime}$ is nonempty. Now
suppose that we have embedded $v_{1},\ldots,v_{j-1}$ for some $j>k$. Our goal
is to embed $v_{j}\in W_{i}$ in a way that maintains these properties. Let
$S\subseteq\\{v_{1},\ldots,v_{j-1}\\}$ comprise those neighbors of $v_{j}$ in
$\hat{H}^{(1)}$ preceding it in the ordering. Note that $|S|\leq
d_{1}(\hat{H})\leq d+k$. Because $G^{\prime\prime}$ is
$((n/k)^{1/3},d+k)$-vertex extending, there are at least $(n/k)^{1/3}$
vertices $v\in V_{i}$ such that $e\cup\\{v\\}\in E(G^{\prime\prime})$ for each
$e\subseteq\phi(S)$ such that $e\in E(G^{\prime\prime(k-2)}[V_{-i}])$. Pick
$\phi(v_{j})$ to be one of these vertices which has not already appeared in
the image of $\phi$. We can do this because we assumed that $(n/k)^{1/3}\geq
v(\hat{H})=v(H)+k$.

We claim that $\phi$ still maps edges of $\hat{H}$ to edges of $G$ after this
choice of $\phi(v_{j})$. Let $e\cup\\{v_{j}\\}\in E(\hat{H})$ be some edge. We
know that $e\cup\\{\hat{w}_{i}\\}$ is a previously-embedded edge. In
particular, we know that $\phi(e\cup\\{\hat{w}_{i}\\})\in
E(G^{\prime\prime})$, so $\phi(e)\in E(G^{\prime\prime(k-2)})$. By our choice
of $\phi(v_{j})$, we conclude that $\phi(e)\cup\\{\phi(v_{j})\\}\in
E(G^{\prime\prime})$, as desired.

This embedding procedure terminates in a copy of $\hat{H}$ in
$G^{\prime\prime}\subseteq G$. Because $H$ is a subhypergraph of $\hat{H}$,
this completes the proof. ∎

##  3\. Lower bounds on the Turán number

In this section we prove several lower bounds on the Turán number. We give
lower bounds for some specific classes of hypergraphs an well as a general
lower bound in terms of the $i$-th skeletal degeneracy.

In this section we write $\mathbb{G}^{k}(n;p)$ for the Erdős–Rényi random
$k$-uniform hypergraph. In detail, $\mathbb{G}^{k}(n;p)$ has $n$ vertices and
each of the $\binom{n}{k}$ possible $k$-edges is present independently with
probability $p$.

We first give a lower bound for the Turán number of $K^{(k)}_{d,d,\ldots,d}$.
This result follows from standard probabilistic tools. We include the proof
for completeness, since this lower bound on the Turán number of
$K^{(k)}_{d,d,\ldots,d}$ shows that the upper bound in Theorem 1.4 is tight
(up to the constant $c_{k}$) in some cases.

######  Proposition 3.1.

For each $d,k\geq 2$ we have

$\operatorname{ex}(n,K^{(k)}_{d,d,\ldots,d})\geq\Omega_{k}(n^{k-k/d^{k-1}})$

while $d_{1}(K^{(k)}_{d,d,\ldots,d})=(k-1)d$.

###### Proof.

For ease of notation write $H$ for $K^{(k)}_{d,d,\ldots,d}$. Then the
$1$-skeleton $H^{(1)}$ is the complete $k$-partite graph with $d$ vertices in
each part. Since $H$ is $(k-1)d$-regular, we see that ${d_{1}({H})}=(k-1)d$.

Let $p=n^{-k/d^{k-1}}$ and let $G^{\prime}\sim\mathbb{G}^{k}(n;p)$. Then we
have $\mathbb{E}[e(G^{\prime})]=\binom{n}{k}p$. On the other hand, the number
$X$ of labeled copies of $H$ in $G^{\prime}$ has expectation
$\mathbb{E}[X]\leq n^{kd}p^{d^{k}}=1$. Therefore there exists $G^{\prime}$
such that

$e(G^{\prime})-X\geq\binom{n}{k}p-1\geq\frac{1}{k^{k}}n^{k-\frac{k}{d^{k-1}}}-1.$

We may remove an edge for each copy of $H$ in $G^{\prime}$ to get $G$. Now $G$
contains no copy of $H$ and has at least $\Omega_{k}(n^{k-k/d^{k-1}})$ edges.
∎

Next we prove a general lower bound for the Turán number in terms of the
$i$-th skeletal degeneracy for each $i$. The $i=1$ case of the following
theorem implies the lower bound in Theorem 1.4.

######  Theorem 3.2.

Let $d,k,i$ be positive integers where $1\leq i<k$ and $d>\binom{k}{i+1}$. Let
$H$ be any $k$-uniform hypergraph with $d_{i}(H)\geq d$. Then

$\operatorname{ex}(n,H)\geq\Omega_{k}(n^{k-3^{k}/d}).$

###### Proof.

Suppose that $n$ is sufficiently large in terms of $k$. Write $r=i+1$ and set
$p=n^{-r/d}$. Let $G_{0}\sim\mathbb{G}^{r}(n,p)$ and let $X$ be the number of
copies of $K_{k}^{(r)}$ in $G_{0}$. We have
$\mathbb{E}[X]=\binom{n}{k}p^{\binom{k}{r}}$. Since $d_{i}(H)\geq d$, there is
an $r$-uniform hypergraph $F\subseteq H^{(i)}$ on $v$ vertices with minimum
degree at least $d$. This implies that $e(F)\geq\frac{vd}{r}$. The number $Y$
of copies of $F$ in $G_{0}$ is in expectation at most $\mathbb{E}[Y]\leq
n^{v}p^{e(F)}\leq 1$. Hence there exists a choice of $G_{0}$ such that

$Z=X-\binom{n}{k-r}Y\geq\mathbb{E}\left[X-\binom{n}{k-r}Y\right]\geq\left(\frac{n}{k}\right)^{k}n^{-\frac{r}{d}\binom{k}{r}}-n^{k-r}\geq\Omega_{k}\left(n^{k-r\binom{k}{r}/d}\right).$

Here, we have used the assumption that $d>\binom{k}{r}$. We note that
$r\binom{k}{r}/d\leq 3^{k}/d$, so $Z\geq\Omega_{k}(n^{k-3^{k}/d})$.

We construct $G_{1}$ from $G_{0}$ by removing a single $r$-edge for each copy
of $F$ in $G_{0}$. By doing this the number of $r$-edges we remove is at most
$Y$, and therefore the number of copies of $K_{k}^{(r)}$ we remove is at most
$\binom{n}{k-r}Y$. Hence $G_{1}$ has at least
$\Omega_{k}\left(n^{k-3^{k}/d}\right)$ copies of $K_{k}^{(r)}$. Finally, we
construct the $k$-uniform hypergraph $G$ by putting a $k$-edge on every copy
of $K_{k}^{(r)}$ in $G_{1}$. By construction, $G^{(i)}\subseteq G_{1}$ does
not contain any copies of $F$, and therefore contains no copies of $H$, as
desired. ∎

Note that examining the bound above more carefully in the $i=1$ case gives the
following result with a better constant in the exponent.

######  Theorem 3.3.

For $k\geq 2$ and $d>k(k-1)/2$, every $k$-uniform hypergraph $H$ satisfying
${d_{1}({H})}\geq d$ has

$\operatorname{ex}(n,H)\geq\Omega_{k}(n^{k-k(k-1)/d}).$

We now give the details of the construction promised in the introduction of a
family of $k$-uniform $k$-partite hypergraphs that are all 1-degenerate (but
not 1-skeletal degenerate) and with Turán exponent $k-o(1)$. By Theorem 3.3
(or Theorem 3.2) it suffices to exhibit a family of $k$-uniform $k$-partite
hypergraphs $H$ with $d_{k-1}(H)=1$ but $d_{1}(H)$ arbitrarily large.

######  Definition 3.4.

For $k\geq 2$ and $d\geq 1$ define the _bipartite hedgehog_ $H_{d}^{(k)}$ to
be the $k$-uniform $k$-partite hypergraph on $2d+(k-2)d^{2}$ vertices formed
by extending each edge of $K_{d,d}$ to a $k$-edge.111The typical hedgehog
hypergraphs are formed by applying the same procedure to $K_{d}$ instead of
$K_{d,d}$. Formally, $H_{d}^{(k)}$ has vertices
$[d]\sqcup[d]\sqcup\bigsqcup_{i=1}^{k-2}[d]^{2}$ and the $d^{2}$ $k$-edges
$(i,j,(i,j),\ldots,(i,j))$ for each $(i,j)\in[d]^{2}$.

######  Corollary 3.5.

For each $k\geq 3$ and $d>k(k-1)/2$ we have

$\operatorname{ex}(n,H_{d}^{(k)})\geq\Omega_{k}(n^{k-k(k-1)/d})$

while $d_{k-1}(H_{d}^{(k)})=1$.

###### Proof.

Clearly $H_{d}^{(k)}$ is 1-degenerate; any subhypergraph of $H_{d}^{(k)}$
either contains one of the vertices in the latter $k-2$ parts, which all have
degree at most 1, or contains none of these vertices and thus is the empty
hypergraph.

However one can also easily see that $d_{1}(H_{d}^{(k)})\geq d$, since the
1-skeleton of $H_{d}^{(k)}$ contains $K_{d,d}$. Therefore by Theorem 3.3 we
have the desired bound on the Turán number of $H_{d}^{(k)}$. ∎

For completeness, we also give a matching upper bound on the Turán exponent of
$H_{d}^{(k)}$. The following result shows that the lower bound in Theorem 1.4
is sometimes of the correct shape.

######  Proposition 3.6.

For every $d\geq k\geq 2$ we have

$\operatorname{ex}(n,H_{d}^{(k)})\leq O_{d,k}(n^{k-1/d})$

and $d_{1}(H_{d}^{(k)})=d$.

###### Proof.

Let $n$ be sufficiently large in terms of $d,k$. Let $G$ be a $k$-uniform
hypergraph with $n$ vertices and at least $Cn^{k-1/d}$ edges for some large
constant $C$ depending on $d,k$. Define $G^{\prime}$ to be the graph on the
same vertex set whose edges are the pairs of vertices that are contained in
more than $kd^{2}n^{k-3}$ many $k$-edges in $G$. The number of edges in
$G^{\prime}$ is at least

$\frac{Cn^{k-1/d}\binom{k}{2}-kd^{2}n^{k-3}\binom{n}{2}}{\binom{n-2}{k-2}}>2n^{2-1/d}$

where the last inequality holds for an appropriate choice of $C$ and all
sufficiently large $n$. By the Kővári–Sós–Turán theorem there is a copy of
$K_{d,d}$ in $G^{\prime}$.

We now claim that this copy of $K_{d,d}$ in $G^{\prime}$ extends to a copy of
$H_{d}^{(k)}$ in $G$. Recall that $H_{d}^{(k)}$ has vertex set
$V=V_{1}\sqcup\cdots\sqcup V_{k}$ where $V_{1}=V_{2}=[d]$ and
$V_{3}=\cdots=V_{k}=[d]^{2}$ and edge set $E=\\{e_{i,j}\\}_{i,j\in[d]}$ where
$e_{i,j}=(i,j,(i,j),\ldots,(i,j))$. Pick $\phi\colon V_{1}\sqcup V_{2}\to
V(G)=V(G^{\prime})$ to be a copy of $K_{d,d}$ in $G^{\prime}$.

Now we extend $\phi$ to a map $V(H_{d}^{(k)})\to V(G)$ one edge at a time.
Suppose that at some stage of this process we have a partial map $\phi$ and we
want to extend $\phi$ to $e_{i,j}=(v_{1},v_{2},\ldots,v_{k})$. The number of
vertices appearing so far in the image of $\phi$ is at most
$v(H_{d}^{(k)})<kd^{2}$. Since $\phi(v_{1})\phi(v_{2})$ is an edge of
$G^{\prime}$ there are more than $kd^{2}n^{k-3}$ edges of $G$ containing
$\phi(v_{1})\phi(v_{2})$. We wish to avoid edges that contain vertices in
previously embedded vertices from $V_{3}\sqcup\cdots\sqcup V_{k}$. Since there
are at most $kd^{2}$ of these vertices, there are at most
$kd^{2}\binom{n}{k-3}$ edges we are not allowed to use. Therefore there is at
least one valid edge. We extend the definition of $\phi$ to
$v_{3},\ldots,v_{k}$ so that
$\\{\phi(v_{1}),\phi(v_{2}),\phi(v_{3}),\ldots,\phi(v_{k})\\}$ is this edge.

Since this process cannot get stuck, it produces a copy of $H_{d}^{(k)}$ in
$G$, as desired.

We already saw that $d_{1}(H^{(k)}_{d})\geq d$. This is an equality for $k\geq
d$, since any subgraph of the 1-skeleton of $H^{(k)}_{d}$ either contains one
of the vertices in the latter $k-2$ parts, which all have degree at most
$k-1$, or contains none of these vertices and then is a subgraph of $K_{d,d}$.
Thus $d\leq d_{1}(H^{(k)}_{d})\leq\max\\{k-1,d\\}$. ∎

##  4\. Almost-linear Ramsey number

In this section we use the techniques of Section 2 to give a short argument
that proves that hypergraphs with bounded skeletal degeneracy have almost-
linear Ramsey number. We will improve this bound to linear via a more
complicated argument in the next section.

######  Theorem 4.1.

For $k,d,q\geq 2$, let $H$ be a $k$-uniform hypergraph on $n$ vertices with
${d_{1}({H})}=d$. Then the $q$-color Ramsey number of $H$ satisfies
$r(H;q)\leq n^{1+o_{k,d,q;n\to\infty}(1)}$.

To prove Theorem 4.1, we obtain a different corollary of Lemma 2.3 by choosing
different values for the parameters.

######  Corollary 4.2.

For $p\in(0,1/2)$ and $k,d\geq 1$, there exists a constant $c_{p,k,d}>0$ such
that the following holds. Suppose that $n\geq n_{0}=n_{0}(p,k,d)$ and let $G$
be a $k$-partite $k$-uniform hypergraph with $n$ vertices in each part and at
least $pn^{k}$ edges. Then $G$ contains every $k$-partite $k$-uniform
hypergraph $H$ with ${d_{1}({H})}=d$ on $h$ vertices where

$h\leq n^{1-c_{p,k,d}(\log n)^{-\frac{2}{k(k+1)}}}.$

###### Proof.

We first apply Lemma 2.3 repeated $k$ times starting from $G$ producing a
sequence of hypergraphs $G=G_{0}\supseteq G_{1}\supseteq\cdots\supseteq
G_{k}$. In detail, define $d^{\prime}=d+k$, let $\lambda\geq 1$ be specified
later, and set $d_{t}=(\lambda+1)^{k-t}d^{\prime}$. We apply Lemma 2.3 to
$G_{t-1}$ with parameters $(d_{t},k,t,h,n,\lambda)$ to obtain $G_{t}$.

We may assume that $n$ is sufficiently large with respect to $k,d$. This
implies that the second inequality in the hypothesis of Lemma 2.3 holds as
long as $h\leq n^{1-\frac{2}{\lambda}}$.

Define

$p_{t}=p^{(\lambda+1)^{\binom{t+1}{2}}(d^{\prime})^{t}}$

for $0\leq t\leq k$. By hypothesis $G_{0}$ has at least $p_{0}n^{k}$ edges. We
see that if $e(G_{t-1})\geq p_{t-1}n^{k}$ and
$p_{t-1}^{(\lambda+1)d_{t-1}}n\geq 1$, then the first inequality in the
hypothesis of Lemma 2.3 is satisfied, so then $e(G_{t})\geq
p_{t-1}^{(\lambda+1)d_{t-1}}n^{k}=p_{t}n^{k}$.

All of these inequalities are satisfied if

$p^{(\lambda+1)^{\binom{k+1}{2}}(d^{\prime})^{k}}n\geq 1.$

Therefore we can take any

$\lambda+1\geq\left(\frac{\log n}{(d^{\prime})^{k}\log
1/p}\right)^{\frac{2}{k(k+1)}}=c^{\prime}_{p,d,k}(\log n)^{\frac{2}{k(k+1)}}.$

Now we know that $G_{k}$ is a $k$-uniform $k$-partite hypergraph that is
$(h,d+k)$-vertex-extending to each part and contains at least one edge.
Finally, we find an embedding of $H$ in $G_{k}$ as in the proof of Theorem
2.6. ∎

Using an argument of Kostochka and Rödl [32] we can deduce an almost linear
bound on the Ramsey number from this result. See also [9] for another instance
of this argument.

######  Lemma 4.3 (cf. [32, Proof of Theorem 4]).

Let $H$ be a $k$-uniform hypergraph on $n$ vertices with skeletal degeneracy
$d_{1}(H)=d$ whose 1-skeleton is $\ell$-colorable. For a positive integer $q$
and a $q$-coloring $f\colon E(K_{N}^{(k)})\to[q]$ of the edges of
$K_{N}^{(k)}$, there exist

  * •

a constant $p_{k,\ell,d}>0$ depending only on $k,\ell,d$;

  * •

an $\ell$-uniform $\ell$-partite hypergraph $\hat{H}$ with at most
$(1+(\ell-k)d^{k-1})n$ vertices and $d_{1}(\hat{H})=d$; and

  * •

an $\ell$-uniform $\ell$-partite hypergraph $\hat{G}$ with parts of size
$N^{\prime}=\lfloor N/\ell\rfloor$ and at least $p_{k,\ell,q}N^{\prime\ell}$
edges

such that if $\hat{G}$ contains a copy of $\hat{H}$ then $f$ contains a
monochromatic copy of $H$.

The proof uses the following easy upper bound on the number of edges in a
degenerate hypergraph.

######  Lemma 4.4.

Let $H$ be a $k$-uniform $n$-vertex hypergraph. Then

$e(H)\leq d_{1}(H)^{k-1}n.$

###### Proof.

A well-known characterization of degeneracy of graphs implies that if $G$ is a
$d$-degenerate graph, then there is an ordering $v_{1},v_{2},\ldots,v_{n}$ of
$V(G)$ such that each vertex $v_{i}$ is adjacent to at most $d$ of the
vertices $v_{1},\ldots,v_{i-1}$.

We apply this characterization to the 1-skeleton $H^{(1)}$. We count the
number of $k$-edges of $H$ whose last vertex in this degeneracy ordering is
$v_{j}$. Then the other $k-1$ vertices of the edge must lie in
$v_{1},\ldots,v_{j-1}$ and be adjacent to $v_{i}$ in $H^{(1)}$. Thus the
number of $k$-edges of $H$ whose last vertex is $v_{j}$ is at most
$\binom{d_{1}(H)}{k-1}$. Summing over all $n$ choices of $j$ gives the claimed
bound. ∎

###### Proof of Lemma 4.3.

Note that the result is vacuously true if $N<\ell$. Thus we assume that
$N\geq\ell$. We define an $\ell$-uniform $\ell$-partite hypergraph $\hat{H}$
as follows. As the $1$-skeleton of $H$ is $\ell$-colorable, there is a
partition of $V(H)$ into $\ell$ parts such that every edge of $H$ has vertices
from $k$ different parts of the partition. Then for each edge of $H$, add an
$\ell$-edge to $\hat{H}$ consisting of the $k$ vertices of the original edge
and $\ell-k$ auxiliary vertices. Place the auxiliary vertices in the parts
such that the edge uses one vertex from each part. At the end of the process
we have added $e(H)(\ell-k)$ auxiliary vertices in total, each used in exactly
one edge. This gives an $\ell$-uniform $\ell$-partite hypergraph, as desired.

Note that ${d_{1}({\hat{H}})}={d_{1}({H})}$ using the same degeneracy
ordering, and then placing all the auxiliary vertices at the end of the
ordering. Furthermore since Lemma 4.4 gives $e(H)\leq d^{k-1}n$, we have the
desired bound on $v(\hat{H})$.

Let $r=r(K_{\ell}^{(k)};q)$ be the $q$-color Ramsey number of the complete
$k$-uniform hypergraph on $\ell$ vertices. Given the $q$-coloring $f$ of
$K_{N}^{(k)}$ there are at least

$\frac{\binom{N}{r}}{\binom{N-\ell}{r-\ell}}\geq\frac{N^{\ell}}{r^{\ell}}$

monochromatic copies of $K_{\ell}^{(k)}$ in the coloring, at least a
$1/q$-fraction of which share a color $i\in[q]$. Define $G^{+}$ to be the
$\ell$-uniform hypergraph on $N$ vertices whose $\ell$-edges correspond to the
$i$-colored cliques in $f$.

Finally, consider a uniformly random partition of $V(G^{+})$ into $\ell+1$
parts $V_{1},\ldots,V_{\ell},V_{\ell+1}$, where
$|V_{1}|=|V_{2}|=\ldots=|V_{\ell}|=\lfloor N/\ell\rfloor$. Let $\tilde{G}$ be
the (random) hypergraph with vertex set $\bigcup_{i=1}^{\ell}V_{i}$ and all
edges of $G^{+}$ that have one vertex in each of $V_{1},\ldots,V_{\ell}$.
Since $N\geq\ell$, each edge of $G^{+}$ is in $\tilde{G}$ with probability at
least $\ell!(2\ell)^{-\ell}\geq(2e)^{-\ell}$. Thus, there exists an
$\ell$-uniform $\ell$-partite hypergraph $\hat{G}\subseteq G^{+}$ with
$\lfloor N/\ell\rfloor$ vertices in each part and that contains at least a
$(2e)^{-\ell}$-fraction of the edges in $G^{+}$. As $G^{+}$ has at least
$\frac{1}{q}(N/r)^{\ell}$ edges, it follows that $\hat{G}$ has at least
$pN^{\ell}$ edges with $p=1/(q(2er)^{\ell})$. ∎

######  Remark.

In Lemma 4.3, we can always take $\ell\leq d+1$ since the chromatic number of
a graph is always at most one more than its degeneracy. For fixed $k\geq 3$
and $q$, the value of $p_{k,\ell,q}^{-1}$ grows like a tower of height $k$
with $C_{k,q}d$ at the top. This growth mainly comes from the dependence on
the Ramsey number $r(K_{\ell}^{(k)};q)$.

Now Theorem 4.1 follows by combining Corollaries 4.2 and 4.3.

###### Proof of Theorem 4.1.

Let $N$ be a positive integer and let $f\colon K_{N}^{(k)}\to[q]$ be a
$q$-coloring of the edges of $K_{N}^{(k)}$. We apply Lemma 4.3 to the
hypergraph $H$ with $\ell=d+1$. This produces an $\ell$-uniform $\ell$-partite
hypergraph $\hat{H}$ with at most $O_{\ell,k,d}(n)$ vertices and
$d_{1}(\hat{H})=d$ and an $\ell$-uniform $\ell$-partite hypergraph $\hat{G}$
with parts of size at least $N^{\prime}=\lfloor N/\ell\rfloor$ and at least
$p_{k,\ell,q}(N^{\prime})^{\ell}$ edges. These hypergraphs have the property
that there is a monochromatic copy of $H$ in the $q$-coloring $f$ if there is
a copy of $\hat{H}$ in $\hat{G}$.

We apply Corollary 4.2 to $\hat{G}$ and $\hat{H}$ with
$(n,k,d,p)=(N^{\prime},\ell,d,p_{k,\ell,q})$. This shows that $\hat{G}$
contains a copy of $\hat{H}$ if

$v(\hat{H})\leq(N^{\prime})^{1-c(\log N^{\prime})^{-\frac{2}{\ell(\ell+1)}}}$

holds where $c$ is the constant depending on $p_{k,\ell,q},\ell,d$ in
Corollary 4.2. Thus in our setting $c$ only depends on $k,d,q$. Now using that
$v(\hat{H})\leq O_{\ell,k,d}(n)=O_{k,d}(n)$, and $N^{\prime}=\lfloor
N/\ell\rfloor=\lfloor N/(d+1)\rfloor$, we conclude that the above inequality
holds as long as

$N\geq Cn^{1+c^{\prime}(\log n)^{-\frac{2}{(d+1)(d+2)}}}$

holds for some appropriately chosen $c^{\prime},C$ depending only on $k,d,q$.
As long as this inequality is satisfied, for every $q$-coloring $f$ of the
edges of $K_{N}^{(k)}$, we know that $\hat{G}$ always contain a copy of
$\hat{H}$, so $f$ always contains a monochromatic copy of $H$. ∎

##  5\. Linear Ramsey number

In this section we prove that every $k$-uniform hypergraph on $n$ vertices
with bounded skeletal degeneracy has Ramsey number linear in $n$. This
involves a refinement of the previous Turán result that uses a notion of
defect that carefully keeps track of vertex sets that do not extend
sufficiently.

Recall from the introduction that Lee [34] proved the graphical (i.e., $k=2$)
case of Theorem 1.5. Our main innovation is introducing a new notion of defect
for hypergraphs. We use dependent random choice to prune a given hypergraph
while controlling this notion of defect. The hypergraph $H$ can then be
embedded into the pruned hypergraph. The embedding step is essentially
identical to the one used by Lee [34] in the graphical case.

Similarly to the previous section our main Ramsey result, Theorem 1.5, is
deduced from the following Turán result via Lemma 4.3.

######  Theorem 5.1.

Let $p\in(0,1/2)$ and let $k,d$ be positive integers. There exists a constant
$c_{p,k,d}>0$ such that the following holds. Let $G$ be a $k$-partite
$k$-uniform hypergraph with $n$ vertices in each part and at least $pn^{k}$
edges. Then $G$ contains every $k$-partite $k$-uniform $H$ with
${d_{1}({H})}=d$ on $h$ vertices where $h\leq c_{p,k,d}n$.

###### Proof of Theorem 1.5 assuming Theorem 5.1.

Let $N$ be a positive integer and let $f\colon E(K_{N}^{(k)})\to[q]$ be a
$q$-coloring of the edges of $K_{N}^{(k)}$. Since, by assumption, $H^{(1)}$ is
$d$-degenerate it is $\ell=(d+1)$-colorable. Thus, by Lemma 4.3 there exists
an $\ell$-uniform $\ell$-partite hypergraph $\hat{H}$ with at most
$(1+(\ell-k)d^{k-1})n$ vertices and $d_{1}(\hat{H})=d$, and an $\ell$-uniform
$\ell$-partite hypergraph $\hat{G}$ with parts of size $N^{\prime}=\lfloor
N/\ell\rfloor$ and at least $p_{k,\ell,q}(N^{\prime})^{\ell}$ edges, such that
if there is a copy of $\hat{H}$ in $\hat{G}$ then $f$ contains a monochromatic
copy of $H$.

Applying Theorem 5.1 with $(n,k,d,p)=(N^{\prime},\ell,d,p_{k,\ell,q})$ we
conclude that $\hat{G}$ contains a copy of $\hat{H}$ if $v(\hat{H})\leq
cN^{\prime}$, where $c$ is the constant depending on $p_{k,\ell,q},\ell,d$
from Theorem 5.1. Note that $c$ only depends on $k,d,q$. Using the facts that
$v(\hat{H})\leq(1+(\ell-k)d^{k-1})n$ and $N^{\prime}=\lfloor
N/\ell\rfloor=\lfloor N/(d+1)\rfloor$, we conclude that $v(\hat{H})\leq
cN^{\prime}$ as long as $n\leq c^{\prime}N$ for
$c^{\prime}=\frac{c}{2(d+1)(1+(\ell-k)d^{k-1})}$, a constant depending only on
$k,d,q$. As long as this inequality is satisfied, $\hat{G}$ contains a copy of
$\hat{H}$ which in turn implies that $f$ contains a monochromatic copy of $H$.
Hence the desired result holds with constant $1/c^{\prime}$, which only
depends on $k,d,q$. ∎

We spend the remainder of this section proving the Turán result. In Section
5.1 we define our notion of defect for hypergraphs and prove that we can prune
$G$ in a way that gives us control over the defect. In Section 5.2 we show
that we can embed $H$ into $G$. In Section 5.3 we combine these two results to
prove Theorem 5.1. Almost all of the novelty lies in Section 5.1 while the
arguments in Sections 5.2 and 5.3 closely follow the strategy used in [34].

###  5.1. Pruning

Let $G$ be a $k$-uniform $k$-partite hypergraph with vertex parts
$V_{1},\ldots,V_{k}$. Define

$E^{*}(G)=\\{e\subseteq V(G):e\subseteq f\text{ for some }f\in E(G)\\}.$

We refer to $E^{*}(G)$ as the _partial edges_ of $G$. Note that $\emptyset\in
E^{*}(G)$ for any nonempty hypergraph $G$.

For $Q\subseteq V(G)$, write

$PE_{Q}(G)=\\{s\subseteq Q:s\in E^{*}(G)\\}$

for the partial edges of $G$ contained in $Q$. For $E\subseteq E^{*}(G)$
define the _common neighborhood_ of $E$ to be

$N(E;G)=\\{v\in V(G):e\sqcup\\{v\\}\in E^{*}(G)\text{ for all }e\in E\\}.$

For $Q\subseteq V(G)$ we will often consider $N(PE_{Q}(G);G)$, the common
neighborhood of $Q$. In words this is the set of vertices $v$ such that every
partial edge in $Q$ extends to another partial edge with the addition of the
vertex $v$.

Finally for $\theta>0$ define the _defect_

$\omega_{\theta}(Q,V_{i};G)=\omega_{\theta}(|N(PE_{Q}(G);G)\cap V_{i}|),$
(5.1)

where $\omega_{\theta}\colon\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq
0}\cup\\{+\infty\\}$ is defined by

$\omega_{\theta}(x)=\begin{cases}+\infty\quad&\text{if }x=0,\\\
\frac{\theta}{x}\quad&\text{if }0<x<\theta,\\\ 0&\text{otherwise}.\end{cases}$
(5.2)

The defect $\omega_{\theta}(Q,V_{i};G)$ measures if there are at least
$\theta$ vertices of $V_{i}$ in the common neighborhood of $Q$. The defect is
0 when the common neighborhood contains at least $\theta$ vertices of $V_{i}$,
the defect is infinite when the common neighborhood has zero vertices of
$V_{i}$, and for intermediate sizes it interpolates between these values.

Given a partition $V_{1}\sqcup\cdots\sqcup V_{k}$, recall that we write
$V_{-i}=\bigcup_{j\neq i}V_{j}$. We will often consider
$\omega_{\theta}(Q,V_{i};G)$ for $Q\in(V_{-i})^{d}$. (Note that we abuse
notation and view a tuple as its set of coordinates.)

Note that if $Q\subseteq Q^{\prime}$, then $PE_{Q}(G)\subseteq
PE_{Q^{\prime}}(G)$, so $N(PE_{Q}(G);G)\cap V_{i}\supseteq
N(PE_{Q^{\prime}}(G);G)\cap V_{i}$, and thus
$\omega_{\theta}(Q,V_{i};G)\leq\omega_{\theta}(Q^{\prime},V_{i};G)$.

We now state our main dependent random choice lemma.

######  Lemma 5.2.

Suppose that $G$ is a $k$-partite $k$-uniform hypergraph on
$V_{1}\sqcup\cdots\sqcup V_{k}$ with at least $p|V_{1}|\cdots|V_{k}|$ edges.
Let $d,t$ be positive integers and $\theta$ be a positive real number. For
each $1\leq i\leq k$, let $\bm{X}_{i}=((\bm{X}_{i})_{u})_{u\in[t]}\in
V_{i}^{t}$ be a uniform random $t$-tuple of vertices. Let $G^{\prime}\subseteq
G$ be chosen in the following way: for every edge $e=(e_{1},\dots,e_{k})\in
E(G)$, we keep $e$ in $G^{\prime}$ if and only if all edges in
$(\\{e_{1}\\}\cup\bm{X}_{1})\times\cdots\times(\\{e_{k}\\}\cup\bm{X}_{k})$ are
in $E(G)$. Next, remove all isolated vertices to get the random $k$-partite
$k$-uniform hypergraph $G^{\prime}$ with parts
$V_{1}^{\prime}\sqcup\cdots\sqcup V_{k}^{\prime}$. Then
$\mathbb{E}[e(G^{\prime})]\geq p^{(t+1)^{k}}|V_{1}|\cdots|V_{k}|$, and for
each $i\in[k]$,

$\mathbb{E}\left[\sum_{Q\in(V_{-i}^{\prime})^{d}}\omega_{\theta}(Q,V_{i}^{\prime};G^{\prime})^{t}\right]\leq
2^{2^{d}}\left(\frac{\theta}{|V_{i}|}\right)^{t}v(G)^{d}.$

######  Remark.

To prove the last inequality in the lemma, we will show that for each
$d$-tuple of vertices $Q$, we have
$\mathbb{E}\left[\omega_{\theta}(Q,V_{i}^{\prime};G^{\prime})^{t}\right]\leq
2^{2^{d}}\left(\frac{\theta}{|V_{i}|}\right)^{t}$. In other words, we can
control up through the $t$-th moment of the defect for each $Q$. Intuitively
(and imprecisely), the reason for this is that if some $Q\in(V_{-i})^{t}$ has
large defect, say $\theta/m$, then $Q$ has a small (size $m$) common
neighborhood. In this case it is unlikely for $Q$ to survive into
$G^{\prime}$, since all $t$ of the vertices
$(\bm{X}_{i})_{1},\ldots,(\bm{X}_{i})_{t}$ would have to be chosen from the
common neighborhood. Hence, although $Q$ would have $t$-th moment of defect
$(\theta/m)^{t}$, the probability that $Q$ survives into $G^{\prime}$ is only
$(m/|V_{i}|)^{t}$. This gives the $(\theta/|V_{i}|)^{t}$ contribution in the
inequality.

In the next sections we will take $\theta/v(G)$ to be a sufficiently small
constant in terms of $p$. The inequality then implies that on average over
$Q\in(V_{-i}^{\prime})^{d}$ we expect
$\omega_{\theta}(Q,V_{i}^{\prime};G)^{t}$ to be small. Heuristically, this
implies that for a large fraction of $d$-sets in $V^{\prime}_{-i}$ the number
of common neighbors is linear in $\theta$, which is itself linear in $v(G)$.
This property will be crucial when we embed hypergraphs into $G$ vertex by
vertex.

###### Proof of Lemma 5.2.

Note that if any edge in $\bm{X}_{1}\times\cdots\times\bm{X}_{k}$ is not
present in $G$ then $G^{\prime}$ is empty. In what follows, expectations are
taken over $(\bm{X}_{1},\ldots,\bm{X}_{k})$ unless specified otherwise.

First we compute the expectation of $e(G^{\prime})$. Note that we can see this
as a $k$-step procedure of deleting edges: $G=G_{0}\leadsto
G_{1}\leadsto\cdots\leadsto G_{k}=G^{\prime\prime}\leadsto G^{\prime}$, where
in step $i\geq 1$ the hypergraph $G_{i}$ is derived from $G_{i-1}$ by keeping
only edges $e\in G_{i-1}$ if $(e\cap V_{-i})\cup(\bm{X}_{i})_{u}\in
E(G_{i-1})$ for all $1\leq u\leq t$. Finally $G^{\prime}$ is derived from
$G^{\prime\prime}$ by removing isolated vertices, so
$E(G^{\prime})=E(G^{\prime\prime})$.

Condition on $G_{i-1}$. For each $e\in\prod_{j\neq i}V_{j}$, note that all
$|N(\\{e\\};G_{i-1})|$ edges containing $e$ are kept in $G_{i}$ if and only if
$\bm{X}_{i}$ are all in $N(\\{e\\};G_{i-1})$. First, we have

$\sum_{e\in\prod_{j\neq i}V_{j}}|N(\\{e\\};G_{i-1})|=e(G_{i-1}).$

Second, since the probability that $\bm{X}_{i}$ are all in
$N(\\{e\\};G_{i-1})$ is
$\left(\frac{|N(\\{e\\};G_{i-1})|}{|V_{i}|}\right)^{t}$, we obtain

$\mathbb{E}_{\bm{X}_{i}}[e(G_{i})]=\sum_{e\in\prod_{j\neq
i}V_{j}}|N(\\{e\\};G_{i-1})|\left(\frac{|N(\\{e\\};G_{i-1})|}{|V_{i}|}\right)^{t}\geq\frac{e(G_{i-1})^{t+1}}{\prod_{j=1}^{k}|V_{j}|^{t}}.$

As a consequence, combining this for all $i=k,k-1,\ldots,1$, we have

$\mathbb{E}\left[\frac{e(G^{\prime\prime})}{\prod_{j=1}^{k}|V_{j}|}\right]\geq\mathbb{E}\left[\left(\frac{e(G_{k-1})}{\prod_{j=1}^{k}|V_{j}|}\right)^{(t+1)}\right]\geq\cdots\geq\left(\frac{e(G)}{\prod_{j=1}^{k}|V_{j}|}\right)^{(t+1)^{k}},$

as desired.

Now we aim to establish the second inequality. By symmetry we may assume that
$i=1$. For each $Q\in V_{-1}^{d}$ and each nonempty subset $E\subseteq
PE_{Q}(G)$, we first aim to bound

$\mathop{\mathbb{E}}\left[\omega_{\theta}(|N(E;G^{\prime})\cap
V_{1}^{\prime}|)^{t}\mathbf{1}\\{E\subseteq PE_{Q}(G^{\prime})\\}\right].$

For each $s\in E$, the event $s\in PE_{Q}(G^{\prime})$ occurs if and only if
every $k$-tuple in $\prod_{\ell=1}^{k}\bm{X}_{\ell}\cup(s\cap V_{\ell})$ lies
in $E(G)$. Note that since $Q\in(V_{-1})^{d}$, we know that $s\cap
V_{1}=\emptyset$. Define $\bm{F}_{E}=\bigcup_{s\in
E}\prod_{\ell=2}^{k}\bm{X}_{\ell}\cup(s\cap V_{\ell})$. Thus the event
$E\subseteq PE_{Q}(G^{\prime})$ occurs if and only if
$\bm{X}_{1}\times\bm{F}_{E}\subseteq E(G)$ which occurs if and only if
$\bm{X}_{1}\subseteq N(\bm{F}_{E};G)$. Furthermore, if $\bm{X}_{1}\subseteq
N(\bm{F}_{E};G)$, then $N(E;G^{\prime})\cap V_{1}^{\prime}\supseteq
N(\bm{F}_{E};G)$. Therefore, conditioning on $\bm{F}_{E}$, we compute

$\displaystyle\mathop{\mathbb{E}}_{\bm{X}_{1}}\left[\omega_{\theta}(|N(E;G^{\prime})\cap
V_{1}^{\prime}|)^{t}\mathbf{1}\\{E\subseteq PE_{Q}(G^{\prime})\\}\right]$
$\displaystyle\leq\mathop{\mathbb{E}}_{\bm{X}_{1}}\left[\omega_{\theta}(|N(\bm{F}_{E};G)|)^{t}\mathbf{1}\\{\bm{X}_{1}\subseteq
N(\bm{F}_{E};G)\\}\right]$
$\displaystyle\leq\left(\frac{\theta}{|N(\bm{F}_{E};G)|}\right)^{t}\left(\frac{|N(\bm{F}_{E};G)|}{|V_{1}|}\right)^{t}$
$\displaystyle=\left(\frac{\theta}{|V_{1}|}\right)^{t}.$

For each $Q\in(V_{-1}^{\prime})^{d}$ clearly $PE_{Q}(G^{\prime})\subseteq
PE_{Q}(G)$. Furthermore since no vertex of $G^{\prime}$ is isolated we also
have $\emptyset\neq PE_{Q}(G^{\prime})$. Thus for every $Q\in V_{-1}^{d}$,

$\displaystyle\mathop{\mathbb{E}}\left[\omega_{\theta}(Q,V_{1}^{\prime};G^{\prime})^{t}\mathbf{1}\\{Q\in(V_{-1}^{\prime})^{d}\\}\right]$
$\displaystyle\leq\sum_{\emptyset\neq E\subseteq
PE_{Q}(G)}\mathop{\mathbb{E}}\left[\omega_{\theta}(|N(E;G^{\prime})\cap
V_{1}^{\prime}|)^{t}\mathbf{1}\\{E=PE_{Q}(G^{\prime})\\}\right]$
$\displaystyle\leq\sum_{\emptyset\neq E\subseteq
PE_{Q}(G)}\mathop{\mathbb{E}}\left[\omega_{\theta}(|N(E;G^{\prime})\cap
V_{1}^{\prime}|)^{t}\mathbf{1}\\{E\subseteq PE_{Q}(G^{\prime})\\}\right]$
$\displaystyle\leq\sum_{\emptyset\neq E\subseteq
PE_{Q}(G)}\left(\frac{\theta}{|V_{1}|}\right)^{t}$ $\displaystyle\leq
2^{2^{d}}\left(\frac{\theta}{|V_{1}|}\right)^{t}.$

Finally, taking the sum over all possible choices of $Q$ yields the inequality

$\mathbb{E}\left[\sum_{Q\in(V_{-1}^{\prime})^{d}}\omega_{\theta}(Q,V_{1}^{\prime};G^{\prime})^{t}\right]\leq
2^{2^{d}}\left(\frac{\theta}{|V_{1}|}\right)^{t}v(G)^{d}.\qed$

For each $i\in[k]$ and $\mathcal{Q}\subseteq(V_{-i})^{d}$, we define the
average defect

$\mu_{\theta,t}\left(\mathcal{Q},V_{i};G\right)=\frac{1}{|\mathcal{Q}|}\sum_{Q\in\mathcal{Q}}\omega_{\theta}(Q,V_{i};G)^{t}.$
(5.3)

Lemma 5.2 can be used to construct a subhypergraph for which we have control
over the average defects.

######  Corollary 5.3.

Suppose that $G$ is a $k$-partite $k$-uniform hypergraph on
$V_{1}\sqcup\cdots\sqcup V_{k}$ where $|V_{1}|=\cdots=|V_{k}|=n$ with at least
$pn^{k}$ edges. Let $d,t$ be positive integers satisfying $d\geq k-1$ and let
$\theta>0$. There exists a subhypergraph $G^{\prime}$ of $G$, with vertex
partition $V_{1}^{\prime}\sqcup\ldots\sqcup V_{k}^{\prime}$, that contains at
least $\tfrac{1}{2}p^{(t+1)^{k}}n^{k}$ edges and for each $i\in[k]$, we have

$\mu_{\theta,t}\left((V^{\prime}_{-i})^{d},V_{i}^{\prime};G^{\prime}\right)\leq
2^{2^{d}+1}k^{d+1}p^{-\frac{d}{k-1}(t+1)^{k}}\left(\frac{\theta}{n}\right)^{t}.$

###### Proof.

Let $G^{\prime}\subseteq G$ be a random subhypergraph defined by the random
process in Lemma 5.2, with parts $V_{1}^{\prime}\sqcup\cdots\sqcup
V_{k}^{\prime}$. We shall define

$S_{i}=\sum_{Q\in(V_{-i}^{\prime})^{d}}\omega_{\theta}(Q,V_{i}^{\prime};G^{\prime})^{t}.$

Then by Lemma 5.2 we have $\mathbb{E}[S_{i}]\leq
2^{2^{d}}k^{d}\theta^{t}n^{d-t}$. Since $d\geq k-1$, by convexity we know that

$\mathbb{E}\left[e(G^{\prime})^{\frac{d}{k-1}}\right]\geq\left(\mathbb{E}[e(G^{\prime})]\right)^{\frac{d}{k-1}}\geq
p^{\frac{d}{k-1}(t+1)^{k}}n^{\frac{dk}{k-1}}.$

Therefore, there exists a choice of subhypergraph $G^{\prime}$ for which

$\frac{e(G^{\prime})^{\frac{d}{k-1}}}{p^{\frac{d}{k-1}(t+1)^{k}}n^{\frac{dk}{k-1}}}-\sum_{i=1}^{k}\frac{1}{2k}\frac{S_{i}}{2^{2^{d}}k^{d}\theta^{t}n^{d-t}}\geq\mathbb{E}\left[\frac{e(G^{\prime})^{\frac{d}{k-1}}}{p^{\frac{d}{k-1}(t+1)^{k}}n^{\frac{dk}{k-1}}}-\sum_{i=1}^{k}\frac{1}{2k}\frac{S_{i}}{2^{2^{d}}k^{d}\theta^{t}n^{d-t}}\right]\geq\frac{1}{2}.$

This means that $e(G^{\prime})\geq\tfrac{1}{2}p^{(t+1)^{k}}n^{k}$ and for each
$i\in[k]$ we have

$\frac{S_{i}}{e(G^{\prime})^{\frac{d}{k-1}}}\leq
2k2^{2^{d}}k^{d}p^{-\frac{d}{k-1}(t+1)^{k}}n^{-\frac{d}{k-1}}\left(\frac{\theta}{n}\right)^{t}.$

Note that $e(G^{\prime})\leq\prod_{j=1}^{k}|V_{j}^{\prime}|\leq
n|V_{-i}^{\prime}|^{k-1}$. We conclude that

$\mu_{\theta,t}\left((V_{-i}^{\prime})^{d},V_{i}^{\prime};G^{\prime}\right)=\frac{1}{|V^{\prime}_{-i}|^{d}}S_{i}\leq\frac{S_{i}n^{\frac{d}{k-1}}}{e(G^{\prime})^{\frac{d}{k-1}}}<2^{2^{d}+1}k^{d+1}p^{-\frac{d}{k-1}(t+1)^{k}}\left(\frac{\theta}{n}\right)^{t}.\qed$

###  5.2. Embedding

In this section $G$ and $H$ always refer to hypergraphs of the following type.

######  Setup 5.4.

Fix positive integers $K\geq k\geq 2$ and $d\geq 1$. Let $G$ be a $k$-uniform
hypergraph with vertex set partitioned as $V(G)=V_{1}\sqcup\cdots\sqcup
V_{K}$. Assume that $G$ has no isolated vertices.

Let $H$ be a $k$-uniform hypergraph with vertex set partitioned as
$V(H)=W_{1}\sqcup\cdots\sqcup W_{K}$. Assume that each edge of $H$ has
vertices coming from $k$ different parts of the partition. For each vertex
$v\in W_{i}$ with $i<K$, let $N^{+}(v)$ be the set of neighbors of $v$ in the
1-skeleton of $H$ which lie in $W_{i+1}\sqcup\cdots\sqcup W_{K}$. Assume that
$|N^{+}(v)|\leq d$ for each vertex $v\in W_{i}$ with $i<K$. Pick $d$-tuples
$f_{v}\in(W_{i+1}\sqcup\cdots\sqcup W_{K})^{d}$ which consist of the elements
of $N^{+}(v)$ in some order padded by $d-|N^{+}(v)|$ additional vertices.

Let $\theta_{1},\ldots,\theta_{K-1}>0$ be real numbers. Finally assume that
$|V_{K}|\geq|W_{k}|$.

We use the following random greedy process based on [34, Section 4] to define
a random map $\psi\colon V(H)\to V(G)$.

######  Algorithm 5.5.

Suppose we are in 5.4. Define a random map $\psi\colon V(H)\to V(G)$ as
follows:

  1. 1.

Order the vertices of $W_{K}$ arbitrarily as $x_{1},\ldots,x_{|W_{K}|}$. For
each vertex $x_{j}$, let $\psi(x_{j})$ be a uniform random element of
$V_{K}\setminus\\{\psi(x_{1}),\ldots,\psi(x_{j-1})\\}$.

  2. 2.

In decreasing order, for each $i<K$, given a map $\psi$ defined on
$W_{i+1}\sqcup\cdots\sqcup W_{K}$, we extend $\psi$ to $W_{i}$ as follows. Let
$x_{1},\ldots,x_{|W_{i}|}$ be an ordering of $W_{i}$ such that
$\omega_{\theta_{i}}(\psi(f_{x_{j}}),V_{i};G)$ is non-increasing in $j$.

  3. 3.

After embedding $x_{1},\dots,x_{j-1}$, we now embed $x_{j}$. Define

$N_{j}=N(PE_{\psi(f_{x_{j}})}(G);G)\cap V_{i}$

and

$L_{j}=N_{j}\setminus\\{\psi(x_{1}),\ldots,\psi(x_{j-1})\\}.$

    1. (a)

If $|N_{j}|=0$, let $\psi(x_{j})$ be a uniform random vertex in $V_{i}$;

    2. (b)

If $|L_{j}|<|N_{j}|/2$, let $\psi(x_{j})$ be a uniform random vertex in
$N_{j}$;

    3. (c)

If $|L_{j}|\geq|N_{j}|/2$, let $\psi(x_{j})$ be a uniform random vertex in
$L_{j}$.

Our goal is to show that if $G$ has small average defect then Algorithm 5.5
produces an embedding $\psi\colon V(H)\to V(G)$. In particular, we want to
show that we always use step 3(c) and never steps 3(a) and 3(b).

######  Notation 5.6.

We now introduce some notation used to analyze Algorithm 5.5. For $i<K$, $x\in
W_{i}$, and $\phi\colon V(H)\to V(G)$ we use the following shorthand:

  1. (1)

$\theta_{x}=\theta_{i}$ and $V_{x}=V_{i}$;

  2. (2)

$\omega(x;\phi)=\omega_{\theta_{x}}(\phi(f_{x}),V_{x};G)$;

  3. (3)

$\mathcal{Q}_{x}=V_{i_{1}}\times\cdots\times V_{i_{d}}$ where $f_{x}\in
W_{i_{1}}\times\cdots\times W_{i_{d}}$;

  4. (4)

$\mu_{t}(x)=\mu_{\theta_{x},t}(\mathcal{Q}_{x},V_{x};G)$ and
$\mu_{t}=\max_{x\in V(H)}\mu_{t}(x)$;

  5. (5)

$\gamma=\max\\{1,\max_{i<K}|V_{i}|/\theta_{i}\\}$.

We extend this notation to $i=K$ as follows. For $x\in W_{K}$ we write
$V_{x}=V_{K}$ and $\omega(x;\phi)=0$.

######  Remark.

Note that $\mu_{\theta,t}(\mathcal{Q},V_{i};G)$ is only finite for some
choices of $\mathcal{Q}=V_{i_{1}}\times\cdots\times V_{i_{d}}$. For example,
if there is an edge $e=\\{v_{1},\ldots,v_{k}\\}$ with $v_{j}\in V_{i_{j}}$
say, then $\mu_{\theta,t}(\mathcal{Q},V_{i};G)$ is infinite. This is because
$e$ is an entire edge so it can have no extension to $V_{i}$. In our
application we will choose the vectors $f_{x}$ carefully so that
$\mu_{t}(x)=\mu_{\theta_{x},t}(\mathcal{Q}_{x},V_{x};G)$ is always finite (and
in fact quite small).

######  Lemma 5.7 (cf. [34, Lemma 4.3]).

Suppose we are in 5.4. Assume that $\theta_{i}\geq 2|W_{i}|$ for all $i<K$.
Let $\psi$ be the random map produced by Algorithm 5.5. For $s\geq 1$, let
$\phi\colon V(H)\to V(G)$ be a deterministic map satisfying $\Pr(\psi=\phi)>0$
and $\sum_{x\in W_{i}}\omega(x;\phi)^{s}\leq\tfrac{1}{2}\theta_{i}$ for all
$i<K$. Then $\phi$ is an embedding of $H$ in $G$.

###### Proof.

It suffices to prove this when $s=1$ since the hypothesis is stronger for
larger $s$. We now prove that for each $i<K$, if we condition on
$\psi|_{W_{i+1}\cup\cdots\cup W_{K}}=\phi|_{W_{i+1}\cup\cdots\cup W_{K}}$ then
Algorithm 5.5 embeds $W_{i}$ using step 3(c) for every vertex.

Since $\omega(x_{1};\phi)\geq\cdots\geq\omega(x_{j};\phi)$, by hypothesis we
have $\omega(x_{j};\phi)\leq\tfrac{1}{2j}\theta_{i}$. We claim that
$|N_{j}|\geq 2j>0$. Indeed, by definition,
$\omega(x_{j};\phi)=\omega_{\theta_{i}}(|N_{j}|)$. Hence, if
$|N_{j}|\in(0,\theta_{i})$ then by definition of $\omega_{\theta_{i}}$ we have
the bound $\theta_{i}/|N_{j}|\leq\theta_{i}/(2j)$. This implies that
$|N_{j}|\geq 2j>0$. Additionally, we must have $|N_{j}|>0$, for otherwise by
definition $\omega(x_{j};\phi)=\infty>\frac{1}{2}\theta_{i}$. Finally, since
we have assumed that $\theta_{i}\geq 2|W_{i}|\geq 2j$, if
$|N_{j}|\geq\theta_{i}$ then $|N_{j}|\geq 2j$, as claimed. Now, since
$|L_{j}|\geq|N_{j}|-j+1\geq|N_{j}|/2$ we are in case 3(c) as desired. In
particular, this implies that $\phi\colon V(H)\to V(G)$ is injective.
Furthermore, it implies that for every $x\in W_{1}\sqcup\cdots\sqcup W_{K-1}$
it is the case that $\phi(x)\in N(PE_{\phi(f_{x})}(G);G)\cap V_{i}$.

Next we verify that $\phi$ is a hypergraph homomorphism. We will prove
inductively that for every $e\in E^{*}(H)$ that is contained in
$W_{i}\cup\cdots\cup W_{K}$ it holds that $\phi(e)\in E^{*}(G)$. For the base
case, suppose that $e\subseteq W_{K}$ and $e\in E^{*}(H)$. Since every edge in
$H$ has at most one vertex in each part we conclude that $e=\\{x\\}$ for some
$x\in W_{K}$. Hence, since $G$ has no isolated vertices we have
$\\{\phi(x)\\}\in E^{*}(G)$.

Assume that we have proved the claim for $e\subseteq W_{i+1}\cup\cdots\cup
W_{K}$. Let $e\in E^{*}(H)$ with $e\subseteq W_{i}\cup\cdots\cup W_{K}$ and
$e\cap W_{i}\neq\emptyset$. Since $e$ has at most one vertex from each part
there is some $x\in W_{i}$ such that $\\{x\\}=e\cap W_{i}$. Set
$e^{\prime}=e\setminus\\{x\\}$ and note that $e^{\prime}\in E^{*}(H)$. We have
already shown that $\phi(x)$ is an element of $N(PE_{\phi(f_{x})}(G);G)\cap
V_{i}$. Furthermore, we know that $e^{\prime}$ is a subset of $f_{x}$, and by
the inductive assumption we know that $\phi(e^{\prime})\in E^{*}(G)$.
Combining these facts we see that $\phi(e)\in E^{*}(G)$.

We have shown that for every edge $e\in E(H)$, we have $\phi(e)\in E^{*}(G)$.
Since $\phi$ is an injection $|\phi(e)|=|e|$. Since both $G$ and $H$ are
$k$-uniform this implies that $\phi(e)\in E(G)$, completing the proof that
$\phi$ is an embedding. ∎

In analyzing Algorithm 5.5 the main difficulty is controlling the sums
$\sum_{x\in W_{i}}\omega(x;\phi)$. If $\phi\colon W_{i+1}\cup\cdots\cup
W_{K}\to V_{i+1}\cup\cdots\cup V_{K}$ were a uniform random map, then in
expectation this sum would simply be $|W_{i}|$ times the average defect. Thus
our goal is to control how much Algorithm 5.5 differs from a uniform random
map.

Following [34, Section 4] we make the following definitions. Denote by $\nu$
the probability distribution on maps $\psi\colon V(H)\to V(G)$ induced by
Algorithm 5.5. For $I\subseteq V(H)$, the probability distribution obtained
from $\nu$ by _neutralizing $I$_ is the distribution induced by following the
randomized process above but each time we reach a vertex $x\in I$ we choose
the image of $x$ to be a uniform random vertex of $V_{x}$.

######  Lemma 5.8 (cf. [34, Lemma 4.4]).

Suppose we are in 5.4. Assume that $|V_{K}|\geq 2|W_{K}|$. Let $\nu$ be the
probability distribution on maps $\psi\colon V(H)\to V(G)$ induced by
Algorithm 5.5. For sets $I_{1},I_{2},J\subseteq V(H)$ with $I_{2}=I_{1}\cup
J$, let $\nu_{i}$ be the distribution obtained from $\nu$ by neutralizing
$I_{i}$ for $i=1,2$. Let $X$ be any random variable which only depends on the
images of the vertices in $J$. If $t=|J\setminus I_{1}|\geq 1$, then

$\mathop{\mathbb{E}}_{\nu_{1}}[X]\leq
2^{t}\gamma^{t}\mathop{\mathbb{E}}_{\nu_{2}}[X]+2^{2t-1}\gamma^{2t}\mathop{\mathbb{E}}_{\nu_{2}}[X^{2}]+\frac{1}{2t}\sum_{y\in
J\setminus I_{1}}\mathop{\mathbb{E}}_{\psi\sim\nu_{2}}[\omega(y;\psi)^{2t}].$

Other than a slight change in the definition of $C_{y}(\phi)$, this proof is
identical to [34, Proof of Lemma 4.4].

###### Proof.

For $y\in I_{2}\setminus I_{1}$, define

$C_{y}(\phi)=\frac{2|V_{y}|}{|N(PE_{\phi(f_{y})}(G);G)\cap V_{y}|}$

if $y\notin W_{K}$ and $C_{y}(\phi)=2$ if $y\in W_{K}$. The motivation for
this definition (as well as the assumption that $|V_{K}|\geq 2|W_{K}|$) is
that when embedding $y$ in Algorithm 5.5, each particular vertex is chosen as
its image with probability at most $C_{y}(\phi)/|V_{y}|$. Furthermore, we have
the inequality $C_{y}(\phi)\leq 2\gamma\max\\{1,\omega(y;\phi)\\}$ for all
$y$.

For $0\leq s\leq v(H)$, define $\psi_{s}$ to be the random partial map
$V(H)\to V(G)$ defined by running Algorithm 5.5 until it embeds $s$ vertices.
For a set $W\subseteq V(H)$ of size $s$ and a deterministic map $\phi\colon
W\to V(G)$ our goal is to understand the event $\psi_{s}=\phi$. Note that this
event occurs with nonzero probability only for some choices of $W$ and $\phi$.

Define $I_{W}=I_{2}\setminus(W\cup I_{1})$ and let $\nu_{W}$ be the
distribution obtained from $\nu$ by neutralizing $I_{1}\cup I_{W}$. Our goal
is to prove

$\mathop{\mathbb{E}}_{\psi\sim\nu_{1}}[X|\psi_{s}=\phi]\leq\mathop{\mathbb{E}}_{\psi\sim\nu_{W}}\left[X\cdot\prod_{y\in
I_{W}}C_{y}(\psi)\right|\left.\vphantom{\prod_{I_{W}}}\psi_{s}=\phi\right]$
(5.4)

for all choices of $s,W,\phi$ with $s=|W|$. We abuse notation and say that 5.4
holds vacuously for those $s,W,\phi$ for which $\Pr(\psi_{s}=\phi)=0$.

We prove 5.4 by induction on $s$. For the base case, suppose $s=v(H)$. Then
$I_{W}=\emptyset$ so $\nu_{1}=\nu_{W}$ and the product disappears.

Let $W$ be a set of size $s$ and suppose that 5.4 holds for all larger sets.
Given $\psi_{s}=\phi$, we know which vertex will be embedded next by the
random process $\nu_{1}$. Let this vertex be $z\in W_{i}$ for some $i$. For
each vertex $v\in V_{i}$, write $\phi_{v}\colon W\cup\\{z\\}\to V(G)$ for the
map which sends $z$ to $v$ and otherwise agrees with $\phi$. Then we have

$\begin{split}\mathop{\mathbb{E}}_{\psi\sim\nu_{1}}[X|\psi_{s}=\phi]&=\sum_{v\in
V_{i}}\Pr_{\nu_{1}}(\psi(z)=v|\psi_{s}=\phi)\mathop{\mathbb{E}}_{\psi\sim\nu_{1}}[X|\psi_{s+1}=\phi_{v}]\\\
&\leq\sum_{v\in
V_{i}}\Pr_{\nu_{1}}(\psi(z)=v|\psi_{s}=\phi)\mathop{\mathbb{E}}_{\psi\sim\nu_{W\cup\\{z\\}}}\left[X\cdot\prod_{y\in
I_{W\cup\\{z\\}}}C_{y}(\psi)\right|\left.\vphantom{\prod_{I_{W\cup\\{z\\}}}}\psi_{s+1}=\phi_{v}\right]\\\
&=\sum_{v\in
V_{i}}\Pr_{\nu_{1}}(\psi(z)=v|\psi_{s}=\phi)\mathop{\mathbb{E}}_{\psi\sim\nu_{W}}\left[X\cdot\prod_{y\in
I_{W\cup\\{z\\}}}C_{y}(\psi)\right|\left.\vphantom{\prod_{I_{W\cup\\{z\\}}}}\psi_{s+1}=\phi_{v}\right].\end{split}$
(5.5)

To see the last line, note that $\nu_{W}$ and $\nu_{W\cup\\{z\\}}$ only differ
on whether or not $z$ is neutralized. However, conditioning on
$\psi_{s+1}=\phi_{v}$, we see that the image of $z$ is already fixed and thus
the two distributions become identical. Let us point out that we continue to
abuse notation slightly in the above equation since for some choices of $v$
the event $\psi_{s+1}=\phi_{v}$ never occurs so we are conditioning on a null
event. However for these terms we are multiplying by 0 so the equation
continues to be valid.

We have two cases. Either $I_{W\cup\\{z\\}}=I_{W}$, or
$I_{W\cup\\{z\\}}\cup\\{z\\}=I_{W}$. If $I_{W\cup\\{z\\}}=I_{W}$, then
$z\notin I_{W}$ so
$\Pr_{\nu_{1}}(\psi(z)=v|\psi_{s}=\phi)=\Pr_{\nu_{W}}(\psi(z)=v|\psi_{s}=\phi)$
(to see this, note that we are conditioning on the fact that the two processes
agree for the first $s$ steps and since neither of them neutralize $z$ they
agree on step $s+1$ as well). Thus in this case, the final expression in (5.5)
can be written as

$\sum_{v\in
V_{i}}\Pr_{\nu_{W}}(\psi(z)=v|\psi_{s}=\phi)\mathop{\mathbb{E}}_{\psi\sim\nu_{W}}\left[X\cdot\prod_{y\in
I_{W}}C_{y}(\psi)\right|\left.\vphantom{\prod_{I_{W}}}\psi_{s+1}=\phi_{v}\right]=\mathop{\mathbb{E}}_{\psi\sim\nu_{W}}\left[X\cdot\prod_{y\in
I_{W}}C_{y}(\psi)\right|\left.\vphantom{\prod_{I_{W}}}\psi_{s}=\phi\right].$

In the second case $I_{W\cup\\{z\\}}\cup\\{z\\}=I_{W}$. This means that $z\in
I_{W}$, but $z\notin I_{1}$. We claim that this implies that

$\Pr_{\nu_{1}}(\psi(z)=v|\psi_{s}=\phi)\leq
C_{z}(\phi)\Pr_{\nu_{W}}(\psi(z)=v|\psi_{s}=\phi).$

Indeed, since $z$ is neutralized in $\nu_{W}$, each element of $V_{i}$ gets
chosen as $\psi(z)$ with probability $1/|V_{i}|$ under $\nu_{W}$. Since $z$ is
not neutralized in $\nu_{1}$, by our earlier observation each vertex gets
chosen as $\psi(z)$ with probability at most $C_{z}(\phi)/|V_{i}|$ under
$\nu_{1}$ conditioned on $\psi_{s}=\phi$. This implies the desired inequality.
Thus in this case, we can write

$\displaystyle\mathop{\mathbb{E}}_{\psi\sim\nu_{1}}[X|\psi_{s}=\phi]$
$\displaystyle\leq\sum_{v\in
V_{i}}C_{z}(\phi)\Pr_{\nu_{W}}(\psi(z)=v|\psi_{s}=\phi)\mathop{\mathbb{E}}_{\psi\sim\nu_{W}}\left[X\cdot\prod_{y\in
I_{W\cup\\{z\\}}}C_{y}(\psi)\right|\left.\vphantom{\prod_{I_{W\cup\\{z\\}}}}\psi_{s+1}=\phi_{v}\right]$
$\displaystyle=\sum_{v\in
V_{i}}\Pr_{\nu_{W}}(\psi(z)=v|\psi_{s}=\phi)\mathop{\mathbb{E}}_{\psi\sim\nu_{W}}\left[X\cdot\prod_{y\in
I_{W}}C_{y}(\psi)\right|\left.\vphantom{\prod_{I_{W}}}\psi_{s+1}=\phi_{v}\right]$
$\displaystyle=\sum_{v\in
V_{i}}\mathop{\mathbb{E}}_{\psi\sim\nu_{W}}\left[X\cdot\prod_{y\in
I_{W}}C_{y}(\psi)\right|\left.\vphantom{\prod_{I_{W}}}\psi_{s}=\phi\right].$

Thus we have completed the induction in either case.

Now we apply 5.4 with $s=0$. This gives the bound

$\mathop{\mathbb{E}}_{\psi\sim\nu_{1}}[X]\leq\mathop{\mathbb{E}}_{\psi\sim\nu_{2}}\left[X\cdot\prod_{y\in
I_{2}\setminus I_{1}}C_{y}(\psi)\right].$

Since $|N(PE_{\psi(f_{y})}(G);G)\cap
V_{y}|\geq\min\\{\theta_{y},\theta_{y}/\omega(y;\psi)\\}$ we have the bound

$C_{y}(\psi)\leq 2\tfrac{|V_{y}|}{\theta_{y}}\max\\{1,\omega(y;\psi)\\}\leq
2\gamma\max\\{1,\omega(y;\psi)\\}$

for all $y\notin V_{K}$. Note that the bound also trivially holds for $y\in
V_{K}$.

Recalling that $I_{2}\setminus I_{1}=J\setminus I_{1}$ is a set of size $t\geq
1$, we conclude that

$\prod_{y\in J\setminus I_{1}}C_{y}(\psi)\leq 2^{t}\gamma^{t}\prod_{y\in
J\setminus I_{1}}\max\\{1,\omega(y;\psi)\\}\leq
2^{t}\gamma^{t}\frac{1}{t}\sum_{y\in J\setminus I_{1}}(1+\omega(y;\psi)^{t}).$

Finally this gives

$\displaystyle\mathop{\mathbb{E}}_{\psi\sim\nu_{1}}[X]$ $\displaystyle\leq
2^{t}\gamma^{t}\mathop{\mathbb{E}}_{\psi\sim\nu_{2}}[X]+\frac{1}{t}\sum_{y\in
J\setminus
I_{1}}\mathop{\mathbb{E}}_{\psi\sim\nu_{2}}[2^{t}\gamma^{t}X\cdot\omega(y;\psi)^{t}]$
$\displaystyle\leq
2^{t}\gamma^{t}\mathop{\mathbb{E}}_{\psi\sim\nu_{2}}[X]+\frac{1}{t}\sum_{y\in
J\setminus
I_{1}}\mathop{\mathbb{E}}_{\psi\sim\nu_{2}}\left[\frac{1}{2}\left(2^{2t}\gamma^{2t}X^{2}+\omega(y;\psi)^{2t}\right)\right]$
$\displaystyle=2^{t}\gamma^{t}\mathop{\mathbb{E}}_{\psi\sim\nu_{2}}[X]+2^{2t-1}\gamma^{2t}\mathop{\mathbb{E}}_{\psi\sim\nu_{2}}[X^{2}]+\frac{1}{2t}\sum_{y\in
J\setminus
I_{1}}\mathop{\mathbb{E}}_{\psi\sim\nu_{2}}\left[\omega(y;\psi)^{2t}\right].\qed$

We now iterate this neutralizing procedure. The following proof is very
similar to [34, Proof of Lemma 4.5] applied to $H^{(1)}$.

######  Lemma 5.9 (cf. [34, Lemma 4.5]).

Suppose we are in 5.4. Assume that $|V_{K}|\geq 2|W_{K}|$. Let $\nu$ be the
probability distribution on maps $\psi\colon V(H)\to V(G)$ induced by
Algorithm 5.5. For all vertices $x\in V(H)$,

$\mathop{\mathbb{E}}_{\psi\sim\nu}[\omega(x;\psi)^{2d}]\leq
2^{2d+1}\gamma^{2d}\mu_{4d}.$

###### Proof.

Fix $x\in V(H)$. We construct a sequence of rooted trees $T_{0}\subseteq
T_{1}\subseteq\cdots\subseteq T_{m}$ whose vertices are labelled by elements
of $V(H)$. Let $T_{0}$ be the tree consisting of the single vertex $a$
labelled $x$. To construct $T_{i+1}$ from $T_{i}$ we do the following
procedure. For each leaf $b$ of $T_{i}$, let $A(b)$ be the set of ancestors of
$b$ in $T_{i}$, and let $I(b)=\bigcup_{c\in A(b)}f_{c}$. In this proof we use
$f_{c}$ to refer to the set $f_{y}$ where $c\in T_{i}$ is labelled by the
vertex $y\in V(H)$. Then we add as children of $b$ new vertices labelled
$f_{b}\setminus I(b)$. Call this set of added vertices $C(b)$.

Note that our trees may have multiple vertices with the same label. However,
the process eventually terminates. Indeed, any path from the root contains
distinct vertices (except that there may be a second vertex labelled $x$ on
the path). Therefore the depth is at most $v(H)$. Call the final tree $T_{m}$.

We define a vertex-weighting $\sigma\colon V(T_{m})\to[0,1]$ as follows.
Define $\sigma(a)=1$ and whenever we add a new vertex which is a child of $b$,
assign it the weight $\sigma(b)/(2|f_{b}\setminus I(b)|)$. Note that total
weight of the new leaves in $T_{i}$ (that is, $V(T_{i})\setminus V(T_{i-1})$)
is $2^{-i}$, so the total weight of the vertices in any of the trees is less
than 2.

Let $\nu_{b}$ be the probability distribution formed from $\nu$ by
neutralizing $I(b)$. For notational convenience let $T_{-1}$ be the empty
tree. We wish to prove that for all $i\geq 0$ the following holds

$\mathop{\mathbb{E}}_{\psi\sim\nu}[\omega(a;\psi)^{2d}]\leq
2^{2d}\gamma^{2d}\mu_{4d}\sum_{b\in V(T_{i-1})}\sigma(b)+\sum_{b\in
V(T_{i})\setminus
V(T_{i-1})}\sigma(b)\mathop{\mathbb{E}}_{\psi\sim\nu_{b}}[\omega(b;\psi)^{2d}].$
(5.6)

We will prove 5.6 by induction on $i$. The base case $i=0$ is trivial since
$I(a)=\emptyset$ so $\nu=\nu_{a}$.

For $b\in V(T_{i+1})\setminus V(T_{i})$, let $\tilde{\nu}_{b}$ be the
probability distribution obtained from $\nu$ by neutralizing $I(b)\cup f_{b}$.
Write $t_{b}=|f_{b}\setminus I(b)|$. By assumption $H$ has skeletal degeneracy
at most $d$ so $t_{b}\leq d$. If $t_{b}\geq 1$ then by Lemma 5.8 (with
$J=f_{b}$) we have

$\displaystyle\mathop{\mathbb{E}}_{\psi\sim\nu_{b}}[\omega(b;\psi)^{2d}]$
$\displaystyle\leq
2^{t_{b}}\gamma^{t_{b}}\mathop{\mathbb{E}}_{\psi\sim\tilde{\nu}_{b}}[\omega(b;\psi)^{2d}]+2^{2t_{b}-1}\gamma^{2t_{b}}\mathop{\mathbb{E}}_{\psi\sim\tilde{\nu}_{b}}[\omega(b;\psi)^{4d}]+\frac{1}{2t_{b}}\sum_{c\in
f_{b}\setminus
I(b)}\mathop{\mathbb{E}}_{\psi\sim\tilde{\nu}_{b}}[\omega(c;\psi)^{2d}]$
$\displaystyle\leq
2^{2d}\gamma^{2d}\mathop{\mathbb{E}}_{\psi\sim\tilde{\nu}_{b}}[\omega(b;\psi)^{4d}]+\frac{1}{2t_{b}}\sum_{c\in
f_{b}\setminus
I(b)}\mathop{\mathbb{E}}_{\psi\sim\tilde{\nu}_{b}}[\omega(c;\psi)^{2d}].$

Since $f_{b}$ is neutralized by $\tilde{\nu}_{b}$ we have that the expectation
that $\mathop{\mathbb{E}}_{\psi\sim\tilde{\nu}_{b}}[\omega(b;\psi)^{4d}]$
agrees with $\mu_{4d}$, defined in (5.3). Furthermore, it follows from the
definitions that for each $c\in f_{b}\setminus I(b)$ we have
$\tilde{\nu}_{b}=\nu_{c}$. Thus we have shown that

$\mathop{\mathbb{E}}_{\psi\sim\nu_{b}}[\omega(b;\psi)^{2d}]\leq
2^{2d}\gamma^{2d}\mu_{4d}+\frac{1}{2t_{b}}\sum_{c\in f_{b}\setminus
I(b)}\mathop{\mathbb{E}}_{\psi\sim\nu_{c}}[\omega(c;\psi)^{2d}]$

whenever $t_{b}>0$.

If $t_{b}=0$, then $f_{b}\subseteq I(b)$. This means that all of $f_{b}$ is
already neutralized by $\nu_{b}$ and so
$\mathop{\mathbb{E}}_{\psi\sim\tilde{\nu}_{b}}[\omega(b;\psi)^{2d}]=\mu_{2d}\leq\mu_{4d}$.
We abuse notation and use the above bound in either case and simply ignore the
second term when $t_{b}=0$.

Putting together these results with the inductive hypothesis, we see that

$\displaystyle\mathop{\mathbb{E}}_{\psi\sim\nu}[\omega(a;\psi)^{2d}]$
$\displaystyle\leq 2^{2d}\gamma^{2d}\mu_{4d}\sum_{b\in
V(T_{i-1})}\sigma(b)+\sum_{b\in V(T_{i})\setminus
V(T_{i-1})}\sigma(b)\mathop{\mathbb{E}}_{\psi\sim\nu_{b}}[\omega(b;\psi)^{2d}]$
$\displaystyle\leq 2^{2d}\gamma^{2d}\mu_{4d}\sum_{b\in V(T_{i-1})}\sigma(b)$
$\displaystyle\qquad\qquad+\sum_{b\in V(T_{i})\setminus
V(T_{i-1})}\sigma(b)\left(2^{2d}\gamma^{2d}\mu_{4d}+\frac{1}{2t_{b}}\sum_{c\in
f_{b}\setminus
I(b)}\mathop{\mathbb{E}}_{\psi\sim\nu_{c}}[\omega(c;\psi)^{2d}]\right)$
$\displaystyle=2^{2d}\gamma^{2d}\mu_{4d}\sum_{b\in
V(T_{i})}\sigma(b)+\sum_{c\in V(T_{i+1})\setminus
V(T_{i})}\sigma(c)\mathop{\mathbb{E}}_{\psi\sim\nu_{c}}[\omega(c;\psi)^{2d}].$

This completes the induction. Finally, 5.6 with $i=m+1$ gives the desired
result. ∎

######  Theorem 5.10 (cf. [34, Theorem 4.2]).

Suppose we are in 5.4. Assume that $|V_{K}|\geq 2|W_{K}|$, that
$\theta_{i}\geq 2|W_{i}|$ for all $i<K$ and that
$2^{2d+2}\gamma^{2d}\mu_{4d}\sum_{i<K}|W_{i}|/\theta_{i}<1$. Then there is an
embedding of $H$ into $G$.

###### Proof.

By Lemma 5.9 for each $i<K$,

$\mathop{\mathbb{E}}_{\psi\sim\nu}\left[\sum_{x\in
W_{i}}\omega(x;\psi)^{2d}\right]\leq|W_{i}|2^{2d+1}\gamma^{2d}\mu_{4d}.$

Thus by Markov’s inequality

$\Pr_{\psi\sim\nu}\left(\sum_{x\in
W_{i}}\omega(x;\psi)^{2d}>\frac{1}{2}\theta_{i}\right)<\frac{|W_{i}|}{\theta_{i}}2^{2d+2}\gamma^{2d}\mu_{4d}.$

Therefore we see that by hypothesis, there is a deterministic map $\phi$ that
satisfies $\Pr(\psi=\phi)>0$ and $\sum_{x\in
W_{i}}\omega(x;\phi)^{2d}\leq\tfrac{1}{2}\theta_{i}$ for all $i\in[K]$. By
Lemma 5.7, $\phi$ is an embedding of $H$ into $G$. ∎

###  5.3. Putting it all together

####  5.3.1. Partitioning $H$

Say that two vertices of a hypergraph $H$ are neighbors if they are adjacent
in the 1-skeleton $H^{(1)}$.

######  Lemma 5.11.

Let $H$ be an $n$-vertex, $k$-uniform, $k$-partite hypergraph with
${d_{1}({H})}\leq d$ and vertex partition $V(H)=W_{1}\sqcup\cdots\sqcup
W_{k}$. There exists a refinement of the partition
$\\{W_{i}^{(j)}\\}_{i\in[T],j\in[k]}$, with the following properties:

  1. (i)

$T\leq\log_{2}n$;

  2. (ii)

for all $i\in[T]$, $j\in[k]$, we have $|W_{i}^{(j)}|\leq 2^{-i+1}n$;

  3. (iii)

for all $j\in[k]$, the set $\bigcup_{i\in[T]}W_{i}^{(j)}=W_{j}$; and

  4. (iv)

for all $i\in[T]$, $j\in[k]$, each vertex in $W_{i}^{(j)}$ has at most $4d$
neighbors in $\bigcup_{i^{\prime}\geq
i,j^{\prime}\in[k]}W_{i^{\prime}}^{(j^{\prime})}$.

######  Remark.

Lemma 5.11 follows by applying [34, Lemma 3.1] to $H^{(1)}$. For completeness
we include the proof here as well.

###### Proof.

Let $U_{1}=V(H)$, and recursively define $U_{i+1}\subseteq U_{i}$ to be the
set of vertices having degree at least $4d$ in the induced subgraph
$H^{(1)}[U_{i}]$. Finally define $V_{i}=U_{i}\setminus U_{i+1}$ and
$W_{i}^{(j)}=V_{i}\cap W_{j}$.

By assumption $H^{(1)}$ is $d$-degenerate. Hence there are at most $d|U_{i}|$
edges in $H^{(1)}[U_{i}]$, so $4d|U_{i+1}|\leq 2d|U_{i}|$. Equivalently,
$2|U_{i+1}|\leq|U_{i}|$. Therefore $U_{T+1}=\emptyset$ for some
$T\leq\log_{2}n$, which gives (i). Because $2|U_{i+1}|\leq|U_{i}|$, we have
$|W_{i}^{(j)}|\leq|U_{i}|\leq 2^{-i+1}|U_{1}|=2^{-j+1}n$, which gives (ii).

Meanwhile we have $\bigcup_{i\in[T]}V_{i}=U_{1}\setminus U_{T+1}=V(H)$ which
immediately implies (iii). Finally, $W_{i}^{(j)}\subseteq U_{i}\setminus
U_{i+1}$, and $\bigcup_{i^{\prime}\geq
i,j^{\prime}\in[k]}W_{i^{\prime}}^{(j^{\prime})}=U_{i}$, so all vertices in
$W_{i}^{(j)}$ have degree less than $4d$ in $H^{(1)}[U_{i}]$, thereby
establishing (iv) as desired. ∎

####  5.3.2. Partitioning $G$

In the proof of Theorem 5.1, after applying Corollary 5.3, we will construct a
subhypergraph of $G$ in which we have good control of the $\theta$-defect.
Lemma 5.13 asserts that such a subhypergraph exists. To prove Lemma 5.13 we
rely on the next lemma, which quantifies the way in which $\mu_{\theta,t}$
controls the worst-case behavior of the $\theta$-defect. (Note that
$\mu_{\theta,t}$ controls the average-case behavior of the defect by
definition.)

######  Lemma 5.12.

Let $G$ be a $k$-uniform $k$-partite hypergraph on $V_{1}\sqcup\cdots\sqcup
V_{k}$. For any $i,\theta,t$ and $\mathcal{Q}$ a collection of subsets of
$V(G)\setminus V_{i}$, if $\mu_{\theta,t}(\mathcal{Q},V_{i};G)>0$ then every
tuple $Q\in\mathcal{Q}$ satisfies

$|N(PE_{Q}(G);G)\cap
V_{i}|\geq\frac{\theta}{(|\mathcal{Q}|\cdot\mu_{\theta,t}(\mathcal{Q},V_{i};G))^{1/t}}.$

If $\mu_{\theta,t}(\mathcal{Q},V_{i};G)=0$ then every tuple $Q\in\mathcal{Q}$
satisfies $|N(PE_{Q}(G);G)\cap V_{i}|\geq\theta$.

###### Proof.

If $\mu_{\theta,t}(\mathcal{Q},V_{i};G)=0$ then, by definition of
$\mu_{\theta,t}$ and $\omega_{\theta}$ (see (5.1), (5.2), and (5.3)) we have
$|N(PE_{Q}(G);G)\cap V_{i}|\geq\theta$ for every $Q\in\mathcal{Q}$.

Henceforth, we assume that $\mu_{\theta,t}(\mathcal{Q},V_{i};G)>0$. By (5.2),
if $\omega_{\theta}(x)\neq 0$ then $\omega_{\theta}(x)>1$. Since
$\mu_{\theta,t}(\mathcal{Q},V_{i};G)>0$, by (5.3) we actually have
$|\mathcal{Q}|\cdot\mu_{\theta,t}(\mathcal{Q},V_{i};G)\geq 1$.

Let $Q\in\mathcal{Q}$. Suppose, for a contradiction, that

$|N(PE_{Q}(G);G)\cap
V_{i}|<\frac{\theta}{(|\mathcal{Q}|\cdot\mu_{\theta,t}(\mathcal{Q},V_{i};G))^{1/t}}<\theta$

(with the last inequality following from the discussion above). Then by 5.3 we
have

$|\mathcal{Q}|\cdot\mu_{\theta,t}(\mathcal{Q},V_{i};G)\geq\omega_{\theta}(|N(PE_{Q}(G);G)\cap
V_{i}|)^{t}=\left(\frac{\theta}{|N(PE_{Q}(G);G)\cap V_{i}|}\right)^{t}.$

This contradicts our assumption, proving the desired bound on the size of the
common neighborhood of $Q$. ∎

######  Lemma 5.13 (cf. [34, Lemmas 5.3 and 6.2]).

There exists an absolute constant $C$ such that the following holds. Fix any
$T,d,t,k,m,\theta\in\mathbb{N}$ and $\varepsilon,\varepsilon^{\prime}\in(0,1)$
that satisfy $k\geq 2$, $t\geq 4d$,
$m\geq\left(\frac{k^{d}Tt}{\varepsilon^{d}\varepsilon^{\prime}}\right)^{C}$
and $\theta\geq\varepsilon m$. Fix constants $p_{1},p_{2},\ldots,p_{T}\geq
m^{-1/(10d)}$ such that $\sum_{i}p_{i}\leq 1$. Let $\theta_{i}=p_{i}\theta/4$
for each $i\in[T]$. Let $G$ be a $k$-uniform $k$-partite hypergraph on
$A_{1}\sqcup\cdots\sqcup A_{k}$. Suppose that $\varepsilon m\leq|A_{j}|\leq m$
and $\mu_{\theta,t}(A_{-j}^{d},A_{j};G)<\tfrac{1}{2}$ for each $j\in[T]$. Then
there exist disjoint sets $V_{i}^{(j)}$ for $i\in[T]$ and $j\in[k]$ such that

  1. (i)

$V_{i}^{(j)}\subseteq A_{j}$ and
$\tfrac{1}{4}p_{i}|A_{j}|\leq|V_{i}^{(j)}|\leq p_{i}|A_{j}|$ for all $i\in[T]$
and $j\in[k]$,

  2. (ii)

for all $i\in[T]$, $j\in[k]$ and $i_{1},\ldots,i_{d}\in[T]$,
$j_{1},\ldots,j_{d}\in[k]\setminus\\{j\\}$,

$\mu_{\theta_{i},t}\left(\prod_{a=1}^{d}V_{i_{a}}^{(j_{a})},V_{i}^{(j)};G\right)\leq\max\left\\{\varepsilon^{\prime},8\varepsilon^{-d}k^{d}\mu_{\theta,t}(A_{-j}^{d},A_{j};G)\right\\}.$

We will prove the lemma by giving a randomized construction for the sets
$V_{i}^{(j)}$ and then showing that they satisfy Items i and ii with positive
probability. A naïve attempt at such a construction might be to take
$V_{i}^{(j)}$ as a uniformly random subset of $A_{j}$ of size $p_{i}|A_{j}|$
(in such a way that the sets are disjoint) and then attempt to prove that Item
ii holds with positive probability. Indeed, this is almost the approach we
use. However, in order to prove Item ii we rely on McDiarmid’s inequality. To
apply this we would require the average defect to satisfy a bounded
differences condition, which in fact fails in general. To rectify this, we
precede the random construction by removing vertices that might violate our
desired bounded differences condition.

We first state the versions of Hoeffding’s inequality and McDiarmid’s
inequality that we use.

######  Theorem 5.14 (Hoeffding’s inequality (see, e.g., [42, Theorem 2.2.6]).

Let $X_{1},\ldots,X_{N}$ be independent $\\{0,1\\}$-valued random variables.
Then for any $t\geq 0$,

$\Pr\left(\sum_{i=1}^{N}(X_{i}-\mathop{\mathbb{E}}[X_{i}])\geq
t\right)\leq\exp\left(-\frac{2t^{2}}{N}\right).$

######  Theorem 5.15 (McDiarmid’s inequality (see, e.g., [42, Theorem 2.9.1]).

Let $\mathcal{S}$ be a finite set and let $X_{1},\ldots,X_{N}$ be independent
$\mathcal{S}$-valued random variables. Let
$f\colon\mathcal{S}^{N}\to\mathbb{R}$ be a function such that
$|f(X)-f(X^{\prime})|\leq c$ where $X,X^{\prime}\in\mathcal{S}^{N}$ are
arbitrary $N$-tuples that agree on $N-1$ coordinates. Then for any $t\geq 0$,

$\Pr\left(f(X_{1},\ldots,X_{n})-\mathop{\mathbb{E}}[f(X_{1},\ldots,X_{n})]\geq
t\right)\leq\exp\left(-\frac{2t^{2}}{c^{2}N}\right).$

###### Proof of Lemma 5.13.

For each $j\in[k]$ we define $B_{j}\subseteq A_{j}$ by removing the vertices
that contribute too much to any $\mu_{\theta,t}(A_{-i}^{d},A_{i};G)$.
Specifically, for each $i\in[k]$ let $R_{i}\subseteq A_{-i}$ be the set of
vertices $v\in A_{-i}$ such that

$\sum_{Q:v\in Q\in
A_{-i}^{d}}\omega_{\theta}(Q,A_{i};G)^{t}\geq|A_{-i}|^{d-5/8}.$

By definition (see (5.3))

$\mu_{\theta,t}(A_{-i}^{d},A_{i};G)=\frac{1}{d|A_{-i}^{d}|}\sum_{v\in
A_{-i}^{d}}\sum_{{Q\in A_{-i}^{d}:v\in Q}}\omega_{\theta}(Q,A_{i};G)^{t}.$

Hence

$|R_{i}|\cdot|A_{-i}|^{d-5/8}\leq
d|A_{-i}|^{d}\mu_{\theta,t}(A_{-i}^{d},A_{i};G),$

so, applying the lemma’s assumptions, $|R_{i}|\leq dkm^{5/8}$ for all
$i\in[k]$.

Next, for each $j\in[k]$ define $B_{j}=A_{j}\setminus\bigcup_{i\neq j}R_{i}$.
Fix some $j\in[k]$. By the bound above we have
$|B_{j}|\geq|A_{j}|-dk^{2}m^{5/8}$. By our assumption on $m$ (and taking $C$
sufficiently large) we have
$m^{3/8}\geq\frac{t^{2}k^{2}}{\varepsilon}\geq\frac{dk^{2}}{\varepsilon}(1-2^{-\frac{1}{2d}})^{-1}$.
Using the additional assumption that $|A_{j}|\geq\varepsilon m$ we conclude
that

$|B_{j}|\geq|A_{j}|\left(1-dk^{2}\frac{m^{5/8}}{|A_{j}|}\right)\geq|A_{j}|\left(1-\frac{dk^{2}}{\varepsilon
m^{3/8}}\right)\geq 2^{-1/(2d)}|A_{j}|.$ (5.7)

Similarly, for every $Q\in A_{-j}^{d}$ we have $|N(PE_{Q}(G);G)\cap
B_{j}|\geq|N(PE_{Q}(G);G)\cap A_{j}|-dk^{2}m^{5/8}$. By Lemma 5.12, the
assumption $\mu_{\theta,t}(A^{d}_{-j},A_{j};G)<1/2$, and the assumption $t\geq
4d$ we have $|N(PE_{Q}(G);G)\cap
A_{j}|\geq\theta|A_{-j}|^{-d/t}\geq\theta|A_{-j}|^{-1/4}\geq\varepsilon
k^{-1/4}m^{3/4}$. (If $\mu_{\theta,t}(A^{d}_{-j},A_{j};G)=0$ then we have the
stronger bound $|N(PE_{Q}(G);G)\cap A_{j}|\geq\theta$.) Again by our
assumption on $m$, taking $C$ sufficiently large, we have
$m^{1/8}\geq\frac{t^{2}k^{9/4}}{\varepsilon}\geq\frac{dk^{9/4}}{\varepsilon}(1-2^{-1/(2t)})^{-1}$
which implies that $|N(PE_{Q}(G);G)\cap B_{j}|\geq
2^{-1/(2t)}|N(PE_{Q}(G);G)\cap A_{j}|$. Thus

$\begin{split}\mu_{\theta,t}(B_{-j}^{d},B_{j};G)&=\frac{1}{|B_{-j}|^{d}}\sum_{Q\in
B_{-j}^{d}}\omega_{\theta}(|N(PE_{Q}(G);G)\cap B_{j}|)^{t}\\\
&\leq\frac{2^{1/2}}{|B_{-j}|^{d}}\sum_{Q\in
B_{-j}^{d}}\omega_{\theta}(|N(PE_{Q}(G);G)\cap A_{j}|)^{t}\\\
&\leq\frac{2}{|A_{-j}|^{d}}\sum_{Q\in
B_{-j}^{d}}\omega_{\theta}(|N(PE_{Q}(G);G)\cap A_{j}|)^{t}\\\ &\leq
2\mu_{\theta,t}(A_{-j}^{d},A_{j};G).\end{split}$ (5.8)

We also obtain the lower bound

$|N(PE_{Q}(G);G)\cap B_{j}|\geq 2^{-1/(2t)}\varepsilon
k^{-1/4}m^{3/4}\geq\varepsilon k^{-1/4}m^{3/4}\\!/2.$ (5.9)

Finally, for every vertex $v\in B_{-j}$, applying similar reasoning and the
definition of $B_{-j}$ we have

$\sum_{Q:v\in Q\in B_{-j}^{d}}\omega_{\theta}(Q,B_{j};G)^{t}\leq
2^{1/2}\sum_{Q:v\in Q\in A_{-j}^{d}}\omega_{\theta}(Q,A_{j};G)^{t}\leq
2^{1/2}|A_{-j}|^{d-5/8}\leq 2|B_{-j}|^{d-5/8}.$ (5.10)

We now give a randomized construction for the desired sets $V_{i}^{(j)}$, and
show that Items i and ii are satisfied with positive probability. For each
$j\in[k],i\in[T]$, and vertex $v\in B_{j}$ we assign $v$ to $V_{i}^{(j)}$ with
probability $q_{i}=p_{i}/2$ (so that $v$ is assigned to at most one set and to
no set with probability $1-\sum_{i}q_{i}$). We make these assignments
independently for each vertex. In this way we obtain the sets
$\\{V_{i}^{(j)}\\}_{j\in[k],i\in[T]}$ which by construction are disjoint and
also satisfy $V_{i}^{(j)}\subseteq A_{j}$ for every $i$ and $j$.

Let $E_{1}$ be the event that for all $i\in[T]$, for all $j\in[k]$, and for
all $Q\in B_{-j}^{d}$ we have

$|N(PE_{Q}(G);G)\cap V_{i}^{(j)}|\geq\frac{q_{i}}{2}|N(PE_{Q}(G);G)\cap
B_{j}|.$

Let $E_{2}$ be the event that for all $i\in[T]$, $j\in[k]$ and
$i_{1},\ldots,i_{d}\in[T]$, $j_{1},\ldots,j_{d}\in[k]\setminus\\{i\\}$,

$\mu_{\theta,t}\left(\prod_{a=1}^{d}V_{i_{a}}^{(j_{a})},B_{j};G\right)\leq\max\left\\{\varepsilon^{\prime},4\varepsilon^{-d}k^{d}\mu_{\theta,t}(B_{-j}^{d},B_{j};G)\right\\}.$

Let $E_{3}$ be the event that for all $i\in[T]$, $j\in[k]$ we have

$\frac{q_{i}}{2^{1/(2d)}}|B_{j}|\leq|V_{i}^{(j)}|\leq 2q_{i}|B_{j}|.$

We will prove that with positive probability, all of $E_{1},E_{2},E_{3}$
occur. We will then show that $E_{1}\land E_{2}\land E_{3}$ implies Items i
and ii.

We begin with $E_{3}$. Fix $i\in[T]$ and $j\in[k]$. By Hoeffding’s inequality
(Theorem 5.14),

$\displaystyle\Pr\left(|V_{i}^{(j)}|<\frac{q_{i}}{2^{1/(2d)}}|B_{j}|\right)$
$\displaystyle\leq\exp\left(-\frac{2(q_{i}|B_{j}|(1-2^{-1/(2d)}))^{2}}{m}\right),$
$\displaystyle\Pr\left(|V_{i}^{(j)}|>2q_{i}|B_{j}|\right)$
$\displaystyle\leq\exp\left(-\frac{2(q_{i}|B_{j}|)^{2}}{m}\right).$

Using the assumption that $p_{i}\geq m^{-1/(10d)}$, the inequality
$1-2^{-1/(2x)}\geq 1/(4x)$ (which holds for all $x>0$), and (5.7) we obtain
the inequality

$q_{i}|B_{j}|\geq\left(1-2^{-1/(2d)}\right)q_{i}|B_{j}|\geq\left(\frac{1}{4d}\right)\left(\frac{1}{2}m^{-1/(10d)}\right)\left(2^{-1/(2d)}\varepsilon
m\right)\geq\frac{\varepsilon m^{9/10}}{16d}.$

Union-bounding over all choices of $i,j$, we see that

$\Pr(\neg E_{3})\leq
2Tk\exp\left(-\frac{\varepsilon^{2}m^{4/5}}{128d^{2}}\right).$

By our assumption on $m$ and taking $C$ sufficiently large we have
$m^{4/5}\geq\frac{t^{6}Tk}{\varepsilon^{2}}\geq\frac{4^{6}d^{2}Tk}{\varepsilon^{2}}$,
so

$2Tk\exp\left(-\frac{\varepsilon^{2}m^{4/5}}{128d^{2}}\right)\leq
2Tke^{-32Tk}<1/4.$

We turn out attention to $E_{1}$, for which the analysis is similar. Fix
$i\in[T]$, $j\in[k]$, and $Q\in B_{-j}^{d}$. By Hoeffding’s inequality
(Theorem 5.14),

$\Pr\left(|N(PE_{Q}(G);G)\cap V_{i}^{(j)}|<\frac{q_{i}}{2}|N(PE_{Q}(G);G)\cap
B_{j}|\right)\leq\exp\left(-\frac{2(q_{i}|N(PE_{Q}(G);G)\cap
B_{j}|/2)^{2}}{m}\right).$

Applying (5.9) we obtain

$q_{i}|N(PE_{Q}(G);G)\cap B_{j}|\geq\tfrac{1}{2}m^{-1/(10d)}\varepsilon
k^{-1/4}m^{3/4}\\!/2\geq\varepsilon k^{-1/4}m^{13/20}\\!/4.$

Union-bounding over all choices of $i,j,Q$, we see that

$\Pr(\neg E_{1})\leq
Tk(km)^{d}\exp\left(-\frac{\varepsilon^{2}m^{13/10}}{32k^{1/2}m}\right)=Tk(km)^{d}\exp\left(-\frac{\varepsilon^{2}m^{3/10}}{32k^{1/2}}\right).$

Repeatedly applying the assumption on $m$, as long as $C$ is sufficiently
large we have $4Tk(km)^{d}\leq m^{2d}$ and $m^{3/20}\geq\log m$ as well as
$m^{3/20}\geq 64dk^{1/2}/\varepsilon^{2}$. Putting these together we obtain
$\Pr(\neg E_{1})\leq 1/4$.

Finally we consider $E_{2}$. First we study the related event
$E_{2}^{\prime}$, defined to be the event that for all $i\in[T]$, $j\in[k]$
and $i_{1},\ldots,i_{d}\in[T]$, $j_{1},\ldots,j_{d}\in[k]\setminus\\{j\\}$,
writing $\mathcal{Q}=\prod_{a=1}^{d}V_{i_{a}}^{(j_{a})}$ and
$\mathcal{B}=\prod_{a=1}^{d}B_{j_{a}}$, we have

$|\mathcal{Q}|\mu_{\theta,t}\left(\mathcal{Q},B_{j};G\right)\leq|\mathcal{B}|\prod_{a=1}^{d}q_{i_{a}}\cdot\max\left\\{2\mu_{\theta,t}(\mathcal{B},B_{j};G),\frac{\varepsilon^{\prime}}{2}\right\\}.$

Fix some $i\in[T]$, $j\in[k]$ and $i_{1},\ldots,i_{d}\in[T]$,
$j_{1},\ldots,j_{d}\in[k]\setminus\\{j\\}$. Let $\mathcal{Q},\mathcal{B}$ be
as defined above. Then

$\displaystyle\mathop{\mathbb{E}}\left[|\mathcal{Q}|\mu_{\theta,t}\left(\mathcal{Q},B_{j};G\right)\right]$
$\displaystyle=\mathop{\mathbb{E}}\left[\sum_{Q\in\mathcal{Q}}\omega_{\theta}(|N(PE_{Q}(G);G)\cap
B_{j}|)^{t}\right]$
$\displaystyle=\sum_{Q\in\mathcal{B}}\omega_{\theta}(|N(PE_{Q}(G);G)\cap
B_{j}|)^{t}\cdot\Pr(Q\in\mathcal{Q})$

Let $\partial\mathcal{B}$ be the subset of $\mathcal{B}$ that consists of
$d$-tuples with at least one repeated coordinate. For
$Q\in\mathcal{B}\setminus\partial\mathcal{B}$ we have
$\Pr(Q\in\mathcal{Q})=\prod_{a=1}^{d}q_{i_{a}}$. Thus we see

$\displaystyle\mathop{\mathbb{E}}\left[|\mathcal{Q}|\mu_{\theta,t}\left(\mathcal{Q},B_{j};G\right)\right]$
$\displaystyle\leq|\mathcal{B}|\prod_{a=1}^{d}q_{i_{a}}\cdot\mu_{\theta,t}(\mathcal{B},B_{j};G)+\sum_{Q\in\partial\mathcal{B}}\omega_{\theta}(|N(PE_{Q}(G);G)\cap
B_{j}|)^{t}.$

Observe that for $Q\subseteq Q^{\prime}$ it holds that
$\omega_{\theta}(|N(PE_{Q}(G);G)\cap
B_{j}|)\leq\omega_{\theta}(|N(PE_{Q^{\prime}}(G);G)\cap B_{j}|)$. Thus, for
every $\ell\in[d]$, we have

$\sum_{Q\in\prod_{a\in[d]\setminus\\{\ell\\}}B_{j_{a}}}\omega_{\theta}(|N(PE_{Q}(G);G)\cap
B_{j}|)^{t}\leq\frac{1}{|B_{j_{\ell}}|}\sum_{Q\in\mathcal{B}}\omega_{\theta}(|N(PE_{Q}(G);G)\cap
B_{j}|)^{t}.$

Using the bound $|B_{j_{\ell}}|\geq 2^{-1/(2d)}\varepsilon m$ (which follows
from (5.7) and the assumption $|A_{j_{\ell}}|\geq\varepsilon m$) and summing
over all $d(d-1)/2$ choices of where the repeated coordinates occur, we have
the bound

$\displaystyle\sum_{Q\in\partial\mathcal{B}}\omega_{\theta}(|N(PE_{Q}(G);G)\cap
B_{j}|)^{t}$ $\displaystyle\leq\frac{d(d-1)}{2\cdot 2^{-1/(2d)}\varepsilon
m}\sum_{Q\in\mathcal{B}}\omega_{\theta}(|N(PE_{Q}(G);G)\cap B_{j}|)^{t}$
$\displaystyle\leq\frac{d(d-1)}{2\cdot 2^{-1/(2d)}\varepsilon
m}|B_{-j}|^{d}\mu_{\theta,t}(B_{-j}^{d},B_{j};G)$
$\displaystyle\leq\frac{d(d-1)}{2\cdot 2^{-1/(2d)}\varepsilon m}k^{d}m^{d}$

(where the final inequality follows from (5.8) and the assumption
$\mu_{\theta,t}(A_{-j}^{d},A_{j};G)\leq 1/2$). Thus

$\mathop{\mathbb{E}}[|\mathcal{Q}|\mu_{\theta,t}\left(\mathcal{Q},B_{j};G\right)]\leq|\mathcal{B}|\prod_{a=1}^{d}q_{i_{a}}\cdot\mu_{\theta,t}(\mathcal{B},B_{j};G)+\varepsilon^{-1}d^{2}k^{d}m^{d-1}.$

Observe that (5.10) and the bound $|B_{-j}|\leq km$ imply that the random
variable $|\mathcal{Q}|\mu_{\theta,t}\left(\mathcal{Q},B_{j};G\right)$ only
changes by at most $2k^{d}m^{d-5/8}$ when the assignment of a single vertex
$v$ to a part $V_{i}^{(j)}$ is changed. Thus by McDiarmid’s inequality
(Theorem 5.15) we see that

$\Pr\left(|\mathcal{Q}|\mu_{\theta,t}\left(\mathcal{Q},B_{j};G\right)\geq|\mathcal{B}|\prod_{a=1}^{d}q_{i_{a}}\cdot\max\left\\{2\mu_{\theta,t}(\mathcal{B},B_{j};G),\frac{\varepsilon^{\prime}}{2}\right\\}\right)\leq\exp\left(-\frac{2\Delta^{2}}{m(2k^{d}m^{d-5/8})^{2}}\right)$

where

$\displaystyle\Delta$
$\displaystyle=|\mathcal{B}|\prod_{a=1}^{d}q_{i_{a}}\cdot\max\left\\{2\mu_{\theta,t}(\mathcal{B},B_{j};G),\frac{\varepsilon^{\prime}}{2}\right\\}-\left(|\mathcal{B}|\prod_{a=1}^{d}q_{i_{a}}\cdot\mu_{\theta,t}(\mathcal{B},B_{j};G)+\varepsilon^{-1}d^{2}k^{d}m^{d-1}\right)$
$\displaystyle\geq|\mathcal{B}|\prod_{a=1}^{d}q_{i_{a}}\cdot\max\left\\{\mu_{\theta,t}(\mathcal{B},B_{j};G),\frac{\varepsilon^{\prime}}{4}\right\\}-\varepsilon^{-1}d^{2}k^{d}m^{d-1}.$

The last line follows from the easy inequality
$\max\\{x,y\\}-x/2\geq\max\\{x/2,y/2\\}$.

Note that
$\prod_{a=1}^{d}q_{i_{a}}\geq(\tfrac{1}{2}m^{-1/(10d)})^{d}=2^{-d}m^{-1/10}$.
Also, $|\mathcal{B}|\geq(2^{-1/(2d)}\varepsilon
m)^{d}=2^{-1/2}\varepsilon^{d}m^{d}$. We bound the maximum from below by
$\varepsilon^{\prime}/4$, giving

$\Delta\geq
2^{-d-5/2}\varepsilon^{d}\varepsilon^{\prime}m^{d-1/10}-\varepsilon^{-1}d^{2}k^{d}m^{d-1}\geq
2^{-4d}\varepsilon^{d}\varepsilon^{\prime}m^{d-1/10},$

where the last inequality follows from our assumed lower bound on $m$ and
provided that $C$ is sufficiently large.

Union-bounding over all choices of $i,j,i_{1},\ldots,i_{d},j_{1},\ldots,j_{d}$
we see that

$\Pr(\neg
E_{2}^{\prime})\leq(Tk)^{d+1}\exp\left(-\frac{2(2^{-4d}\varepsilon^{d}\varepsilon^{\prime}m^{d-1/10})^{2}}{4k^{2d}m^{2d-1/4}}\right)=(Tk)^{d+1}\exp\left(-\frac{\varepsilon^{2d}\varepsilon^{\prime
2}}{2^{8d+1}k^{2d}}m^{1/20}\right).$

Assuming that $C$ is sufficiently large, we have
$m^{1/20}\geq\frac{2^{10d}k^{2d}}{\varepsilon^{2d}\varepsilon^{\prime
2}}(d+1)\log(Tkt)$. Then $\Pr(\neg E_{2}^{\prime})\leq t^{-d-1}<1/4$.

It now follows that $\Pr(E_{1}\land E_{2}^{\prime}\land E_{3})\geq 1-\Pr(\neg
E_{1})-\Pr(\neg E_{2}^{\prime})-\Pr(\neg E_{3})\geq 1/4$. Thus, with positive
probability all of $E_{1},E_{2}^{\prime},E_{3}$ occur. When this happens we
have that

$\displaystyle\mu_{\theta,t}\left(\prod_{a=1}^{d}V_{i_{a}}^{(j_{a})},B_{j};G\right)$
$\displaystyle\leq\frac{|\mathcal{B}|}{|\mathcal{Q}|}\prod_{a=1}^{d}q_{i_{a}}\max\left\\{2\mu_{\theta,t}(\mathcal{B},B_{j};G),\tfrac{\varepsilon^{\prime}}{2}\right\\}$
$\displaystyle\leq\max\left\\{2^{3/2}\mu_{\theta,t}(\mathcal{B},B_{j};G),\varepsilon^{\prime}\right\\},$

where the first inequality follows from $E_{2}^{\prime}$ and the second from
the fact that $E_{3}$ implies $|\mathcal{B}|\prod_{a=1}^{d}q_{i_{a}}\leq
2^{1/2}|\mathcal{Q}|$. Finally

$\mu_{\theta,t}(\mathcal{B},B_{j};G)\leq\frac{|B_{-j}|^{d}}{|\mathcal{B}|}\mu_{\theta,t}(B_{-j}^{d},B_{j};G)\leq\left(\frac{km}{2^{-1/(2d)}\varepsilon
m}\right)^{d}\mu_{\theta,t}(B_{-j}^{d},B_{j};G),$

so when $E_{1},E_{2}^{\prime},E_{3}$ occur, $E_{2}$ also occurs.

To finish the proof we show that when $E_{1}\land E_{2}\land E_{3}$ occurs the
desired conclusions are satisfied. By $E_{3}$ we have $|V_{i}^{(j)}|\leq
2q_{i}|B_{j}|\leq 2q_{i}|A_{j}|=p_{i}|A_{j}|$ and

$|V_{i}^{(j)}|\geq\frac{q_{i}}{2^{1/(2d)}}|B_{j}|\geq\frac{q_{i}}{2^{1/d}}|A_{j}|\geq\tfrac{1}{4}p_{i}|A_{j}|$

where the middle inequality follows from (5.7). Thus Item i holds.
Furthermore, for all $i,j,Q$ by $E_{1}$ we have

$|N(PE_{Q}(G);G)\cap V_{i}^{(j)}|\geq\frac{q_{i}}{2}|N(PE_{Q}(G);G)\cap
B_{j}|$

so since $\theta_{i}=q_{i}\theta/2$ we have
$\omega_{\theta_{i}}(Q,V_{i}^{(j)};G)\leq\omega_{\theta}(Q,B_{j};G)$. Thus

$\displaystyle\mu_{\theta_{i},t}\left(\prod_{a=1}^{d}V_{i_{a}}^{(j_{a})},V_{i}^{(j)};G\right)$
$\displaystyle\leq\mu_{\theta,t}\left(\prod_{a=1}^{d}V_{i_{a}}^{(j_{a})},B_{j};G\right)$
$\displaystyle\leq\max\left\\{\varepsilon^{\prime},4\varepsilon^{-d}k^{d}\mu_{\theta,t}(B_{-j}^{d},B_{j};G)\right\\}$
(since $E_{2}$ occurs)
$\displaystyle\leq\max\left\\{\varepsilon^{\prime},8\varepsilon^{-d}k^{d}\mu_{\theta,t}(A_{-j}^{d},A_{j};G)\right\\}.$

Therefore we have shown with positive probability the sets $V_{i}^{(j)}$
satisfy the desired properties. ∎

####  5.3.3. Finishing up

###### Proof of Theorem 5.1.

Let $H$ be a $k$-partite $k$-uniform hypergraph on $h$ vertices with
${d_{1}({H})}=d$. Since ${d_{1}({H})}>0$ we conclude that $H$ is nonempty,
which implies that $d\geq k-1$. Let $V(H)=W_{1}\sqcup\cdots\sqcup W_{k}$ be
the vertex partition of $H$. We apply Lemma 5.11 to further partition $H$.
This produces $W_{i}^{(j)}$ for $i\in[T]$, $j\in[k]$ with $T\leq\log_{2}h$.
For each $j\in[k]$ such that $W_{T}^{(j)}$ is empty we modify $H$ by adding an
isolated vertex to $H$ that is in this vertex set. We abuse notation and also
refer to the modified hypergraph as $H$.

Define

$\eta=\frac{p^{\frac{4d}{k-1}(16d+1)^{k}}}{2^{2^{4d}+1}k^{4d+1}}\qquad\text{and}\qquad\theta=\eta^{3}n.$

Let $G$ be a $k$-partite $k$-uniform hypergraph with parts consisting of $n$
vertices each and with at least $pn^{k}$ edges. By Corollary 5.3 (applied with
$t=16d$, and noting that $4d\geq k-1$) we can find a subhypergraph
$G^{\prime}$ of $G$ with vertex parts $A_{1}\sqcup\cdots\sqcup A_{k}$ with at
least $\tfrac{1}{2}p^{(16d+1)^{k}}n^{k}$ edges such that

$\mu_{\theta,16d}(A_{-j}^{4d},A_{j};G^{\prime})\leq
2^{2^{4d}+1}k^{4d+1}p^{-\frac{4d}{k-1}(16d+1)^{k}}\left(\frac{\theta}{n}\right)^{16d}\leq\eta^{47d}.$

for each $j\in[k]$.

We apply Lemma 5.13 with parameters
$(T,d,t,k,m,\theta,\varepsilon,\varepsilon^{\prime})=(T,4d,16d,k,n,\theta,\eta^{3},\eta^{34d}$).
We quickly verify that the assumptions of Lemma 5.13 hold. Clearly, we have
$k\geq 2$ and $16d\geq 4\cdot 4d$. Let $C$ be the universal constant from
Lemma 5.13. By taking $c_{p,d,k}$ sufficiently small and noting that Theorem
5.1 holds vacuously when $c_{p,k,d}n<1$, we may assume that $n$ is
sufficiently large that $n\geq\left(\frac{k^{4d}T\cdot
16d}{(\eta^{3})^{d}\eta^{34d}}\right)^{C}$ holds. By definition
$\theta\geq\eta^{3}n$.

For each $i\in[T]$, let $p_{i}=c2^{-i/(80d)}$ where $c$ is the normalizing
constant such that $\sum_{i}p_{i}=1$. We have

$c=\frac{1}{\sum_{i=1}^{T}2^{-i/(80d)}}\geq\frac{1}{160d}.$

Then $\sum p_{i}\leq 1$ and $p_{i}\geq p_{T}\geq
2^{-\log_{2}n/(80d)}/(160d)\geq n^{-1/(40d)}$ (since we can assume that
$n>(160d)^{80d}$).

Since $G^{\prime}$ has at least $\tfrac{1}{2}p^{(16d+1)^{k}}n^{k}$ edges, we
see that $\eta^{3}n\leq\tfrac{1}{2}p^{(16d+1)^{k}}n\leq|A_{j}|\leq n$ for each
$j\in[k]$. Finally, we know that
$\mu_{\theta,16d}(A_{-j}^{4d},A_{j};G)\leq\eta^{47d}<\tfrac{1}{2}$.

Having verified its assumptions, Lemma 5.13 now produces disjoint sets
$V_{i}^{(j)}$ for $i\in[T]$, $j\in[k]$ such that
$\tfrac{1}{4}p_{i}|A_{j}|\leq|V_{i}^{(j)}|\leq p_{i}|A_{j}|\leq p_{i}n$ and

$\mu_{\theta_{i},16d}\left(\prod_{a=1}^{4d}V_{i_{a}}^{(j_{a})},V_{i}^{(j)};G\right)\leq\max\left\\{\eta^{34d},8\eta^{-12d}k^{4d}\mu_{\theta,16d}(A_{-j}^{4d},A_{j};G)\right\\}=\eta^{34d}$

for all $i\in[T]$, $j\in[k]$ and $i_{1},\ldots,i_{4d}\in[T]$,
$j_{1},\ldots,j_{4d}\in[k]\setminus\\{j\\}$. In the above expression,
$\theta_{i}=p_{i}\theta/4$.

Now we wish to apply Theorem 5.10 to show that Algorithm 5.5 produces an
embedding of $H$ into $G$ with positive probability. We have produced
partitions $V_{i}^{(j)}$ and $W_{i}^{(j)}$ of $V(G)$ and $V(H)$ respectively
into $K=Tk\leq k\log_{2}h$ parts. We order these parts by the lexicographic
order on $(i,j)$. Note that in particular, each edge of $H$ has vertices
coming from $k$ different parts of this partition, and each vertex $v\in V(H)$
has at most $4d$ neighbors in later parts of this partition. Finally, for 5.4
we need to pick a $4d$-tuple $f_{v}$ for each $v\in W_{i}^{(j)}$ with
$(i,j)\neq(T,k)$. We produce this tuple by arbitrarily ordering the neighbors
$N^{+}(v)$ and then padding with elements of $W_{i^{\prime}}^{(j^{\prime})}$
where $j^{\prime}\neq j$ and $(i,j)$ precedes $(i^{\prime},j^{\prime})$ in
lexicographic order. (We can always do this padding because the
$W_{T}^{(j^{\prime})}$ are never empty).

In what follows we use the notation from 5.6. By our choice of $f_{x}$, we
have that $\mathcal{Q}_{x}$ is a set of the form that is controlled by Lemma
5.13(ii). Thus we know
$\mu_{16d}(x)=\mu_{\theta_{x},16d}(\mathcal{Q}_{x};V_{x})\leq\eta^{34d}$ and
so $\mu_{16d}\leq\eta^{34d}$.

Now we check the hypotheses of Theorem 5.10. By our choice of $\theta$ we have

$\theta_{j}=p_{j}\theta/4\geq\frac{1}{160d}2^{-j/(80d)}\eta^{3}n\geq
2^{-j+2}h\geq 2|W_{i}^{(j)}|.$

The second inequality holds for a sufficiently-small choice of $c_{p,d,k}>0$
and the assumption $h\leq c_{p,d,k}n$. Similarly, we have

$|V_{T}^{(k)}|\geq\frac{1}{4}p_{T}|A_{k}|\geq\frac{1}{640d}2^{-T/(80d)}\eta^{3}n\geq
2^{-T+2}h\geq 2|W_{T}^{(k)}|.$

Now

$\gamma\leq\max_{i,j}\frac{|V_{i}^{(j)}|}{\theta_{j}}\leq\max_{j}\frac{p_{j}n}{p_{j}\theta/4}\leq\frac{4n}{\theta}=\frac{4}{\eta^{3}}.$

Similarly,

$\frac{|W_{i}^{(j)}|}{\theta_{j}}\leq\frac{2^{-j+1}h}{p_{j}\theta/4}\leq\frac{2^{-j+1}h}{\frac{1}{160d}2^{-j/(80d)}\eta^{3}n}\leq\frac{327680h}{2^{j/2}\eta^{3}n}\leq\frac{1}{2^{j/2}}$

where we have again used the fact that $h\leq c_{p,d,k}n$ for a sufficiently-
small choice of $c_{p,d,k}>0$.

Therefore

$\displaystyle 2^{8d+2}\gamma^{8d}\mu_{16d}\sum_{i,j}|W_{i}^{(j)}|/\theta_{i}$
$\displaystyle\leq
2^{8d+2}\left(\frac{4}{\eta^{3}}\right)^{8d}\eta^{34d}\sum_{i,j}\frac{1}{2^{j/2}}$
$\displaystyle\leq k2^{24d+4}\eta^{10d}<1.$

Thus, Theorem 5.10 implies that Algorithm 5.5 produces an embedding of $H$
into $G$ with positive probability, as desired. ∎

######  Remark.

The above proof works for $c_{p,d,k}\leq(k^{-1}\eta)^{100Cd}$. For fixed $d,k$
this gives $c_{p,d,k}\leq p^{2^{O(k\log d)}}$.

##  6\. Concluding remarks

Define $\exp^{(k)}(x)$ (the exponential tower of height $k$ with $x$ at the
top) by $\exp^{(1)}(x)=2^{x}$ and $\exp^{(k)}(x)=2^{\exp^{(k-1)}(x)}$. For
$k\geq 4$, our proof of Theorem 1.5 gives
$r(H;q)\leq\exp^{(k-1)}(O_{k,q}(d))n$. This is known to be best-possible for
most regimes of the parameter choices. For example, for $k\geq 3$ and $q\geq
4$ it is known [16] that the complete $k$-uniform hypergraph has
$r(K_{d+1}^{(k)};q)\leq\exp^{(k-1)}(O_{k,q}(d))$. For $q=2,3$ it is not known
if there is a matching lower bound but this is generally conjectured to be the
case (see [10] for the best-known lower bound). Thus for $k\geq 4$ we should
not expect to be able to improve our bound on $r(H;q)$ in general. As further
evidence for this being the correct $d$-dependence note that it also matches
the best-known upper bound for bounded-degree hypergraphs [9].

However, for $k=3$ our argument only gives the bound
$r(H;q)\leq\exp^{(2)}(O_{q}(d\log d))n$. In fact, with a little more care our
argument gives $r(H;q)\leq\exp^{(2)}(O_{q}(d))n$ for 3-uniform $H$ as long as
$H^{(1)}$ has bounded chromatic number, but this does not improve the bound
for general 3-uniform $d$-skeletal degenerate hypergraphs. We conjecture that
the $\log d$ factor can be removed from the top of the tower.

######  Conjecture 6.1.

For a 3-uniform $n$-vertex hypergraph $H$ with $d_{1}(H)=d$,

$r(H;q)\leq\exp^{(2)}(O_{q}(d))n.$

A similar statement [3] is known when the skeletal degeneracy is replaced by
the square root of the number of edges. 6.1 is stronger than this result since
$d_{1}(H)\leq O(\sqrt{e(H^{(1)})})\leq O(\sqrt{e(H)})$.

###  6.1. Better bounds on the Turán number

Theorem 1.4 states that for every $k$-uniform $k$-partite hypergraph $H$,

$\Omega_{k}\left(n^{k-\frac{C_{k}}{d_{1}(H)}}\right)\leq\operatorname{ex}(n,H)\leq
O_{H}\left(n^{k-\frac{c_{k}}{d_{1}(H)^{k-1}}}\right).$ (6.1)

We would like to better understand the gap between the lower and upper bounds.
We will momentarily suggest a finer measure of degeneracy and conjecture that
it better captures the exponent of $\operatorname{ex}(n,H)$. Before doing so
we point out that both rates of growth in (6.1) are possible.

First note that Proposition 3.1 implies that the upper bound in (6.1) is tight
for the complete $k$-uniform $k$-partite hypergraph $K^{(k)}_{d,\ldots,d}$ (up
to the constant $c_{k}$). Furthermore, Proposition 3.6 shows show that the
lower bound in (6.1) is tight for the bipartite hedgehog $H_{d}^{(k)}$ (up to
the constant $C_{k}$).

Given these two examples, it is clear that $d_{1}(H)$ is not a fine enough
measure to capture the Turán exponent closely. Instead we consider
$d_{\mathsf{max}}(H)=\max_{1\leq i<k}d_{i}(H)$, the maximum of the $i$-th
skeletal degeneracy over all $i$ (see Definition 1.3 for the definition).

Theorem 3.2 implies that there is some constant $C_{k}>0$ such that for every
$k$-uniform $k$-partite hypergraph $H$ with at least two edges, we have

$\operatorname{ex}(n,H)\geq\Omega_{k}(n^{k-C_{k}/d_{\mathsf{max}}(H)}).$

We conjecture that this result is tight up to the constant $C_{k}$.

######  Conjecture 6.2.

There is a constant $c_{k}>0$ such that for every $k$-uniform $k$-partite
hypergraph $H$,

$\mathrm{ex}(n,H)\leq
O_{H}\left(n^{k-\frac{c_{k}}{d_{\mathsf{max}}(H)}}\right).$

###  6.2. Relations between various skeletal degeneracies

For a $k$-uniform $H$, note the inequalities
$d_{i}(H)\leq\binom{d_{1}(H)}{i}$, implying that

${d_{1}({H})}\leq d_{\mathsf{max}}(H)\leq\frac{{d_{1}({H})}^{k-1}}{(k-1)!}.$

(In fact one can deduce more relations between the $d_{i}(H)$ using the
Kruskal–Katona theorem.)

It follows from standard properties of the usual notion of degeneracy that for
any $k$-uniform $H$ and any $1\leq i<k$ there is an ordering of $V(H)$ such
that each vertex is the last vertex of at most $d_{i}(H)$ edges of $H^{(i)}$.
However, at first sight it seems possible that this produces $k-1$ different
orderings, one for each value of $i$. We show the nonobvious fact that (losing
a factor of $k^{2}$) one can take a single ordering simultaneously for all
$i$. This is a property of max-degeneracy that may be useful in attacking 6.2.

######  Proposition 6.3.

For every $k$-uniform hypergraph $H$ there is an ordering
$v_{1},v_{2},\ldots,v_{n}$ of $V(H)$ such that for each vertex $v_{i}$, the
number of sets $S\subseteq\\{v_{1},\ldots,v_{i-1}\\}$ such that there exists
an edge $e$ of $H$ with $e\cap\\{v_{1},\ldots,v_{i}\\}=S\cup\\{v_{i}\\}$ is at
most $k^{2}d_{\mathsf{max}}(H)$.

###### Proof.

For a $k$-uniform hypergraph $H=(V,E)$ write $H^{*}[U]=(U,\\{e\cap U:e\in
E\\})$ for the not-necessarily-uniform “induced subhypergraph” on $U$.

We will first show that for each nonempty $U\subseteq V$ there exists a vertex
$v\in U$ such that

$\sum_{r=1}^{k}\deg_{r}(v,H^{*}[U])\leq\sum_{i=0}^{k-1}(i+1)d_{i}(H).$ (6.2)

where $\deg_{r}(v,G)$ is the number of $r$-edges of $G$ which contain $v$.

Write $E_{r}(G)$ for the set of $r$-edges of $G$. Let $U\subseteq V$ be
nonempty. For the sake of contradiction, suppose that 6.2 fails for every
$v\in U$. Then we have

$\sum_{r=1}^{k}r|E_{r}(H^{*}[U])|=\sum_{r=1}^{k}\sum_{v\in
U}\deg_{r}(v,H^{*}[U])>|U|\sum_{i=0}^{k-1}(i+1)d_{i}(H).$

However, since the $(i+1)$-uniform part of $H^{*}[U]$ has $i$-th skeletal
degeneracy at most $d_{i}(H)$, we know that
$|E_{i+1}(H^{*}[U])|\leq|U|d_{i}(H)$. Summing over all $i$ contradicts the
above inequality.

Now to produce the ordering, suppose that we have already chosen vertices
$v_{i+1},\ldots,v_{n}$. Let $v_{i}$ be a vertex that satisfies 6.2 for
$U=V(H)\setminus\\{v_{i+1},\ldots,v_{n}\\}$. Iterating this procedure $n$
times produces an ordering with the required property since
$\sum_{i=0}^{k-1}(i+1)d_{i}(H)\leq k^{2}d_{\mathsf{max}}(H)$. ∎

###  6.3. More conjectures on max-skeletal degeneracy

As shown above, we have the bounds $d_{1}(H)\leq d_{\mathsf{max}}(H)\leq
d_{1}(H)^{k-1}$. The hardest cases for 6.2 should be for those $H$ where there
is a large gap between $d_{\mathsf{max}}(H)$ and $d_{1}(H)^{k-1}$. An
interesting example comes from Latin squares.

######  Conjecture 6.4.

Let $L$ be a $d\times d$ Latin square. Define $H_{L}$ to be the 3-uniform
3-partite hypergraph on vertex set $[d]\sqcup[d]\sqcup[d]$ where $(i,j,k)\in
E(H_{L})$ if and only if $L(i,j)=k$. Then
$\mathrm{ex}(n,H_{L})=n^{3-\Theta(1/d)}$.

Note that for every $d\times d$ Latin square we have
$d_{1}(H_{L}),d_{2}(H_{L})=\Theta(d)$, but Theorem 1.4 only shows that
$\mathrm{ex}(n,H_{L})\leq O(n^{3-c/d^{2}})$. It is worth pointing out that the
1-skeleton of $H_{L}$ is $K_{d,d,d}$ which is also the 1-skeleton of
$K^{(3)}_{d,d,d}$, the complete 3-partite 3-uniform hypergraph. Indeed, our
techniques only show that a hypergraph with $n^{3-c/d^{2}}$ edges contains
$H_{L}$ because it in fact contains $K^{(3)}_{d,d,d}$ and therefore every
3-partite $H$ with at most $d$ vertices in each side.

It would still be interesting to find some Latin square in any hypergraph of
this density (not necessarily some specific one), or even some large subset of
a Latin square. Along these lines we make the following weaker conjecture that
we are still unable to prove.

######  Conjecture 6.5.

There is a constant $c>0$ such that for all $d\geq 4$ the following holds. If
$G$ is a (not necessarily linear) 3-uniform hypergraph on $n$ vertices with at
least $n^{3-c/d}$ edges, then there is a linear subhypergraph of $G$ with $d$
vertices and at least $d^{2}/100$ edges.

Note that if the linearity constraint on the subhypergraph is omitted then the
conjecture is easily seen to be true. Indeed, it follows from a hypergraph
generalization of the standard Kővári–Sós–Turán argument (first written down
by Erdős [15]), that any $3$-uniform hypergraph with at least $n^{3-c/d}$
edges contains a copy of $K^{(3)}_{1,(d-1)/2,(d-1)/2}$. This is a (nonlinear)
hypergraph with $d$ vertices and $(d-1)^{2}/4$ edges.

## References

  * [1] AimPL: Graph Ramsey Theory, available at http://aimpl.org/graphramsey.
  * [2] Noga Alon, Michael Krivelevich, and Benny Sudakov, _Turán numbers of bipartite graphs and related Ramsey-type questions_ , Combin. Probab. Comput. 12 (2003), 477–494.
  * [3] Domagoj Bradač, Jacob Fox, and Benny Sudakov, _Ramsey numbers of hypergraphs of a given size_ , arXiv:2308.10833.
  * [4] Domagoj Bradač, Oliver Janzer, Benny Sudakov, and István Tomon, _The Turán number of the grid_ , Bulletin of the London Mathematical Society 55 (2023), 194–204.
  * [5] S. A. Burr and P. Erdős, _On the magnitude of generalized Ramsey numbers for graphs_ , Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vols. I, II, III, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975, pp. 215–240.
  * [6] Marcelo Campos, Simon Griffiths, Robert Morris, and Julian Sahasrabudhe, _An exponential improvement for diagonal Ramsey_ , arXiv:2303.09521.
  * [7] C. Chvatál, V. Rödl, E. Szemerédi, and W. T. Trotter, Jr., _The Ramsey number of a graph with bounded maximum degree_ , J. Combin. Theory Ser. B 34 (1983), 239–243.
  * [8] David Conlon, Jacob Fox, and Vojtěch Rödl, _Hedgehogs are not colour blind_ , J. Comb. 8 (2017), 475–485.
  * [9] David Conlon, Jacob Fox, and Benny Sudakov, _Ramsey numbers of sparse hypergraphs_ , Random Structures Algorithms 35 (2009), 1–14.
  * [10] David Conlon, Jacob Fox, and Benny Sudakov, _Hypergraph Ramsey numbers_ , J. Amer. Math. Soc. 23 (2010), 247–266.
  * [11] David Conlon, Jacob Fox, and Benny Sudakov, _On two problems in graph Ramsey theory_ , Combinatorica 32 (2012), 513–535.
  * [12] David Conlon, Jacob Fox, and Benny Sudakov, _Recent developments in graph Ramsey theory_ , Surveys in combinatorics 2015, London Math. Soc. Lecture Note Ser., vol. 424, Cambridge Univ. Press, Cambridge, 2015, pp. 49–118.
  * [13] David Conlon, Oliver Janzer, and Joonkyung Lee, _More on the extremal number of subdivisions_ , Combinatorica 41 (2021), 465–494.
  * [14] David Conlon and Joonkyung Lee, _On the extremal number of subdivisions_ , Int. Math. Res. Not. IMRN (2021), 9122–9145.
  * [15] P. Erdős, _On extremal problems of graphs and generalized graphs_ , Israel J. Math. 2 (1964), 183–190.
  * [16] P. Erdős, A. Hajnal, and R. Rado, _Partition relations for cardinal numbers_ , Acta Math. Acad. Sci. Hungar. 16 (1965), 93–196.
  * [17] P. Erdős and M. Simonovits, _A limit theorem in graph theory_ , Studia Sci. Math. Hungar. 1 (1966), 51–57.
  * [18] P. Erdös, _Some remarks on the theory of graphs_ , Bull. Amer. Math. Soc. 53 (1947), 292–294.
  * [19] P. Erdős, _Some recent results on extremal problems in graph theory. Results_ , Theory of Graphs (Internat. Sympos., Rome, 1966), Gordon and Breach, New York; Dunod, Paris, 1967, pp. 117–123 (English); pp. 124–130 (French).
  * [20] P. Erdös and A. H. Stone, _On the structure of linear graphs_ , Bull. Amer. Math. Soc. 52 (1946), 1087–1091.
  * [21] P. Erdös and G. Szekeres, _A combinatorial problem in geometry_ , Compositio Math. 2 (1935), 463–470.
  * [22] Jacob Fox and Benny Sudakov, _Two remarks on the Burr-Erdős conjecture_ , European J. Combin. 30 (2009), 1630–1645.
  * [23] R. L. Graham, V. Rödl, and A. Ruciński, _On graphs with linear Ramsey numbers_ , J. Graph Theory 35 (2000), 176–192.
  * [24] R. L. Graham, V. Rödl, and A. Ruciński, _On bipartite graphs with linear Ramsey numbers_ , Combinatorica 21 (2001), 199–209, Paul Erdős and his mathematics (Budapest, 1999).
  * [25] Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer, _Ramsey theory_ , second ed., John Wiley & Sons, Inc., New York, 1990.
  * [26] Oliver Janzer, _Improved bounds for the extremal number of subdivisions_ , Electron. J. Combin. 26 (2019), Paper No. 3.3, 6.
  * [27] Oliver Janzer, _The extremal number of the subdivisions of the complete bipartite graph_ , SIAM J. Discrete Math. 34 (2020), 241–250.
  * [28] Oliver Janzer, _The extremal number of longer subdivisions_ , Bull. Lond. Math. Soc. 53 (2021), 108–118.
  * [29] Oliver Janzer and Benny Sudakov, _On the Turán number of the hypercube_ , arXiv:2211.02015.
  * [30] Peter Keevash, _Hypergraph Turán problems_ , Surveys in combinatorics 2011, London Math. Soc. Lecture Note Ser., vol. 392, Cambridge Univ. Press, Cambridge, 2011, pp. 83–139.
  * [31] A. V. Kostochka and V. Rödl, _On graphs with small Ramsey numbers. II_ , Combinatorica 24 (2004), 389–401.
  * [32] A. V. Kostochka and V. Rödl, _On Ramsey numbers of uniform hypergraphs with given maximum degree_ , J. Combin. Theory Ser. A 113 (2006), 1555–1564.
  * [33] Alexandr Kostochka and Benny Sudakov, _On Ramsey numbers of sparse graphs_ , Combin. Probab. Comput. 12 (2003), 627–641.
  * [34] Choongbum Lee, _Ramsey numbers of degenerate graphs_ , Ann. of Math. (2) 185 (2017), 791–829.
  * [35] W. Mantel, _Problem 28_ , Wiskundige Opgaven 10 (1907), 60–61.
  * [36] Bojan Mohar and Carsten Thomassen, _Graphs on surfaces_ , Johns Hopkins University Press, 2001.
  * [37] Dhruv Mubayi and Andrew Suk, _A survey of hypergraph Ramsey problems_ , Discrete mathematics and applications, Springer Optim. Appl., vol. 165, Springer, Cham, 2020, pp. 405–428.
  * [38] F. P. Ramsey, _On a problem of formal logic_ , Proc. London Math. Soc. (2) 30 (1929), 264–286.
  * [39] Joel Spencer, _Ramsey’s theorem—a new lower bound_ , J. Combinatorial Theory Ser. A 18 (1975), 108–115.
  * [40] Benny Sudakov and István Tomon, _Turán number of bipartite graphs with no $K_{t,t}$_, Proc. Amer. Math. Soc. 148 (2020), 2811–2818.
  * [41] Paul Turán, _Eine Extremalaufgabe aus der Graphentheorie_ , Mat. Fiz. Lapok 48 (1941), 436–452.
  * [42] Roman Vershynin, _High-dimensional probability: An introduction with applications in data science_ , vol. 47, Cambridge University Press, 2018.