2.1 Hypergraphs

Let G be an r-graph. The complement of G is . For a vertex $v\in V(G)$ , its link is the $(r-1)$ -hypergraph

For $U\subseteq V(G)$ , its induced subgraph is . The vertex sets of $\overline {G}$ , $L_{G}(v)$ , and $G[U]$ are by default $V(G)$ , $V(G)\setminus \{v\}$ , and U, respectively. The degree of $v\in V(G)$ is . Let $\Delta (G)$ and $\delta (G)$ denote respectively the maximum and minimum degrees of the r-graph G.

An embedding of an r-graph F into G is an injection $f:V(F)\to V(G)$ such that $f(E)\in G$ for every $E\in F$ . Thus, F is a subgraph of G if and only if F admits an embedding into G. An embedding is induced if non-edges are mapped to non-edges.

The edit distance between two r-graphs G and H with the same number of vertices is the smallest number of edits (i.e., removal and addition of edges) that have to be applied to G to make it isomorphic to H; in other words, this is the minimum of $|G\bigtriangleup \sigma (H)|$ over all bijections $\sigma :V(H)\to V(G)$ . We say that G and H are $\mathbf {s}$ -close if they are at edit distance at most s.

2.2 Further definitions and results for a single pattern

In this section, we focus on a single pattern $P = (m, E, R)$ . Let the Lagrange polynomial of E be

(2.1)

The special case of (2.1) when E is an r-graph (i.e., E consists of simple sets) gives the well-known hypergraph Lagrangian (see, for example, [Reference Baber and Talbot1, Reference Frankl and Rödl13]) that has been successfully applied to Turán-type problems, with the basic idea going back to Motzkin and Straus [Reference Motzkin and Straus28].

For $i\in [m]$ , let the link $L_{E}(i)$ consist of all $(r-1)$ -multisets A such that if we increase the multiplicity of i in A by one, then the obtained r-multiset belongs to E.

The following simple fact follows easily from the definitions.

See also Lemma 2.4 that relates $\lambda _E$ and $\lambda _{P}$ .

We call a pattern P proper if it is minimal and $0<\lambda _{P}<1$ . Trivially, every minimal pattern $P=(m,E,R)$ satisfies that

(2.3) $$ \begin{align} L_{E}(i)\not=\emptyset,\qquad \text{for every }i\in [m]. \end{align} $$

We will also need the following result from [Reference Pikhurko30], which characterizes those patterns whose Lagrangian is $1$ .

The standard $\mathbf {(m-1)}$ -dimensional simplex is

(2.4)

Also, let

be obtained from the simplex ${\mathbb S}_m$ by excluding all its vertices (i.e., the standard basis vectors).

For a pattern $P=(m,E,R)$ , we say that a vector $\mathbf {x}\in {\mathbb R}^{m}$ is $\mathbf {P}$ -optimal if $\mathbf {x}\in {\mathbb S}_{m}^*$ and

(2.5) $$ \begin{align} \lambda_{E}(\mathbf{x}) + \lambda_{P} \sum_{j\in R} x_j^r = \lambda_{P}. \end{align} $$

Note that when we define P-optimal vectors we restrict ourselves to ${\mathbb S}_{m}^*$ (i.e., we do not allow any standard basis vector to be included).

We will need the following result from [Reference Pikhurko30], which extends some classical results (see e.g. [Reference Frankl and Rödl13, Theorem 2.1]) about the Lagrangian of hypergraphs.

Lemma 2.4 ([Reference Pikhurko30, Lemma 14]).

Let $P=(m,E,R)$ be a proper r-graph pattern and let

be the left-hand side of (2.5). Let ${ \cal X}$ be the set of all P-optimal vectors. Then the following statements hold.

1. (a) The set ${ \cal X}$ is nonempty.

2. (b) We have $f(\mathbf {x})\le \lambda _{P}$ for all $\mathbf {x}\in {\mathbb S}_{m}$ .

3. (c) The set ${ \cal X}$ does not intersect the boundary of ${\mathbb S}_{m}$ (i.e., no vector in ${ \cal X}$ has a zero coordinate).

4. (d) For every $\mathbf {x}\in { \cal X}$ and $j\in [m]$ , we have $\frac {\partial f}{\partial _j}(\mathbf {x}) = r\cdot \lambda _{P}$ .

5. (e) The set ${ \cal X}$ , as a subset of ${\mathbb S}_{m}$ , is closed. (In particular, no sequence of P-optimal vectors can converge to a standard basis vector.)

6. (f) For every ${\varepsilon }>0$ , there is $\alpha>0$ such that for every $\mathbf {y}\in {\mathbb S}_{m}$ with $\max (y_1,\dots ,y_{m})\le 1-{\varepsilon }$ and $f(\mathbf {y})\ge \lambda _{P}-\alpha $ , there is $\mathbf {x}\in { \cal X}$ with $\|\mathbf {x}-\mathbf {y}\|_\infty \le {\varepsilon }$ .

7. (g) There is a constant $\beta>0$ such that for every $\mathbf {x}\in { \cal X}$ and every $j\in [m]$ , we have $x_j\ge \beta $ .

Observe that, in the above lemma, Parts (a) and (b) imply that ${ \cal X}$ is precisely the set of elements in ${\mathbb S}_{m}^*$ that maximise $\lambda _{E}(\mathbf {x}) + \lambda _{P} \sum _{j\in R} x_j^r$ . Also, note that (c) is a consequence of (g).

We will also need the following easy inequality.

Lemma 2.5. Suppose that E is a collection of r-multisets on $[m]$ and $\mathbf {u}, \mathbf {x} \in \mathbb {S}_m$ . Then for every $j\in [m]$ , we have

$$ \begin{align*} \left|\frac{\partial\lambda_{E}}{\partial_{j}}(\mathbf{u}) -\frac{\partial\lambda_{E}}{\partial_{j}}(\mathbf{x})\right| \le r^2 m \cdot \|\mathbf{u} - \mathbf{x}\|_\infty. \end{align*} $$

Proof. Fix $j_{\ast } \in [m]$ . By Fact 2.1(b), we have $\frac {\partial \lambda _{E}}{\partial _{j_{\ast }}}(\mathbf {y}) = r\cdot \lambda _{L_{E}(j_{\ast })}(\mathbf {y})$ for every $\mathbf {y} \in \mathbb {S}_{m}$ . Let . Similarly, for every $i \in [m]$ and $\mathbf {y} \in \mathbb {S}_{m}$ , we have $\frac {\partial \lambda _{\hat {E}}}{\partial _{i}}(\mathbf {y}) = (r-1)\cdot \lambda _{L_{\hat {E}}(i)}(\mathbf {y})$ , and hence,

$$ \begin{align*} \left|\frac{\partial^2\lambda_{E}}{\partial_{i}\partial_{j_{\ast}}}(\mathbf{y})\right| = r\cdot \frac{\partial\lambda_{\hat{E}}}{\partial_{i}}(\mathbf{y}) & = r(r-1)\cdot \lambda_{L_{\hat{E}}(i)}(\mathbf{y}) \\ & \le r^2 \sum_{S\in \left(\kern-.45em\left(\genfrac{}{}{0pt}{}{[m]}{r-2}\right)\kern-.45em\right)}\prod_{i\in S} y_i = r^2 \left(\sum_{i=1}^{m} y_i\right)^{r-2} = r^2. \end{align*} $$

Given $\mathbf {u}, \mathbf {x} \in \mathbb {S}_m$ , it follows from the Mean Value Theorem that there exists $\mathbf {y} = \alpha \mathbf {u}+ (1-\alpha ) \mathbf {x} \in \mathbb {S}_{m}$ for some $\alpha \in [0,1]$ such that

$$ \begin{align*} \left| \frac{\partial\lambda_{E}}{\partial_{j_{\ast}}}(\mathbf{u}) -\frac{\partial\lambda_{E}}{\partial_{j_{\ast}}}(\mathbf{x})\right| = \left| \sum_{i \in [m]} \frac{\partial^2\lambda_{E}}{\partial_{i}\partial_{j_{\ast}}}(\mathbf{y}) \cdot (u_i - x_i)\right| & \le \max_{i\in [m]}\left\{ \left|\frac{\partial^2\lambda_{E}}{\partial_{i}\partial_{j_{\ast}}}(\mathbf{y})\right| \right\} \cdot \sum_{i=1}^{m}\left|u_i-x_i\right| \\ & \le r^2\sum_{i=1}^{m}\left|u_i-x_i\right| \le r^2m \cdot \|\mathbf{u} -\mathbf{x}\|_\infty. \end{align*} $$

This proves Lemma 2.5.

2.3 Mixing patterns

Let (1.1) apply; that is, $P_I=\{P_i: i \in I\}$ , where $P_{i} = (m_i, E_i, R_i)$ is an r-graph pattern for each $i\in I$ .

First, to each $P_I$ -mixing construction G, we will associate its base value $b(G)$ . For this, we need to designate some special element not in I, say, $\emptyset \not \in I$ . If G has no edges, then we set ; otherwise, let $b(G)$ be the element of I such that the first step when making the $P_I$ -mixing construction G was to take a blowup of $E_j$ . It may in principle be possible that some different choices of j lead to another representation of the same r-graph G as a $P_I$ -mixing construction. We fix one choice for $b(G)$ , using it consistently. We say that G has base $P_{b(G)}$ and call b the base function.

Next, to every $G\in \Sigma P_I$ , we will associate a pair $(\mathbf {V}_{G},\mathbf {T}_G)$ which encodes how the $P_{I}$ -mixing construction G is built. In brief, the tree $\mathbf {T}_G$ of G records the information how the patterns are mixed while the partition structure $\mathbf {V}_{G}$ specifies which vertex partitions were used when making each blowup.

Let us formally define $\mathbf {V}_{G}$ and $\mathbf {T}_G$ , also providing some related terminology. We start with $\mathbf {V}_{G}$ having only one set and with $\mathbf {T}_{G}$ consisting of the single root $((), \emptyset )$ . If G has no edges, then this finishes the definition of $(\mathbf {V}_{G},\mathbf {T}_G)$ . So suppose that $|G|>0$ . By the definition of , there exists a partition $V(G) = V_1 \cup \dots \cup V_{m_{j}}$ with $V_i\not =V$ for $i\in R_{j}$ such that $G\setminus \left (\bigcup _{k\in R_{j}}G[V_k]\right ) = E_{j}(\!(V_1, \ldots , V_{m_{j}})\!)$ . (Again, it may be possible that some different choices of the partition lead to another representation of $G\in \Sigma P_I$ , so fix one choice and use it consistently.) This initial partition $V(G)=V_1\cup \dots \cup V_{m_{j}}$ is called the level- $\mathbf {1}$ partition and $V_1, \ldots , V_{m_{j}}$ are called the level- $\mathbf {1}$ (or bottom) parts. We add the parts $V_1,\ldots ,V_{m_{j}}$ to $\mathbf {V}_{G}$ and add $((1), j), \ldots , ((m_{j}), j)$ as the children of the root $((),\emptyset )$ of $\mathbf {T}_G$ . Note that we add all $m_{j}$ children, even if some of the corresponding parts are empty. Next, for every $i\in R_{j}$ with $|G[V_i]|>0$ , we apply recursion to $G[V_i]$ to define the descendants of $((i),j)$ as follows. Let $P_t$ be the base of $G[V_i]$ (that is, ). Add $((i,1),t),\dots ,(i,m_t),t)$ as the children of $((i), j)$ in $\mathbf {T}_G$ and add to $\mathbf {V}_{G}$ the sets $V_{i,1},\dots , V_{i,m_t}$ (called level- $\mathbf {2}$ parts) forming the partition of $V_i$ that was used for the blowup of $E_t$ . In other words, the set of level- $2$ parts of G is the union over $i\in R_{j}$ of level-1 parts of $G[V_i]$ . We repeat this process. Namely, a node $(\mathbf {i},j)$ in $\mathbf {T}_G$ , where $\mathbf {i}=(i_1,\ldots ,i_s)$ , has children if and only if $|G[V_{\mathbf {i}}]|>0$ (then necessarily, $i_s\in R_j$ ), in which case the children are $((\mathbf {i},k),t)$ for $k\in [m_t]$ , where ; then we also add to $\mathbf {V}_{G}$ the level- $\mathbf {(s+1)}$ parts $V_{\mathbf {i},1},\dots ,V_{\mathbf { i},m_t}$ which we used for the blowup of $E_t$ . Note that we are slightly sloppy with our bracket notation, with $\mathbf {i},k$ meaning $i_1,\dots ,i_s,k$ (and with $\emptyset $ sometimes meaning the empty sequence). Thus, level- $(s+1)$ parts of G can be defined as the level-s parts of $G[V_i]$ for all $i\in R_{b(G)}$ . This finishes the definition of $(\mathbf {V}_{G},\mathbf {T}_G)$ . For some examples, see Section 2.4.

Clearly, the pair $(\mathbf {V}_{G},\mathbf {T}_G)$ determines G (although this representation has some redundancies). We often work with just $\mathbf {V}_{G}$ (without explicitly referring to $\mathbf {T}_G$ ). When G is understood, we may write $\mathbf {V}_{}$ for $\mathbf {V}_{G}$ .

A sequence $(i_1,\dots ,i_s)$ is called legal (with respect to G) if $V_{i_1,\ldots ,i_s}$ is defined during the above process. This includes the empty sequence, which is always legal. We view $\mathbf {V}_{G}$ and $\mathbf {T}_G$ as vertical (see, for example, Figure 3) with the index sequence growing as we go up in level. This motivates calling the level- $1$ parts bottom (even though we regard $V_{\emptyset }$ as level- $0$ ). By default, the profile of $X\subseteq V(G)$ is taken with respect to the bottom parts; that is, its multiplicities are $(|X\cap V_1|,\dots ,|X\cap V_m|)$ . The height of G is the maximum length of a legal sequence (equivalently, the maximum number of edges in a directed path in the tree $\mathbf {T}_G$ ). Call a part $V_{i_1,\ldots ,i_s}$ recursive if $s=0$ or the (unique) node $((i_1,\ldots ,i_s),t)$ of $\mathbf {T}_G$ satisfies $i_s\in R_t$ . (Note that we do not require that $|G[V_{i_1,\dots ,i_s}]|>0$ in this definition.) Otherwise, we call $V_{i_1,\ldots ,i_s}$ non-recursive. The branch $\mathbf {\mathrm {br}_{G}(v)}$ of a vertex $v\in V(G)$ is the (unique) maximal sequence $\mathbf {i}$ such that $v\in V_{\mathbf {i}}$ . If $b(G)=\emptyset $ , then every branch is the empty sequence; otherwise, every branch is nonempty. Let $\mathbf {T}_{G}^{\mathrm {level}\le \ell }$ be obtained from $\mathbf {T}_{G}$ by removing all nodes at level higher than $\ell $ .

Note that the values of the base function b are incorporated into the tree $\mathbf {T}_G$ by ‘shifting’ them one level up: namely, if a part $V_{\mathbf {i}}$ is recursive and is not $\emptyset $ , then j appears as the second coordinate on all children of the unique node of $\mathbf {T}_G$ with the first coordinate $\mathbf {i}$ . This is notationally convenient: for example, if $G'$ is obtained from $G\in \Sigma P_I$ by deleting all edges inside some part $V_{\mathbf {i}}$ then $\mathbf {T}_{G'}$ is a subtree of $\mathbf {T}_G$ ; that is, it can be obtained from $\mathbf {T}_G$ by iteratively deleting leaves. (In fact, the subtree $\mathbf {T}_{G'}$ is full, that is, every non-leaf node of $\mathbf {T}_{G'}$ has the same set of children in $\mathbf {T}_{G'}$ as in $\mathbf {T}_{G}$ .)

We say that $\mathbf {T}$ is a feasible tree if there exists a $P_{I}$ -mixing construction G with $\mathbf {T}_{G}=\mathbf {T}$ . We say that a feasible tree $\mathbf {T}$ is non-extendable if it has positive height and every leaf $v=((i_1,\dots ,i_s),t)$ of $\mathbf {T}$ satisfies $i_s\not \in R_t$ . Equivalently, $\mathbf {T}$ is non-extendable if it is not a subtree of a strictly larger feasible tree. Otherwise, we say that $\mathbf {T}$ is extendable.

Given a family $P_I=\{P_i \colon i\in I\}$ of r-graph patterns, recall that ${ \cal F}_\infty $ consists of those r-graphs F that do not embed into a $P_{I}$ -mixing construction. For an integer s, let ${ \cal F}_s$ consist of all members of ${ \cal F}_\infty $ with at most s vertices.

Note that we do not require here (nor in Theorem 1.2) that all patterns $P_i$ have the same Lagrangian (although this will be the case in all concrete applications of Theorem 1.2 that we present in this paper). As we will see in Lemma 3.4, patterns $P_i$ with $\lambda _{P_i}< \max \{\lambda _{P_j}: j\in I\}$ will not affect the largest asymptotic density of $P_I$ -mixing constructions (however, they may appear in maximum constructions at the recursion level when we consider parts of bounded size).

2.4 Examples

In this section, we give some examples to illustrate some of the above definitions. The set $P_I$ of the first example will be later used in our proof of Theorem 1.5.

Recall that $K_{5}^3$ is the complete $3$ -graph on $5$ vertices (let us assume that its vertex set is $[5]$ ). Let $B_{5,3}$ be the $3$ -graph on $7$ vertices (let us assume that its vertex set is $[7]$ ) whose edge set is the union of all triples that have at least two vertices in $\{1,2,3\}$ and all triples (with their ordering ignored) from the following set:

$$ \begin{align*} \Big(\{1\}\times \{4,5\}\times \{6,7\}\Big) \cup \Big(\{2\}\times \{4,6\}\times \{5,7\}\Big) \cup \Big(\{3\}\times \{4,7\}\times \{5,6\}\Big). \notag \end{align*} $$

In particular, for $i\in \{1,2,3\}$ , the induced subgraph of $L_{B_{5,3}}(i)$ on $\{4,5,6,7\}$ is a copy of $K_{2,2}$ (where $K_{m,n}$ denotes the complete bipartite graph with parts of size m and n), and their union covers each pair in $\{4,5,6,7\}$ exactly twice. See Figure 1 for an illustration.

Figure 1 The induced subgraph of $L_{B_{5,3}}(i)$ on vertex set $\{4,5,6,7\}$ is a copy of $K_{2,2}$ for $i\in \{1,2,3\}$ .

The motivation for defining $B_{5,3}$ comes from the so-called crossed blowup defined in [Reference Hou, Li, Liu, Mubayi and Zhang15] so, in fact, $B_{5,3}$ is a 3-crossed blowup of $K_{5}^{3}$ .

Let and . Suppose that G is a $\{P_1, P_2\}$ -mixing construction with exactly three levels: the base for G is $P_1$ , the base for $G[V_1]$ is $P_2$ , and the base for $G[V_{1,1}]$ is $P_1$ (see Figure 2). It is clear that every feasible tree (see, for example, Figure 3) is extendable since every pattern $P_i$ has nonempty $R_i$ .

Figure 2 The partition structure of a $\{P_1, P_2\}$ -mixing construction G with exactly three levels: the base for level-1 is $P_1$ , while the bases for the (unique) recursive parts at levels 2 and 3 are, respectively, $P_2$ and $P_1$ .

Figure 3 The tree $\mathbf {T}_G$ of G.

For the second example, we take $P_1 = (3, \{123\}, \{1\})$ and $P_2 = (4, K_4^3, \emptyset )$ . Let G be a $\{P_1, P_2\}$ -mixing construction with three levels: the base for G is $P_1$ , the base for $G[V_1]$ is $P_1$ , and the base for $G[V_{1,1}]$ is $P_2$ ; see Figure 4. Note that the tree $\mathbf {T}_G$ of G (see Figure 5) of G is non-extendable, since every leaf in $\mathbf {T}_G$ is non-recursive.

Figure 4 The partition structure of a $\{P_1, P_2\}$ -mixing construction G with exactly three levels: the base for level-1 is $P_1$ , while the bases for the unique recursive parts at level 2 and 3 are $P_1$ and $P_2$ , respectively.

Figure 5 The tree $\mathbf {T}_G$ of G.

3.1 Some additional assumptions and definitions related to $P_I$

Recall that I is finite, $P_I=\{P_i \colon i\in I\}$ with each pattern $P_i = (m_i, E_i, R_i)$ for $i\in I$ being minimal. Let us define

(3.1)

We can assume that $\lambda>0$ : if $\lambda =0$ , then every $P_I$ -mixing construction is edgeless, and we can satisfy Theorem 1.2 by letting $M = r$ , with ${ \cal F}_{M} = \{K^r_r\}$ consisting of a single edge.

Furthermore, we can assume that $\lambda _{P_i}>0$ for every $i\in I$ by removing all patterns with zero Lagrangian. (This does not change the family of all $\Sigma P_i$ -mixing constructions, since $E_i=\emptyset $ for every $i\in I$ with $\lambda _{P_i}=0$ and we always have the option to put the empty r-graph into a part.)

Note that if $\lambda = 1$ (i.e., $\lambda _{P_t} = 1$ for some $t\in I$ ), then every complete r-graph is a $P_t$ -construction by Lemma 2.3. Indeed, for example, if the second statement of Lemma 2.3 holds – that is, $\{\hspace {-0.25em}\{\hspace {0.1em}{i}^{(r-1)},j\hspace {0.1em}\}\hspace {-0.25em}\}\in E_t$ for some $i\in R_t$ – then this is attained by making all partitions to consist of only two nonempty parts, the j-th part consisting of a single vertex and the i-th (recursive) part being the rest. So, if $\lambda = 1$ , then $\Lambda _{P_I}(n)=\binom {n}{r}$ , and we can satisfy Theorem 1.2 by letting $M = 0$ with $\mathcal {F}_{M} = \emptyset $ being the empty forbidden family. Therefore, let us assume that every $P_i$ , in addition to being minimal, is also proper (that is, that $0<\lambda _{P_i}<1$ for each $i\in I$ ).

We can additionally assume that, for all distinct $i,j\in [m]$ , the patterns $P_i$ and $P_j$ are non-isomorphic (that is, there is no bijection $f:[m_i]\to [m_j]$ with $f(R_i)=R_j$ and $f(E_i)=E_j$ ), by just keeping one representative from each isomorphism class.

Also, let us state here some definitions that apply in Section 3 (that is, for the rest of the proof of Theorem 1.2). Since the set I is finite, we can fix a constant $\beta>0$ that satisfies Part (g) of Lemma 2.4 for each pattern $P_i$ with $i\in I$ . Also, for $i\in I$ , let us define

(3.2)

and let ${ \cal X}_i\subseteq {\mathbb S}_{m_i}^*$ be the set of $P_i$ -optimal vectors. Similar to Fact 2.1(a), for every $P_{I}$ -mixing construction G on $[n]$ with base $P_i$ and bottom partition $[n] = V_{1} \cup \cdots \cup V_{m_i}$ , we have

(3.3) $$ \begin{align} \lambda \ge f_i\left(|V_1|/n, \ldots, |V_{m_i}|/n\right) = \rho(G) + o(1). \end{align} $$

3.2 Basic properties of $P_I$ -mixing constructions

In this section, we present some simple properties of $P_I$ -mixing constructions.

The following two lemmas follow easily from the definitions. We refer the reader to [Reference Pikhurko30, Lemmas 6 and 7], where the proofs for Lemmas 3.1 and 3.2 are provided for P-constructions.

It follows from Lemma 3.2 that $\mathrm {ex}(n,{ \cal F}_n)=\mathrm {ex}(n,{ \cal F}_\infty )=\Lambda _{P_I}(n)$ .

The following result states that the maximum asymptotic edge density of a $P_I$ -mixing construction is the same as the largest one attained by a single pattern $P_i$ .

Proof. By fixing some i in $I'\not =\emptyset $ , we trivially have that $\Lambda _{P_I}(n)\ge \Lambda _{P_i}(n)$ for each n. This implies that

$$ \begin{align*} \lim_{n\to \infty}\Lambda_{P_I}(n)/\binom{n}{r}\ge \lim_{n\to\infty} \Lambda_{P_i}(n)/\binom{n}{r}=\lambda. \end{align*} $$

Let us show the converse inequality. Let $\Sigma _hP_I$ consist of all $P_I$ -mixing constructions whose partition structure has height at most h. For example, $\Sigma _1P_I$ consists of all possible blowups of $E_i$ , for $i\in I$ , without putting any edges into their recursive parts.

Let us show by induction on $h\ge 1$ that $\lambda _h\le \lambda $ , where we let

(The limit exists since the ratios are non-increasing in n by the same argument as in Lemma 3.3.)

If $h=1$ , then every r-graph in $\Sigma _hP_I$ is a $P_i$ -construction for some $i\in I$ and has asymptotic density at most $\max \{\lambda _{P_i}\colon i\in I\}=\lambda $ , as desired. Let $h\ge 2$ . Take any maximum $G_n\in \Sigma _hP_I$ of order $n\to \infty $ . By passing to a subsequence assume that there is $i\in I$ such that each $G_n$ has base pattern $P_i$ . Let $V(G_n)=V_{n,1}\cup \cdots \cup V_{n,m_i}$ be the base partition of $G_n$ . Let for $j\in [m_i]$ . By passing to a subsequence again, assume that $x_{n,j}$ tends to some limit $x_j$ for each $j\in [m_i]$ . Then it follows from the definition of $\Sigma _h P_{I}$ , continuity of $\lambda _{E_i}$ , and induction that

$$ \begin{align*} \rho(G_n) & \le \lambda_{E_i}(x_{n,1}, \ldots, x_{n,m_i}) + \lambda_{h-1}\sum_{j\in R_i} x_{n,j}^{r} + o(1) \notag\\ & \le \lambda_{E_i}(x_1, \ldots, x_{m_i}) + \lambda\sum_{j\in R_i} x_j^{r} + o(1). \notag \end{align*} $$

Furthermore, by Part (b) of Lemma 2.4 and by $\lambda _{P_i}\le \lambda $ , we have

$$ \begin{align*} \lambda_{E_i}(x_1, \ldots, x_{m_i}) \le \lambda_{P_i}\left(1-\sum_{j\in R_i} x_j^{r}\right)\le \lambda \left(1-\sum_{j\in R_i} x_j^{r}\right). \end{align*} $$

By putting these together, we conclude that $\rho (G_n) \le \lambda +o(1)$ , giving the required. This finishes the proof of the lemma.

Given a $P_I$ -mixing construction G and a vertex v in G, a newly added vertex $v'$ is called a clone of v if the link of $v'$ in the new r-graph is identical to the link of v in G. Note that adding a clone of a vertex to a $P_I$ -mixing construction results a $P_I$ -mixing subconstruction.

The following lemma says that the minimum degree of a maximum ${ \cal F}_s$ -free r-graph is close to its average degree.

3.3 Properties of proper patterns

Recall that all assumptions made in Section 3.1 continue to apply to the fixed family $P_I$ ; in particular, we have $0<\lambda <1$ . The following lemma shows that no bottom part of a $P_{I}$ -mixing construction G can contain almost all vertices if G has large minimum degree.

Proof. Given $c'>0$ , let $n\to \infty $ and take any c and G as in the lemma. Let the base of G be $P_i$ . If $j\in [m_i]\setminus R_i$ , then it follows from $\delta (G)n/r\le |G|\le \binom {n}{r}-\binom {|V_j|}{r}$ that

$$ \begin{align*} \left(\frac{|V_j|-r}{n}\right)^r \le \frac{\binom{|V_j|}{r}}{\binom{n}{r}} \le 1-c. \end{align*} $$

Simplifying this inequality, we obtain

$$ \begin{align*} |V_j| \le (1-c)^{1/r} n +r \le \left(1-\frac{c}{r} - \frac{(r-1)c^2}{2r^2}\right)n + r \le \left(1-\frac{c}{r}\right)n, \end{align*} $$

as desired. Here, we used the inequality $(1-x)^{1/r} \le 1-\frac {x}{r} - \frac {(r-1)x^2}{2r^2}$ for all $r \ge 1$ and $x \in [0,1]$ .

Now suppose that $j\in R_i$ . Since $V_j \neq V(G)$ , pick any vertex $v \in V_k$ with $k\neq j$ . Since $\{\hspace {-0.25em}\{\hspace {0.1em}{j}^{(r-1)},k\hspace {0.1em}\}\hspace {-0.25em}\} \not \in E_i$ by Lemma 2.3, every edge through v contains at least one other vertex outside of $V_j$ . Thus, $c\binom {n-1}{r-1} \le d_G(v)\le (n-|V_j|)\binom {n-2}{r-2}$ , implying $|V_j| \le (1-c/(r-1)+o(1))n\le (1-c/r)n$ .

Informally speaking, the following lemma (which is a routine generalization of [Reference Pikhurko30, Lemma 15]) implies, among other things, that all part ratios of bounded height in a $P_{I}$ -mixing construction with large minimum degree approximately follow some optimal vectors. In particular, for each $i\in I'$ , the set ${ \cal X}_i$ consists precisely of optimal limiting bottom ratios that lead to asymptotically maximum $P_{I}$ -mixing constructions with base pattern $P_i$ . Recall that $\beta>0$ is the constant that satisfies Part (g) of Lemma 2.4 for every $i\in I$ while ${ \cal X}_i$ is the set of $P_i$ -optimal vectors.

Proof. We choose positive constants in this order:

$$ \begin{align*} \alpha_{\ell+1}\gg {\varepsilon}_\ell\gg \alpha_\ell\gg \dots\gg {\varepsilon}_0\gg \alpha_0, \end{align*} $$

each being sufficiently small depending on $ P_{I}$ , ${\varepsilon }$ , $\beta $ , and the previous constants. We use induction on $s=0,1,\dots ,\ell $ , with the induction step also working for the base case $s=0$ , in which $\mathbf {i}$ is the empty sequence. Take any $s\ge 0$ and suppose that the lemma holds for all smaller values of s.

Let n be large and let G and $\mathbf {i}$ be as in the lemma. Let for $k\in [m_j]$ and . Thus, $U=U_1\cup \dots \cup U_{m_j}$ , and $\mathbf {v}_{\mathbf {i}}=(|U_1|/|U|,\dots ,|U_{m_j}|/|U|)$ . Note that

(3.4) $$ \begin{align} \delta(G[U])\ge (\lambda-\alpha_s)\binom{|U|-1}{r-1}, \end{align} $$

which holds by Part (d) of the inductive assumption applied to G if $s>0$ , and by the assumption of the lemma if $s=0$ (when $U=V_\emptyset =V(G)$ ). Thus, we have that

(3.5) $$ \begin{align} |G[U]|\ge \delta(G[U])|U|/r \ge (\lambda-\alpha_s)\binom{|U|}{r}. \end{align} $$

Note that $|U|$ can be made arbitrarily large by choosing n large. Indeed, this follows from the induction assumption for $s-1$ (namely, Part (c)) applied to G if $s\ge 1$ , while $U=V(G)$ has n elements if $s=0$ .

We claim that $\lambda _{P_j}=\lambda $ . Suppose on the contrary that the base $P_j$ of $G[U]$ satisfies $j\in I\setminus I'$ . Using the asymptotic notation with respect to $|U|\to \infty $ , we have by Lemma 2.4(b) that

$$ \begin{align*} \rho(G[U])&\le \lambda_{E_j}(\mathbf{v}_{\mathbf{i}})+\lambda \sum_{i\in R_j}\mathbf{v}_{\mathbf{i},i}^r+o(1)\\ &= f_j(\mathbf{v}_{\mathbf{i}})+(\lambda-\lambda_{P_j}) \sum_{i\in R_j}\mathbf{v}_{\mathbf{i},i}^r+o(1)\\ &\le \lambda_{P_j} + (\lambda-\lambda_{P_j}) \sum_{i\in R_j}\mathbf{v}_{\mathbf{i},i}^r+o(1). \end{align*} $$

This is strictly smaller than $\lambda -\alpha _s$ since, by (3.4) and Lemma 3.8, each $\mathbf {v}_{\mathbf {i},i}$ is at most, say, $1-\lambda /2r$ , and thus,

$$ \begin{align*} \sum_{i\in R_j}\mathbf{v}_{\mathbf{i},i}^r \le \left(1-\frac{\lambda}{2r}\right) \cdot \sum_{i\in R_j}\mathbf{v}_{\mathbf{i},i}^{r-1} \le \left(1-\frac{\lambda}{2r}\right) \cdot \left(\sum_{i\in R_j}\mathbf{v}_{\mathbf{i},i}\right)^{r-1} \le 1-\frac{\lambda}{2r} \end{align*} $$

is bounded away from 1. This contradiction shows that $j\in I'$ , proving Part (a).

Since $\alpha _s\ll {\varepsilon }_s$ , Equation (3.5), Lemma 3.8 and Part (f) of Lemma 2.4 (when applied to $P=P_j$ and $\mathbf {y}=\mathbf {v}_{\mathbf {i}}$ ) give the desired $P_j$ -optimal vector $\mathbf {x}$ , proving Part (b). Fix one such $\mathbf {x}=(x_1,\ldots ,x_{m_j})$ .

For all $k\in [m_j]$ , we have $|U_{k}|\ge (x_k-{\varepsilon }_s)|U| \ge (\beta /2)|U|$ . This is at least $(\beta /2)^{s+1}n$ by the inductive assumption on $|U|$ if $s\ge 1$ (and is trivial if $s=0$ ). Likewise, $|U| \le \left (1 - \frac {\lambda }{{{2r}}}\right )^{s}n$ . Therefore, it follows from Lemma 3.8 (with ) and (3.4) that

$$ \begin{align*} |U_k| \le \left(1 - \frac{\lambda}{{{2r}}}\right)|U| \le \left(1 - \frac{\lambda}{{{2r}}}\right)^{s+1}n. \notag \end{align*} $$

This proves Part (c).

Finally, take arbitrary $k\in R_j$ and $y\in U_k$ . By the definition of Lagrange polynomials and Fact 2.1(b), the degree of y in $E_j(\!(U_1,\dots ,U_{m_j})\!)$ is

$$ \begin{align*} d_{E_j(\!(U_1,\dots,U_{m_j})\!)}(y) = \left(\lambda_{L_{E_j}(k)}(\mathbf{v}_{\mathbf{i}}) +o(1)\right)\binom{|U|-1}{r-1} =\left(\frac1r\cdot \frac{\partial\lambda_{E_j}}{\partial_k}(\mathbf{v}_{\mathbf{i}})+o(1)\right) \binom{|U|-1}{r-1}. \end{align*} $$

Since $\|\mathbf {v}_{\mathbf {i}}-\mathbf {x}\|_\infty \le {\varepsilon }_s\ll \alpha _{s+1}$ , we have by Part (d) of Lemma 2.4 and Lemma 2.5 that, for example,

$$ \begin{align*} \frac{\partial \lambda_{E_j}}{\partial_k}(\mathbf{v}_{\mathbf{i}})-\alpha_{s+1}^2 \le \frac{\partial \lambda_{E_j}}{\partial_k}(\mathbf{x}) =\frac{\partial f}{\partial_k} (\mathbf{x})- r\lambda x_k^{r-1} = r\lambda-r\lambda x_k^{r-1}. \notag \end{align*} $$

Combining this with the previous equality, we obtain

$$ \begin{align*} d_{E_j(\!(U_1,\dots,U_{m_j})\!)}(y) \le \frac{1}{r}\left(r\lambda - r\lambda x_{k}^{r-1} + \alpha_{s+1}^2 +o(1)\right) \binom{|U|-1}{r-1} \le \left(\lambda - \lambda x_{k}^{r-1} +\frac{2 \alpha_{s+1}^2}{r}\right) \binom{|U|-1}{r-1}. \end{align*} $$

Thus, by (3.4) and the fact $\|\mathbf {v}_{\mathbf {i}}-\mathbf {x}\|_\infty \le {\varepsilon }_s$ , we have

$$ \begin{align*} d_{G[U_k]}(y) &= d_{G[U]}(y)-d_{E_j(\!(U_1,\dots,U_{m_j})\!)}(y)\\ &\ge \left((\lambda-\alpha_s)- \left(\lambda-\lambda x_k^{r-1}+\frac{2 \alpha_{s+1}^2}{r}\right)\right)\binom{|U|-1}{r-1}\\ &= \left(\lambda x_k^{r-1}-\alpha_s - \frac{2 \alpha_{s+1}^2}{r}\right)\binom{|U|-1}{r-1}\\ &\ge \left(\lambda (\mathbf{v}_{\mathbf{i}, k} - \varepsilon_{s})^{r-1}-\alpha_s - \frac{2 \alpha_{s+1}^2}{r}\right)\binom{|U|-1}{r-1}\\ &\ge \left(\lambda \mathbf{v}_{\mathbf{i}, k}^{r-1} - \lambda (r-1) \mathbf{v}_{\mathbf{i}, k}^{r-2} \varepsilon_{s}-\alpha_s - \frac{2 \alpha_{s+1}^2}{r}\right)\binom{|U|-1}{r-1}. \end{align*} $$

Since $\mathbf {v}_{\mathbf {i}, k} \gg \alpha _{s+1}\gg {\varepsilon }_s\gg \alpha _s$ , we have $\lambda (r-1) \mathbf {v}_{\mathbf {i}, k}^{r-2} \varepsilon _{s} + \alpha _s + \frac {2 \alpha _{s+1}^2}{r} \le \alpha _{s+1} \mathbf { v}_{\mathbf {i}, k}^{r-1}$ . Therefore, the above inequality on $d_{G[U_k]}(y)$ continues as

$$ \begin{align*} d_{G[U_k]}(y) \ge \left(\lambda \mathbf{v}_{\mathbf{i}, k}^{r-1} - \alpha_{s+1} \mathbf{v}_{\mathbf{i}, k}^{r-1}\right)\binom{|U|-1}{r-1} \ge \left(\lambda - \alpha_{s+1} \right)\binom{\mathbf{v}_{\mathbf{i}, k} |U|-1}{r-1} = \left(\lambda - \alpha_{s+1} \right)\binom{|U_k|-1}{r-1}. \end{align*} $$

This finishes the proof of Part (d).

For every $P_{I}$ -mixing construction G with base $P_i$ , the following lemma gives a bound for the degree of a vertex in G in terms of the distance between the vector of the part ratios and the set ${ \cal X}_i$ .

Lemma 3.10. Let $G \in \Sigma P_{I}$ be an r-graph on n vertices with base $P_{i}$ and bottom partition for some $i\in I'$ . Let and $\mathbf {x}\in { \cal X}_i$ . Then for every $j\in [m_i]$ and for every $v\in V_j$ we have

$$ \begin{align*} d_{G}(v) \le \begin{cases} \left(\lambda - \lambda x_j^{r-1} +rm_i \cdot \|\mathbf{u} - \mathbf{x}\|_\infty+o(1)\right) \binom{n-1}{r-1} + d_{G[V_{j}]}(v), & \text{if } j\in R_i, \\ \left(\lambda +rm_i \cdot \|\mathbf{u} - \mathbf{x}\|_\infty+o(1)\right) \binom{n-1}{r-1}, & \text{if } j\in [m_i]\setminus R_i. \end{cases} \end{align*} $$

Proof. First, it is easy to see from the definition of $\Sigma P_{I}$ that

$$ \begin{align*} d_{G}(v) = d_{E_{i}(\!(V_{1}, \cdots, V_{m_{i}})\!)}(v) + d_{G[V_{j}]}(v) = \left(\frac1r\cdot \frac{\partial\lambda_{E_{i}}}{\partial_{j}}(\mathbf{u})+o(1)\right) \binom{n-1}{r-1} + d_{G[V_{j}]}(v). \notag \end{align*} $$

So it follows from Lemma 2.5 that

$$ \begin{align*} d_{G}(v) \le \left(\frac1r\cdot \frac{\partial\lambda_{E_{i}}}{\partial_{j}}(\mathbf{x}) +rm_i \cdot \|\mathbf{u} - \mathbf{x}\|_\infty +o(1)\right) \binom{n-1}{r-1} + d_{G[V_{j}]}(v). \notag \end{align*} $$

If $j\in R_i$ , then it follows from Lemma 2.4(d) that

$$ \begin{align*} \frac{\partial\lambda_{E_{i}}}{\partial_{j}}(\mathbf{x}) = \frac{\partial\left(\lambda_{E_{i}}+\lambda \sum_{k\in R_i}x_k^{r}\right)}{\partial_{j}}(\mathbf{x}) - \frac{\partial\left(\lambda \sum_{k\in R_i}x_k^{r}\right)}{\partial_{j}}(\mathbf{x}) = r \lambda - r \lambda x_j^{r-1}, \notag \end{align*} $$

and hence,

$$ \begin{align*} d_{G}(v) \le \left( \lambda - \lambda x_j^{r-1} +rm_i \cdot \|\mathbf{u} - \mathbf{x}\|_\infty+o(1)\right) \binom{n-1}{r-1} + d_{G[V_{j}]}(v). \notag \end{align*} $$

If $j\in [m_i]\setminus R_i$ , then $d_{G[V_{j}]}(u) = 0$ and we have by Lemma 2.4(d) that $\partial \lambda _{E_{i}}(\mathbf {x})/\partial _{j} = r \lambda $ , and hence,

$$ \begin{align*} d_{G}(v) \le \left(\frac1r\cdot r \lambda +rm_i \cdot \|\mathbf{u} - \mathbf{x}\|_\infty+o(1)\right) \binom{n-1}{r-1} = \left( \lambda +rm_i \cdot \|\mathbf{u} - \mathbf{x}\|_\infty+o(1)\right) \binom{n-1}{r-1}. \notag \end{align*} $$

This proves Lemma 3.10.

The next lemma shows that every $ P_{I}$ -mixing subconstruction with large minimum degree is almost regular.

Proof. Fix any $\varepsilon>0$ . Choose a large constant $\ell \in \mathbb {N}$ . Let $\alpha _0<{\varepsilon }_0<\dots <\alpha _\ell <{\varepsilon }_\ell <\alpha _{\ell +1}$ in $(0,{\varepsilon })$ be the constants given by Lemma 3.9, where $\ell $ and $\varepsilon $ corresponds to the same constants in both lemmas. Next, choose sufficiently small constants $\delta \gg 1/n_0$ . Let us show that they satisfy the lemma. So pick any G as in the lemma.

By adding edges to the given r-graph G, we see that it is enough to prove the lemma when $G\in \Sigma P_I$ . So suppose that G is a $P_I$ -mixing construction on $n\ge n_0$ vertices with partition structure $\mathbf {V}$ such that $\delta (G) \ge (\lambda -\delta )\binom {n-1}{r-1}$ . Let $u\in V$ and let denote the branch of u, where s is an integer depending on u. Let and for $0 \le j \le s$ . Notice that $i_{j+1} \in R_{b_j}$ for $0 \le j \le s-1$ and $d_{G[V_{\mathbf {i}_{s}}]}(u) = 0$ . Additionally, note that $\mathbf {i}_0 = ()$ is the empty sequence, $\mathbf {i}_s = \mathbf {i}$ , and $V_{\mathbf {i}_0} = V(G)$ . Let for $1\le j \le s$ . Notice from Lemma 3.9(a) that $b_{j} \in I'$ for every $1 \le j \le \ell $ . Additionally, by Lemma 3.9(b) and our choice of constants, for each $j\in [\ell ]$ , the vector $\mathbf {u}_{j}$ is within distance ${\varepsilon }_j$ from some $P_{b_{j-1}}$ -optimal vector $\mathbf { x}_{j}$ . Also, let .

By Lemma 3.10, we obtain

$$ \begin{align*} d_{G}(u) & \le \left(\lambda - \lambda \mathbf{x}_{1,i_1}^{r-1} + rm \cdot \|\mathbf{u}_{1} - \mathbf{x}_{1}\|_\infty\right) \binom{|V_{\mathbf{i}_0}|-1}{r-1} + d_{G[V_{\mathbf{i}_1}]}(u) \\ & \le \left(\lambda - \lambda \left(\mathbf{u}_{1,i_1} - \varepsilon_1 \right)^{r-1} + rm \varepsilon_1\right) \binom{|V_{\mathbf{i}_0}|-1}{r-1} + d_{G[V_{\mathbf{i}_1}]}(u) \\ & \le \left(\lambda - \lambda \mathbf{u}_{1,i_1}^{r-1} + (r-1) \mathbf{u}_{1,i_1}^{r-2} \varepsilon_{1} + rm \varepsilon_1\right) \binom{|V_{\mathbf{i}_0}|-1}{r-1} + d_{G[V_{\mathbf{i}_1}]}(u) \\ & = \lambda \binom{|V_{\mathbf{i}_0}|-1}{r-1} - \lambda \mathbf{u}_{1,i_1}^{r-1} \binom{|V_{\mathbf{i}_0}|-1}{r-1} + \left((r-1) \mathbf{u}_{1,i_1}^{r-2} \varepsilon_{1} + rm \varepsilon_1\right) \binom{|V_{\mathbf{ i}_0}|-1}{r-1} + d_{G[V_{\mathbf{i}_1}]}(u) \\ & \le \lambda \binom{|V_{\mathbf{i}_0}|-1}{r-1} - \lambda \binom{\mathbf{u}_{1,i_1} |V_{\mathbf{i}_0}|-1}{r-1} + 2 rm \varepsilon_1 \binom{n-1}{r-1} + d_{G[V_{\mathbf{i}_1}]}(u) \\ & = \lambda \binom{|V_{\mathbf{i}_0}|-1}{r-1} - \lambda \binom{|V_{\mathbf{i}_1}|-1}{r-1} + 2 rm \varepsilon_1 \binom{n-1}{r-1} + d_{G[V_{\mathbf{i}_1}]}(u). \end{align*} $$

If $s < \ell $ , then by repeating the argument above for s times, we obtain

$$ \begin{align*} d_{G}(u) & \le \sum_{j=0}^{s-1} \left(\lambda \binom{|V_{\mathbf{i}_j}|-1}{r-1} - \lambda \binom{|V_{\mathbf{i}_{j+1}}|-1}{r-1} + 2 rm \varepsilon_{j+1} \binom{n-1}{r-1} \right) + d_{G[V_{\mathbf{i}_s}]}(u) \\ & = \lambda \binom{|V_{\mathbf{i}_0}|-1}{r-1} - \lambda \binom{|V_{\mathbf{i}_{s}}|-1}{r-1} + \sum_{j=0}^{s-1} \varepsilon_{j+1} \cdot 2 rm \binom{n-1}{r-1} \\ & \le \lambda \binom{n-1}{r-1} + \sum_{j=0}^{s-1} \varepsilon_{j+1} \cdot 2 rm \binom{n-1}{r-1} \le (\lambda + \varepsilon) \binom{n-1}{r-1}. \end{align*} $$

If $s \ge \ell $ , then by repeating the argument above for $\ell $ times and applying Lemma 3.9(c) to $V_{\mathbf {i}_{\ell }}$ , we obtain

$$ \begin{align*} d_{G}(u) & \le \sum_{j=0}^{\ell-1} \left(\lambda \binom{|V_{\mathbf{i}_j}|-1}{r-1} - \lambda \binom{|V_{\mathbf{i}_{j+1}}|-1}{r-1} + 2 rm \varepsilon_{j+1} \binom{n-1}{r-1} \right) + d_{G[V_{\mathbf{i}_{\ell}}]}(u) \\ & = \lambda \binom{|V_{\mathbf{i}_0}|-1}{r-1} - \lambda \binom{|V_{\mathbf{i}_{\ell}}|-1}{r-1} + \sum_{j=0}^{\ell-1} \varepsilon_{j+1} \cdot 2 rm \binom{n-1}{r-1} + \binom{|V_{\mathbf{i}_{\ell}}|-1}{r-1} \\ & \le \lambda \binom{|V_{\mathbf{i}_0}|-1}{r-1} + \sum_{j=0}^{\ell-1} \varepsilon_{j+1} \cdot 2 rm \binom{n-1}{r-1} + \binom{\left(1-\frac{\lambda}{2r}\right)^{\ell} n - 1}{r-1} \\ & \le \left(\lambda + \sum_{j=0}^{\ell-1} \varepsilon_{j+1} \cdot 2 rm + \left(1-\frac{\lambda}{2r}\right)^{\ell}\right) \binom{n-1}{r-1} \le (\lambda + \varepsilon) \binom{n-1}{r-1}. \end{align*} $$

This proves Lemma 3.11.

Given a collection E of r-multisets on a set V, a subset $U\subseteq V$ is called externally $\mathbf {E}$ -homogeneous if every permutation $\sigma $ of V that fixes every vertex outside of U is a symmetry of the set of multisets in E that intersect the complement of U, that is, . Equivalently, every permutation of V that moves only the elements of U preserves the set of multisets from E that intersect both U and $V\setminus U$ .

It is clear from the definition that if $|U| = 1$ , then U is always externally E-homogeneous. In addition, we have the following simple fact.

Fact 3.12. If E is an r-graph (that is, all multisets in E are simple sets), then a set $U \subseteq V(E)$ is externally E-homogeneous if and only if for every $s \in [r-1]$ and for every $S \in \binom {V\setminus U}{s}$

$$ \begin{align*} \mathrm{either}\quad L_{E}(S) \cap \binom{U}{r-s} = \emptyset \quad\mathrm{or}\quad L_{E}(S) \cap \binom{U}{r-s} = \binom{U}{r-s}. \end{align*} $$

Given a pattern $P = (m, E, R)$ , a map $h:[m]\to [m]$ is an automorphism of the pattern P if h is bijective, $h(R)=R$ , and h is an automorphism of E (that is, $h(E)=E$ ). Let us call a $P_{I}$ -mixing construction G with the base $P_i$ and the bottom partition $V_1\cup \dots \cup V_{m_i}$ for some $i\in I'$ rigid if, for every embedding f of G into a $P_{I}$ -mixing construction H with some base $P_j$ and bottom partition $U_1\cup \dots \cup U_{m_j}$ such that $f(V(G))$ intersects at least two different parts $U_{k}$ , we have $j = i$ and there is an automorphism h of $P_i$ such that $f(V_{k})\subseteq U_{h(k)}$ for every $k\in [m_i]$ .

The following key lemma generalizes [Reference Pikhurko30, Lemma 17] by allowing more than one pattern. Its proof requires some new ideas. For example, a trick that was used a number of times in [Reference Pikhurko30], in particular when proving Lemma 17 there, is that any embedding of a maximum P-construction G into another P-construction is induced (that is, non-edges are mapped to non-edges). However, a maximum $P_I$ -mixing construction whose base has to be $P_i$ for given $i\in I'$ need not be maximum (nor even maximal) among all $P_I$ -mixing constructions and some different arguments are required.

Proof. For every $i\in I$ , define

Since $P_i$ is minimal, we have $\eta _i> 0$ . Let . Clearly, $\eta>0$ .

Recall that $\beta>0$ is a constant satisfying Lemma 2.4(g) for each pattern $P_i$ . Choose sufficiently small positive constants in this order $\varepsilon _2\gg \varepsilon _1\gg \varepsilon _0$ . Let n be a sufficiently large integer and G be a $P_{I}$ -mixing construction on $[n]$ that satisfies the assumptions in Lemma 3.13. Let $\mathbf {V}$ denote the partition structure of G. Assume that the bottom partition is $V(G) = V_1 \cup \cdots \cup V_{m_i}$ for some $i\in I$ .

By our choice of the constants (and by Lemmas 3.9 and 3.11), we have that

1. (A) $|V_k| \ge \beta n/2$ for all $k\in [m_i]$ ,

2. (B) $\delta (G[V_k]) \ge (\lambda -\varepsilon _1)\binom {|V_k|-1}{r-1}$ for all $k\in R_i$ , and

3. (C) every $P_{I}$ -mixing subconstruction $G'$ on n vertices with $\delta (G') \ge (\lambda -\varepsilon _0)\binom {n-1}{r-1}$ satisfies $\Delta (G') \le (\lambda +\varepsilon _1)\binom {n-1}{r-1}$ .

Take any embedding f of G into some $P_{I}$ -mixing construction H with the base $P_j$ and the bottom partition $V(H)=U_1\cup \dots \cup U_{m_j}$ for some $j\in I$ such that $f(V(G))$ intersects at least two different parts $U_{k}$ .

Since $|V_k| \ge \beta n/2> \varepsilon _2 m_j n$ for all $k\in [m_i]$ , by the Pigeonhole Principle, there is a function $h\colon [m_i]\to [m_j]$ such that

(3.6) $$ \begin{align} |f(V_{k})\cap U_{h(k)}|\ge \varepsilon_2 n,\quad \text{for all }k\in [m_i]. \end{align} $$

Claim 3.13.1. We can choose h in (3.6) so that, additionally, $h(R_i)\subseteq R_j$ and h assumes at least two different values.

Proof of Claim. First, we prove that we can choose h so that $h(R_i)\subseteq R_j$ . This is trivially true if $R_i$ is empty, so suppose otherwise.

We claim that $R_j$ is also nonempty. Suppose to the contrary that $R_j = \emptyset $ . Let $k\in R_i$ . If there exists $j_0\in [m_j]$ such that $|f(V_k)\cap U_{j_0}|\le \varepsilon _2 n$ , then there exists a subset $V_k'\subseteq V_k$ of size at least $|V_k|-\varepsilon _2 n$ such that $f(V_{k}') \subseteq U\setminus U_{j_0}$ . Since, by (A),

(3.7) $$ \begin{align} \rho(G[V_k']) = |G[V_k']|/\binom{|V_k'|}{r} & \ge {\left(|G[V_{k}]|-\varepsilon_2 n \binom{|V_k|-1}{r-1}\right)}/{\binom{|V_k|}{r}} \notag \\ & = \rho(G[V_{k}]) - \varepsilon_2 n \cdot \frac{r}{|V_k|} \ge \rho(G[V_{k}]) - \frac{r \varepsilon_2}{\beta/2}, \end{align} $$

which is at least $\lambda -\frac {\eta }{2}$ by (B), the induced subgraph of H on $f(V_{k}') \subseteq U\setminus U_{j_0}$ has edge density at least $\lambda -\eta /2$ . Since n is large and $R_{j} = \emptyset $ , we have $\lambda _{P_j - j_0} \ge \rho (H[f(V_{k}')])-\eta /4 \ge \lambda -3\eta /4> \lambda -\eta _j$ , contradicting our definition of $\eta _j$ (that is, the minimality of $P_j$ ). Therefore, we have that $|f(V_k)\cap U_{s}|\ge \varepsilon _2 n$ for all $s\in [m_j]$ .

For every $s\in [m_j]$ , let . Pick some $k'\in [m_i]\setminus \{k\}$ and a vertex $u\in V_{k'}$ ; note that $V_{k'}\not =\emptyset $ by (A). Since $|W_s|\ge \varepsilon _2 n\ge r$ for all $s\in [m_j]$ and the $E_j$ -link of every element of $[m_j]$ is nonempty by (2.3), there exists an edge $D\in H$ containing $f(u)$ such that $D\setminus \{f(u)\}$ is contained in $\bigcup _{s\in [m_j]}W_s$ . Let X denote the profile of D and $X'$ be the profile of $D\setminus \{f(u)\}$ , both with respect to $U_{1}\cup \cdots \cup U_{m_j}$ . Since H is a $P_{I}$ -mixing construction, all r-subsets of $V(H)$ with profile X are contained in H. Let $\mathcal {D}$ be the collection of all r-subsets $D'\ni f(u)$ such that the profile of $D'\setminus f(u)$ with respect to $W_1,\ldots ,W_{m_j}$ is $X'$ . No element of the set $f^{-1}(\mathcal {D})$ is contained in G because every member in $f^{-1}(\mathcal {D})$ has profile $\{\hspace {-0.25em}\{\hspace {0.1em}k^{r-1},k'\hspace {0.1em}\}\hspace {-0.25em}\}$ which cannot belong to $E_i$ by Lemma 2.3. However, if we add $f^{-1}(\mathcal {D})$ into the edge set of G, the new r-graph $G'$ is still embedded into H by the same function f. In other words, $G'$ is a $P_{I}$ -mixing subconstruction. However, the degree of u in $G'$ satisfies

$$ \begin{align*} d_{G'}(u) \ge d_{G}(u)+ |f^{-1}(\mathcal{D})| & \ge (\lambda-\varepsilon_0)\binom{n-1}{r-1}+\prod_{s\in [m_j]}\frac{(\varepsilon_2 n)^{{X'(s)}}}{X'(s)!} \notag\\ & \ge (\lambda-\varepsilon_0)\binom{n-1}{r-1} + \frac{\varepsilon_2^{r-1}n^{r-1}}{(r-1)!}> (\lambda+\varepsilon_1)\binom{n-1}{r-1}, \notag \end{align*} $$

which contradicts (C) above. This proves that $R_j \neq \emptyset $ .

Suppose to the contrary that we cannot satisfy the first part of the claim for some $k \in R_i$ ; that is, for each $\ell \in R_j$ we have $|f(V_{k})\cap U_{\ell }|<\varepsilon _2 n$ . Since $|f(V_{k})\cap U_{\ell }|<\varepsilon _2 n$ for all $\ell \in R_j$ , there exists a subset $V_k' \subseteq V_k$ of size at least $|V_k| - \varepsilon _2 n |R_j|$ such that ; that is, the induced subgraph $G[V_{k}']$ is embedded into $H[U_{[m_j]\setminus R_j}]$ . Since $|V_{k}| \ge \beta n/2 \gg \varepsilon _2 n |R_j|$ and $\rho (G[V_{k}]) \ge \lambda - \varepsilon _1$ , we have

$$ \begin{align*} \rho(G[V_k']) = \frac{|G[V_{k}']|}{\binom{|V_{k}'|}{r}} \ge \frac{|G[V_{k}]| - \varepsilon_2 n |R_j| \binom{|V_k|-1}{r-1}}{\binom{|V_k|}{r}} & = \rho(G[V_{k}]) - \varepsilon_2 n |R_j| \cdot \frac{r}{|V_{k}|} \\ &> \lambda - \varepsilon_1 - \frac{r\, |R_j| \varepsilon_2}{\beta/2} > \lambda - \frac{\eta}{2}. \end{align*} $$

This means that there are arbitrarily large $(P_j-R_j)$ -constructions of edge density at least $\lambda - \eta /2$ , that is, $\lambda _{P_j-R_j}\ge \lambda - \eta /2> \lambda - \eta $ . This contradicts the minimality of $P_j$ since $R_j\not =\emptyset $ .

Let us restrict ourselves to those h with $h(R_i)\subseteq R_j$ . Suppose that we cannot fulfill the second part of the claim. Then there is $s \in [m_j]$ such that $|f(V_{k})\cap U_{s}|\ge \varepsilon _2 n$ for every $k \in [m_i]$ . Since $E_i \neq \emptyset $ , the induced subgraph $G[f^{-1}(U_{s})]$ is nonempty (it has at least $\varepsilon _2 n$ vertices from each bottom part of G) and is mapped entirely into $U_{s}$ . Thus, $s\in R_j$ . Since $f(V(G))$ intersects at least two different bottom parts of H, we can pick some $v\in V_{t}$ for some $t\in [m_i]$ such that $f(v)\in U_{s'}$ and $s' \in [m_j]\setminus \{s\}$ . Fix some $(r-1)$ -multiset X in $L_{E_i}(t)$ ; note that $L_{E_i}(t)\neq \emptyset $ by (2.3) – that is, by the minimality of $P_i$ . Take an edge $D\in G$ containing v so that $D\setminus \{v\}$ is a subset of $f^{-1}(U_{s})$ and has profile X; it exists because each bottom part of G contains at least $\varepsilon _2 n\ge r$ vertices of $f^{-1}(U_{s})$ . The r-set $f(D)$ is an edge of H as f is an embedding. However, it has $r-1$ vertices in $U_{s}$ and one vertex in $U_{s'}$ . Thus, the r-multiset $\{\hspace {-0.25em}\{\hspace {0.1em}{s}^{(r-1)},s'\hspace {0.1em}\}\hspace {-0.25em}\}$ belongs to $E_j$ . Since $s\in R_j$ , this contradicts Lemma 2.3. The claim is proved.

Claim 3.13.2. Each h satisfying Claim 3.13.1 is a bijection. Moreover, $j=i$ and h is an automorphism of $P_i$ .

Proof of Claim. Fix a map h that satisfies Claim 3.13.1. First, we prove that h is injective. For every $s\in [m_j]$ , let . Note that $U_s'=\emptyset $ for s not in the image of h. Let $H'$ be the $P_{I}$ -mixing construction on $f(V(G))$ such that $U_1'\cup \dots \cup U_{m_j}'$ is the bottom partition of $H'$ with base $P_j$ (thus, $E_j(\!(U_1',\dots ,U_{m_j}')\!) \subseteq H'$ ), and, for each $s\in R_j$ , $H'[U_s']$ is the image of the $P_{I}$ -mixing construction $G[f^{-1}(U_s')]$ under the bijection f.

We have just defined a new $P_{I}$ -mixing construction $H'$ so that each part $V_s$ of G is entirely mapped by f into the $h(s)$ -th part of $H'$ ; that is,

(3.8) $$ \begin{align} f(V_s)\subseteq U_{h(s)}',\quad\text{for every }s\in [m_i]. \end{align} $$

This $H'$ will be used only for proving Claim 3.13.2.

Let us show first that the same map f is an embedding of G into $H'$ . Take any edge $D\in G$ . First, suppose that $f(D)$ intersects at least two different parts $U_t'$ . By (3.8), D has to be a bottom edge of G. Let $D'\in G$ have the same profile as D with respect to $V_1,\ldots ,V_{m_i}$ and satisfy

(3.9) $$ \begin{align} D'\subseteq \bigcup_{s\in[m_i]} \left( V_s\cap f^{-1}(U_{h(s)}) \right), \end{align} $$

which is possible because there are at least $\varepsilon _2 n$ vertices available in each part $V_s\cap f^{-1}(U_{h(s)})$ . Since $f(D')\cap U_t= f(D')\cap U_t'$ for all $t\in [m_j]$ , the bottom edge $f(D')$ of H has the same profile X with respect to the partitions $U_1\cup \dots \cup U_{m_j}$ and $U_1'\cup \dots \cup U_{m_j}'$ . Thus $X\in E_j$ . Next, as each $f(V_s)$ lies entirely inside $U_{h(s)}'$ , the sets $f(D)$ and $f(D')$ have the same profiles with respect to the partition $U_1'\cup \dots \cup U_{m_j}'$ . Thus $f(D)$ is an edge of $E_j(\!(U_1',\dots ,U_{m_j}')\!)$ , as required. It remains to consider the case that $f(D)$ lies inside some part $U_t'$ . Let . Assume that $t\in [m_j]\setminus R_j$ , for otherwise, $f(D)\in f(G')$ , which is a subset of $H'$ by the definition of $H'$ . We claim that $G'$ has no edges in this case (obtaining a contradiction to $D\in G'$ ). Since $h(R_i)\subseteq R_j$ , we have $h^{-1}(t)\cap R_i=\emptyset $ and D must be a bottom edge of G. As before, we can find an edge $D'\in G$ that satisfies (3.9) and has the same profile as D with respect to $V_1,\dots ,V_{m_i}$ . However, f maps this $D'$ inside a non-recursive part $U_t$ of H, a contradiction. Thus, f is an embedding of G into $H'$ .

Thus, by considering $H'$ instead of H (and without changing h), we have that $f(V_s)\subseteq U_{h(s)}'$ for all $s\in [m_i]$ .

Suppose on the contrary to the claim that $|h^{-1}(s)|\ge 2$ for some $s\in [m_j]$ . Let and . Since h assumes at least two different values, the set B is nonempty.

Trivially, the set $U_s'$ is externally $H'$ -homogeneous. We claim that $f^{-1}(U_s')=V_A$ is externally G-homogeneous (recall that we denote ). Indeed, suppose that $V_A$ is not externally G-homogeneous. Then there is $D\in G$ that intersects both $V_A$ and its complement such that for some bijection $\sigma $ of $V(G)$ that moves only points of $V_A$ the r-set is not in G. The profile of $D'$ with respect to $V_1,\dots ,V_{m_i}$ contains at least two different elements of $[m_i]$ , one in A and another in $[m_i]\setminus A$ . Let ${ \cal D}'$ consist of all r-sets that have the same profile with respect to $V_1,\dots ,V_{m_i}$ as $D'$ . Since each bottom part $V_k$ has at least $\beta n/2$ vertices, it holds that $|{ \cal D}'|\ge (\beta n/2)^r/r!$ . Since $D'\not \in G$ , no r-set in ${ \cal D}'$ is an edge of G. With respect to $U_1',\dots ,U_{m_j}'$ , all r-sets in $f({ \cal D}')$ have by (3.8) the same profile as $f(D')$ , which in turn is the same as the profile as that of $f(D)$ (because the bijection $f\circ \sigma \circ f^{-1}$ of $V(H')$ moves only elements inside $f(V_A)\subseteq U_s'$ ). Since $f(D)\in H'$ , we must have $f({ \cal D}')\subseteq H'$ . Thus, we can add ${ \cal D}'$ to G, keeping it a $P_I$ -mixing subconstruction. However, the new r-graph has edge density at least $\lambda -\varepsilon _0+(\beta /2)^r$ , which is a contradiction to (C) since $\beta \gg \varepsilon _{1} \gg \varepsilon _0\gg 1/n$ .

Thus, $V_A$ is externally G-homogeneous. It follows that A is externally $E_i$ -homogeneous (since each $V_t$ has at least $\beta n/2\ge r$ elements).

Next, let us show that $A\cap R_i = \emptyset $ . Suppose that this is false. Then fix $i_{\ast } \in A\cap R_i$ . Let $\hat {G}$ be the r-graph obtained from G by replacing $G[V_A]$ with a maximum $P_I$ -mixing construction. By Fact 3.12, the r-graph $\hat {G}$ remains a $P_I$ -mixing construction, with A playing the role of $i_{\ast }$ . This implies that $\rho (G[V_A]) \ge \lambda -3\varepsilon _0/\beta ^r$ , for otherwise, we would have

$$ \begin{align*} |\hat{G}| = |G| - |G[V_{A}]| + |\hat{G}[V_{A}]| & \ge (\lambda - \varepsilon_{0}) \binom{n}{r} - \left(\lambda- \frac{3\varepsilon_0}{\beta^r}\right) \binom{|V_{A}|}{r} + (\lambda+o(1)) \binom{|V_{A}|}{r} \\ & \ge (\lambda - \varepsilon_{0}) \binom{n}{r} + \frac{2\varepsilon_0}{\beta^r} \binom{|V_{A}|}{r} \\ & \ge (\lambda - \varepsilon_{0}) \binom{n}{r} + 2\varepsilon_0 \binom{|V_{A}|/\beta}{r} \ge (\lambda - \varepsilon_{0}) \binom{n}{r} + 2\varepsilon_0 \binom{n}{r}, \end{align*} $$

a contradiction to (3.3). Here, the last inequality follows from (A) and the assumption that $|A| \ge 2$ .

Recall that $B=[m_j]\setminus A$ . Consider the pattern obtained from $P_i$ by removing B. Let and . Without loss of generality, we may assume that $A = [a]$ for some $a\in [m_i-1]$ . Let , where for $k\in [a]$ . Then it follows from $\rho (G[V_A]) \ge \lambda -3\varepsilon _0/\beta ^r$ that the obtained vector $\mathbf {x}\in \mathbb {S}_{a}$ satisfies that

(3.10) $$ \begin{align} \lambda_{E'}(\mathbf{x}) + \lambda \sum_{k\in R'}x_{k}^r = \rho(G[V_A]) + o(1) \ge \lambda - 4\varepsilon_0/\beta^r. \end{align} $$

This inequality does not contradict the minimality of $P_i$ yet, since $G[V_A]$ is not necessarily a Q-construction (for $k\in R'$ , the $P_I$ -mixing construction $G[V_k]$ can use parts indexed by B). However, if we replace $G[V_k]$ by a maximum Q-construction for every $k\in R'$ , then the resulting r-graph has edge density $\lambda _{E'}(\mathbf {x}) + \lambda _{Q} \sum _{k\in R'}x_{k}^r + o(1)$ . By the definition of Lagrangian, we have

(3.11) $$ \begin{align} \lambda_{Q} \ge \lambda_{E'}(\mathbf{x}) + \lambda_{Q} \sum_{k\in R'}x_{k}^r. \end{align} $$

By $|A|\ge 2$ and (A), we have that $x_k\le 1 - \beta /2$ for every $k\in [a]$ . So it follows from $\sum _{k=1}^{a}x_k = 1$ that, say, $\sum _{k=1}^{a}x_k^r \le 1 - \varepsilon _2$ . In particular, $\sum _{k\in R'}x_{k}^r \le 1 - \varepsilon _2$ . Therefore, by (3.10) and (3.11), we obtain

$$ \begin{align*} \lambda_Q\left(1-\sum_{k\in R'}x_{k}^r\right) \ge \lambda_{E'}(\mathbf{x}) \ge \lambda \left(1-\sum_{k\in R'}x_{k}^r\right) - 4\varepsilon_0/\beta^r, \notag \end{align*} $$

which implies that $\lambda _{Q} \ge \lambda -\eta /2$ , contradicting the minimality of $P_i$ . Therefore, $A\cap R_i= \emptyset $ .

Since $|A| \ge 2$ , we can choose $t_1, t_2 \in A$ such that $t_1 \neq t_2$ . Since A is externally $E_i$ -homogeneous and, by Lemma 2.2, we have $L_{E_i}(t_1) \not = L_{E_i}(t_2)$ , there exists a multiset in $E_i$ that is completely contained inside A.

So, $G[V_A] \neq \emptyset $ . Since $U_s' = f(V_A)$ , we have $H'[U_s'] \neq \emptyset $ , and hence, $s\in R_j$ . Notice that $H'$ is a $P_{I}$ -mixing construction on n vertices with $\delta (H') \ge \delta (f(G))\ge (\lambda -\varepsilon _0)\binom {n-1}{r-1}$ . So, similarly to (B), we have $\rho (H'[U_k']) \ge \lambda - \varepsilon _1$ for all $k\in R_j$ . In particular, we have $\rho (H'[U_s']) \ge \lambda - \varepsilon _1$ . Therefore, $|H'\setminus H'[U_s']| \le (\lambda +\varepsilon _1)\binom {n}{r} - (\lambda - \varepsilon _1)\binom {|U_s'|}{r}$ , which implies that

$$ \begin{align*} |G\setminus G[V_A]| \le |H'\setminus H'[U_s']| \le (\lambda+\varepsilon_1)\binom{n}{r} - (\lambda - \varepsilon_1)\binom{|U_s'|}{r}. \end{align*} $$

Note that $|U_s'|=|V_A|$ since f gives a bijection between these two sets. Therefore,

$$ \begin{align*} |G[V_A]| = |G| - |G\setminus G[V_A]| & \ge (\lambda-\varepsilon_0)\binom{n}{r}-\left((\lambda+\varepsilon_1)\binom{n}{r} - (\lambda - \varepsilon_1)\binom{|V_A|}{r}\right) \notag\\ & \ge \lambda \binom{|V_A|}{r} - 3\varepsilon_1 \binom{n}{r}. \notag \end{align*} $$

Thus,

$$ \begin{align*} \rho(G[V_A]) = \frac{|G[V_{A}]|}{\binom{|V_{A}|}{r}} \ge \frac{\lambda \binom{|V_A|}{r} - 3\varepsilon_1 \binom{n}{r}}{\binom{|V_A|}{r}} \ge \lambda - \frac{3\varepsilon_1 \binom{n}{r}}{\binom{\beta n}{r}} = \lambda - \frac{3\varepsilon_1}{\beta^r + o(1)} \ge \lambda - \frac{\eta}{2}. \end{align*} $$

This implies that $\lambda _{P_i-B}\ge \rho (G[V_A]) \ge \lambda - \eta /2> \lambda -\eta $ , which contradicts the minimality of $P_i$ . Therefore, h is injective.

Since each multiset in $E_i$ corresponds to a nonempty set of edges of G by (A) and f is an embedding, we have $h(E_i)\subseteq E_j$ .

Suppose to the contrary that h is not surjective; that is, $m_j \ge m_i + 1$ . Let $\mathbf {x} = (x_1, \ldots , x_{m_i}) \in { \cal X}_i$ be a $P_i$ -optimal vector. Let , where $x_{\emptyset }$ means 0. Thus, $\mathbf {y}$ is defined by rearranging the entries of $\mathbf {x}$ according to h and padding them with $m_j-m_i$ zeros. By $ h(R_i) \subseteq R_j$ and $h(E_i) \subseteq E_j$ , we have

$$ \begin{align*}\lambda_{E_j}(\mathbf{y}) + \lambda \sum_{k\in R_j}y_k^{r} \ge \lambda_{E_i}(\mathbf{x}) + \lambda \sum_{k\in R_i}x_k^r = \lambda.\end{align*} $$

However, by Lemma 2.4(b), we have $\lambda _{E_j}(\mathbf {y}) + \lambda \sum _{k\in R_j}y_k^{r} \le \lambda $ . Therefore, $\lambda _{E_j}(\mathbf {y}) + \lambda \sum _{k\in R_j}y_k^{r} = \lambda $ , which implies that $\mathbf {y} \in { \cal X}_j$ is a $P_j$ -optimal vector. However, $\mathbf {y}$ has at least one entry 0, which contradicts Lemma 2.4(c). Therefore, h is surjective, and hence is bijective.

None of the inclusions $h(E_i)\subseteq E_j$ and $h(R_i)\subseteq R_j$ can be strict as otherwise, since every $P_j$ -optimal vector has all coordinates positive by the minimality of $P_j$ , we would have $\lambda _{P_j}>\lambda _{P_i}=\lambda $ , a contradiction. Thus, h gives an isomorphism between $P_i$ and $P_j$ , and we conclude that $j=i$ . This finishes the proof of the claim.

By relabelling the parts of H, we can assume for notational convenience that h is the identity mapping. Now we are ready to prove the lemma – namely, that $f(V_s)\subseteq U_s$ for every $s\in [m_i]$ .

Suppose on the contrary that $f(v)\in U_t$ for some $v\in V_s$ and $t\in [m_i]\setminus \{s\}$ . It follows that $L_{E_i}(s) \subseteq L_{E_i}(t)$ . By Lemma 2.2, this inclusion is strict and $s\in R_i$ . Pick some X from $L_{E_i}(t)\setminus L_{E_i}(s) \neq \emptyset $ . For every $D\in H$ containing $f(v)$ such that $D\setminus \{f(v)\}$ has the profile X with respect to both $U_1\cup \dots \cup U_{m_i}$ and $f(V_1)\cup \dots \cup f(V_{m_i})$ , we add $f^{-1}(D)$ into G. Denote by $\tilde {G}$ the new r-graph. Observe that f is also an embedding of $\tilde {G}$ into H. Thus, $\tilde {G}$ is a $P_I$ -mixing subconstruction. Notice that since $|f(V_j)\cap U_j| \ge \varepsilon _2 n$ , there are at least $\prod _{j\in [m_i]}(\varepsilon _2 n)^{X(j)}/X(j)! \ge \varepsilon _2^{r-1} n^{r-1}/(r-1)!$ such edges D. Since all edges in $f^{-1}(D)$ contain v, we have $d_{\tilde {G}}(v) \ge d_{G}(v) + \varepsilon _2^{r-1} n^{r-1}/(r-1)!> (\lambda +\varepsilon _1)\binom {n-1}{r-1}$ contradicting (C) above. This shows that G is rigid.