2. Preliminaries

When dealing with singleton sets, we may omit the parentheses, for instance, given a set $I$ and $r\in I$ , we may simply write $I\smallsetminus r$ etc.

When proving $\pi _{\boldsymbol{\therefore }}(K_4^{(3)-})=\frac {1}{4}$ , Reiher, Rödl, and Schacht [Reference Reiher, Rödl and Schacht19] used the hypergraph regularity lemma. After ‘regularising’ a hypergraph, the problem reduces to an extremal problem in the reduced hypergraph. We will follow this approach and use the terminology introduced in [Reference Reiher, Rödl and Schacht19] and laid out systematically by Reiher in his survey [Reference Reiher18].

For a hypergraph $H$ , we denote the number of its edges by $e(H)=\vert E(H)\vert$ and the number of its vertices by $v(H)=\vert V(H)\vert$ . Given a set $I$ , we denote by $I^{(\ell )}$ the set of all $\ell$ -element subsets of  $I$ . When considering such subsets, we often omit the parentheses and write for instance $ijk$ for an element of $I^{(3)}$ , instead of $\{i,j,k\}$ . For a hypergraph $H$ , we define the shadow of $H$ as $\partial H=\{e\smallsetminus x\,:\,x\in e\in E(H)\}$ .

For brevity, we often simply write ‘let $\mathcal{A}=(I,\mathcal{P}^{ij},\mathcal{A}^{ijk})$ be a reduced hypergraph’ instead of ‘let $\mathcal{A}$ be a reduced hypergraph with index set $I$ , vertex classes $\mathcal{P}^{ij}$ and constituents $\mathcal{A}^{ijk}$ ’.

Next, let us take a look at how the density condition in our host hypergraphs translates to a density condition in the respective reduced hypergraphs.

The following definition of a reduced map describes the setting in which a hypergraph $F$ can be embedded into a host hypergraph $H$ (by using the hypergraph regularity method) in terms of the reduced hypergraph of $H$ .

Now the following theorem due to Reiher, Rödl, and Schacht (and appearing in this formulation in Reiher’s survey [Reference Reiher18]) reduces the problem of determining $\pi _{\boldsymbol{\therefore }}(F)$ to a problem about reduced hypergraphs.

Theorem 2.4. For a $3$ -graph $F$ , we have

\begin{align*} \pi _{\boldsymbol{\therefore }}(F)=\sup \{d\in [0,1]\,:\,&\ \mathrm{For\ every}\ M\in \mathbb{N}\ \mathrm{, there\ is\ a}\ (d,\boldsymbol{\therefore})\mathrm{-dense,} \\ &F\mathrm{-free\ reduced\ hypergraph}\ \mathcal{A}\ \mathrm{with\ index\ set}\ [M]\}\,. \end{align*}

3. Proof of Theorem1.1

Proof of Theorem 1.1. Since $K_4^{(3)-}\subseteq F_{\star }$ , we have $1/4=\pi _{\boldsymbol{\therefore }}(K_4^{(3)-})\leqslant \pi _{\boldsymbol{\therefore }}(F_{\star })$ .

Due to Theorem2.4, it is thus enough to show that for every $\varepsilon \gt 0$ , there is some large $M\in \mathbb{N}$ such that every $(\frac {1}{4}+\varepsilon , \boldsymbol{\therefore })$ -dense reduced hypergraph with index set $[M]$ contains a reduced image of $F_{\star }$ . Let thus $\varepsilon \gt 0$ be given, without loss of generality $\varepsilon \ll 1$ , and choose $M,M_*,m\in \mathbb{N}$ , and $\delta \gt 0$ such that

(3.1) \begin{align} M^{-1}\ll M_*^{-1}\ll m^{-1}\ll \delta \ll \varepsilon \ll 1\,. \end{align}

Then let $\mathcal{A}$ be a $(\frac {1}{4}+\varepsilon , \boldsymbol{\therefore })$ -dense reduced hypergraph with index set $[M]$ , vertex classes $\mathcal{P}^{ij}$ and constituents $\mathcal{A}^{ijk}$ . We will show that $\mathcal{A}$ contains a reduced image of $F_{\star }$ .

We begin with a ‘cleaning process’ (until Lemma 3.2) similar to the one in [Reference Reiher, Rödl and Schacht19]. However, we will allow for a bit more ‘robustness’. Consider any $ijk\in [M]^{(3)}$ with $i\lt j\lt k$ . We define the bipartite graph $Q^i_{jk}$ on the vertex set $\mathcal{P}^{ij}\mathbin {\cdot \kern -4.8pt\cup }\mathcal{P}^{ik}$ by placing an edge between $w \in \mathcal{P}^{ij}$ and $v \in \mathcal{P}^{ik}$ if there are at least $\varepsilon ^2 |\mathcal{P}^{jk}|$ vertices $u$ in $\mathcal{P}^{jk}$ such that $wvu \in E(\mathcal{A}^{ijk})$ . Similarly, we define the bipartite graph $Q^k_{ij}$ on the vertex set $\mathcal{P}^{ik}\mathbin {\cdot \kern -4.8pt\cup }\mathcal{P}^{jk}$ by placing an edge between $v \in \mathcal{P}^{ik}$ and $w \in \mathcal{P}^{jk}$ if there are at least $\varepsilon ^2 |\mathcal{P}^{ij}|$ vertices $u$ in $\mathcal{P}^{ij}$ such that $uvw \in E(\mathcal{A}^{ijk})$ . We write $N_{Q^i_{jk}}(x)$ and $d_{Q^i_{jk}}(x)$ for the neighbourhood and the degree of a vertex $x$ in the graph $Q^i_{jk}$ , respectively, and similarly we define $N_{Q^k_{ij}}(x)$ and $d_{Q^k_{ij}}(x)$ .

Lemma 3.1. For any $ijk\in [M]^{(3)}$ with $i\lt j\lt k$ , we have

\begin{equation*} \sum _{v \in \mathcal{P}^{ik}} d_{Q^i_{jk}}(v) d_{Q^k_{ij}}(v) \geqslant \big (\frac 14+\frac {\varepsilon }2\big ) |\mathcal{P}^{ij}||\mathcal{P}^{jk}||\mathcal{P}^{ik}| \,.\end{equation*}

Proof. We use a double-counting argument. For $v \in \mathcal{P}^{ik}$ , set $T(v)=\{w_1vw_2\in E(\mathcal{A}^{ijk})\}$ and $S(v)=\{w_1vw_2\in E(\mathcal{A}^{ijk})\,:\,vw_1\in E(Q^i_{jk}),vw_2\in E(Q^k_{ij})\}$ ,

\begin{align*} &S_1(v)=\{w_1vw_2\in E(\mathcal{A}^{ijk})\,:\,w_1\in \mathcal{P}^{ij},vw_1\notin E(Q^i_{jk})\}\text{, and}\\ &S_2(v)=\{w_1vw_2\in E(\mathcal{A}^{ijk})\,:\,w_2\in \mathcal{P}^{jk},vw_2\notin E(Q^k_{ij})\}\,. \end{align*}

Note that by double-counting, we have the following.

\begin{align*} \big (\frac {1}{4}+\varepsilon \big )\vert \mathcal{P}^{ij}\vert \vert \mathcal{P}^{jk}\vert \vert \mathcal{P}^{ik}\vert &\leqslant \sum _{v\in \mathcal{P}^{ik}}\vert T(v)\vert \leqslant \sum _{v\in \mathcal{P}^{ik}}\vert S(v)\vert +\vert S_1(v)\vert +\vert S_2(v)\vert \\ &\leqslant \sum _{v\in \mathcal{P}^{ik}} d_{Q^i_{jk}}(v) d_{Q^k_{ij}}(v)+2\varepsilon ^2\vert \mathcal{P}^{ij}\vert \vert \mathcal{P}^{jk}\vert \vert \mathcal{P}^{ik}\vert \,. \end{align*}

Since $\varepsilon \ll 1$ , the assertion follows.

Given $ijk\in [M]^{(3)}$ with $i\lt j\lt k$ , by Lemma 3.1 and the Cauchy-Schwartz inequality, we have either

(3.2) \begin{align} \sum _{v \in \mathcal{P}^{ik}} d_{Q^i_{jk}}(v)^2 \geqslant \big (\frac 14+\frac \varepsilon 2\big ) |\mathcal{P}^{ij}|^2 |\mathcal{P}^{ik}|\,, \end{align}

in which case we colour $ijk$ blue, and if this is not true, we must have

\begin{equation*} \sum _{v \in \mathcal{P}^{ik}} d_{Q^k_{ij}}(v)^2 \geqslant \big (\frac 14+\frac \varepsilon 2\big ) |\mathcal{P}^{jk}|^2 |\mathcal{P}^{ik}|\,,\end{equation*}

in which case we colour $ijk$ red.

By (3.1) and by Ramsey’s theorem, there is a subset of $M_*$ indices, without loss of generality $[M_*]$ , such that all $3$ -subsets of this set are coloured with the same colour, say blue.

There is one more step in the ‘cleaning process’, for which we apply Ramsey’s theorem to a different colouring of the $3$ -subsets of $[M_*]$ . For $ijk\in [M_*]^{(3)}$ with $i\lt j\lt k$ and $r \in \mathbb{N}$ , let

\begin{equation*} S_{jk}^i(r) = \{x \in \mathcal{P}^{ik}\,:\, d_{Q^i_{jk}}(x) \geqslant \big (\frac 12+r \delta \big ) |\mathcal{P}^{ij}|\}\,.\end{equation*}

Since $ijk$ was coloured in blue, (3.2) entails

\begin{align*} \big (\frac 14+\frac {\varepsilon }2\big ) |\mathcal{P}^{ij}|^2 |\mathcal{P}^{ik}|\leqslant \sum _{v \in \mathcal{P}^{ik}} d_{Q^i_{jk}}(v)^2\leqslant \big (\frac 12+\delta \big )^2 |\mathcal{P}^{ij}|^2|\mathcal{P}^{ik}\smallsetminus S_{jk}^i(1)|+ |\mathcal{P}^{ij}|^2|S_{jk}^i(1)|\,. \end{align*}

Because of (3.1), we infer that $\vert S_{jk}^i(1)\vert \geqslant \delta \vert \mathcal{P}^{ik}\vert$ .

Clearly the $S_{jk}^i(r)$ ’s are decreasing and $S_{jk}^i(r) = \varnothing$ for $r \gt \frac {1}{2\delta }$ , so we may colour $ijk$ by the maximum $r\in [\frac {1}{2\delta }]$ (w.l.o.g., we assume that $\frac {1}{2\delta }$ is an integer) for which $|S_{jk}^i(r)| \geqslant \delta |\mathcal{P}^{ik}|$ .

Again by Ramsey’s theorem, as $m \ll M_{*}$ and after potentially reordering the indices, we can suppose that $[m]$ is a blue clique in the first colouring and an $r_{*}$ -coloured clique in the second colouring, for some $r_*\in [\frac {1}{2\delta }]$ . The following is the conclusion of our cleaning.

\begin{align*} (\star ) \text{ Every }ijk\in [m]^{(3)}\text{ with }i\lt j\lt k\text{ satisfies (3.2) and }\vert S_{jk}^i(r_*)\vert \geqslant \delta \vert \mathcal{P}^{ik}\vert \gt \vert S_{jk}^i(r_*+1)\vert \,. \end{align*}

Now, for all $i \in [m]$ , define the graph $Q^i = \bigcup _{1\leqslant i\lt j \lt k\leqslant m} Q^i_{jk}$ . We need the following auxiliary result, which is a robust version of a result in [Reference Reiher, Rödl and Schacht19].

Proof. Let $A_{j_1}$ be the neighbours of $x$ in $\mathcal{P}^{ij_1}$ , and let $A_{j_2}$ be the neighbours of $x$ in $\mathcal{P}^{ij_2}$ . By definition of $x$ (and $S^i_{jk}$ ), we have that $|A_{j_1}| \geqslant (\frac 12+r_* \delta ) |\mathcal{P}^{ij_1}|, |A_{j_2}| \geqslant (\frac 12+r_* \delta ) |\mathcal{P}^{ij_2}|$ .

Also, denote $B_{j_1}=\mathcal{P}^{ij_1}\smallsetminus A_{j_1}$ and $B_{j_2}=\mathcal{P}^{ij_2}\smallsetminus A_{j_2}$ . Now let $C = B_{j_2}\cap S_{j_1j_2}^i(r_*+1)$ . By $(\star )$ , we know $|C| \lt \delta |\mathcal{P}^{ij_2}|$ , and by definition of $S_{j_1j_2}^i(r_*+1)$ , we have $d_{Q^i_{j_1 j_2}}(y) \lt (\frac 12+(r_*+1)\delta )|\mathcal{P}^{ij_1}|$ for all $y \in B_{j_2}\smallsetminus C$ .

Note that any edge between $A_{j_1}$ and $A_{j_2}$ gives rise to a triangle of the kind the statement asks for, so suppose for the sake of contradiction that there are less than $\delta |\mathcal{P}^{ij_1}||\mathcal{P}^{ij_2}|$ edges between $A_{j_1}$ and $A_{j_2}$ .

Then, when setting $d'_{Q^i_{j_1 j_2}}(y)=\vert N_{Q^i_{j_1 j_2}}(y)\cap A_{j_1}\vert$ for all $y \in A_{j_2}$ , we have $\sum _{y \in A_{j_2}} d'_{Q^i_{j_1 j_2}}(y) \lt \delta |\mathcal{P}^{ij_1}||\mathcal{P}^{ij_2}|$ . Since each $d'_{Q^i_{j_1 j_2}}(y) \leqslant |\mathcal{P}^{ij_1}|$ , we also know $\sum _{y\in A_{j_2}} \big (d'_{Q^i_{j_1 j_2}}(y)\big )^2 \leqslant \delta |\mathcal{P}^{ij_1}|^2|\mathcal{P}^{ij_2}|$ . By our conditions on $|A_{j_1}|$ , we have $d_{Q^i_{j_1 j_2}}(y) - d'_{Q^i_{j_1 j_2}}(y) \leqslant |B_{j_1}| \leqslant (\frac 12-r_* \delta )|\mathcal{P}^{ij_1}|$ . Hence

\begin{align*} \sum _{y \in A_{j_2}} d_{Q^i_{j_1 j_2}}(y)^2 &= \sum _{y \in A_{j_2}} \big (d_{Q^i_{j_1 j_2}}(y)-d'_{Q^i_{j_1 j_2}}(y)+d'_{Q^i_{j_1 j_2}}(y)\big )^2 \\ &\leqslant |A_{j_2}| (\frac 12-r_* \delta )^2 |\mathcal{P}^{ij_1}|^2 + \delta |\mathcal{P}^{ij_1}|^2|\mathcal{P}^{ij_2}| + 2 (\frac 12-r_*\delta ) \delta |\mathcal{P}^{ij_1}|^2 |\mathcal{P}^{ij_2}| \\ &\lt |A_{j_2}| (\frac 12-r_* \delta )^2 |\mathcal{P}^{ij_1}|^2 + 2\delta |\mathcal{P}^{ij_1}|^2|\mathcal{P}^{ij_2}|\,. \end{align*}

Now recalling $(\star )$ and splitting the sum yields

\begin{align*} &\big (\frac 14+\frac {\varepsilon }2\big ) |\mathcal{P}^{ij_1}|^2 |\mathcal{P}^{ij_2}|\leqslant \sum _{x \in \mathcal{P}^{ij_2}} d_{Q^i_{j_1 j_2}}(x)^2\\ \leqslant &\sum _{x \in B_{j_2}\smallsetminus C} d_{Q^i_{j_1 j_2}}(x)^2+\sum _{x \in A_{j_2}} d_{Q^i_{j_1 j_2}}(x)^2+\sum _{x \in C} d_{Q^i_{j_1 j_2}}(x)^2\\ \leqslant &|B_{j_2}| \big (\frac 12+(r_*+1)\delta \big )^2 |\mathcal{P}^{ij_1}|^2 + |A_{j_2}| \big (\frac 12-r_* \delta \big )^2 |\mathcal{P}^{ij_1}|^2 + 3\delta |\mathcal{P}^{ij_1}|^2|\mathcal{P}^{ij_2}|\,. \end{align*}

Since $\vert A_{j_2}\vert +\vert B_{j_2}\vert =\vert \mathcal{P}^{ij_2}\vert$ and $\vert B_{j_2}\vert \leqslant (\frac {1}{2}-r_{\star }\delta )\vert \mathcal{P}^{ij_2}\vert$ , the right-hand side is maximised when $\vert B_{j_2}\vert =(\frac {1}{2}-r_{\star }\delta )\vert \mathcal{P}^{ij_2}\vert$ and $\vert A_{j_2}\vert =(\frac {1}{2}+r_{\star }\delta )\vert \mathcal{P}^{ij_2}\vert$ . Cancelling $\vert \mathcal{P}^{ij_1}\vert ^2 \vert \mathcal{P}^{ij_2}\vert$ entails

\begin{align*} \frac 14+\frac {\varepsilon }2 &\leqslant \big (\frac 12-r_* \delta \big ) \big (\frac 12+(r_*+1)\delta \big )^2 + \big (\frac 12+r_* \delta \big ) \big (\frac 12-r_* \delta \big )^2 + 3\delta \\ &\leqslant \big (\frac 12-r_* \delta \big ) \big (\frac 12+r_* \delta \big )^2 + \big (\frac 12+r_* \delta \big ) \big (\frac 12-r_* \delta \big )^2 + 6\delta \\ &\lt \frac 14 + 6 \delta \,. \end{align*}

Since $\delta \ll \varepsilon$ , this yields a contradiction.

In our proof, we will iteratively prepare a number of ‘rows’, each of which is a subgraph of a $Q^r$ , by finding many triangles that are ‘compatible’ with each other. By definition of $Q^r$ , for each edge in $e\in E(Q^r)$ , there exists a small subset $X$ in some vertex class of $Q^{r'}$ for some $r'\gt r$ , such that every $x\in X$ together with $e$ forms an edge in $\mathcal{A}$ . This subset $X$ can be thought of as the ‘projection’ of the row $r$ onto the row $r'$ . After preparing many rows, we will show that some of these projections have to intersect. From this, the reduced image of $F_{\star }$ will arise (see Fig. 4).

The following lemma encapsulates the preparation of one row which is ‘paid for’ by shrinking the index set.

Now, we apply Lemma 3.3 iteratively, in each step preparing a row and shrinking the index set. First, let $I_0=[m]$ , and $r_1=\min I_0$ . Lemma 3.3 provides some $I_1\subseteq I_0\smallsetminus r_1$ with $m\in I_1$ and $\vert I_1\vert \geqslant \delta ^2 \vert I_0\vert$ , $x_1\in \mathcal{P}^{r_1m}$ , $y_1\in \mathcal{P}^{r_1r_2}$ , where $r_2=\min I_1$ , and $z_{1j}\in \mathcal{P}^{r_1j}$ for all $j\in I_1\smallsetminus \{r_2,m\}$ such that $x_1z_{1j}y_1$ forms a triangle in $Q^{r_1}$ .

Next, we apply Lemma 3.3 again, but this time to $I_1$ . Generally, assume that for some $i\in [\frac {2}{\varepsilon ^2}]$ , we have defined sets $I_0,\dots ,I_i\subseteq [m]$ , indices $r_1,\dots r_{i+1}\in [m]$ , and for all $j\in [i]$ and $k\in I_j\smallsetminus \{r_{j+1},m\}$ , vertices $x_j\in \mathcal{P}^{r_{j}m}$ , $y_j\in \mathcal{P}^{r_{j}r_{j+1}}$ , and $z_{jk}\in \mathcal{P}^{r_{j}k}$ such that the following holds. For all $j\in [i]$ , we have $I_{j}\subseteq I_{j-1}\smallsetminus r_{j}$ , $m\in I_{j}$ , $r_{j+1}=\min I_j$ , and $\vert I_{j}\vert \geqslant \delta ^2\vert I_{j-1}\vert$ , and further for all $k\in I_j\smallsetminus \{r_{j+1},m\}$ , $x_jz_{jk}y_j$ forms a triangle in $Q^{r_{j}}$ . Then applying Lemma 3.3 to $I_i$ yields $I_{i+1}\subseteq I_{i}\smallsetminus r_{i+1}$ with $m\in I_{i+1}$ and $\vert I_{i+1}\vert \geqslant \delta ^2\vert I_i\vert$ , $x_{i+1}\in \mathcal{P}^{r_{i+1}m}$ , $y_{i+1}\in \mathcal{P}^{r_{i+1}r_{i+2}}$ , where $r_{i+2}=\min I_{i+1}$ , and $z_{{i+1}j}\in \mathcal{P}^{r_{i+1}j}$ for all $j\in I_{i+1}\smallsetminus \{r_{i+2},m\}$ such that $x_{i+1}z_{{i+1}j}y_{i+1}$ forms a triangle in $Q^{r_{i+1}}$ .

Note that we can perform this process $\frac {2}{\varepsilon ^2}+1$ times since in the last step (and thus in all steps prior) we have that $\vert I_{\frac {2}{\varepsilon ^2}}\vert \geqslant (\delta ^2)^{\frac {2}{\varepsilon ^2}} m\gt \frac {2}{\delta ^2}$ (using the hierarchy (3.1)) and thus we can still construct the set $I_{\frac {2}{\varepsilon ^2}+1}$ with $\vert I_{\frac {2}{\varepsilon ^2}+1}\vert \geqslant 3$ .

After this iteration procedure, let the maximum element of $I_{\frac {2}{\varepsilon ^2}+1}\smallsetminus m$ be $m'$ . For all $i \in [\frac {2}{\varepsilon ^2}+1]$ , since $I_{\frac {2}{\varepsilon ^2}+1} \subseteq I_i$ , there is some triangle $x_i z_{im'} y_i$ in $Q^{r_{i}}$ and we set $e_i=x_iz_{im'}$ . Note that $e_i$ is between $\mathcal{P}^{r_i m}$ and $\mathcal{P}^{r_i m'}$ . Since $e_i\in E(Q^{r_i})$ , we know that there is a set $H(e_i)\subseteq \mathcal{P}^{m'm}$ with $\vert H(e_i)\vert \geqslant \varepsilon ^2\vert \mathcal{P}^{m'm}\vert$ such that $x_iz_{im'}v\in E(\mathcal{A}^{r_im'm})$ for every $v\in H(e_i)$ . Thus, there are at least three indices $i,j,k\in [\frac {2}{\varepsilon ^2}+1]$ such that $H(e_i)\cap H(e_j)\cap H(e_k)\neq \varnothing$ . Without loss of generality, assume $i\lt j\lt k$ .

Let $v\in H(e_i)\cap H(e_j)\cap H(e_k)$ and note that $r_k\gt r_j \geqslant r_{i+1}$ and that since $\vert I_{\frac {2}{\varepsilon ^2}+1} \vert \geqslant 3$ and $m = \max I_{\frac {2}{\varepsilon ^2}+1}$ , $m' = \max I_{\frac {2}{\varepsilon ^2}+1} \smallsetminus m$ , we know $r_k \lt m'$ . Thus, there are $z_{im'}\in \mathcal{P}^{r_im'}$ and $z_{i r_k}\in \mathcal{P}^{r_i r_k}$ such that $x_iz_{im'}y_i$ is a triangle in $Q^{r_i}$ and $z_{i r_k}y_i\in E(Q^{r_i})$ (we do not need the other edges in the respective triangle). Now these edges imply the existence of vertices $u_1 \in \mathcal{P}^{r_{i+1} m}, u_2 \in \mathcal{P}^{r_{i+1} m'}, u_3 \in \mathcal{P}^{r_{i+1} r_k}$ such that $x_{i}y_{i}u_1 \in E(\mathcal{A}^{r_ir_{i+1}m})$ , $z_{im'}y_{i}u_2\in E(\mathcal{A}^{r_ir_{i+1}m'})$ , and $z_{i r_k}y_{i}u_3 \in E(\mathcal{A}^{r_ir_{i+1}r_k})$ . Together with the edges $x_iz_{im'}v\in E(\mathcal{A}^{r_im'm})$ and $x_kz_{km'}v\in E(\mathcal{A}^{r_km'm})$ , this yields a reduced embedding of $F_{\star }$ . This iteration process and the resulting embedding is illustrated in Fig. 4.

Indeed, as shown in Fig. 3, the edges mentioned show that when setting $\lambda (1)=r_i$ , $\lambda (2)=r_{i+1}$ , $\lambda (3)=m$ , $\lambda (4)=m'$ , and $\lambda (5)=r_k$ and $\varphi (12)=y_i$ , $\varphi (13)=x_i$ , $\varphi (14)=z_{im'}$ , $\varphi (15)=z_{ir_k}$ , $\varphi (23)=u_1$ , $\varphi (24)=u_2$ , $\varphi (25)=u_3$ , $\varphi (34)=v$ , $\varphi (35)=x_k$ , and $\varphi (45)=z_{km'}$ , then $(\lambda ,\varphi )$ is a reduced embedding of $F_{\star }$ into $\mathcal{A}$ .

Figure 4.

$F_{\star }$ embedded across several prepared rows in the reduced hypergraph $\mathcal{A}$ . Blue lines represent edges in $Q^r$ .

4. Proof of Theorem1.2

Proof. Let $\varepsilon \gt 0$ be given, without loss of generality, $\varepsilon \ll 1$ , and choose $M,M_*,m\in \mathbb{N}$ and $\delta \gt 0$ such that

(4.1) \begin{align} M^{-1}\ll M_*^{-1}\ll m^{-1}\ll \delta \ll \varepsilon \ll 1\,. \end{align}

Then let $\mathcal{A}$ be a $(\frac {1}{4}+\varepsilon )$ -dense reduced hypergraph with index set $[M]$ , vertex classes $\mathcal{P}^{ij}$ and constituents $\mathcal{A}^{ijk}$ . We need to show that there are four indices $i_1,i_2,i_3,i_4\in [M]$ and vertices $x_{\alpha \beta }\in \mathcal{P}^{i_{\alpha }i_{\beta }}$ for $\alpha \beta \in [4]^{(2)}$ as well as $x_{23}'\in \mathcal{P}^{i_2i_3}$ and $x_{24}'\in \mathcal{P}^{i_2i_4}$ such that $x_{12}x_{13}x_{23}\in E(\mathcal{A}^{i_1i_2i_3})$ , $x_{12}x_{14}x_{24}\in E(\mathcal{A}^{i_1i_2i_4})$ , $x_{13}x_{14}x_{34}\in E(\mathcal{A}^{i_1i_3i_4})$ , and $x_{23}'x_{24}'x_{34}\in E(\mathcal{A}^{i_2i_3i_4})$ .

We proceed as in the last section until Lemma 3.3. Instead of this lemma, we need the following variant.

Proof. We will choose the $z_{k}$ iteratively and with each choice the set of considered indices will shrink. As $|S_{jm}^r(r_{*})| \geqslant \delta |\mathcal{P}^{rm}|$ for all $j \in I\smallsetminus \{m, r\}$ , it follows that there is some set $I' \subseteq I\smallsetminus \{r, m\}$ such that $|I'| \geqslant \delta (|I|-2)$ and some $x \in \bigcap _{j \in I'} S_{jm}^r(r_*)$ . For any $k \in I'$ , let $A_k$ be the set of neighbours of $x$ in $\mathcal{P}^{rk}$ . Since for all $jk\in I'^{(2)}$ with $j\lt k$ , we have $x \in S_{km}^r(r_*) \cap S_{jm}^r(r_*)$ , by Lemma 3.2, there are at least $\delta |\mathcal{P}^{rk}||\mathcal{P}^{rj}|$ edges in $Q^r$ between $A_k$ and $A_j$ . Let now $k_1=\max I'$ and let $D_j$ be the set of vertices in $\mathcal{P}^{rk_1}$ which lie in a triangle between $A_{k_1}$ and $A_j$ . Note that $\vert D_j\vert \geqslant \delta \vert \mathcal{P}^{rk_1}\vert$ . Therefore, there is some set $I_1'\subseteq I'\smallsetminus k_1$ with $\vert I_1'\vert \geqslant \delta (\vert I'\vert -1)$ and some $z_{k_1}\in \bigcap _{j\in I_1'}D_j$ . Set $I_1=I_1'\cup \{k_1,m\}$ and note that $\vert I_1\vert \geqslant \delta ^2\vert I\vert$ and that for all $j\in I_1$ with $j\lt k_1$ , there is some $y\in \mathcal{P}^{rj}$ such that $xz_{k_1}y$ forms a triangle in $Q^r$ .

Now suppose that we have found indices $m\gt k_1\gt \dots \gt k_i$ in $I$ for some $i\lt m_2$ , a set $I_i\subseteq I\smallsetminus r$ with $\{m,k_1,\dots ,k_i\}\subseteq I_i$ and $\vert I_i\vert \geqslant \delta ^{i+1}\vert I\vert$ , and vertices $z_k\in \mathcal{P}^{rk}$ for all $k\in \{k_1,\dots ,k_i\}$ such that for all $k\in \{k_1,\dots ,k_i\}$ and $j\in I_i$ with $j\lt k$ , there is some $y\in \mathcal{P}^{rj}$ such that $xz_ky$ forms a triangle in $Q^r$ . Then let $I_{i+1}'=I_i\smallsetminus \{m,k_1,\dots ,k_i\}$ and note that $\vert I_{i+1}'\vert \geqslant \delta ^{i+1} m_1-(i+1)\geqslant 1$ (this is where we use the lower bound on $m_1$ ; we need $|I'_{i+1}|\geqslant 1$ for the following maximum to be well defined). Let $k_{i+1}=\max I_{i+1}'$ and for $j\in I_{i+1}'\smallsetminus k_{i+1}$ , let $D_j'$ be the set of vertices in $\mathcal{P}^{rk_{i+1}}$ which lie in a triangle between $A_{k+1}$ and $A_j$ . As before, we have that $\vert D_j'\vert \geqslant \delta \vert \mathcal{P}^{rk_{i+1}}\vert$ and thus, there is some set $I_{i+1}''\subseteq I_{i+1}'\smallsetminus k_{i+1}$ and some $z_{k_{i+1}}\in \bigcap _{j\in I_{i+1}''}D_j'$ (if $I_{i+1}''=\varnothing$ , pick $z_{k_{i+1}}\in \mathcal{P}^{rk_{i+1}}$ arbitrarily). Set $I_{i+1}=I_{i+1}''\cup \{m,k_1,\dots k_{i+1}\}$ and note that

\begin{equation*}\vert I_{i+1}\vert \geqslant \delta (\vert I_{i}\vert -(i+2))+i+2\geqslant \delta \vert I_i\vert \geqslant \delta ^{i+2}\vert I\vert \,,\end{equation*}

and that for all $k\in \{k_1,\dots k_{i+1}\}$ and $j\in I_{i+1}$ with $j\lt k$ , there is some $y\in \mathcal{P}^{rj}$ such that $xz_ky$ forms a triangle in $Q^r$ . We cease this process once $I_{m_2}$ is chosen (corresponding to $i = m_2 - 1$ in the above). Note that $\{m,k_1,\dots ,k_{m_2}\}\subseteq I_{m_2}$ .

Eventually, we set $J=\{m,k_1,\dots ,k_{m_2}\}$ and note that $J$ , $x$ , and $z_k$ for $k\in J$ have the asserted properties.

Similarly as in the last section, we will now conclude the proof by an iteration process, this time repeatedly applying Lemma 4.1. Let $m_1,\dots m_{\frac {1}{\varepsilon ^2}+1}\in \mathbb{N}$ with

(4.2) \begin{align} m^{-1}=m_1^{-1}\ll m_2^{-1}\ll \dots \ll m_{\frac {1}{\varepsilon ^2}+1}\ll \delta \,, \end{align}

and note that this is compatible with the hierarchy (4.1). Set $I_0=[m]$ , $r_1=1$ (note that we will use $I_i$ here in a different sense than in the proof of Lemma 4.1 but essentially in the same sense as in the proof of Theorem1.1). Generally, assume that we have defined, for some $i\in [\frac {1}{\varepsilon ^2}]$ , sets $I_0,\dots ,I_i\subseteq [m]$ , indices $r_1,\dots ,r_{i+1}\in [m]$ , and for each $i'\in [i]$ and $k\in I_{i'}\smallsetminus \{r_{i'+1},m\}$ , vertices $x_{i'}\in \mathcal{P}^{r_{i'}m}$ and $z_{i'k}\in \mathcal{P}^{r_{i'}k}$ such that the following holds. For all $i'\in [i]$ , we have $I_{i'}\subseteq I_{i'-1}\smallsetminus r_{i'}$ , $m\in I_{i'}$ , $r_{i'+1}=\min I_{i'}$ , and $\vert I_{i'}\vert \geqslant m_{i'}$ , and further for all $jk\in (I_{i'}\smallsetminus m)^{(2)}$ with $j\lt k$ , there is some $y\in \mathcal{P}^{r_{i'}j}$ such that $x_{i'}z_{i'k}y$ forms a triangle in $Q^{r_{i'}}$ .

Then we apply Lemma 4.1 with $I_i$ instead of $I$ , and $m_i$ and $m_{i+1}$ in place of $m_1$ and $m_2$ , respectively. This yields a set $I_{i+1}\subseteq I_i\smallsetminus r_{i+1}$ with $m\in I_{i+1}$ and $\vert I_{i+1}\vert \geqslant m_{i+1}$ , a vertex $x_{i+1}\in \mathcal{P}^{r_{i+1}m}$ , and for all $k\in I_{i+1}\smallsetminus \{r_{i+2},m\}$ , where $r_{i+2}=\min I_{i+1}$ , vertices $z_{i+1k}\in \mathcal{P}^{r_{i+1}k}$ such that for all $jk\in (I_{i+1}\smallsetminus m)^{(2)}$ with $j\lt k$ , there is some $y\in \mathcal{P}^{r_{i+1}j}$ such that $x_{i+1}z_{i+1k}y$ forms a triangle in $Q^{r_{i+1}}$ .

Due to (4.2), we can proceed in this manner until $i=\frac {1}{\varepsilon ^2}+1$ , that is, we can construct a set $I_{\frac {1}{\varepsilon ^2}+1}$ with $\vert I_{\frac {1}{\varepsilon ^2}+1}\vert \geqslant m_{\frac {1}{\varepsilon ^2}+1}$ in this manner. Let $m'=\max I_{\frac {1}{\varepsilon ^2}+1}\smallsetminus m$ . During the iteration, we found for each $i\in [\frac {1}{\varepsilon ^2}+1]$ vertices $x_i$ and $z_{im'}$ such that, in particular, $x_iz_{im'}\in E(Q^{r_i})$ . We set $e_i=x_iz_{im'}$ . By definition of $Q^{r_i}$ , there is a set $H(e_i)\subseteq \mathcal{P}^{m'm}$ with $\vert H(e_i)\vert \geqslant \varepsilon ^2\vert \mathcal{P}^{m'm}\vert$ such that $x_iz_{im'}v\in E(\mathcal{A}^{r_im'm})$ for every $v\in H(e_i)$ . Thus there are two indices $i,j\in [\frac {1}{\varepsilon ^2}+1]$ such that $H(e_i)\cap H(e_j)\neq \varnothing$ . W.l.o.g., assume $i\lt j$ .

Let $v\in H(e_i)\cap H(e_j)$ and let $y\in \mathcal{P}^{r_ir_j}$ such that $x_iz_{im'}y$ forms a triangle in $Q_{r_i}$ (such a $y$ exists due to the choice of $x_i$ and $z_{im'}$ ). The definition of $Q^{r_i}$ implies that there are vertices $u_1\in \mathcal{P}^{r_jm}$ and $u_2\in \mathcal{P}^{r_jm'}$ such that $x_iyu_1\in E(\mathcal{A}^{r_ir_jm})$ and $z_{im'}yu_2\in E(\mathcal{A}^{r_ir_jm'})$ . Since we also have the edges $x_iz_{im'}v\in E(\mathcal{A}^{r_im'm})$ and $x_jz_{jm'}v\in E(\mathcal{A}^{r_jm'm})$ , the indices $r_i$ , $r_j$ , $m'$ , and $m$ and the vertices $x_i$ , $z_{im'}$ , $y$ , $x_j$ , $u_1$ , $z_{jm'}$ , $u_2$ , and $v$ form the desired configuration. This is illustrated in Fig. 5.

Figure 5.

$K_4^{(3)-}$ with one vertex glued embedded in the reduced hypergraph $\mathcal{A}$ that we obtain, following the procedure above.