3·1. Setup

To begin, we recall an important function used in this construction. For a nonnegative integer x, let $x = \sum_{i=0}^{\infty} a_i 2^i$ be its unique binary representation (where $a_i = 0$ for all but finitely many i). We denote $\mathrm{bit}(x, i) = a_i.$ Then $\delta(x, y) := \max \{ i \in \mathbb{Z}_{\ge 0} \, \vert \, \mathrm{bit}(x, i) \neq \mathrm{bit}(y, i)\}.$ For nonnegative integers $x_1 \lt x_2 \lt \ldots \lt x_t,$ we denote $\delta(\{x_1, \ldots, x_t\}) = (\delta_1, \ldots, \delta_{t-1})$ where for $i \in [t-1],$ $\delta_i = \delta(x_i, x_{i+1}).$ The following properties of this function are well known and easy to verify.

1. (P1) $x \lt y \iff \mathrm{bit}(x, \delta(x, y)) \lt \mathrm{bit}(y, \delta(x, y))$ .

2. (P2) For any $x \lt y \lt z,$ $\delta(x, y) \neq \delta(y, z)$ .

3. (P3) For any $x_1 \lt x_2 \lt \ldots \lt x_k,$ $\delta(x_1, x_k) = \max_{1 \le i \le k-1} \delta(x_i, x_{i+1})$ .

Let us now define the colouring which will be used to prove Theorem 1·3. For a positive integer n, we start with a red-blue colouring $\phi_n^{(2)}$ of the complete graph with vertex set $\{0, \ldots, N_2-1\}$ , where $N_2 = N_2(n) = 2^{n/2}$ , containing no monochromatic clique of size n. Such a colouring exists by the well known result of Erdős mentioned in the introduction. For $k \ge 3,$ the colouring $\phi_n^{(k)}$ is on the vertex set $\{0, \ldots, N_k - 1\},$ where $N_k = N_k(n) = 2^{N_{k-1}(n)} = \mathrm{tw}_k(n/2)$ and is defined as follows. For a set $\{x_1, \ldots, x_k\}$ with $0 \le x_1 \lt \ldots \lt x_k \lt N_k,$ we consider the vector $\delta(\{x_1, \ldots, x_k\}) = (\delta_1, \ldots, \delta_{k-1}).$ Note that $0 \le \delta_i \lt N_{k-1}$ for all $i \in [k-1]$ . Hence for distinct $\delta_i$ , the set $\{\delta_1, \ldots, \delta_{k-1}\}$ forms an edge of the complete $(k-1)$ -uniform hypegraph on $\{0, \ldots, N_{k-1}-1\}$ with colour $\phi^{(k-1)}_n(\{\delta_1, \ldots, \delta_{k-1}\})$ . For $k = 3,$ the 4-colouring is given as:

\begin{align*} \phi^{(3)}_n(\{x_1, x_2, x_3\}) = \begin{cases} C_1, &\text{if } \delta_1 \lt \delta_2 \text{ and } \phi_n^{(2)}(\{\delta_1, \delta_2\}) \text{ is red;}\\ C_2, &\text{if } \delta_1 \lt \delta_2 \text{ and } \phi_n^{(2)}(\{\delta_1, \delta_2\}) \text{ is blue;}\\ C_3, &\text{if } \delta_1 \gt \delta_2 \text{ and } \phi_n^{(2)}(\{\delta_1, \delta_2\}) \text{ is red;}\\ C_4, &\text{if } \delta_1 \gt \delta_2 \text{ and } \phi_n^{(2)}(\{\delta_1, \delta_2\}) \text{ is blue.} \end{cases}\end{align*}

We denote by $\mathrm{arg\,max}_{i \in [k-1]} \delta_i$ the unique index $j \in [k-1]$ such that $\delta_j = \max_{i \in [k-1]} \delta_i$ , where the uniqueness follows from Properties (P2) and (P3). For $k \ge 4,$ the colouring is given as:

\begin{align*} \phi^{(k)}_n(\{x_1, \ldots, x_k\}) =\begin{cases} \phi^{(k-1)}_n(\{\delta_1, \ldots, \delta_{k-1}\}), &\text{if } \delta \text{ is a monotone sequence;}\\ C_1, &\text{if } \delta \text{ is not monotone and } \mathrm{arg\,max}_{i \in [k-1]}\\ & \qquad\qquad \delta_i \in \{1, k-1\}; \\ C_2, &\text{if } \mathrm{arg\,max}_{i \in [k-1]} \delta_i \not\in \{1, k-1\}.\end{cases}\end{align*}

3·2. Proof outline

Let us now discuss the main ideas of our proof. First, we recall Erdős and Hajnal’s proof of the lower bound $r_k(n;\, 4) \ge \mathrm{tw}_k(2^{-k} n).$ Their proof uses a slightly different colouring than given above, but the same proof works with our colouring, so we consider it instead. Suppose that $\phi^{(k)}_n$ contains a monochromatic clique of size $n_k = 2^k n$ . Denote by $x_1 \lt x_2 \lt \ldots \lt x_{n_k}$ the vertices of this clique and let $\delta = (\delta_1, \ldots, \delta_{n_k-1}) = \delta(\{x_1, \ldots, x_{n_k}\}).$ It is not difficult to show that $\delta$ must contain a monotone contiguous subsequence $\delta' = (\delta_a, \delta_{a+1}, \ldots, \delta_b)$ of length at least $n_k/2.$ By Property (P3) and the definition of $\phi^{(k)}_n,$ it follows that $\{\delta_a, \delta_{a+1}, \ldots \delta_b\}$ forms a monochromatic clique in $\phi^{(k-1)}_n$ of size at least $n_k/2.$ Applying the same argument to this clique in $\phi^{(k-1)}_n$ , we find a monochromatic clique of size at least $n_k / 4$ in $\phi^{(k-2)}_n$ and so on. After $k-2$ steps, we thus reach a monochromatic clique of size 4n in $\phi^{(2)}_n,$ a contradiction.

We will show that instead of a clique, we can take a much sparser hypergraph $H_k$ on $n_k = \alpha_k n$ vertices with $m = O(n_k^2) = O_k(n^2)$ edges and reach a similar conclusion, i.e. that $\phi^{(k-1)}_n$ contains a monochromatic copy of some $(k-1)$ -uniform hypergraph $H_{k-1}$ on $\alpha_{k-1} n$ vertices, where $H_{k-1}$ is “of the same form” as $H_k.$ For the argument to work, we need to make sure of a few a things. With $x_1 \lt x_2 \lt \ldots \lt x_{n_k}$ and $\delta = (\delta_1, \ldots, \delta_{n_{k-1}})$ defined as above, we need that $\delta$ contains a monotone subsequence of length $\Omega(n_k).$ Furthermore, this monotone subsequence should imply the existence of a hypergraph $H_{k-1}$ on $\alpha_{k-1}n$ vertices on which we can apply induction. We remark here that $H_{k-1}$ will not be a fixed hypergraph, but rather some large enough hypergraph of the same form as $H_k$ . Finally, after $k-2$ steps, we should reach a graph containing a clique of size n to obtain a contradiction. Given that this argument works for a clique and we want a much sparser hypergraph, it should be no surprise that our construction is based on an expander graph. We next define our construction formally and carry out the outlined proof strategy.

3·3. Formal proof

Given a graph G and an integer $k \ge 2,$ we define a k-uniform hypergraph $H = H(G, k)$ on the same vertex set where for every path $(v_1, \ldots, v_{k-1})$ in G and any vertex $v_k \in V(G)$ not on this path, we put the k-edge $\{v_1, \ldots, v_k\}$ in H. Note that for $k=2,$ H(G, k) is simply the complete graph on the vertex set $V(G).$

Given a k-uniform hypergraph $\Gamma$ with a colouring $\phi \colon E(\Gamma) \rightarrow \mathcal{C}$ and a hypergraph H, a set of vertices $X \subseteq V(\Gamma)$ forms a monochromatic copy of H if there exists a bijection $\Psi \colon V(H) \rightarrow X$ such that $\phi(\Psi(e)) = \phi(\Psi(e'))$ for all $e, e' \in E(H).$

We shall need the following simple lemma about sparse random graphs.

Proof. Let $H \sim G(M, d/M),$ that is, H is a random graph on M vertices where every possible edge is present with probability $d/M$ independently. Let G be the graph obtained from H by removing all edges incident to vertices of degree greater than 2d. Thus, G satisfies b) deterministically. The expected number of edges removed from H to obtain G is at most

\begin{align*} \sum_{\{u,v\}\subseteq V(H)} &\mathbb{P}[uv \in E(H)] \cdot \mathbb{P}[\max\{d_H(u), d_H(v)\} \gt 2d \, \vert \, uv \in E(H)]\\ &\le \binom{M}{2} \frac{d}{M} \cdot 2 \mathbb{P}[\mathrm{Bin}(M-2, d/M) \ge 2d] \le 2Md e^{-d/3} \lt M, \end{align*}

where we used a standard Chernoff bound (e.g. [ Reference Janson and Rucinski18 , corollary 2·3]) and that $d \ge 10^9.$ By Markov’s inequality, with probability at least $3/4,$ we have $e(H) - e(G) \le 4M.$ For fixed disjoint sets of vertices S and T of size at least ${M}/{d^{1/3}}$ using the same form of the Chernoff bound, we have

\begin{align*} \mathbb{P}\left[ \big|e_H(S, T) - \frac{d}{M}|S||T|\big| \gt \frac{1}{4} \frac{d}{M} |S||T| \right] \le 2e^{-\frac{d}{M} |S||T| / 48} \le 2e^{-Md^{1/3} / 48} \lt 2e^{-20M}. \end{align*}

Taking a union bound over all sets S, T as above, with probability at least $1 - 2^M \cdot 2^M \cdot 2e^{-20M} \gt 3/4$ , we have

(2) \begin{equation} \big|e_H(S, T) - \frac{d}{M}|S||T|\big| \le \frac{1}{4} \frac{d}{M} |S||T|, \, \forall S, T \subseteq V(H), S \cap T = \emptyset, |S|, |T| \ge \frac{M}{d^{1/3}}. \end{equation}

By a union bound, with probability at least $1/2$ we have $e(H) - e(G) \leq 4M$ and (2). Noting that $4M \le ({1}/{4}) ({d}/{M}) \left({M}/{d^{1/3}} \right)^2,$ it follows that G satisfies (a) with probability at least $1/2,$ finishing the proof.

Proof of Theorem 1·3. Fix $k \ge 3,$ let n be a large enough integer, set $d = 10^{20k}$ and let G be a graph on $n_k = dn$ vertices satisfying (a) and (b) for d whose existence is given by Lemma 3·1. Let $H_k = H(G, k).$ We will show that there is no monochromatic copy of $H_k$ in $\phi^{(k)}_n,$ where we remind the reader that $\phi^{(k)}_n$ is a colouring of the complete k-graph with vertex set $\{0, \ldots, N_k(n)-1\},$ where $N_k(n) = \mathrm{tw}_k(n/2)$ . This would prove the theorem since, by construction, $e(H_k) \le n_k \cdot \#\{\text{paths of length } k-2 \text{ in } G\} \le n_k^2 (2d)^{k-2} = O(n^2)$ , while $r_k(H_k;\, 4) \gt N_k(n) = \mathrm{tw}_k(n/2) = \mathrm{tw}_k(\Omega(\sqrt{e(H)})).$ We make repeated use of the following lemma.

First, let us finish the proof of Theorem 1·3 given Lemma 3·2. By repeated uses of the lemma, it follows that there are subsets $V(G) = U_k \supseteq U_{k-1} \supseteq \ldots \supseteq U_2$ such that there is a monochromatic copy of $H(G[U_\ell], \ell)$ in $\phi^{(\ell)}_n$ for all $2 \le \ell \le k$ and $|U_\ell| \ge |U_{\ell+1}| / 1000$ for all $2 \le \ell \le k-1.$ Hence, we have $|U_2| \ge n_k / 1000^k = 10^{20k} n / 1000^k \gt n$ and a monochromatic copy of $H(G[U_2], 2)$ in $\phi^{(2)}_n.$ Recall that by definition, $H(G[U_2], 2)$ is a clique on $|U_2| \gt n$ vertices, hence there is no monochromatic copy of $H(G[U_2], 2)$ in $\phi^{(2)}_n,$ a contradiction.

Proof of Lemma 3·2. Let $s = |U| = |V(H)|,$ let $X = \{x_1, \ldots, x_s\} \subseteq \{0, \ldots, N_\ell - 1\},$ where $x_1 \lt \ldots \lt x_s$ , form a mononchromatic copy of H and denote by $\Psi \colon V(H) \rightarrow \{ 0, \ldots, N_\ell-1 \}$ the given monochromatic embedding.

First we finish the proof of the lemma given Claim 3·3. Let $Y \subseteq X$ with $|Y| = t \ge s / 200$ be given by Claim 3·3 and assume that $\delta(Y)$ is increasing, the other case being analogous. We denote $L = \{\Psi^{-1}(y_1), \ldots, \Psi^{-1}(y_{t/2})\} \subseteq U$ and let $U' \subseteq U$ be the set of all vertices $\Psi^{-1}(y_j)$ with $t/2 \lt j \le t$ which in G have at least one neighbour in L. We have that $|U'| \ge t / 4,$ as otherwise there is a set of $t/4$ vertices with no edges toward L, contradicting (a) since

\begin{align*} |L| \ge t/4 \ge s / 800 \ge n_k / (1000^k) \gt n_k / (10^{20k / 3}) = n_k/d^{1/3}. \end{align*}

Let us verify that $\phi_n^{(\ell-1)}$ contains a monochromatic copy of $H' = H(G[U'], \ell-1).$ Let $z_1, z_2, \ldots, z_{t'}$ be the elements of $\Psi(U')$ in increasing order and recall that $y_i \lt z_j$ for all $i \in [t/2], j \in [t'].$ Denote $a_1 = \delta(y_1, z_1)$ and $a_i = \delta(z_{i-1}, z_i)$ for $2 \le i \le t'.$ We will show that the set $\mathcal{A} = \{a_1, \ldots, a_{t'}\}$ forms a monochromatic copy of H’ in $\phi^{(\ell-1)}_n$ with the natural correspondence $\Psi' \colon U' \rightarrow \mathcal{A}$ defined by $\Psi'(\Psi^{-1}(z_i)) = a_i$ for all $i \in [t']$ . We do so by showing that, for an edge $e \in E(H'),$ the colour $\phi^{(\ell-1)}_n(\Psi'(e))$ is inherited from the colour of $\phi_n^{(\ell)}(\Psi(f))$ of some edge $f \in E(H).$

By monotonicity of $\delta(\{y_1, \ldots, y_t\}),$ using (P3), we have $\delta(z_i, z_j) = a_j$ for any $1 \le i \lt j \le t'$ and $\delta(y_i, z_j) = a_j$ for any $i \in [t/2]$ and $j \in [t'].$ Now, consider an arbitrary edge $e = \{\Psi^{-1}(z_{j_1}), \ldots, \Psi^{-1}(z_{j_{\ell-1}})\} \in E(H'),$ where $j_1 \lt j_2 \lt \ldots \lt j_{\ell-1}.$ By construction, some $\ell-2$ of these vertices form a path P’ in G. By definition of U’, any vertex on this path, in particular one of its endpoints, has a neighbour L. So, we can attach a vertex $w \in L$ to one of the endpoints of P’ to obtain a path on $\ell-1$ vertices in G. Hence, $f = e \cup \{w\}$ is a set of $\ell$ vertices, some $\ell-1$ of which form a path in G, implying that f is an edge of H. Note that $\delta(\Psi(f)) = (a_{j_1}, a_{j_2}, \ldots, a_{j_{\ell-1}}),$ which is an increasing sequence. If $\ell \ge 4,$ we have $\phi^{(\ell)}_n(\Psi(f)) = \phi^{(\ell-1)}_n(\delta(\Psi(f))) = \phi^{(\ell-1)}_n(\Psi'(e)).$ In the case $\ell = 3,$ if $\phi^{(2)}_n(\Psi'(e)) = \mathrm{red},$ then $\phi^{(\ell)}_n = C_1$ , and if $\phi^{(2)}_n(\Psi'(e)) = \mathrm{blue}$ , then $\phi^{(\ell)}_n = C_2$ . In either case, it follows that $\mathcal{A}$ forms a monochromatic copy of H’ in $\phi_n^{(\ell-1)},$ as needed.

Proof of Claim 3·3. Consider the following procedure. Start with $Z = X.$ At each step, let q be the largest integer such that not all elements of Z have the same bit at position q. Consider the partition $Z = Z_0\, {\cdot\!\!\cup} Z_1,$ where $Z_p$ denotes the set of elements $z \in Z$ with $\mathrm{bit}(z, q) = p.$ Then, let Z be the larger of $Z_0, Z_1$ and continue the procedure. Eventually we reach a point where $s/4 \le |Z| \le s/2,$ where the lower bound follows since $|Z|$ drops by a factor of at most 2 in each step. Let $Z^*$ denote the final set Z and let $q^*$ be the last value of q before this point. Then, for all distinct $u, v \in Z^*, w \in X \setminus Z^*,$ we have $\delta(u, v) \lt q^* \le \delta(u, w).$ Also, note that the elements of $Z^*$ form an interval in the ordered set X. Indeed, at each step all elements in $Z_0$ are smaller than all elements of $Z_1,$ since all elements in Z have the same bit on all positions larger than q. Hence, if Z was an interval in the ordered set X before step i, it is also an interval after step i. We shall assume that at least $s/4$ vertices in $X \setminus Z^*$ are smaller than all elements of $Z^*,$ the other case being analogous. Let W denote the set of elements in $X \setminus Z^*$ smaller than every element of $Z^*.$ Now, let $A = \Psi^{-1}(W) \subseteq U$ and let B be the set of all vertices in $\Psi^{-1}(Z^*) \subseteq U$ that have at least one neighbour of G in A. By a), it follows that

\begin{align*} |B| \ge |\Psi^{-1}(Z^*)| / 2 \ge s / 8, \end{align*}

as otherwise we obtain a set of $s/8$ vertices with no edge towards A, which is a contradiction since $|A| \ge s/8 \ge n_k / 1000^k \gt n_k / d^{1/3}.$

Now, we analyse the set $S_1 := \Psi(B)$ using a similar procedure as above in steps $i=1, \ldots, h,$ where the number of steps, h, is to be determined by the procedure. At the beginning of step i, we have a set $S_i$ of size at least $2.$ Let $q_i$ be the largest integer such that not all elements of $S_i$ have the same bit at position $q_i.$ Let $S_i = S^0_i\, {\cdot\!\!\cup} S^1_i,$ where $S^p_i$ consists of the elements $z \in S_i$ with $\mathrm{bit}(z, q_i) = p.$ Let $p_i \in \{0,1\}$ be such that $|S^{p_i}_i| \ge |S^{1-p_i}_i|.$ Let $S_{i+1} = S^{p_i}_i.$ If $|S_{i+1}| \lt s / 100,$ stop the process, otherwise continue to step $i+1.$

Assume first that the procedure runs for at least $s / 100$ steps. Then, there is a set $I, |I| \ge s / 200$ and $p \in \{0, 1\}$ such that for all $i \in I,$ we have $p_i = p$ and so $S_{i+1} = S^p_i.$ For each $i \in I,$ let $y_i$ be an arbitrary element in $S^{1-p}_i$ and let $Y = \{y_i, \vert \, i \in I\}.$ Using 3, we have $\delta(y_i, y_{i'}) = q_i$ for any $i, i' \in I, i\lt i'.$ Moreover, the sequence $(y_i)_{i\in I}$ is increasing if $p=1,$ and decreasing otherwise. Observing that $q_i \gt q_{i'}$ for $i \lt i',$ it follows that Y is the desired set.

Therefore, we may assume that the above procedure runs for $h \lt s / 100$ steps and we will show that this leads to a contradiction. First, we require the following claim.

Proof of Claim 3·4. Let $Q = \bigcup_{i \in [h], |S^{1-p_i}_i| \ge 2} \Psi^{-1}(S^{1-p_i}_i)$ and $T_0 = \Psi^{-1}(S_{h+1}),$ where $S_{h+1}$ is the final set after halting the procedure. Note that $|T_0| \ge s / 200.$ We repeatedly remove from $T_0$ vertices that have fewer than $\ell$ neighbours in G in the current set $T_0.$ Let T denote the final set after these deletions. Then, $|T| \ge s / 400 \ge n_k / (1000)^k,$ as otherwise at the point when we removed half of the vertices, we have two sets of size $q \ge s/400 \ge n / d^{1/3}$ with at most $\ell q$ edges between them, contradicting that G satisfies a). Using a) again, it follows that there is an edge vu with $v \in Q$ and $u \in T$ since $|Q| \ge |S_1| - |S_{h+1}| - h \ge s/8 - s/100 - s/100 \gt s/16 \gt n / d^{1/3}.$ Since G[T] has minimum degree at least $\ell,$ we can extend this edge to a path of length $\ell-2$ using only vertices in T. Let i be the index such that $v \in \Psi^{-1}(S^{1-p_i}_i).$ Note that $S_j^{p_j} \subseteq S_{j-1}^{p_{j-1}}$ for all $2 \le j \le h$ and $T \subseteq \Psi^{-1}(S_{h+1}) = \Psi^{-1}(S_h^{p_h}).$ It follows that $T \subseteq \Psi^{-1}(S_i^{p_i}),$ so the abovementioned path indeed has all vertices but the first in $\Psi^{-1}(S_i^{p_i}).$ By definition of Q, we also have $|S^{1-p_i}_i| \ge 2,$ as needed.

Let i, v, P be given by Claim 3·4 and let w be an arbitrary vertex in $\Psi^{-1}(S^{1-p_i}_i)$ distinct from v. We will show that then $\Psi$ is not a valid embedding, that is, we will find two edges of H whose images get different colours. Let $e = P \cup \{w\} \in E(H).$ We now find another edge $f \in E(H)$ whose image under $\Psi$ gets a different colour than e.

Consider first the case $\ell = 3.$ Then, the path P consists of a single edge vu for some $u \in \Psi^{-1}(S^{p_i}_i).$ Let u’ be an arbitrary vertex in $S^{p_i}_i$ distinct form u, which clearly exists since $|S^{p_i}_i| \ge |S^{1-p_i}_i| \ge 2,$ and let $f = \{ v,u,u' \}.$ Note that, by construction, $\delta(u, u'), \delta(v, w) \lt q_i,$ while $\delta(z, z') = q_i$ for any $(z, z') \in S_i^{p_i} \times S_i^{1-p_i}$ . It follows that if $p_i = 1,$ then $\delta(\Psi(e))$ is increasing, while $\delta(\Psi(f))$ is decreasing whereas if $p_i = 0,$ then $\delta(\Psi(e))$ is decreasing, while $\delta(\Psi(f))$ is increasing. In either case, $\Psi(e)$ and $\Psi(f)$ are coloured differently by $\phi_n^{(3)}$ , as claimed.

Now, consider $\ell \ge 4$ and see Figure 1 for an illustration. Recall that $e = P \cup \{w\},$ so e has exactly two vertices in $\Psi^{-1}(S^{1-p_i}_i)$ and the other vertices are in $\Psi^{-1}(S^{p_i}_i).$ Let $\delta = (\delta_1, \ldots, \delta_{\ell-1}) = \delta(\Psi(e)).$ Then, $\mathrm{arg\,max}_{j \in [\ell-1]} \delta_j = 2$ if $p_i = 1$ and $\mathrm{arg\,max}_{j \in [\ell-1]} \delta_j = k-2$ if $p_i = 0.$ In either case, $\phi_n^{(\ell)}(\Psi(e)) = C_2.$ We will find an edge $f \in E(H)$ whose image receives colour $C_1$ . Recall that every vertex in $B \supseteq \Psi^{-1}(S^{1-p_i}_i)$ has a neighbour in A. Hence, we can extend P by attaching a vertex $a \in A$ to v and then remove its last vertex (which is in $\Psi^{-1}(S_i^{p_i})$ ) to obtain a path P’ of length $\ell-2$ whose first vertex is $a \in A,$ the second vertex is $v \in \Psi^{-1}(S^{1-p_i}_i)$ and the remaining vertices are in $\Psi^{-1}(S^{p_i}_i).$

Figure 1. The two chosen edges in the case $\ell=5$ . Sets $\Psi(A), \Psi(B), S_i^0$ and $S_i^1$ are depicted by ovals. The vertices appearing in both e and f are depicted by points, the vertices in $e \setminus f$ by squares and the vertices in $f \setminus e$ by crosses. The vertices further to the right are mapped by $\Psi$ to larger values. The black triangles correspond to the value of $\delta$ of consecutive vertices, where higher triangles represent larger bit positions. The curves connecting the points and crosses represent edges between the corresponding vertices in G.

If $p_i = 1,$ then let $f = V(P') \cup \{w\} \in E(H).$ Consider $\delta = (\delta_1, \ldots, \delta_{\ell-1}) = \delta(\Psi(f)).$ Since f has one vertex in A and the rest are in B, it follows that $\mathrm{arg\,max}_{j \in [\ell-1]} \delta_j = 1.$ Additionally, $\Psi(f)$ has two vertices in $S_i^0$ and the remaining ones are in $S_i^1.$ Hence, $\delta_2 \lt q_i = \delta_3,$ so $\delta$ is not monotone, implying that $\phi_n^{(\ell)}(\Psi(f)) = C_1.$

If $p_i = 0,$ then let u be an arbitrary vertex in $\Psi^{-1}(S^0_i) \setminus V(P'),$ which exists since $|S^0_i| \ge s / 100 \ge \ell.$ Let $f = V(P') \cup \{ u\} \in E(H)$ and denote $\delta = (\delta_1, \ldots, \delta_{\ell-1}) = \delta(\Psi(f)).$ As before, we have $\mathrm{arg\,max}_{j \in [\ell-1]} \delta_j = 1.$ The largest element of $\Psi(f)$ is $\Psi(v) \in S^1_i,$ while the second and third largest elements are in $S^0_i.$ Hence, $\delta_{\ell-1} \gt \delta_{\ell-2} \lt \delta_1,$ which gives $\phi_n^{(\ell)}(\Psi(f)) = C_1.$