Proof. Suppose first that \(\mathcal{F}\) is \(\mathscr{P}\)-colorable. Then there exists \(F\in \mathcal{F}\) such that \(F\) is \(\mathscr{P}\)-colorable. Set \(m=|V(F)|\le n\). Let \(v_1\prec v_2\prec \cdots \prec v_m\) be an ordering of \(V(F)\) and let \(\varphi:\binom{V(F)}{k-1}\to \mathcal{C}\) be a function witnessing that \(F\) is \(\mathscr{P}\)-colorable. Define \(\phi:V(F)\to [n]\) by \(\phi(v_i)=i\) for each \(i\in[m]\). Next, for every \(S=\{v_{i_1},v_{i_2},\dots,v_{i_{k-1}}\}\in \partial F\), define \(\psi(S)\) to be the copy of the color \(\varphi(S)\) in the vertex class \(\mathcal{P}_{\mathcal{I}}\) of \(\mathcal{A}(\mathscr P)\), where \(\mathcal{I}=\{i_1,i_2,\dots, i_{k-1}\}\). Then condition (2) in 6 holds by construction. Moreover, if \[e=\{v_{i_1},v_{i_2},\dots,v_{i_k}\}\in E(F) \quad\text{with}\quad v_{i_1}\prec v_{i_2}\prec \cdots \prec v_{i_k},\] then, since \(\varphi\) witnesses that \(F\) is \(\mathscr P\)-colorable, \[\bigl(\varphi(e\setminus\{v_{i_1}\}),\varphi(e\setminus\{v_{i_2}\}),\dots,\varphi(e\setminus\{v_{i_k}\})\bigr)\in\mathcal{T}.\] By the definition of \(\mathcal{A}(\mathscr P)\), this implies that \[\{\psi(e\setminus\{v_{i_1}\}),\psi(e\setminus\{v_{i_2}\}),\dots,\psi(e\setminus\{v_{i_k}\})\}\in E(\mathcal{A}_{\phi(e)}),\] where \(\phi(e)=\{\phi(v):v\in e\}\). Hence \((\phi, \psi)\) is a reduced map from \(F\) to \(\mathcal{A}(\mathscr P)\), so \(\mathcal{A}(\mathscr P)\) embeds \(\mathcal{F}\).

Conversely, suppose that \(\mathcal{A}(\mathscr P)\) embeds \(\mathcal{F}\). Then there exist \(F\in\mathcal{F}\) and a reduced map \((\phi,\psi)\) from \(F\) to \(\mathcal{A}(\mathscr P)\). The map \(\phi:V(F)\to [n]\) induces an ordering “\(\prec\)” on \(V(F)\): \(v_i\prec v_j\) if and only if \(\phi(v_i)<\phi(v_j)\). For each \(S\in \partial F\), define \(\varphi(S)\in\mathcal{C}\) to be the color represented by the vertex \(\psi(S)\in \mathcal{P}_{\phi(S)}\), where \(\phi(S)=\{\phi(v):v\in S\}\). Extend \(\varphi\) arbitrarily to all \((k-1)\)-subsets of \(V(F)\) not in \(\partial F\). It is then immediate from the definition of \(\mathcal{A}(\mathscr P)\) that the order \(\prec\) and the function \(\varphi\) witness that \(F\) is \(\mathscr P\)-colorable. Hence \(\mathcal{F}\) is \(\mathscr P\)-colorable. ◻

Proof of 1. If \(\mathcal{F}=\emptyset\), then both sides are equal to \(1\), so there is nothing to prove. Hence we may assume that \(\mathcal{F}\) is nonempty. For each integer \(n\ge 1\), let \(\mathcal{F}_n\subseteq \mathcal{F}\) denote the subfamily consisting of all members of \(\mathcal{F}\) with at most \(n\) vertices. Then \[\mathcal{F}=\bigcup_{n=1}^{\infty}\mathcal{F}_n.\]

Set \(\pi:=\pi_{k-2}(\mathcal{F})\). Fix \(\varepsilon>0\). Choose \(n_0\) such that \(\mathcal{F}_{n_0}\neq\emptyset\). For every \(n\ge n_0\), we shall construct a \(k\)-palette \(\mathscr P_n=(\mathcal{C}_n,\mathcal{T}_n)\) with density at least \(\pi-\frac{2\varepsilon}{3}\) such that \(\mathcal{F}_n\) is not \(\mathscr P_n\)-colorable and \(|\mathcal{C}_n|\) depends only on \(\varepsilon\) and \(k\).

We first claim that, for every \(n\geq n_0\), there exists \(N'(n)\) such that for every \(N\geq N'(n)\) there exists an \(N\)-reduced \(k\)-graph \(\mathcal{A}_n\) of density at least \(\pi-\varepsilon/3\) which does not embed \(\mathcal{F}_n\). Indeed, let \(N'(n)\) be the constant \(m_0\) obtained by applying 6 with \(d=\pi-\varepsilon/3\). Since \(\mathcal{F}_n\subseteq\mathcal{F}\), we have \[\pi_{k-2}(\mathcal{F}_n)\geq \pi_{k-2}(\mathcal{F})=\pi.\] If no such \(\mathcal{A}_n\) existed, then every \((\pi-\varepsilon/3)\)-dense \(N\)-reduced \(k\)-graph would embed \(\mathcal{F}_n\). Hence, for every \(\eta>0\), every \((\pi-\varepsilon/3+\eta)\)-dense \(N\)-reduced \(k\)-graph would also embed \(\mathcal{F}_n\). Applying 6, we would obtain \[\pi_{k-2}(\mathcal{F}_n)\leq \pi-\frac{\varepsilon}{3},\] which is a contradiction. This proves the claim.

Fix \(n\). Let \(s=s({\varepsilon}/{3},k)\), \(m=R_k(n,2^{s^k})\) and \(N_0=N_0(m,{\varepsilon}/{3},k)\) be given by 2. Let \(N=\max\{N'(n),N_0\}\). Applying 2 to \(\mathcal{A}_n\), we obtain a subset \(M\subseteq[N]\) of size \(m\) and, for each \(\mathcal{X}\in\binom{M}{k-1}\), a multiset \(S_{\mathcal{X}}\) of \(s\) vertices in \(\mathcal{P}_{\mathcal{X}}\) such that the \(m\)-reduced \(k\)-graph \(\mathcal{A}'\) on these multisets is \((\pi-\frac{2\varepsilon}{3})\)-dense.

Let \(v_{\mathcal{X}}^1,\dots,v_{\mathcal{X}}^s\) be the vertices in \(S_{\mathcal{X}}\) for each \(\mathcal{X}\in\binom{M}{k-1}\), where repetitions are allowed. For each \(\mathcal{Y}\in\binom{M}{k}\), the constituent \(\mathcal{A}'_{\mathcal{Y}}\) is determined by which of the \(s^k\) possible \(k\)-tuples \[\{v_{\mathcal{X}_1}^{i_1},v_{\mathcal{X}_2}^{i_2},\dots,v_{\mathcal{X}_k}^{i_k}\}, \qquad (i_1,\dots,i_k)\in [s]^k,\] form edges, where \(\binom{\mathcal{Y}}{k-1}=\{\mathcal{X}_1,\dots,\mathcal{X}_k\}\). Thus each constituent \(\mathcal{A}'_{\mathcal{Y}}\) can be labeled by a subset of \([s]^k\), and there are exactly \(2^{s^k}\) possible labels.

Since \(m=R_k(n,2^{s^k})\), there exists a subset \(M_0\subseteq M\) of size \(n\) such that all constituents \(\mathcal{A}'_{\mathcal{Y}}\) with \(\mathcal{Y}\in\binom{M_0}{k}\) receive the same label \(L\subseteq [s]^k\). Since \(\mathcal{A}'\) is \((\pi-\frac{2\varepsilon}{3})\)-dense, every constituent \(\mathcal{A}'_{\mathcal{Y}}\) with \(\mathcal{Y}\in\binom{M_0}{k}\) contains at least \((\pi-\frac{2\varepsilon}{3})s^k\) edges. Hence \[\frac{|L|}{s^k}\ge \pi-\frac{2\varepsilon}{3}.\]

Define a \(k\)-palette \(\mathscr P_n=(\mathcal{C}_n,\mathcal{T}_n)\) by \(\mathcal{C}_n=[s]\) and \(\mathcal{T}_n=L\). Then \[d(\mathscr P_n)=\frac{|L|}{s^k}\ge \pi-\frac{2\varepsilon}{3}.\] Moreover, after identifying each multiset \(S_{\mathcal{X}}\) with the color set \([s]\), the \(n\)-reduced \(k\)-graph obtained from \(\mathcal{A}'\) by restricting the index set to \(M_0\) is precisely of the form \(\mathcal{A}_n(\mathscr P_n)\). Since this reduced \(k\)-graph is a subgraph of the blow-up of \(\mathcal{A}_n\), it also does not embed \(\mathcal{F}_{n}\). Therefore, by 1, the family \(\mathcal{F}_{n}\) is not \(\mathscr P_n\)-colorable.

Since \(s\) is a constant, there are only finitely many possible palettes \(\mathscr P_n\). Hence there exists an infinite increasing sequence \[n_1<n_2<\cdots\] with \(n_1>n_0\) such that all palettes \(\mathscr P_{n_j}\) are equal. Let \(\mathscr P=\mathscr P_{n_1}\). We claim \(\mathcal{F}\) is not \(\mathscr P\)-colorable. Indeed, suppose there is some \(k\)-graph \(F\in \mathcal{F}\) that is \(\mathscr P\)-colorable. Choose \(j\) such that \(n_j\geq |V(F)|\). Then \(F\in\mathcal{F}_{n_j}\). Since \(\mathcal{F}_{n_j}\) is not \(\mathscr P_{n_j}\)-colorable and \(\mathscr P_{n_j}=\mathscr P\), the graph \(F\) is not \(\mathscr P\)-colorable, leading to a contradiction.

Then \(\pi_k^{{\rm pal}}(\mathcal{F})\ge d(\mathscr P)\ge \pi-\frac{2\varepsilon}{3}\). Since \(\varepsilon>0\) was arbitrary, we conclude that \(\pi_k^{{\rm pal}}(\mathcal{F})\ge \pi_{k-2}(\mathcal{F})\). Together with 5, this yields \[\pi_k^{{\rm pal}}(\mathcal{F})=\pi_{k-2}(\mathcal{F}).\] ◻

Proof. Assume for contradiction that for every \(M\in \binom{[n]}{m}\), there exists some \(\mathcal{X}=\{ x_1,x_2,\ldots,x_{k-1}\} \in \binom{M}{k-1}\) such that \[\bigcup_{x_k\in M\setminus\mathcal{X}} B^{x_k}_{\mathcal{X}} =\mathcal{P}_{\mathcal{X}}.\] We label each ordered \(m\)-set \(M=\llbracket u_1,u_2,\ldots,u_m\rrbracket\in \binom{[n]}{m}\) by the \((k-1)\)-subset \[\mathcal{L}(M):=\{\,i\in[m]:u_i\in \mathcal{X}\,\}\in \binom{[m]}{k-1}.\]

Let \(n=R_m(2km,\binom{m}{k-1})\). By Ramsey’s theorem, there exists a subset \(J\subseteq[n]\) of size \(2km\) such that every \(M\in \binom{J}{m}\) receives the same label \(\mathcal{L}=\{\ell_1,\dots,\ell_{k-1}\}\in\binom{[m]}{k-1}\). Relabeling the indices if necessary, we may assume that \(J=[2km]\).

Now let \(\mathcal{I}=\{2m,4m,\dots,2(k-1)m\}\). For each index \(i_k\in[2km]\setminus\mathcal{I}\), we have \(|B_{\mathcal{I}}^{i_k}|\le \frac{1}{3k}\,|\mathcal{P}_{\mathcal{I}}|\). By double counting, at most \(\frac{2}{3}|\mathcal{P}_{\mathcal{I}}|\) vertices in \(\mathcal{P}_{\mathcal{I}}\) belong to at least \(m\) of the sets \(B_{\mathcal{I}}^{i_k}\). Therefore, there exists a vertex \(v^*\in\mathcal{P}_{\mathcal{I}}\) that belongs to at most \(m-1\) of these sets.

We now extend \(\mathcal{I}\) to an ordered \(m\)-set \(M_0=\llbracket u_1',\dots,u_m'\rrbracket\subseteq J\) such that the positions indexed by \(\mathcal{L}=\{\ell_1,\ldots,\ell_{k-1}\}\) are occupied by the elements of \(\mathcal{I}\), namely \[u'_{\ell_j}=2jm \qquad\text{for every } j\in[k-1],\] and such that for every \(u_i'\in M_0\setminus \mathcal{I}\), we have \(v^*\notin B_{\mathcal{I}}^{u_i'}\). This is possible because \(v^*\) belongs to at most \(m-1\) forbidden sets, whereas there are \(2m-(k-1)\ge m\) available indices in \(\{2im+1,2im+2,\ldots,2(i+1)m-1\}\) for \(0\le i\le k-1\). This ensures that \[v^*\notin \bigcup_{j_k\in M_0\setminus\mathcal{I}} B_{\mathcal{I}}^{j_k}.\]

However, since all \(m\)-sets of \(J\) receive the same label \(\mathcal{L}\), \(M_0\) is labeled by \(\mathcal{L}\), which implies \[\bigcup_{j_k\in M_0\setminus\mathcal{I}} B_{\mathcal{I}}^{j_k} =\mathcal{P}_{\mathcal{I}}.\] This contradicts the choice of \(v^*\). ◻

Proof of 2. We begin with a brief outline. The proof proceeds in \(r\) rounds. In each round, we choose a multiset of \(t\) vertices from every relevant vertex class and then apply 4 to shrink the index set (denoted \(M_i\)) to a smaller index set (denoted \(M_{i+1}\)), on which all these choices simultaneously satisfy the required density conditions. After \(r\) rounds, we will have selected \(s=rt\) vertices in each surviving vertex class. The accumulated density losses are controlled such that every constituent still contains at least \((d-\varepsilon)s^k\) edges.

We now turn to the details. Let \(r=\lceil k(k-1)\varepsilon^{-1}\rceil\), \(t=\lceil 2k^2\varepsilon^{-2}\log(3kr^{k-1})\rceil\), and set \(s=rt\). Starting from \(m_r=m\), choose integers \(m_{r-1},m_{r-2},\ldots,m_0\) recursively such that 4 can be applied with parameters \(m_i\) and \(m_{i-1}\) for each \(i\in[r]\), and let \(N_0:=m_0\). Let \(\mathcal{A}\) be a \(d\)-dense \(N_0\)-reduced \(k\)-graph (this suffices for the proof: for any \(N>N_0\), a \(d\)-dense \(N\)-reduced \(k\)-graph contains a \(d\)-dense \(N_0\)-reduced \(k\)-graph as a subgraph). We recursively construct index sets \([N_0]=M_0\supseteq M_1\supseteq \cdots \supseteq M_r\) with \(|M_i|=m_i\).

For each round \(i\in [r]\) and each \(\mathcal{X} \in \binom{M_{i-1}}{k-1}\), we select a multiset \(T_{\mathcal{X}}^i \subseteq \mathcal{P}_{\mathcal{X}}\) of size \(t\). Finally, for every \(\mathcal{X} \in \binom{M_r}{k-1}\), we define \(S_{\mathcal{X}}=\bigcup_{i=1}^r T_{\mathcal{X}}^i\), and hence \(S_{\mathcal{X}}\) is a multiset of size \(s\) in \(\mathcal{P}_{\mathcal{X}}\). Given a \(k\)-set \(\mathcal{Y}=\llbracket y_1,\dots,y_k\rrbracket\in \binom{M_r}{k}\) of indices, let \(\mathcal{X}_i=\mathcal{Y}\setminus\{y_i\}\). Our goal is to prove that \[\label{eq:goal32contraction} |E(S_{\mathcal{X}_1},\dots,S_{\mathcal{X}_k})|\ge (d-\varepsilon)s^k.\tag{5}\]

To achieve this, it suffices to ensure that for every choice of distinct rounds \(i_1,\dots,i_k\in[r]\) and every \(\mathcal{Y}\in \binom{M_r}{k}\), we have \[\label{eq:goal32contraction2} |E(T_{\mathcal{X}_1}^{i_1},\dots,T_{\mathcal{X}_k}^{i_k})| \ge \left(d-\frac{\varepsilon}{2}\right)t^k.\tag{6}\] Since each \(k\)-tuple of distinct rounds contributes at least \((d-\frac{\varepsilon}{2})t^k\) edges, summing over all such tuples gives \[|E(S_{\mathcal{X}_1},\dots,S_{\mathcal{X}_k})| \ge \frac{r!}{(r - k)!} (d-\tfrac{\varepsilon}{2}) t^k \ge (d-\varepsilon)s^k.\]

To ensure that 6 holds, we need to maintain a stronger family of inductive invariants. For \(j\in\{0,1,\dots,r\}\), let \[W_j:=\Bigl\{(w_1,\dots,w_k): 0\le w_i\le j \text{ for all } i\in[k], \text{ and all nonzero entries are distinct}\Bigr\}.\] Note that \(|W_j|=1+\sum_{i=1}^k \binom{k}{i}\binom{j}{i}\cdot i!\) if \(k\leq j\) and \(|W_j|=1+\sum_{i=1}^j\binom{k}{i}\binom{j}{i} \cdot i!\) if \(k> j\). For \(\bar{w}=(w_1,w_2,\dots,w_k)\in W_j\), let \[|\bar w|_+ := |\{i\in[k]:w_i\ne 0\}| \qquad\text{and}\qquad w_{\max}:=\max\{w_1,\dots,w_k\}.\] Moreover, for \(\mathcal{Y}=\llbracket y_1,\dots,y_k\rrbracket\in \binom{M_{w_{\max}}}{k}\), let \[\mathcal{X}_i=\mathcal{Y}\setminus \{y_i\} \quad \text{~for each~} i\in[k].\] Recall that \(T_{\mathcal{X}}^i \subseteq \mathcal{P}_{\mathcal{X}}\) is a multiset of size \(t\) that we will select for each \(i\in [r]\) and let \(T_{\mathcal{X}}^0=\mathcal{P}_{\mathcal{X}}\). Hence, it suffices to ensure that the following invariants throughout the construction, \[\begin{align} \label{eqlm2466462} \nu(T_{\mathcal{X}_1}^{w_1},\dots,T_{\mathcal{X}_k}^{w_k}) \ge d-\frac{\varepsilon \cdot|\bar{w}|_+ }{2k} ~\text{ for each}~ \bar{w}\in W_r ~\text{and}~ \mathcal{Y}\in \binom{M_{w_{\max}}}{k}, \end{align}\tag{7}\] where \(\nu(T_{\mathcal{X}_1}^{w_1},\dots,T_{\mathcal{X}_k}^{w_k})\) denotes the edge density of \(\mathcal{A}\) induced on \(T_{\mathcal{X}_1}^{w_1},\dots,T_{\mathcal{X}_k}^{w_k}\).

We now prove 7 by induction on \(j\). Assume that \(M_{j-1}\) has already been constructed, together with multisets \(T_{\mathcal{X}}^{i}\) for each \(i\in [j-1]\) and \(\mathcal{X}\in \binom{M_{j-1}}{k-1}\) and that 7 holds for all \(\bar{w}\in W_{j-1}\). We now construct \(M_j\) and the multisets \(T_{\mathcal{X}}^{j}\) for each \(\mathcal{X}\in \binom{M_{j}}{k-1}\) and verify that all invariants hold for \(\bar{w}\in W_{j}\).

Fix \(\mathcal{X}\in \binom{M_{j-1}}{k-1}\). Let \((\mathcal{P}_{\mathcal{X}})^t\) denote the set of vectors of length \(t\) with entries in \(\mathcal{P}_{\mathcal{X}}\) and view a vector as a multiset. We now start to choose \(T_{\mathcal{X}}^j \in (\mathcal{P}_{\mathcal{X}})^t\). For each \(z\in M_{j-1}\setminus\mathcal{X}\), let \(B_{\mathcal{X}}^z\subseteq (\mathcal{P}_{\mathcal{X}})^t\) denote the set of vectors which would violate at least one invariant (with \(\mathcal{Y}=\mathcal{X}\cup \{z\}\)) if chosen as \(T_{\mathcal{X}}^j\). We claim that \[|B_{\mathcal{X}}^z| \le \frac{1}{3k}|\mathcal{P}_{\mathcal{X}}|^t .\]

To prove this, fix \(\mathcal{X}\) and \(z\), and let \(z=y_1\), \(\mathcal{X}=\{y_2,\dots,y_k\}\), \(\mathcal{Y}=\{y_1,\dots,y_k\}\) and \(\mathcal{X}_i=\mathcal{Y}\setminus\{y_i\}\). Analogous to the definition of \(W_j\), define \[W_{j-1}':=\Bigl\{(w_2,\dots,w_k): 0\le w_i\le j-1 \text{ for } i=2,\dots,k,\text{ and all nonzero entries are distinct}\Bigr\}.\] For each \(\bar w'=(w_2,\dots,w_k)\in W_{j-1}'\), define a function \(f_{\bar{w}'}:\mathcal{P}_{\mathcal{X}_1}\to[0,1]\) as follows: \[f_{\bar w'}(v):=\nu\bigl(v,T_{\mathcal{X}_2}^{w_2},\dots,T_{\mathcal{X}_k}^{w_k}\bigr).\] By the inductive hypothesis, we have \[\bar f_{\bar{w}'}(\mathcal{P}_{\mathcal{X}_1})\ge d - \frac{\varepsilon\cdot|\bar{w}'|_+}{2k},\] where \(\bar f_{\bar{w}'}(\mathcal{P}_{\mathcal{X}_1})\) is the average value of \(f_{\bar{w}'}\) over \(\mathcal{P}_{\mathcal{X}_1}\).

Now choose \(T_{\mathcal{X}_1}^j\) uniformly at random from \((\mathcal{P}_{\mathcal{X}_1})^t\). By 3, we have \[\Pr\!\left( \bar f_{\bar{w}'}(T_{\mathcal{X}_1}^j) \le \bar f_{\bar{w}'}(\mathcal{P}_{\mathcal{X}_1}) -\frac{\varepsilon}{2k} \right) \le e^{-2(\frac{\varepsilon}{2k})^2 t} \le \frac{1}{3kr^{k-1}}.\] Since the number of such functions is at most \(|W_{j-1}'|\le j^{k-1}\le r^{k-1}\), the union bound implies that with probability at least \(1-\frac{1}{3k}\) none of the above bad events occurs. Hence, \[|B_{\mathcal{X}}^z| \le \frac{1}{3k}|\mathcal{P}_{\mathcal{X}}|^t .\]

We now apply 4 to the set \((\mathcal{P}_{\mathcal{X}})^t\) and \(B_{\mathcal{X}}^z\) for \(\mathcal{X}\in\binom{M_{j-1}}{k-1}\). This yields a subset \(M_j\subseteq M_{j-1}\) with \(|M_j|=m_j\) such that for every \(\mathcal{X}\in\binom{M_j}{k-1}\), one can choose \(T_{\mathcal{X}}^j\in (\mathcal{P}_{\mathcal{X}})^t\) avoiding all corresponding forbidden sets \(B_{\mathcal{X}}^z\) with \(z\in M_j\setminus \mathcal{X}\). By construction, this guarantees that 7 holds for all \(\bar w\in W_j\). After completing \(r\) such rounds, we conclude that 6 holds as desired. ◻

Proof. Let \(\mathscr{P}=(\mathcal{C}, \mathcal{T})\) and \(\mathscr{P}_0=(\mathcal{C}_0, \mathcal{T}_0)\) be two \(k\)-palettes as in the statement. Set \[m:=|\mathcal{C}|\cdot |\mathcal{C}_0|, \qquad \ell:=|\mathcal{C}_0|^{|\mathcal{C}|}, \qquad R:=R_{k-1}(k,\ell), \qquad d_{k-1}:=\frac{1}{2m}.\] Choose auxiliary constants satisfying \[{1}/{n_1}\ll {1}/{r}, \delta \ll d_2,\dots,d_{k-2}\ll \delta_{k-1} \ll d_{k-1}, {1}/{k},\] where \(1/d_i\in \mathbb{N}\) for all \(i=2,\dots,k-2\), so that the assumptions of 9 are satisfied with \(k\) replaced by \(k-1\) and \(F=K_k^{(k-1)}\). In addition, choose \(\delta_{k-1}>0\) sufficiently small such that \[\label{eq:delta123k-1125-single} 2\sqrt{\delta_{k-1}}\,m\, R^{k-1}<1.\tag{9}\]

Apply 8 with parameters \(R, k-1, m, \eta=1/R, \delta_{k-1}, r, \delta\) to obtain integers \(t_0\) and \(n_0\). Next choose \(\varepsilon>0\) sufficiently small such that \[\label{eq:eps-single} \varepsilon<\min\left\{\frac{1}{2},\;(1-\eta)t_0^{-(k-1)}\prod_{j=2}^{k-2} d_j^{\binom{k-1}{j}}\right\},\tag{10}\] and let \(N\ge \max\{n_0,n_1\}\) be large enough such that \((R\cdot t_0!)\mid N\) and \[\label{eq:positive32probability32single-order} 1-2^{\binom{N}{k-2}}|\mathcal{C}|e^{-\frac{\varepsilon^3N^{k-1}}{2|\mathcal{C}|}}>0.\tag{11}\]

Let \(G\) be the complete \((k-1)\)-graph on vertex set \([N]\). Color the edges of \(G\) independently and uniformly at random with colors from \(\mathcal{C}\). For any \((k-2)\)-graph \(G^{(k-2)}\) on \([N]\) with \(|\mathcal{K}_{k-1}(G^{(k-2)})|\ge \varepsilon N^{k-1}\) and any color \(x\in \mathcal{C}\), let \(B_x(G^{(k-2)})\) denote the event that fewer than \[(1-\varepsilon)\frac{|\mathcal{K}_{k-1}(G^{(k-2)})|}{|\mathcal{C}|}\] members of \(\mathcal{K}_{k-1}(G^{(k-2)})\) receive color \(x\). By the Chernoff bound, \[\mathbb{P}(B_x(G^{(k-2)})) \le e^{-\frac{\varepsilon^2|\mathcal{K}_{k-1}(G^{(k-2)})|}{2|\mathcal{C}|}} \le e^{-\frac{\varepsilon^3N^{k-1}}{2|\mathcal{C}|}}.\] Since there are at most \(2^{\binom{N}{k-2}}\) choices for \(G^{(k-2)}\), the union bound together with 11 implies that there exists a coloring \(f:E(G)\to \mathcal{C}\) such that for every color \(x\in \mathcal{C}\) and every \((k-2)\)-graph \(G^{(k-2)}\) on \([N]\) with \(|\mathcal{K}_{k-1}(G^{(k-2)})|\ge \varepsilon N^{k-1}\), we have \[\label{eq:random-color-property} |\mathcal{K}_{k-1}(G^{(k-2)})\cap E(G_x)| \ge (1-\varepsilon)\frac{|\mathcal{K}_{k-1}(G^{(k-2)})|}{|\mathcal{C}|},\tag{12}\] where \(G_x\) denotes the spanning subgraph of \(G\) consisting of all edges colored \(x\).

Now define a \(k\)-graph \(H\) on \([N]\) by declaring that for every \[e=\llbracket i_1,i_2,\dots,i_k\rrbracket\in \binom{[N]}{k},\] we have \(e\in E(H)\) if and only if \[\bigl(f(e\setminus\{i_1\}),f(e\setminus\{i_2\}),\dots,f(e\setminus\{i_k\})\bigr)\in \mathcal{T}.\] By construction, the ordered \(k\)-graph \(H\) with the natural order is \(\mathscr P\)-colorable. By assumption, \(H\) is also \(\mathscr{P}_0\)-colorable and let \(f_0: E(G)\to \mathcal{C}_0\) be a coloring witnessing this property.

For each \((x,x_0)\in \mathcal{C}\times \mathcal{C}_0\), let \(G_{x,x_0}\) denote the spanning subgraph of \(G\) with edge set \[E(G_{x,x_0})=\{e\in E(G): f(e)=x,\;f_0(e)=x_0\}.\] Let \([N]=U_1\cup \cdots \cup U_{R}\) be an ordered equipartition such that \(\max\{u: u\in U_i\}< \min\{u: u\in U_j\}\) for \(1\le i<j\le R\). Apply 8 to the \((\mathcal{C}\times \mathcal{C}_0)\)-colored \((k-1)\)-graph \(G\) with initial partition \(U_1\cup\cdots\cup U_{R}\). We obtain a family of partitions \[\boldsymbol{\mathcal{P}}=\boldsymbol{\mathcal{P}}(k-2,\mathbf{a}),\] where \(a_i=1/d_i\) for \(i=2,\dots,k-2\) and \(1/\eta<a_1<t_0\), such that

1. \(\boldsymbol{\mathcal{P}}\) is \((\eta,\delta(\mathbf{a}),t_0)\)-equitable and \(\mathcal{P}^{(1)}\) refines \(U_1\cup\cdots\cup U_{R}\);

2. for each \((x,x_0)\in \mathcal{C}\times\mathcal{C}_0\), the \((k-1)\)-graph \(G_{x,x_0}\) is \((\delta_{k-1},r(\mathbf{a}))\)-regular with respect to \(\boldsymbol{\mathcal{P}}\).

Recall that the elements of \(\mathcal{P}^{(1)}\) are called clusters. We say that a \((k-1)\)-tuple of clusters is good for \((x,x_0)\in \mathcal{C}\times \mathcal{C}_0\), if \(G_{x,x_0}\) is \((\delta_{k-1},r(\mathbf{a}))\)-regular with respect to all but at most a \(\sqrt{\delta_{k-1}}\)-fraction of the polyads induced on this \((k-1)\)-tuple of clusters. A \((k-1)\)-tuple of clusters is called all-good if it is good for every \((x,x_0)\in \mathcal{C}\times \mathcal{C}_0\).

Now fix a choice of \(V_1,V_2,\dots,V_{R}\) satisfying 10. We next choose one “good” polyad for all \((k-1)\)-tuples of these clusters in a consistent way.

Next, fix an \((R, k-2)\)-complex \(\{Q^{(i)}\}_{i=1}^{k-2}\) with clusters \(V_1,\dots,V_R\) satisfying 11. For each \(I\in \binom{[R]}{k-1}\), define a function \[h_I:\mathcal{C}\to \mathcal{C}_0\] as follows: for each \(x\in\mathcal{C}\), let \(h_I(x)\) be a color in \(\mathcal{C}_0\) maximizing \[\bigl|\mathcal{K}_{k-1}(\hat{Q}_I^{(k-2)})\cap E(G_{x,x_0})\bigr|\] over all \(x_0\in\mathcal{C}_0\). Since there are at most \(\ell\) possible such functions and \(R=R_{k-1}(k,\ell)\), there exists a \(k\)-set of indices whose every \((k-1)\)-subset receives the same color function, denoted by \[h:\mathcal{C}\to \mathcal{C}_0.\] Without loss of generality, we may assume that this \(k\)-set of indices is \([k]\). We claim that \(h\) is a homomorphism from \(\mathscr P\) to \(\mathscr P_0\).

Let \((x_1,\dots,x_k)\in\mathcal{T}\). For each \(i\in[k]\), set \[I_i:=[k]\setminus\{i\}.\] By condition [p4] of 10, we have \[|\mathcal{K}_{k-1}(\hat{Q}_{I_i}^{(k-2)})| \ge (1-\eta)\prod_{j=1}^{k-2}\left(\frac{1}{a_j}\right)^{\binom{k-1}{j}}N^{k-1}\ge \varepsilon N^{k-1},\] where the last inequality follows from 10 . Therefore, by 12 , for every \(i\in[k]\) and every \(x\in\mathcal{C}\), \[|\mathcal{K}_{k-1}(\hat{Q}_{I_i}^{(k-2)})\cap E(G_x)| \ge (1-\varepsilon)\frac{|\mathcal{K}_{k-1}(\hat{Q}_{I_i}^{(k-2)})|}{|\mathcal{C}|}.\] Since \(h_{I_i}(x)=h(x)\) is chosen as the majority \(f_0\)-color among those members of \(\mathcal{K}_{k-1}(\hat{Q}_{I_i}^{(k-2)})\) whose \(f\)-color is \(x\), we obtain \[d\bigl(G_{x,h(x)}\mid \hat{Q}_{I_i}^{(k-2)}\bigr) \ge \frac{1-\varepsilon}{|\mathcal{C}||\mathcal{C}_0|} = \frac{1-\varepsilon}{m} \ge d_{k-1}.\] Moreover, by 11, for every \(i\in[k]\), the \((k-1)\)-graph \(G_{x_i,h(x_i)}\) is \((\delta_{k-1},r(\mathbf{a}))\)-regular with respect to \(\hat{Q}_{I_i}^{(k-2)}\).

Now consider the \((k-1)\)-graph \[G':=\bigcup_{i=1}^k G_{x_i,h(x_i)}\Bigl[\bigcup_{\lambda\in I_i} V_\lambda\Bigr].\] By construction, the complex \[\{Q^{(i)}[V_1\cup\cdots\cup V_k]\}_{i=1}^{k-2}\] together with the \((k-1)\)-graph \(G'\) satisfies the assumptions of 9 for the complete \((k-1)\)-graph \(K_k^{(k-1)}\). Hence \(G'\) contains a copy of \(K_k^{(k-1)}\) on the clusters \(V_1,\dots,V_k\).

Let this copy correspond to vertices \(v_1\in V_1,\dots,v_k\in V_k\). Since \(V_i\subseteq U_i\) for each \(i\in[k]\) and the partition \(U_1\cup\cdots\cup U_{R}\) is ordered, we have \[v_1< v_2<\cdots < v_k.\] For each \(i\in[k]\), the \((k-1)\)-set \(\{v_1,\dots,v_k\}\setminus\{v_i\}\) belongs to \(G_{x_i,h(x_i)}\). Because \((x_1,\dots,x_k)\in\mathcal{T}\), the \(k\)-set \(\{v_1,\dots,v_k\}\) is an edge of \(H\). Since \(f_0\) witnesses that \(H\) is \(\mathscr P_0\)-colorable, it follows that \[(h(x_1),h(x_2),\dots,h(x_k))\in \mathcal{T}_0.\] Therefore \(h\) is a homomorphism from \(\mathscr P\) to \(\mathscr P_0\), as required. ◻

Proof. Let \(\mathscr P=(\mathcal{C},\mathcal{T})\) and \(\mathscr P_0=(\mathcal{C}_0,\mathcal{T}_0)\) be two \(k\)-palettes as in the statement, and let \(H^+\) and \(H^-\) be the corresponding ordered \(k\)-graphs. Set \[n_1:=|V(H^+)|, \qquad n_2:=|V(H^-)|, \qquad n:=\max\{n_1,n_2\}, \qquad m:=(n_1-1)(n_2-1)+1,\] and \[p:=|\mathcal{C}|^{-n^{k-1}}.\] Choose \(N\) sufficiently large such that \[\label{eq:random-single-palette} N!\cdot \left(1-p\right)^{N^2/(m^2(m-1)^2)}<1.\tag{13}\] Such an \(N\) exists because \(p>0\) is fixed, \(N!\le N^N=e^{N\log N}\) and \((1-p)^{N^2/(m^2(m-1)^2)}\le e^{-cN^2}\) for some constant \(c=c(p,m)>0\).

Now define a random \(k\)-graph \(H\) on \([N]\) as follows. Choose a coloring \[f:\binom{[N]}{k-1}\to\mathcal{C}\] uniformly at random. For every \(e=\llbracket i_1,i_2,\dots,i_k\rrbracket\in \binom{[N]}{k}\), we choose \(e\in E(H)\) if and only if \[\bigl(f(e\setminus\{i_1\}),f(e\setminus\{i_2\}),\dots,f(e\setminus\{i_k\})\bigr)\in\mathcal{T}.\] Then \(H\) is \(\mathscr P\)-colorable by construction. Next, we shall prove that with positive probability \(H\) is not \(\mathscr P_0\)-colorable

Let \(L\) be a linear \(m\)-graph on \([N]\) with the maximum possible number of edges. Since an \(m\)-edge can intersect fewer than \[\binom{m}{2}\binom{N-2}{m-2}\] other \(m\)-edges in the complete \(m\)-graph on \([N]\), we have \[|E(L)|\ge \frac{\binom{N}{m}}{\binom{m}{2}\binom{N-2}{m-2}} = \frac{2N(N-1)}{m^2(m-1)^2} \ge \frac{N^2}{m^2(m-1)^2}.\] Enumerate the edges of \(L\) as \(e_1,e_2,\dots,e_{|E(L)|}\).

Fix any linear order \(\prec\) on \(V(H)\). By 5, for each \(j\in[|E(L)|]\), \(e_j\) contains either

• an \(n_1\)-subset \(S_j\) whose natural order and \(\prec\)-order coincide, or

• an \(n_2\)-subset \(T_j\) whose natural order and \(\prec\)-order are opposite.

Suppose first that \(e_j\) contains such an \(n_1\)-subset \(S_j\). Since \(H^+\) is \(\mathscr P\)-colorable, there exist a natural order \(u_1< \cdots< u_{n_1}\) of \(V(H^+)\) and a witness coloring \[\varphi_1:\binom{V(H^+)}{k-1}\to\mathcal{C}.\] Identify \(u_1,\dots,u_{n_1}\) with the vertices of \(S_j\) in their common natural order and \(\prec\)-order. If, for every \(X\in\binom{S_j}{k-1}\), the random color \(f(X)\) equals the corresponding value prescribed by \(\varphi_1\), then every edge of \(H^+\) appears in the ordered \(k\)-graph \(H^\prec[S_j]\). The probability of this event is at least \[|\mathcal{C}|^{-\binom{n_1}{k-1}} \ge |\mathcal{C}|^{-n^{k-1}} = p.\] Hence, with probability at least \(p\), the ordered \(k\)-graph \(H^\prec[S_j]\) contains an ordered copy of \(H^+\). Since \(H^+\) is not \(\mathscr P_0\)-colorable, this implies that \(H^\prec[e_j]\) is not \(\mathscr P_0\)-colorable. Now suppose that \(e_j\) contains an \(n_2\)-subset \(T_j\) whose natural order and \(\prec\)-order are opposite. Let \(\rm{rev}(H^{-})\) denote the ordered \(k\)-graph obtained from \(H^{-}\) by reversing its linear order. Similar to the first case, since the natural order on \(T_j\) is the reverse of the \(\prec\)-order, \(H^\prec[T_j]\) contains an ordered copy of \(\rm{rev}(H^{-})\) with probability at least \(p\). Since \(H^{-}\) is not \({\rm rev}(\mathscr P_0)\)-colorable, the ordered \(k\)-graph \(\rm{rev}(H^{-})\) is not \(\mathscr P_0\)-colorable, which implies that \(H^\prec[e_j]\) is not \(\mathscr P_0\)-colorable with probability at least \(p\). Therefore, for every \(j\in[|E(L)|]\), we have \[\mathbb{P}\bigl(H^\prec[e_j]\text{ is }\mathscr P_0\text{-colorable}\bigr)\le 1-p.\]

Since \(L\) is linear and \(k\ge 3\), any two distinct edges of \(L\) share at most one vertex, and hence no \((k-1)\)-subset of vertices is contained in two different edges of \(L\). Therefore, the events \[\bigl\{H^\prec[e_j]\text{ is }\mathscr P_0\text{-colorable}\bigr\}_{j=1}^{|E(L)|}\] are independent.

If \(k\)-graph \(H\) is \(\mathscr P_0\)-colorable, then there exists some linear order \(\prec\) on \([N]\) such that the ordered \(k\)-graph \(H^\prec\) is \(\mathscr P_0\)-colorable. In particular, for this order \(\prec\), every restriction \(H^\prec[e_j]\) would be \(\mathscr P_0\)-colorable. Hence, by independence, \[\mathbb{P}\bigl(H^\prec\text{ is }\mathscr P_0\text{-colorable}\bigr) \le (1-p)^{|E(L)|}.\] Taking the union bound over all \(N!\) linear orders, we obtain \[\mathbb{P}\bigl(H\text{ is }\mathscr P_0\text{-colorable}\bigr) \le N!\cdot (1-p)^{|E(L)|} \le N!\cdot (1-p)^{N^2/(m^2(m-1)^2)} <1\] by 13 . Therefore, with positive probability, the random \(k\)-graph \(H\) is \(\mathscr P\)-colorable but not \(\mathscr P_0\)-colorable. ◻

Proof of 2. Suppose first that there exists a \(k\)-graph \(H\) that is \(\mathscr P\)-colorable but not \(\mathscr P_0\)-colorable. By the basic property of palette homomorphisms, there is no homomorphism from \(\mathscr P\) to \(\mathscr P_0\). Since every \(k\)-graph that is \({\rm rev}(\mathscr P_0)\)-colorable becomes \(\mathscr P_0\)-colorable after reversing the vertex order, there is also no homomorphism from \(\mathscr P\) to \({\rm rev}(\mathscr P_0)\).

Conversely, suppose that there is no homomorphism from \(\mathscr P\) to \(\mathscr P_0\) and no homomorphism from \(\mathscr P\) to \({\rm rev}(\mathscr P_0)\). By 6, there exists an ordered \(k\)-graph \(H_1\) that is \(\mathscr P\)-colorable but not \(\mathscr P_0\)-colorable, and an ordered \(k\)-graph \(H_2\) that is \(\mathscr P\)-colorable but not \({\rm rev}(\mathscr P_0)\)-colorable. Applying 7, we obtain a \(k\)-graph \(H\) that is \(\mathscr P\)-colorable but not \(\mathscr P_0\)-colorable. ◻

Proof. Suppose first that there exists a \(k\)-graph \(F\) that is \(\mathscr P_i\)-colorable for every \(i\in[s]\) but not \(\mathscr Q_j\)-colorable for every \(j\in[t]\). Fix \(i\in[s]\) and \(j\in[t]\). Applying 13 with \({\mathscr P}_0={\mathscr Q}_j\) yields the statement that there is no homomorphism from the palette \({\mathscr P}_i\times \prod_{i'\in[s]\setminus\{i\}} {\mathscr P}_{i'}^{\mathcal{S}}\) to \({\mathscr Q}_j\) or to \({\rm rev}({\mathscr Q}_j)\).

For the converse, fix \(j\in[t]\). Applying 13 with \({\mathscr P}_0={\mathscr Q}_j\), we obtain a \(k\)-graph \(F_j\) that is \({\mathscr P}_i\)-colorable for every \(i\in[s]\) but not \({\mathscr Q}_j\)-colorable. Let \(F\) be the disjoint union of \(F_1,\dots,F_t\). Then \(F\) is \({\mathscr P}_i\)-colorable for every \(i\in[s]\) but not \({\mathscr Q}_j\)-colorable for every \(j \in [t]\). ◻

Proof. Let \(N:=R_{(k-1)t}\bigl(tn,\ell^{((k-1)!)^t}\bigr)\). Fix a function \(F:([N]^t)^{k-1}\to[\ell]\). For each \[Y=\llbracket z_1,\dots,z_{(k-1)t}\rrbracket\in \binom{[N]}{(k-1)t},\] write \(y_r^s:=z_{(s-1)(k-1)+r}\) for each \(s\in[t]\) and \(r\in[k-1]\). Thus, for each fixed \(s\), \[y_1^s<\cdots<y_{k-1}^s.\] We color \(Y\) by the function \[\Gamma_Y:(\mathbb{S}_{k-1})^t\to[\ell]\] defined as follows.

Given \((\tau_1,\ldots,\tau_t)\in (S_{k-1})^t\), with \[\tau_s= \begin{pmatrix} 1 & \cdots & k-1\\ \tau_s(1) & \cdots & \tau_s(k-1) \end{pmatrix}\] for each \(s\in[t]\), let \[\mathbf{x}_r=\bigl(y^1_{\tau_1(r)},\ldots,y^t_{\tau_t(r)}\bigr) \in [N]^t\] for each \(r\in[k-1]\).

Set \[\Gamma_Y(\tau_1,\dots,\tau_t):=F(\mathbf{x}_1,\dots,\mathbf{x}_{k-1}).\] Thus each \((k-1)t\)-subset of \([N]\) receives one of \(\ell^{((k-1)!)^t}\) possible colors.

By the choice of \(N\), there exists a subset \(S=\llbracket x_1,\dots, x_{tn}\rrbracket\subseteq[N]\) of size \(tn\) such that every \((k-1)t\)-subset of \(S\) receives the same function, say \(\Gamma\). For each \(s\in[t]\), define \[J_s:=\{x_{(s-1)n+1},\dots,x_{sn}\}.\] Then each \(J_s\) has size \(n\).

Now for each \(r\in[k-1]\), let \(\mathbf{x}_r=(x_r^1,\dots,x_r^t)\in J_1\times\cdots\times J_t\) be as in the statement. For each \(s\in[t]\), the numbers \(x_1^s,\dots,x_{k-1}^s\) are pairwise distinct and belong to \(J_s\), so their union over all \(s\) is a \((k-1)t\)-subset \(Y\subseteq S\). Since every \((k-1)t\)-subset of \(S\) receives the same function \(\Gamma\), we have \(\Gamma_Y=\Gamma\). By construction of \(\Gamma_Y\), if \[\tau_s=\alpha^*[(x_1^s,\dots,x_{k-1}^s)] \text{ for every }s\in[t],\] then \[F(\mathbf{x}_1,\dots,\mathbf{x}_{k-1})=\Gamma_Y(\tau_1,\dots,\tau_t)=\Gamma(\tau_1,\dots,\tau_t).\] This proves the lemma. ◻

Proof. Let \(\mathscr P_s=(\mathcal{C}_s,\mathcal{T}_s)\) be a \(k\)-palette for every \(s\in[t]\cup\{0\}\). Set \[\mathcal{C}^{\times}:=\prod_{s=1}^t \mathcal{C}_s, \qquad m_0:=|\mathcal{C}^{\times}|=\prod_{s=1}^t |\mathcal{C}_s|, \qquad m:=m_0\cdot |\mathcal{C}_0|, \qquad \ell:=|\mathcal{C}_0|^{m_0}, \qquad d_{k-1}:=\frac{1}{2m}.\] Let \(R\) be the integer obtained from 14 with parameters \(k, n=k\), \(t\), and \(\ell\). Choose auxiliary constants satisfying \[{1}/{n_1}\ll {1}/{r}, \delta \ll d_2,\dots,d_{k-2}\ll \delta_{k-1} \ll d_{k-1}, {1}/{k},\] where \(1/d_i\in \mathbb{N}\) for all \(i=2,\dots,k-2\), such that the assumptions of 9 are satisfied with \(k\) replaced by \(k-1\) and \(F=K_k^{(k-1)}\). Set \(\eta=R^{-t}\) and choose \(\delta_{k-1}>0\) sufficiently small such that \[\label{eq:delta-multicase} 2\sqrt{\delta_{k-1}}\,m\,R^{t(k-1)}<1.\tag{14}\] Apply 8 with parameters \(R^t, k-1, m, \eta, \delta_{k-1}, r, \delta\) to obtain integers \(t_0\) and \(n_0\). Next choose \(\varepsilon>0\) sufficiently small such that \[\label{eq:eps-multicase} \varepsilon<\min\left\{\frac{1}{2},\;(1-\eta)t_0^{-(k-1)}\prod_{j=2}^{k-2}d_j^{\binom{k-1}{j}}\right\},\tag{15}\] and let \(N\ge \max\{n_0,n_1\}\) be large enough such that \(R^t\cdot t_0!\mid N\) and \[\label{eq:positive32probability-order} 1-2^{\binom{N}{k-2}}\cdot m_0\cdot e^{-\frac{\varepsilon^3 N^{k-1}}{2m_0}}>0.\tag{16}\]

Let \(G\) be the complete \((k-1)\)-graph on vertex set \([N]\). Partition \([N]\) into equal parts \[[N]=\bigcup_{\mathbf{i}\in[R]^t}U_{\mathbf{i}}, \qquad \mathbf{i}=(i^1,\dots,i^t).\] For each \(s\in[t]\), choose a linear order \(\prec_s\) on \([N]\) such that \[u\prec_s u' \quad\text{whenever}\quad u\in U_{(i_1,\dots,i_t)},\;u'\in U_{(i_1',\dots,i_t')},\;\text{and } i_s<i'_s.\] In particular, we can take \(\prec_1\) to be the natural order on \([N]\).

Now color the edges of \(G\) independently and uniformly at random with colors from \(\mathcal{C}^{\times}\). For every \(\mathbf{c}\in\mathcal{C}^{\times}\), let \(G_{\mathbf{c}}\) denote the spanning subgraph of \(G\) consisting of all edges colored \(\mathbf{c}\). By the same Chernoff-bound argument as in the proof of 6, there exists a coloring \[\mathbf{f}:E(G)\to \mathcal{C}^{\times}\] such that for every \((k-2)\)-graph \(G^{(k-2)}\) on \([N]\) with \(|\mathcal{K}_{k-1}(G^{(k-2)})|\ge \varepsilon N^{k-1}\) and every \(\mathbf{c}\in\mathcal{C}^{\times}\), we have \[\label{eq:random-color-property-multicase} |\mathcal{K}_{k-1}(G^{(k-2)})\cap E(G_{\mathbf{c}})| \ge (1-\varepsilon)\frac{|\mathcal{K}_{k-1}(G^{(k-2)})|}{m_0}.\tag{17}\] Write \[\mathbf{f}=(f_1,\dots,f_t),\] where \(f_s:E(G)\to \mathcal{C}_s\) is the \(s\)-th coordinate coloring.

We now define a \(k\)-graph \(H\) on \([N]\). A \(k\)-set \(e\in\binom{[N]}{k}\) forms an edge of \(H\) if and only if for every \(s\in[t]\), when the vertices of \(e\) are listed in increasing order with respect to \(\prec_s\) as \(w_1^s\prec_s \cdots \prec_s w_k^s\), we have \[\bigl( f_s(e\setminus\{w_1^s\}), f_s(e\setminus\{w_2^s\}), \dots, f_s(e\setminus\{w_k^s\}) \bigr)\in\mathcal{T}_s.\] By construction, \(H^{\prec_1}\) is \(\mathscr P_1\)-colorable, and \(H\) is \(\mathscr P_s\)-colorable for every \(2\le s\le t\). By the assumption of the lemma, \(H^{\prec_1}\) is also \(\mathscr P_0\)-colorable, and let \[f_0:E(G)\to\mathcal{C}_0\] be a coloring witnessing this.

For each \((\mathbf{c},c_0)\in\mathcal{C}^{\times}\times\mathcal{C}_0\), let \(G_{\mathbf{c},c_0}\) be the spanning subgraph of \(G\) with edge set \[E(G_{\mathbf{c},c_0}) = \{e\in E(G):\mathbf{f}(e)=\mathbf{c},\;f_0(e)=c_0\}.\]

Applying 8 to this \((\mathcal{C}^{\times}\times\mathcal{C}_0)\)-colored \((k-1)\)-graph \(G\) with the initial equipartition \(\{U_{\mathbf{i}}: \mathbf{i}\in [R]^{t}\}\), we obtain a family of partitions \(\boldsymbol{\mathcal{P}}=\boldsymbol{\mathcal{P}}(k-2,\mathbf{a})\) where \(a_i=1/d_i\) for \(i=2,\dots,k-2\) and \(1/\eta<a_1<t_0\), such that

1. \(\boldsymbol{\mathcal{P}}\) is \((\eta,\delta(\mathbf{a}),t_0)\)-equitable and \(\mathcal{P}^{(1)}\) refines the partition \(\{U_{\mathbf{i}}:\mathbf{i}\in [R]^{t}\}\);

2. for each \((\mathbf{c},c_0)\in\mathcal{C}^{\times}\times\mathcal{C}_0\), the \((k-1)\)-graph \(G_{\mathbf{c},c_0}\) is \((\delta_{k-1},r(\mathbf{a}))\)-regular with respect to \(\boldsymbol{\mathcal{P}}\).

We say that a \((k-1)\)-tuple of clusters is good for \((\mathbf{c},c_0)\in\mathcal{C}^{\times}\times\mathcal{C}_0\) if \(G_{\mathbf{c},c_0}\) is \((\delta_{k-1},r(\mathbf{a}))\)-regular with respect to all but at most a \(\sqrt{\delta_{k-1}}\)-fraction of the polyads induced on this \((k-1)\)-tuple of clusters. A \((k-1)\)-tuple of clusters is called all-good if it is good for every \((\mathbf{c},c_0)\in\mathcal{C}^{\times}\times\mathcal{C}_0\). Similarly as 10 and 11, we have the following statement.

Since the proof is identical to that of 10 and 11, we omit the proof of 15. Next, fix an \((R^t,k-2)\)-complex \(\{Q^{(i)}\}_{i=1}^{k-2}\) with clusters \(\{V_{\mathbf{i}}:\mathbf{i}\in[R]^t\}\) satisfying 15. For each \(I\in \binom{[R]^t}{k-1}\), define a function \[\phi_I:\mathcal{C}^{\times}\to \mathcal{C}_0\] as follows: for each \(\mathbf{c}\in \mathcal{C}^{\times}\), let \(\phi_I(\mathbf{c})\) be a color in \(\mathcal{C}_0\) maximizing \[\bigl|\mathcal{K}_{k-1}(\hat{Q}_I^{(k-2)})\cap E(G_{\mathbf{c},c_0})\bigr|\] over all \(c_0\in\mathcal{C}_0\).

Let \(\Phi:=\{\phi:\mathcal{C}^{\times}\to\mathcal{C}_0\}\). Then we have \(|\Phi|=\ell\). Define a function \[F_{\mathrm{maj}}:([R]^t)^{k-1}\to\Phi\] as follows: if \(\mathbf{z}_1,\dots,\mathbf{z}_{k-1}\in[R]^t\) pairwise have no common coordinate, then set \[F_{\mathrm{maj}}(\mathbf{z}_1,\dots,\mathbf{z}_{k-1}) := \phi_{\{\mathbf{z}_1,\dots,\mathbf{z}_{k-1}\}}.\] Otherwise, set \(F_{\mathrm{maj}}\) to be an arbitrary function in \(\Phi\).

We identify \(\Phi\) with \([\ell]\) and apply 14 to the function \(F_{\mathrm{maj}}\). Then we obtain pairwise disjoint \(k\)-element sets \(J_1,\dots,J_t\subseteq [R]\) and a function \[\Gamma:(\mathbb{S}_{k-1})^t\to \Phi\] such that \[\label{eq:gamma-multicase} F_{\mathrm{maj}}(\mathbf{z}_1,\dots,\mathbf{z}_{k-1}) = \Gamma(\sigma_1,\dots,\sigma_t)\tag{18}\] whenever each \(\mathbf{z}_r=(z_r^1,\dots,z_r^t)\in J_1\times\cdots\times J_t\) for every \(r\in[k-1]\), any two distinct tuples \(\mathbf{z}_r\) and \(\mathbf{z}_{r'}\) have no common coordinate in any position, and \(\sigma_s=\alpha^*[(z_1^s,\dots,z_{k-1}^s)]\) for every \(s\in[t]\).

For each \(\mathscr P_s^{\mathcal{S}}=(\mathcal{C}_s^{\mathcal{S}},\mathcal{T}_s^{\mathcal{S}})\) and \(x=c^\sigma\in\mathcal{C}_s^{\mathcal{S}}\), we write \[\operatorname{org}_s(x):=c \qquad\text{and}\qquad \operatorname{pat}_s(x):=\sigma.\] Now define \[h:\mathcal{C}_1\times\prod_{s=2}^t \mathcal{C}_s^{\mathcal{S}}\to \mathcal{C}_0\] by \[h(x_1,x_2,\dots,x_t) := \Gamma\bigl(\mathrm{id},\operatorname{pat}_2(x_2),\dots,\operatorname{pat}_t(x_t)\bigr) \bigl(x_1,\operatorname{org}_2(x_2),\dots,\operatorname{org}_t(x_t)\bigr).\] Note that \(\Gamma\bigl(\mathrm{id},\operatorname{pat}_2(x_2),\dots,\operatorname{pat}_t(x_t)\bigr)\in \Phi\), i.e., \(\Gamma\bigl(\mathrm{id},\operatorname{pat}_2(x_2),\dots,\operatorname{pat}_t(x_t)\bigr)\) is a function from \(\mathcal{C}^{\times}\) to \(\mathcal{C}_0\) We claim that \(h\) is a homomorphism from \[\mathscr P_1\times\prod_{s=2}^t \mathscr P_s^{\mathcal{S}}\] to \(\mathscr P_0\).

Let \[(\mathbf{y}_1,\dots,\mathbf{y}_k)\in \mathcal{T}\!\left({\mathscr P}_1\times\prod_{j=2}^t{\mathscr P}_j^{\mathcal{S}}\right)\] and write \(\mathbf{y}_q=(x_{1,q},x_{2,q},\dots,x_{t,q})\) for each \(q\in[k]\). Thus, \((x_{1,1},\dots,x_{1,k})\in \mathcal{T}_1\) and for each \(s\in\{2,\dots,t\}\), \((x_{s,1},\dots,x_{s,k})\in \mathcal{T}_s^{\mathcal{S}}\).

For \(s=1\), set \(\tau_1:=\mathrm{id}\) and \(c_{1,q}:=x_{1,q}\) for each \(q\in[k]\). For each \(s\in\{2,\dots,t\}\), since \((x_{s,1},\dots,x_{s,k})\in \mathcal{T}_s^{\mathcal{S}}\), there exist a permutation \(\tau_s\in \mathbb{S}_k\) and a tuple \((c_{s,1},\dots,c_{s,k})\in \mathcal{T}_s\) such that \[(x_{s,1},\dots,x_{s,k}) = \tau_s\cdot (c_{s,1},\dots,c_{s,k}).\] Equivalently, \[x_{s,q}=c_{s,\tau_s(q)}^{\partial_q\tau_s} \qquad\text{for every } q\in[k].\] Hence \[\label{eq:org-pat-multicase} \operatorname{org}_s(x_{s,q})=c_{s,\tau_s(q)} \qquad\text{and}\qquad \operatorname{pat}_s(x_{s,q})=\partial_q\tau_s \qquad\text{for every } q\in[k].\tag{19}\] For each \(s\in[t]\), write \[J_s=\llbracket j_1^s, j_2^s, \cdots, j_k^s\rrbracket \subseteq [R],\] and define \[i_q^s:=j_{\tau_s(q)}^s \qquad\text{for } q\in[k],\;s\in[t].\] For each \(q\in[k]\), let \[\mathbf{i}_q:=(i_q^1,\dots,i_q^t)\in J_1\times\cdots\times J_t.\] Then for every \(s\in[t]\), \[\alpha^*[(i_1^s,\dots,i_k^s)]=\tau_s.\] In particular, since \(\tau_1=\mathrm{id}\), we have \(i_1^1<i_2^1<\cdots<i_k^1\).

For each \(q\in[k]\), let \[\Lambda_q:=[k]\setminus\{q\} \qquad\text{and}\qquad I_q:=\{\mathbf{i}_r:r\in\Lambda_q\}.\] Note that \(\partial_q\tau_s=\alpha^*[((i_1^s,\dots,i_k^s)\setminus\{i_q^s\})]\)

Recalling the definition of \(\partial_q\tau_s\), deleting the \(q\)-th entry from the sequence \[i_1^s,\dots,i_k^s\] leaves a \((k-1)\)-tuple with pattern \(\partial_q\tau_s\). Therefore, applying 18 to the ordered tuple \((\mathbf{i}_r)_{r\in\Lambda_q}\), taken in the natural order of the indices \(r\), gives \[F_{\mathrm{maj}}\bigl((\mathbf{i}_r)_{r\in\Lambda_q}\bigr) = \Gamma\bigl(\partial_q\tau_1,\partial_q\tau_2,\dots,\partial_q\tau_t\bigr) = \Gamma\bigl(\mathrm{id},\partial_q\tau_2,\dots,\partial_q\tau_t\bigr).\] Since the tuples \(\mathbf{i}_r\) with \(r\in\Lambda_q\) are pairwise distinct, we also have \[F_{\mathrm{maj}}\bigl((\mathbf{i}_r)_{r\in\Lambda_q}\bigr)=\phi_{I_q}.\] Thus \[\label{eq:phiIq} \phi_{I_q} = \Gamma\bigl(\mathrm{id},\partial_q\tau_2,\dots,\partial_q\tau_t\bigr).\tag{20}\]

Now for each \(q\in[k]\), define \[\mathbf{c}_q:= \bigl(x_{1,q},\,\operatorname{org}_2(x_{2,q}),\,\dots,\,\operatorname{org}_t(x_{t,q})\bigr) \in \mathcal{C}^{\times}.\] By 19 and 20 , we have \[\begin{align} h(\mathbf{y}_q) &= \Gamma\bigl(\mathrm{id},\operatorname{pat}_2(x_{2,q}),\dots,\operatorname{pat}_t(x_{t,q})\bigr) \bigl(x_{1,q},\operatorname{org}_2(x_{2,q}),\dots,\operatorname{org}_t(x_{t,q})\bigr) \\ &= \Gamma\bigl(\mathrm{id},\partial_q\tau_2,\dots,\partial_q\tau_t\bigr)(\mathbf{c}_q) \\ &= \phi_{I_q}(\mathbf{c}_q). \end{align}\] By condition [p4] of 10, we have \[|\mathcal{K}_{k-1}(\hat{Q}_{I_q}^{(k-2)})| \ge (1-\eta)\prod_{j=1}^{k-2}\left(\frac{1}{a_j}\right)^{\binom{k-1}{j}}N^{k-1}\ge \varepsilon N^{k-1},\] where the last inequality follows from 15 . Therefore, by 17 , \[|\mathcal{K}_{k-1}(\hat{Q}_{I_q}^{(k-2)})\cap E(G_{\mathbf{c}_q})| \ge (1-\varepsilon) \frac{|\mathcal{K}_{k-1}(\hat{Q}_{I_q}^{(k-2)})|}{m_0}.\] Since \(\phi_{I_q}(\mathbf{c}_q)=h(\mathbf{y}_q)\) is chosen as a majority \(f_0\)-color among those members of \(\mathcal{K}_{k-1}(\hat{Q}_{I_q}^{(k-2)})\) whose \(\mathbf{f}\)-color is \(\mathbf{c}_q\), we obtain \[d\bigl(G_{\mathbf{c}_q,h(\mathbf{y}_q)}\mid \hat{Q}_{I_q}^{(k-2)}\bigr) \ge \frac{1-\varepsilon}{m_0|\mathcal{C}_0|} = \frac{1-\varepsilon}{m} \ge d_{k-1}.\] Moreover, by 15, the \((k-1)\)-graph \(G_{\mathbf{c}_q,h(\mathbf{y}_q)}\) is \((\delta_{k-1},r(\mathbf{a}))\)-regular with respect to \(\hat{Q}_{I_q}^{(k-2)}\) for every \(q\in[k]\).

Now consider the \((k-1)\)-graph \[G':=\bigcup_{q=1}^k G_{\mathbf{c}_q,h(\mathbf{y}_q)} \Bigl[\bigcup_{r\in\Lambda_q}V_{\mathbf{i}_r}\Bigr].\] By 9, \(G'\) contains a copy of \(K_k^{(k-1)}\) on the clusters \(V_{\mathbf{i}_1},V_{\mathbf{i}_2},\dots,V_{\mathbf{i}_k}\). Let this copy correspond to vertices \(v_q\in V_{\mathbf{i}_q}\) for \(q\in[k]\). Since \(i_1^1<i_2^1<\cdots<i_k^1\) and \(\prec_1\) is the natural order, we have \(v_1<v_2<\cdots<v_k\). Set \(e:=\{v_1,\dots,v_k\}\). For each \(q\in[k]\), the \((k-1)\)-set \(e\setminus\{v_q\}\) belongs to \(G_{\mathbf{c}_q,h(\mathbf{y}_q)}\), so its \(\mathbf{f}\)-color is \(\mathbf{c}_q\) and its \(f_0\)-color is \(h(\mathbf{y}_q)\).

We now verify that \(e\in E(H)\). Fix \(s\in[t]\). Because \(\alpha^*[(i_1^s,\dots,i_k^s)]=\tau_s\), the increasing rearrangement of the numbers \(i_1^s,\dots,i_k^s\) is \[i_{\tau_s^{-1}(1)}^s<i_{\tau_s^{-1}(2)}^s<\cdots<i_{\tau_s^{-1}(k)}^s.\] Hence the vertices of \(e\) are ordered by \(\prec_s\) as \[v_{\tau_s^{-1}(1)}\prec_s v_{\tau_s^{-1}(2)}\prec_s \cdots \prec_s v_{\tau_s^{-1}(k)}.\] For each \(j\in[k]\), let \(q=\tau_s^{-1}(j)\). Then the \(s\)-th coordinate of the vector \(\mathbf{c}_q\) is \[\begin{cases} x_{1,q}=c_{1,j}, & \text{if } s=1,\\[1ex] \operatorname{org}_s(x_{s,q})=c_{s,\tau_s(q)}=c_{s,j}, & \text{if } s\ge 2. \end{cases}\] Therefore \[f_s(e\setminus\{v_{\tau_s^{-1}(j)}\})=c_{s,j} \qquad\text{for every } j\in[k].\] It follows that \[\bigl( f_s(e\setminus\{v_{\tau_s^{-1}(1)}\}), f_s(e\setminus\{v_{\tau_s^{-1}(2)}\}), \dots, f_s(e\setminus\{v_{\tau_s^{-1}(k)}\}) \bigr) = (c_{s,1},c_{s,2},\dots,c_{s,k}) \in \mathcal{T}_s.\] Since this holds for every \(s\in[t]\), the definition of \(H\) gives \(e\in E(H)\).

Finally, \(v_1<\cdots<v_k\) and \(f_0\) witnesses that \(H^{\prec_1}\) is \(\mathscr P_0\)-colorable, so \[\bigl(h(\mathbf{y}_1),h(\mathbf{y}_2),\dots,h(\mathbf{y}_k)\bigr)\in \mathcal{T}_0.\] Therefore, \(h\) is a homomorphism from \(\mathscr P_1\times\prod_{s=2}^t \mathscr P_s^{\mathcal{S}}\) to \(\mathscr P_0\). ◻

Proof. Fix the \(k\)-palettes \(\mathscr{P}_s = (\mathcal{C}_s, \mathcal{T}_s)\) for \(s \in [t] \cup \{0\}\) and the ordered \(k\)-graphs \(H_s^+\) and \(H_s^-\) for \(s \in [t]\), as in the statement of the lemma. Let \[c:=\max \{|\mathcal{C}_s|:s\in[t]\}, \qquad n:=\max\bigl\{|V(H_s^+)|,\;|V(H_s^-)|:s\in[t]\bigr\}, \qquad p:=c^{-t n^{k-1}}.\] Apply 9 with \(n\) and \(t\) to obtain an integer \(R\). Choose \(N\) sufficiently large such that \[\label{eq:random-multicase} N!\cdot (1-p)^{N^2/(R^{4t}(R^t!)^t)}<1.\tag{21}\] Such an \(N\) exists because \(N!\) is at most \(e^{N \log N}\) and the integers \(c, n, t\) and \(R\) are fixed.

We now define a random \(k\)-graph \(H\) on the vertex set \([N]\). First choose linear orders \(\prec_1, \dots, \prec_t\) on \([N]\) independently and uniformly at random. Next, for each \((k-1)\)-subset \(X\in\binom{[N]}{k-1}\) choose independently and uniformly a color vector \[\mathbf{f}(X)=\bigl(f_1(X),\dots,f_t(X)\bigr)\in \mathcal{C}_1\times\cdots\times\mathcal{C}_t.\] Finally, a \(k\)-subset \(e=\{v_1,\dots,v_k\}\subset [N]\) forms an edge of \(H\) if and only if for every \(s\in[t]\), when the vertices of \(e\) are listed in increasing order with respect to \(\prec_s\) as \(v_1'\prec_s \dots \prec_s v'_k\), we have \[(f_s(e\backslash\{v_1'\}),f_s(e\backslash\{v_{2}'\}),\dots,f_s(e\backslash\{v_k'\}))\in\mathcal{T}_s.\] By construction, the resulting \(k\)-graph \(H\) is \(\mathscr P_s\)-colorable for every \(s\in[t]\).

We now show that with positive probability \(H\) is not \(\mathscr P_0\)-colorable. Let \(L\) be a linear \(R^t\)-graph on \([N]\) with the maximum possible number of edges. Since an \(R^t\)-edge can intersect fewer than \[\binom{R^t}{2}\binom{N-2}{R^t-2}\] other \(R^t\)-edges in the complete \(R^t\)-graph on \([N]\), we have \[|E(L)|\ge \frac{\binom{N}{R^t}}{\binom{R^t}{2}\binom{N-2}{R^t-2}} = \frac{2N(N-1)}{R^{2t}(R^t-1)^2} \ge \frac{N^2}{R^{4t}}.\] Enumerate the edges of \(L\) as \(F_1,\dots,F_m\) with \(m:=|E(L)|\). Index the vertices of each \(F_i\) by the set \([R]^t\), writing \(F_i=\{v_{\mathbf{j}}^i:\mathbf{j}\in[R]^t\}\). For each \(i\in[m]\) and each \(s\in[t]\), let \(E_s^i\) be the event that the order \(\prec_s\) is consistent with the \(s\)-th coordinate on \(F_i\), that is, \[v_{\mathbf{j}}^i\prec_s v_{\mathbf{j}'}^i \qquad\text{whenever}\qquad j_s<j_s'.\] Since among the \((R^t)!\) possible orders of the vertices of \(F_i\) at least one has this property, we have \[\mathbb{P}(E_s^i)\ge \frac{1}{(R^t)!}.\] Since the orders \(\prec_1,\dots,\prec_t\) are chosen independently, we have \[\mathbb{P}\Bigl(\bigcap_{s=1}^t E_s^i\Bigr)\ge \frac{1}{(R^t!)^t}.\] We call \(F_i\) good if all events \(E_s^i\) occur. Hence the expected number of good sets is at least \[m\cdot \frac{1}{(R^t!)^t} \ge \frac{N^2}{R^{4t}(R^t!)^t}.\] Therefore there exists a choice of the orders \(\prec_1,\dots,\prec_t\) for which the number of good sets is at least \[M:=\frac{N^2}{R^{4t}(R^t!)^t}.\] Fix such a choice of the orders. From now on, only the color vectors \(\mathbf{f}(X)\) remain random.

Fix any linear order \(\prec\) on \([N]\). For each good set \(F_i\), identify it with \([R]^t\) via the above indexing and apply 9 to the order \(\prec\) restricted to \(F_i\). Then there exist \(n\)-element sets \(J_1, \ldots, J_t \subseteq [R]\), a permutation \(\sigma\) of \([t]\), and a sign function \(\zeta:[t]\to\{-1,+1\}\) such that the restriction of \(\prec\) to \(J_1\times\cdots\times J_t\) is lexicographic in the signed permuted coordinates \(\bigl(\zeta(1)x_{\sigma(1)},\dots,\zeta(t)x_{\sigma(t)}\bigr)\). In particular, on the vertices of \(F_i\) indexed by \(J_1\times\cdots\times J_t\), one of the following the conclusions holds:

• if \(\zeta(1)=1\), \(v_{\mathbf{j}}^i \prec v_{\mathbf{j}'}^i\) for \(\mathbf{j}=(j_1,\ldots,j_t)\), \(\mathbf{j}'=(j_1',\ldots,j_t') \in J_1 \times \cdots \times J_t\) with \(j_{\sigma(1)} < j_{\sigma(1)}'\);

• if \(\zeta(1)=-1\), \(v_{\mathbf{j}}^i \prec v_{\mathbf{j}'}^i\) for \(\mathbf{j}=(j_1,\ldots,j_t)\), \(\mathbf{j}'=(j_1',\ldots,j_t') \in J_1 \times \cdots \times J_t\) with \(j_{\sigma(1)} > j_{\sigma(1)}'\).

We now choose one of the ordered \(k\)-graphs \(H_{\sigma(1)}^+\) and \(H_{\sigma(1)}^-\) depending on the sign of \(\zeta(1)\). If \(\zeta(1)=+1\), let \(G:=H_{\sigma(1)}^+\). If \(\zeta(1)=-1\), let \(G:=H_{\sigma(1)}^-\). For each \(s\in[t]\), choose an ordering \(<_s\) of \(V(G)\) as follows:

• if \(s=\sigma(1)\), take the given order of \(G\) witnessing that \(G\) is \(\mathscr P_{\sigma(1)}\)-colorable;

• if \(s\neq \sigma(1)\), choose any order of \(V(G)\) witnessing that the \(k\)-graph \(\widetilde{G}\) is \(\mathscr P_s\)-colorable.

Since \(|J_s|=n\ge |V(G)|\) for every \(s\in[t]\), we choose, for each \(s\in[t]\), an injective map \(\iota_s:V(G)\to J_s\) that preserves the order \(<_s\). For each vertex \(w\in V(G)\), set \[\mathbf{j}(w):=\bigl(\iota_1(w),\dots,\iota_t(w)\bigr)\in J_1\times\cdots\times J_t.\] Since \(F_i\) is good, for each \(s\in[t]\) the order \(\prec_s\) on the vertices \(\{v_{\mathbf{j}(w)}^i: w\in V(G)\}\) agrees with the chosen order \(<_s\). Thus, if the random color vectors on all \((k-1)\)-subsets of these vertices match the witness colorings for \(\mathscr P_s\)-colorable of \(G\) described above, then there exists a copy of \(G\) on the vertices \(\{v_{\mathbf{j}(w)}^i: w\in V(G)\}\). Note that this happens with probability at least \[\prod_{j=1}^t |\mathcal{C}_j|^{-\binom{|V(G)|}{k-1}} \geq \prod_{j=1}^t |\mathcal{C}_j|^{-n^{k-1}} \geq c^{-tn^{k-1}}=p.\]

If \(\zeta(1)=+1\), then the order \(\prec\) on these vertices agrees with the \(\sigma(1)\)-th coordinate order. Thus, \(H^{\prec}[F_i]\) contains an ordered copy of \(H_{\sigma(1)}^+\). Since \(H_{\sigma(1)}^+\) is not \(\mathscr P_0\)-colorable, this implies that \(H^{\prec}[F_i]\) is not \(\mathscr P_0\)-colorable. If \(\zeta(1)=-1\), then the order \(\prec\) on these vertices is the reverse of the \(\sigma(1)\)-th coordinate order. Let \(\rm{rev}(H_{\sigma(1)}^{-})\) denote the ordered \(k\)-graph obtained from \(H_{\sigma(1)}^{-}\) by reversing its linear order. Then \(H^{\prec}[F_i]\) contains an ordered copy of \(\rm{rev}(H_{\sigma(1)}^{-})\). Since \(\rm{rev}(H_{\sigma(1)}^{-})\) is not \(\mathscr P_0\)-colorable, this again implies that \(H^{\prec}[F_i]\) is not \(\mathscr P_0\)-colorable. Therefore, for every good set \(F_i\), we have \[\mathbb{P}\bigl(H^{\prec}[F_i]\text{ is }\mathscr P_0\text{-colorable}\bigr)\le 1-p.\]

Since the events \(\bigl\{H^{\prec}[F_i]\text{ is }\mathscr P_0\text{-colorable}\bigr\}\) over all good sets \(F_i\) are independent, we obtain \[\mathbb{P}\bigl(H^{\prec}\text{ is }\mathscr P_0\text{-colorable}\bigr)\le (1-p)^M.\]

Finally, taking the union bound over all \(N!\) linear orders on \([N]\), we conclude that \[\mathbb{P}\bigl(H\text{ is }\mathscr P_0\text{-colorable}\bigr) \le N!\cdot (1-p)^M < 1\] by 21 . Therefore, with positive probability, the random \(k\)-graph \(H\) is \(\mathscr P_s\)-colorable for every \(s\in[t]\) but not \(\mathscr P_0\)-colorable. ◻

Proof of 13. Suppose first that there exists a \(k\)-graph \(H\) that is \(\mathscr P_i\)-colorable for every \(i\in[t]\) but not \(\mathscr P_0\)-colorable. Fix \(j\in[t]\). Let \(\prec\) be an order witnessing that \(H\) is \(\mathscr P_j\)-colorable. By 12, for every \(i\in[t]\setminus\{j\}\), the ordered \(k\)-graph \(H^\prec\) is \(\mathscr P_i^{\mathcal{S}}\)-colorable. Hence \(H^\prec\) is colorable by the \(k\)-palette \(\mathscr P_j\times\prod_{i\in[t]\setminus\{j\}}\mathscr P_i^{\mathcal{S}}\). If there exists a homomorphism from this \(k\)-palette to \(\mathscr P_0\), then \(H\) would be \(\mathscr P_0\)-colorable, a contradiction. Thus, no such homomorphism exists.

Conversely, suppose that for every \(j\in[t]\), there is no homomorphism from \(\mathscr P_j\times\prod_{i\in[t]\setminus\{j\}}\mathscr P_i^{\mathcal{S}}\) to \(\mathscr P_0\) or to \({\rm rev}(\mathscr P_0)\). Fix \(i\in [t]\). By 8, there exists an ordered \(k\)-graph \(H_i^{+}\) that is \({\mathscr P}_i\)-colorable but not \({\mathscr P}_0\)-colorable, and \(\widetilde{H}_i^{+}\) is \({\mathscr P}_{i'}\)-colorable, for every \(i' \in [t] \setminus \{i\}\). Applying the same contrapositive of 8 with \({\rm rev}(\mathscr P_0)\), there exists an ordered \(k\)-graph \(H_i^{-}\) that is \({\mathscr P}_i\)-colorable but not \({\rm rev}({\mathscr P}_0)\)-colorable, and \(\widetilde{H}_i^{-}\) is \({\mathscr P}_{i'}\)-colorable for every \(i' \in [t] \setminus \{i\}\).

Thus, the hypotheses of 10 are satisfied. By 10, there exists a \(k\)-graph \(H\) that is \({\mathscr P}_i\)-colorable for every \(i \in [t]\) but not \({\mathscr P}_0\)-colorable. ◻

Proof. By 13, condition [palette32step321] gives a \(k\)-graph \(F\) that is \(\mathscr P_i\)-colorable for every \(i\in[t]\) but is not \(\mathscr P_0\)-colorable. Hence, by 1, \[\pi_{k-2}(F)=\pi_k^{\rm pal}(F)\ge d(\mathscr P_0)=\alpha .\] On the other hand, let \(\mathscr P\) be any \(k\)-palette with \(d(\mathscr P)>\alpha\). By condition [palette32step322], there exists \(i\in[t]\) such that \(\mathscr P_i\) admits a homomorphism to \(\mathscr P\) or to \({\rm rev}(\mathscr P)\). Since \(F\) is \(\mathscr P_i\)-colorable, it follows that \(F\) is \(\mathscr P\)-colorable; in the second case, we can reverse the vertex order witnessing the \({\rm rev}(\mathscr P)\)-coloring. Thus, no \(k\)-palette of density greater than \(\alpha\) contributes to the supremum in \(\pi_k^{\rm pal}(F)\). Again using 1, we get \(\pi_{k-2}(F)=\pi_k^{\rm pal}(F)\le \alpha\). ◻

Proof. For each vertex \(v\in V(D)\), let \(\ell(v)\) be the maximum length of a directed walk ending at \(v\). Since there is no directed walk of length \(r\), we have \(\ell(v)\in\{0,1,\dots,r-1\}\). Let \(L_i=\{v\in V(D):\ell(v)=i\}\) for each \(0\le i\le r-1\). Note that every arc goes from some \(L_i\) to some \(L_j\) with \(i<j\). Hence, \[|E(D)| \le \sum_{0\le i<j\le r-1}|L_i||L_j| = \frac{1}{2}\left(n^2-\sum_{i=0}^{r-1}|L_i|^2\right) \le \frac{1}{2}\left(n^2-\frac{n^2}{r}\right) = \frac{r-1}{2r}n^2.\] ◻

Proof of 3. We prove each value in 3 by 11, respectively.

(1) Proving \(\frac{r-1}{r}\in \Pi^{(k)}_{\rm u}\). Let \[\mathscr P_0=([r],\mathcal{T}_0), \qquad \mathcal{T}_0=\{(x_1,\dots,x_k)\in[r]^k:x_1\ne x_2\}.\] Then \(d(\mathscr P_0)=(r-1)/r\). Let \(T_{r+1}\) and \(T'_{r+1}\) be two disjoint transitive tournaments with \(V(T_{r+1})=\{p_1,\dots,p_{r+1}\}\) and \(V(T'_{r+1})=\{q_1,\dots,q_{r+1}\}\). Define a \(k\)-palette \(\mathscr P_1=(\mathcal{C}_1,\mathcal{T}_1)\) as follows. For every arc \(p_ap_b\) of \(T_{r+1}\) with \(a<b\), put one \(k\)-tuple \((p_a, p_b, \alpha^{ab}_3,\dots, \alpha^{ab}_k)\) into \(\mathcal{T}_1\), where all filler colors are pairwise distinct. For every arc \(q_aq_b\) of \(T'_{r+1}\) with \(a<b\), put one \(k\)-tuple \((\beta^{ab}_1,\dots,\beta^{ab}_{k-2},q_a,q_b)\) into \(\mathcal{T}_1\), again using new pairwise distinct filler colors. \(\mathcal{C}_1\) consists of all colors in the \(k\)-tuples of \(\mathcal{T}_1\).

We first verify condition [palette32step321] of 11. There is no homomorphism from \(\mathscr P_1\) to \(\mathscr P_0\). Indeed, any map from \(\{p_1,\dots,p_{r+1}\}\) to \([r]\) identifies two vertices, and the corresponding arc of \(T_{r+1}\) is mapped to a \(k\)-tuple whose first two coordinates are equal, which is forbidden in \(\mathcal{T}_0\). Similarly, there is no homomorphism from \(\mathscr P_1\) to \({\rm rev}(\mathscr P_0)\), using the arc of \(T'_{r+1}\) and the last two coordinates.

Next, we verify condition [palette32step322] of 11. Let \(\mathscr P=(\mathcal{C},\mathcal{T})\) be a \(k\)-palette with \(d(\mathscr P)>(r-1)/r\). Define two auxiliary digraphs \(L\) and \(R\) on \(\mathcal{C}\) by \[ab\in E(L) \quad\Longleftrightarrow\quad \text{there exists }(x_1,\dots,x_k)\in\mathcal{T} \text{ with }x_1=a,\;x_2=b,\] and \[ab\in E(R) \quad\Longleftrightarrow\quad \text{there exists }(x_1,\dots,x_k)\in\mathcal{T} \text{ with }x_{k-1}=a,\;x_k=b.\] Since \(|\mathcal{T}|\le |E(L)|\cdot|\mathcal{C}|^{k-2}\) and \(|\mathcal{T}|\le |E(R)|\cdot|\mathcal{C}|^{k-2}\), we have \(|E(L)|, |E(R)|>\frac{r-1}{r}|\mathcal{C}|^2\). Combined with 12, both \(L\) and \(R\) either contain a loop or a transitive tournament of \(r+1\) vertices. If \(L\) contains a loop, then there is a map from \(\mathcal{C}_1\) to \(\mathcal{C}\) by sending all vertices \(p_1,\dots,p_{r+1}\) to the loop vertex and using a witnessing admissible tuple for each arc. If \(L\) contains a copy of \(T_{r+1}\), map \(p_1,\dots,p_{r+1}\) to the vertices of this copy in the transitive order. Since all other colors in the admissible tuples associated with \(T_{r+1}\) are distinct, this gives a homomorphism from the first tournament gadget to \(\mathscr P\). By symmetry, if \(R\) contains a loop or a transitive tournament of \(r+1\) vertices, we similarly obtain a homomorphism from the second tournament gadget to \(\mathscr P\). Since the two parts of \(\mathscr P_1\) use distinct colors, these two maps combine to a homomorphism from \(\mathscr P_1\) to \(\mathscr P\).

Thus, the two conditions of 11 hold with \(t=1\) and \(\alpha=(r-1)/r\), implying \(\alpha=(r-1)/r \in \Pi^{(k)}_{\rm u}\).

For \(k=3\), this value was obtained in [31]. We give the proof for \(k\ge4\). Let \[\mathscr P_0=([r],\mathcal{T}_0),\qquad \mathcal{T}_0= \{(x_1,\dots,x_k)\in[r]^k:x_1\ne x_2 \text{ and }x_{k-1}\ne x_k\}.\] Since the two constrained pairs of coordinates are disjoint for \(k\ge4\), we have \(d(\mathscr P_0)=\frac{(r-1)^2}{r^2}\). Moreover, \(\mathscr P_0={\rm rev}(\mathscr P_0)\).

Let \(T_{r+1}\) be a transitive tournament on vertices \(p_1,\dots,p_{r+1}\). Define a \(k\)-palette \(\mathscr P_1=(\mathcal{C}_1,\mathcal{T}_1)\) as follows. For every arc \(p_ap_b\) of \(T_{r+1}\) with \(a<b\), put one \(k\)-tuple \((p_a, p_b, \alpha^{ab}_3,\dots, \alpha^{ab}_k)\) into \(\mathcal{T}_1\), where all filler colors are pairwise distinct. Let \(\mathcal{C}_1\) be the set of all colors appearing in these tuples.

There is no homomorphism from \(\mathscr P_1\) to \(\mathscr P_0\). Indeed, any map from \(\{p_1,\dots,p_{r+1}\}\) to \([r]\) identifies two vertices, say \(p_a\) and \(p_b\) with \(a<b\). Since \(p_ap_b\) is an arc of \(T_{r+1}\), the corresponding admissible tuple of \(\mathscr P_1\) is mapped to a tuple whose first two coordinates are equal, which is forbidden in \(\mathcal{T}_0\). Since \(\mathscr P_0={\rm rev}(\mathscr P_0)\), the same argument excludes homomorphisms to \({\rm rev}(\mathscr P_0)\).

Let \(\mathscr P=(\mathcal{C},\mathcal{T})\) be a \(k\)-palette with \(d(\mathscr P)>\frac{(r-1)^2}{r^2}\). Define two digraphs \(L\) and \(R\) on \(\mathcal{C}\) by recording the first pair and the last pair of an admissible tuple: \[ab\in E(L) \Longleftrightarrow \text{there exists }(x_1,\dots,x_k)\in\mathcal{T}\text{ with }x_1=a,\;x_2=b,\] and \[ab\in E(R) \Longleftrightarrow \text{there exists }(x_1,\dots,x_k)\in\mathcal{T}\text{ with }x_{k-1}=a,\;x_k=b.\] Since the first two coordinates and the last two coordinates of admissible tuples are disjoint, we have \[|\mathcal{T}|\le |E(L)|\cdot|E(R)|\cdot|\mathcal{C}|^{k-4}.\] Hence, at least one of \(L\) and \(R\) has more than \(\frac{r-1}{r}|\mathcal{C}|^2\) arcs.

If \(L\) has this many arcs, then, as in the previous case, either \(L\) has a loop or it contains a copy of \(T_{r+1}\); in both cases \(\mathscr P_1\) admits a homomorphism to \(\mathscr P\). If \(R\) has this many arcs, then the similar argument applied to the first two coordinates of \({\rm rev}(\mathscr P)\) shows that \(\mathscr P_1\) admits a homomorphism to \({\rm rev}(\mathscr P)\).

Applying 11, we obtain \(\frac{(r-1)^2}{r^2}\in\Pi_{\rm u}^{(k)}\) for every \(k\ge4\). Together with the cited \(k=3\) case, this proves the assertion for all \(k\ge3\).

(3) Proving \(\frac{r-1}{2r}\in \Pi^{(k)}_{\rm u}\). Let \[\mathscr P_0=([r],\mathcal{T}_0), \qquad \mathcal{T}_0=\{(x_1,\dots,x_k)\in[r]^k:x_1<x_k\}.\] Then \(d(\mathscr P_0)=\frac{1}{2}-\frac{1}{2r}\). Let \(\mathscr P_1=(\mathcal{C}_1,\mathcal{T}_1)\) be the \(k\)-palette with \(|\mathcal{C}_1|=r(k-1)+1\) and \(\mathcal{T}_1=\{(c_i, c^i_1, \dots, c^i_{k-2}, c_{i+1}): i\in[r]\}\), where \[c_1,\ldots,c_{r+1}, c^1_1,\ldots,c^1_{k-2},\ldots, c^r_1,\ldots,c^r_{k-2}\] are pairwise distinct. There is no homomorphism from \(\mathscr P_1\) to \(\mathscr P_0\) or to \({\rm rev}(\mathscr P_0)\), since such a homomorphism would give a strictly increasing, respectively strictly decreasing, sequence of length \(r+1\) in \([r]\).

Let \(\mathscr P=(\mathcal{C},\mathcal{T})\) be a \(k\)-palette with \(d(\mathscr P)>\frac{1}{2}-\frac{1}{2r}\). Next, we prove that there is a homomorphism from \(\mathscr{P}_1\) to \(\mathscr{P}\). Define a digraph \(D\) on vertex set \(\mathcal{C}\) by putting an arc \(a\to b\) whenever some admissible \(k\)-tuple in \(\mathcal{T}\) has first coordinate \(a\) and last coordinate \(b\). If there is no homomorphism from \(\mathscr{P}_1\) to \(\mathscr{P}\), then \(D\) contains no directed walk of length \(r\). By 13, we have \[\begin{align} d(\mathscr{P})&\leq\frac{|\mathcal{C}|^{k-2}|E(D)|}{|\mathcal{C}|^{k}} \leq\frac{r-1}{2r}, \end{align}\] which leads to a contradiction. By 11, we obtain \(\frac{r-1}{2r}\in\Pi_{\rm u}^{(k)}\) for every \(k\ge3\).

(4) Proving \(\frac{(k-1)^k}{k^k}\in \Pi^{(k)}_{\rm u}\). Let \[\mathscr P_0=([k],\mathcal{T}_0), \qquad \mathcal{T}_0=\{(x_1,\dots,x_k)\in[k]^k: x_i\ne i\text{ for all }i\in[k]\}.\] Then \(d(\mathscr P_0)=\frac{(k-1)^k}{k^k}\). Let \(\mathscr{P}_1=(\mathcal{C}_1, \mathcal{T}_1)\) be a \(k\)-palette with one special color \(a\) and \[\mathcal{T}_1=\{A_i=(c^i_1,\ldots,c^i_{i-1},a,c^i_{i+1},\ldots,c^i_k): i\in[k]\},\] where all colors other than \(a\) are pairwise distinct.

If there is a homomorphism \(f:\mathcal{C}_1 \to [k]\). Let \(f(a)=s\in[k]\). Then we have \[(f(c^s_1),\dots,f(c^s_{s-1}),f(a),f(c^s_{s+1}), \dots,f(c^s_{k}))\in \mathcal{T}_0,\] which leads to a contradiction. Thus, there is no homomorphism from \(\mathscr{P}_1\) to \(\mathscr{P}_0\). Similarly, there is no homomorphism from \(\mathscr P_1\) to \({\rm rev}(\mathscr P_0)\). Since \[{\rm rev}(\mathcal{T}_0) = \{(y_1,\dots,y_k)\in[k]^k:y_i\ne k+1-i\text{ for all }i\in[k]\},\] if \(f(a)=s\), then the admissible tuple of \(\mathscr P_1\) in which \(a\) appears in coordinate \(k+1-s\) is mapped to a tuple whose \((k+1-s)\)-th coordinate is \(s\), which is forbidden in \({\rm rev}(\mathscr P_0)\).

Next, we prove that for every \(k\)-palette \(\mathscr{P}=(\mathcal{C}, \mathcal{T})\) with \(d(\mathscr{P})>\frac{(k-1)^k}{k^k}\) there exists a homomorphism from \(\mathscr{P}_1\) to \(\mathscr{P}\). Suppose for a contradiction that no such homomorphism exists. For each \(i\in[k]\), define \[L_i:=\{x\in \mathcal{C}:x~ \text{is the}~ i\text{-th coordinate of some } k\text{-tuple in}~ \mathcal{T}\}.\] We claim that \(\bigcap_{i=1}^kL_i=\emptyset\). Otherwise, let \(c\in \bigcap_{i=1}^k L_i\). Then \(f(a)=c\) can be extended to a homomorphism from \(\mathscr{P}_1\) to \(\mathscr{P}\), since all other colors in \(\mathcal{C}_1\setminus\{a\}\) appear only once in some \(k\)-tuple in \(\mathcal{T}_1\). If the intersection is empty, then every color belongs to at most \(k-1\) of the sets \(L_i\), so \(\sum_{i=1}^k |L_i|\le (k-1)|\mathcal{C}|\). Consequently, \[\begin{align} d(\mathscr{P}) \leq \frac{\prod_{i=1}^k |L_i|}{|\mathcal{C}|^k}\leq \frac{(\sum_{i=1}^k |L_i|)^k}{(k|\mathcal{C}|)^k}\le \frac{(k-1)^k}{k^k}, \end{align}\] which leads to a contradiction. By 11, we obtain \(\frac{(k-1)^k}{k^k}\in\Pi_{\rm u}^{(k)}\) for every \(k\ge3\).

Let \(\mathcal{C}_0=\mathcal{C}'_0\dot{\cup} \mathcal{C}''_0\) with \(|\mathcal{C}'_0|=2\) and \(|\mathcal{C}''_0|=k-2\). Define \(\mathscr P_0=(\mathcal{C}_0,\mathcal{T}_0)\) by \[\mathcal{T}_0= \{(x_1,\dots,x_k)\in\mathcal{C}_0^k: x_1,x_k\in \mathcal{C}'_0,\;x_2,\dots,x_{k-1}\in \mathcal{C}''_0\}.\] Then \(d(\mathscr P_0)= \frac{|\mathcal{C}'_0|^2|\mathcal{C}''_0|^{k-2}}{(|\mathcal{C}'_0|+|\mathcal{C}''_0|)^k} = \frac{4(k-2)^{k-2}}{k^k}\). Moreover, \(\mathscr P_0={\rm rev}(\mathscr P_0)\). For each \(i\in\{2,\dots,k-1\}\), define a \(k\)-palette \(\mathscr{P}_i=(\mathcal{C}_i,\mathcal{T}_i)\) with one special color \(a_i\) and two admissible tuples \((a_i,\alpha^i_2,\dots,\alpha^i_k)\) and \((\beta^i_1,\dots,\beta^i_{i-1},a_i,\beta^i_{i+1},\dots,\beta^i_k)\), where all colors other than \(a_i\) are pairwise distinct.

We verify condition [palette32step321] of 11. For each \(i\), there is no homomorphism from \(\mathscr P_i\) to \(\mathscr P_0\) or to \({\rm rev}(\mathscr P_0)\), since the special color \(a_i\) appears once in an endpoint coordinate and once in a middle coordinate, while \(\mathcal{C}'_0\) and \(\mathcal{C}''_0\) are disjoint.

We claim that, for any \(i,j\in\{2,\dots,k-1\}\), there is a homomorphism from \(\mathscr P_i\) to \(\mathscr P_j^{\mathcal{S}}\). Indeed, in the symmetrization of \(\mathscr P_j\), the special color \(a_j\) can be placed, with the same superscript, in any prescribed coordinate of either of the two symmetrized admissible tuples. This follows directly from the fact that, for fixed \(p,q\in[k]\) and fixed \(\sigma\in\mathbb{S}_{k-1}\), there is a unique \(\tau\in\mathbb{S}_k\) such that \(\tau(p)=q\) and \(\partial_p\tau=\sigma\). Since all other colors of \(\mathscr P_i\) are new, the desired homomorphism extends arbitrarily over them. Consequently, \(\mathscr P_i\) admits a homomorphism to \[\mathscr P_i\times \prod_{j\in[k]\setminus\{1,i,k\}}\mathscr P_j^{\mathcal{S}}\] by using the identity map in the \(\mathscr P_i\)-coordinate and the above homomorphisms in all other coordinates. Hence any homomorphism from this mixed product to \(\mathscr P_0\) or to \({\rm rev}(\mathscr P_0)\) would imply a homomorphism from \(\mathscr P_i\) to \(\mathscr P_0\) or to \({\rm rev}(\mathscr P_0)\), a contradiction.

We verify condition [palette32step322] of 11. Let \(\mathscr{P}=(\mathcal{C},\mathcal{T})\) be a \(k\)-palette with \(d(\mathscr{P})>\frac{4(k-2)^{k-2}}{k^k}\). We claim that there is a homomorphism from some \(\mathscr{P}_i\) to \(\mathscr{P}\) or to \({\rm rev}(\mathscr{P})\) for \(i\in\{2,\dots,k-1\}\). If not, for each \(j\in [k]\) let \[C_j:= \{c\in\mathcal{C}:\text{ there exists }(x_1,\dots,x_k)\in\mathcal{T} \text{ with }x_j=c\}.\] Then for every \(i\in\{2,\dots,k-1\}\), \(C_1\cap C_i=\emptyset\) and \(C_k\cap C_i=\emptyset\). Therefore every middle coordinate of every admissible tuple of \(\mathscr P\) lies in \(\mathcal{C}\setminus \bigl(C_1\cup C_k\bigr)\). Set \(n=|\mathcal{C}|\) and \(x=|C_1\cup C_k|/n\). Then we have \[d(\mathscr{P})\leq\frac{\prod_{i=1}^k|C_i|}{|\mathcal{C}|^k}\leq \frac{|C_1||C_k|(|\mathcal{C}|-|C_1\cup C_k|)^{k-2}}{|\mathcal{C}|^k}\leq x^2(1-x)^{k-2}.\] Since \[\max_{0\le x\le1}x^2(1-x)^{k-2} =\frac{4(k-2)^{k-2}}{k^k}\] for every \(k\ge3\), we obtain \(d(\mathscr{P})\le \frac{4(k-2)^{k-2}}{k^k}\), which leads to a contradiction. Hence condition [palette32step322] holds. By 11, \(\frac{4(k-2)^{k-2}}{k^k}\in\Pi_{\rm u}^{(k)}\).

Let \(\mathcal{C}_0=C_{1}\dot{\cup} C_{2}\dot{\cup} C_{3}\dot{\cup} C_{4}\) with \(|C_{1}|=| C_2|=|C_{3}|=2\) and \(|C_{4}|=3(k-2)\). Thus \(|\mathcal{C}_0|=3k\). Define \(\mathscr P_0=(\mathcal{C}_0,\mathcal{T}_0)\) by \[\mathcal{T}_0= \{(x_1,\dots,x_k)\in\mathcal{C}_0^k: x_1\in C_{1}\cup C_3,\;x_k\in C_2\cup C_3,\;x_2,\dots,x_{k-1}\in C_4 \text{ and } \{x_1, x_k\}\not\subset C_3\}.\] Hence, \[d(\mathscr P_0) = \frac{\bigl(|C_1||C_2|+|C_1||C_3|+|C_3||C_2|\bigr)|C_4|^{k-2}}{|\mathcal{C}_0|^k} = \frac{12\cdot (3(k-2))^{k-2}}{(3k)^k} = \frac{4(k-2)^{k-2}}{3k^k}.\] For each \(i\in\{2,\dots,k-1\}\), define a \(k\)-palette \(\mathscr{P}_i=(\mathcal{C}_i,\mathcal{T}_i)\) with one special color \(a_i\) and two admissible tuples \((a_i,\alpha^i_2,\dots,\alpha^i_k)\) and \((\beta^i_1,\dots,\beta^i_{i-1},a_i,\beta^i_{i+1},\dots,\beta^i_k)\), where all colors other than \(a_i\) are pairwise distinct. Define \(\mathscr{P}_k=(\mathcal{C}_k,\mathcal{T}_k)\) with two special colors \(b\) and \(c\) and three admissible tuples \[(\rho_1,\dots,\rho_{k-1},b),\qquad (b,\sigma_2,\dots,\sigma_{k-1},c),\qquad (c,\tau_2,\dots,\tau_k),\] where all filler colors are pairwise distinct too.

As above the proof, for any \(i,j\in\{2,\dots,k-1\}\), \(\mathscr P_i\) admits a homomorphism to \(\mathscr P_j^{\mathcal{S}}\). Moreover, each \(\mathscr P_i\) admits a homomorphism to \(\mathscr P_k^{\mathcal{S}}\): in the symmetrization of \(\mathscr P_k\), the color \(b\) can be placed with the same superscript in an endpoint coordinate and in any prescribed middle coordinate. Conversely, \(\mathscr P_k\) admits a homomorphism to \(\mathscr P_i^{\mathcal{S}}\) for every \(i\in\{2,\dots,k-1\}\). Indeed, the symmetrization of \(\mathscr P_i\) allows two fixed formal colors to occupy the three endpoint positions required by the three tuples of \(\mathscr P_k\); all remaining colors of \(\mathscr P_k\) are new and can be mapped to the remaining coordinates of the corresponding symmetrized tuples. Thus each distinguished \(k\)-palette among \(\mathscr P_2,\dots,\mathscr P_{k-1},\mathscr P_k\) admits a homomorphism to its corresponding mixed product. Therefore any homomorphism from such a mixed product to \(\mathscr P_0\) or to \({\rm rev}(\mathscr P_0)\) would yield a homomorphism from the distinguished palette itself to \(\mathscr P_0\) or to \({\rm rev}(\mathscr P_0)\). For each \(i\in\{2,\dots,k-1\}\), there is no homomorphism from \(\mathscr P_i\) to \(\mathscr P_0\) or to \({\rm rev}(\mathscr P_0)\), because the special color \(a_i\) appears once in an endpoint coordinate and once in a middle coordinate, while in every admissible tuple of \(\mathscr P_0\) and of \({\rm rev}(\mathscr P_0)\) the endpoint coordinates lie in \(C_1\cup C_2\cup C_3\) and the middle coordinates lie in the disjoint set \(C_4\). There is also no homomorphism from \(\mathscr P_k\) to \(\mathscr P_0\). Indeed, the first and second \(k\)-tuples in \(\mathcal{T}_k\) force the image of \(b\) to lie in \((C_1\cup C_3)\cap (C_2\cup C_3)=C_3\) and the second and third \(k\)-tuples in \(\mathcal{T}_k\) force the image of \(c\) to lie in \(C_3\), which implies that the middle \(k\)-tuple has both endpoint colors in \(C_3\), which is forbidden by the definition of \(\mathcal{T}_0\). The same argument applies to \({\rm rev}(\mathscr P_0)\). Therefore, for each \(j\in\{2,\dots,k-1\}\), there is no homomorphism from \[\mathscr P_j\times \prod_{j'\in[k]\setminus\{1,j\}}\mathscr P_{j'}^{\mathcal{S}}\] to \(\mathscr P_0\) or to \({\rm rev}(\mathscr P_0)\).

For any \(k\)-palette \(\mathscr{P}=(\mathcal{C},\mathcal{T})\) with \(d(\mathscr{P})>\frac{4(k-2)^{k-2}}{3k^k}\), we claim that there is a homomorphism from some \(\mathscr{P}_i\) to \(\mathscr{P}\) or to \({\rm rev}(\mathscr{P})\) for \(i\in[2,k]\). If not, for each \(j\in [k]\) let \[C'_j:= \{c\in\mathcal{C}:\text{ there exists }(x_1,\dots,x_k)\in\mathcal{T} \text{ with }x_j=c\}.\] Since there is no homomorphism from \(\mathscr{P}_i\) to \(\mathscr{P}\) or to \({\rm rev}(\mathscr{P})\), we have \(C'_1\cap C'_i=\emptyset\) and \(C'_k\cap C'_i=\emptyset\) for each \(i\in \{2, \dots, k-1\}\). Let \(X=C'_1\cap C'_k\), \(Y= C'_1\setminus X\) and \(Z=C'_k\setminus X\). Since there is no homomorphism from \(\mathscr{P}_k\) to \(\mathscr{P}\) or to \({\rm rev}(\mathscr{P})\), each \((c_1, \dots, c_k)\) in \(\mathcal{T}\) has the property that \(c_1\) and \(c_k\) cannot belong to \(X\) at the same time. Thus, \(|\mathcal{T}|\le \bigl(|X||Y|+|X||Z|+|Y||Z|\bigr) \bigl(|\mathcal{C}|-|X|-|Y|-|Z|\bigr)^{k-2}\). Note that for any reals \(x, y, z \ge0\) and \(x+y+z\le1\), we have \[(xy+xz+yz)(1-x-y-z)^{k-2} \le \frac{4(k-2)^{k-2}}{3k^k}.\] Therefore, we have \[\begin{align} d(\mathscr{P})\leq\frac{\bigl(|X||Y|+|X||Z|+|Y||Z|\bigr) \bigl(|\mathcal{C}|-|X|-|Y|-|Z|\bigr)^{k-2}}{|\mathcal{C}|^k}\le \frac{4(k-2)^{k-2}}{3k^k}, \end{align}\] which leads to a contradiction. By 11, \(\frac{4(k-2)^{k-2}}{3k^k} \in\Pi_{\rm u}^{(k)}\). ◻

Proof of 4. We treat the cases \(k=3\) and \(k\ge4\) separately, since the construction for \(k\ge4\) uses the two disjoint coordinate pairs \(\{1,k\}\) and \(\{2,k-1\}\), which degenerate when \(k=3\). In both cases, the proof follows the same strategy: we construct two \(k\)-palettes \(\mathscr P_1,\mathscr P_2\) which give lower bounds for the individual densities, and then show that any \(k\)-palette of density above a smaller threshold admits a homomorphism from at least one of them.

The case 1: \(k=3\). Let \(\mathscr{P}_1=([5], \mathcal{T}_1)\) with \(\mathcal{T}_1=\left\{(1,2,3),(2,4,5)\right\}\) and \(\mathscr{P}'=([3],\mathcal{T}')\) with \(\mathcal{T}'=\left\{(x_1,2,x_3):x_1,x_3\in\{1,3\}\right\}\). Then \(d(\mathscr{P}')=|\mathcal{T}'|/|\mathcal{C}|^3=4/27\).

We first show that no homomorphism exists from \(\mathscr{P}_1\) to \(\mathscr{P}'\) or \(\mathrm{rev}(\mathscr{P}')\). Suppose for contradiction \(f:\mathscr{P}_1\to\mathscr{P}'\) is a homomorphism. Then \((f(1),f(2),f(3))\in\mathcal{T}'\) implies \(f(2)=2\) and \(f(1),f(3)\in\{1,3\}\). Meanwhile, \((f(2),f(4),f(5))\in\mathcal{T}'\) requires \(f(2)\in\{1,3\}\), a contradiction. Since \(\mathrm{rev}(\mathscr{P}')=\mathscr{P}'\), the same holds for \(\mathrm{rev}(\mathscr{P}')\).

Let \(\mathscr{P}=(\mathcal{C},\mathcal{T})\) be an arbitrary 3-palette with \(d(\mathscr{P})>4/27\). For \(i\in[3]\), let \(A_i\) be the set of colors appearing in the \(i\)-th coordinate of some tuple in \(\mathcal{T}\). We claim there exists a homomorphism from \(\mathscr{P}_1\) to \(\mathscr{P}\) or \(\mathrm{rev}(\mathscr{P})\). Suppose not.

We first show \(A_1\cap A_2=\emptyset\). If \(a\in A_1\cap A_2\), there exist \((a,b,c)\in\mathcal{T}\) (as \(a\in A_1\)) and \((d,a,e)\in\mathcal{T}\) (as \(a\in A_2\)). Define \(f:[5]\to\mathcal{C}\) by \(f(1)=d,f(2)=a,f(3)=e,f(4)=b,f(5)=c\). Then \((f(1),f(2),f(3))=(d,a,e)\in\mathcal{T}\) and \((f(2),f(4),f(5))=(a,b,c)\in\mathcal{T}\), so \(f:\mathscr{P}_1\to\mathscr{P}\) is a homomorphism, a contradiction. Thus, \(A_1\cap A_2=\emptyset\). Similarly, no homomorphism to \(\mathrm{rev}(\mathscr{P})\) implies \(A_3\cap A_2=\emptyset\).

Since every tuple in \(\mathcal{T}\) has coordinates in \(A_1,A_2,A_3\) respectively, \(|\mathcal{T}|\le |A_1||A_2||A_3|\). As \(A_1,A_3\subseteq\mathcal{C}\setminus A_2\), we have \(|A_1|,|A_3|\le|\mathcal{C}|-|A_2|\). Thus, \[d(\mathscr{P})=\frac{|\mathcal{T}|}{|\mathcal{C}|^3}\le\frac{|A_2|(|\mathcal{C}|-|A_2|)^2}{|\mathcal{C}|^3}.\] The function \(x\mapsto x(n-x)^2/n^3\) attains its maximum \(4/27\) at \(x=n/3\), so \(d(\mathscr{P})\le4/27\), a contradiction. Hence the claim holds. By 11, there exists a 3-graph \(F_1\) with \(\pi_1(F_1)=4/27\) that is \(\mathscr{P}_1\)-colorable but not \(\mathscr{P}'\)-colorable.

Now let \(\mathscr{P}_2=([5],\mathcal{T}_2)\) with \(\mathcal{T}_2=\left\{(1,2,3),(3,4,5)\right\}\) and let \(\mathscr{P}''=([2],\mathcal{T}'')\) with \(\mathcal{T}''=\{(1,x,2):x\in\{1,2\}\}\). Then \(d(\mathscr{P}'')=\frac{1}{4}\).

There is no homomorphism from \(\mathscr{P}_2\) to \(\mathscr{P}''\) or \(\mathrm{rev}(\mathscr{P}'')\): a homomorphism to \(\mathscr{P}''\) would require \(f(1)=1,f(3)=2\), but then \((f(3),f(4),f(5))=(2,\cdot,\cdot)\notin\mathcal{T}''\). For \(\mathrm{rev}(\mathscr{P}'')\), the contradiction is symmetric.

Let \(\mathscr{P}=(\mathcal{C},\mathcal{T})\) be a 3-palette with \(d(\mathscr{P})>1/4\). For \(i\in[3]\), let \(A_i\) be as before. Then, \[\frac{|A_1||\mathcal{C}||A_3|}{|\mathcal{C}|^3}\ge d(\mathscr{P})>\frac{1}{4}.\] By AM-GM inequality, \(|A_1|+|A_3|\ge2\sqrt{|A_1||A_3|}>|\mathcal{C}|\), so \(A_1\cap A_3\neq\emptyset\). Let \(a\in A_1\cap A_3\), then there exist \((x_1,x_2,a)\in\mathcal{T}\) (as \(a\in A_3\)) and \((a,y_1,y_2)\in\mathcal{T}\) (as \(a\in A_1\)). Define \(f:[5]\to\mathcal{C}\) by \((f(1),f(2),f(3))=(x_1,x_2,a)\) and \((f(3),f(4),f(5))=(a,y_1,y_2)\). By definition, \(f:\mathscr{P}_2\to\mathscr{P}\) is a homomorphism. By 11, there exists a 3-graph \(F_2\) with \(\pi_1(F_2)=1/4\) that is \(\mathscr{P}_2\)-colorable but not \(\mathscr{P}''\)-colorable.

Finally, we show \(\pi_1(\{F_1,F_2\})=1/27<\min\{4/27,1/4\}\). For the upper bound, let \(\mathscr{P}_0=(\mathcal{C},\mathcal{T}_0)\) be a 3-palette with \(d(\mathscr{P}_0)>1/27\). We claim that there exists a homomorphism from one of \(\mathscr{P}_1\), \(\mathrm{rev}(\mathscr{P}_1)\) or \(\mathscr{P}_2\) to \(\mathscr{P}_0\). Suppose not. For \(i\in[3]\), let \(A_i\) be as before. Since there is no homomorphism from \(\mathscr{P}_1\) to \(\mathscr{P}_0\), \(A_1\cap A_2=\emptyset\). Since there is no homomorphism from \(\mathrm{rev}(\mathscr{P}_1)\) to \(\mathscr{P}_0\), \(A_2\cap A_3=\emptyset\). Since there is no homomorphism from \(\mathscr{P}_2\) to \(\mathscr{P}_0\), \(A_1\cap A_3=\emptyset\). Thus \(A_1,A_2,A_3\) are pairwise disjoint, so \(|A_1|+|A_2|+|A_3|\le|\mathcal{C}|\). By AM-GM inequality, \[|\mathcal{T}_0|\le|A_1||A_2||A_3|\le\left(\frac{|A_1|+|A_2|+|A_3|}{3}\right)^3\le\frac{|\mathcal{C}|^3}{27},\] implying \(d(\mathscr{P}_0)\le1/27\), a contradiction. Recall that if there is a homomorphism from \(\mathscr{P}\) to \(\mathscr{P}'\), then every \(k\)-graph that is \(\mathscr{P}\)-colorable is also \(\mathscr{P}'\)-colorable. By our claim above, either \(F_1\) or \(F_2\) is \(\mathscr{P}_0\)-colorable. By 1, \(\pi_1(\{F_1,F_2\})\le1/27\).

For the lower bound, let \(\mathscr{P}_3=([3],\mathcal{T}_3)\) with \(\mathcal{T}_3=\{(1,2,3)\}\), then \(d(\mathscr{P}_3)=1/27\). Trivially, there is a homomorphism from \(\mathscr{P}_3\) to \(\mathscr{P}'\) and a homomorphism from \(\mathscr{P}_3\) to \(\mathscr{P}''\). Hence, \(F_1\) and \(F_2\) are not \(\mathscr{P}_3\)-colorable (as \(F_1\), \(F_2\) is not \(\mathscr{P}',\mathscr{P}''\)-colorable respectively), implying \(\pi_1(\{F_1,F_2\})\ge d(\mathscr{P}_3)=1/27\).

Combining bounds, \(\pi_1(\{F_1,F_2\})=1/27\), completing the case \(k=3\).

The case 2: \(k\ge 4\). Let \(\mathscr{P}_1=([2k-1],\mathcal{T}_1)\) with \(\mathcal{T}_1=\left\{(1,2,\dots,k),(k,k+1,\dots,2k-1)\right\}\). Let \(\mathscr{P}'=([2],\mathcal{T}')\) with \(\mathcal{T}'=\{(1,x_2,x_3,\dots,x_{k-1},2): x_i\in\{1,2\}\;\text{for}\;i\in[2,k-1]\}\). Then \(d(\mathscr{P}')=2^{k-2}/2^k=1/4\).

There is no homomorphism from \(\mathscr{P}_1\) to \(\mathscr{P}'\) or \(\mathrm{rev}(\mathscr{P}')\): a homomorphism to \(\mathscr{P}'\) would require \(f(1)=1,f(k)=2\), but then \((f(k),\dots,f(2k-1))=(2,\dots)\notin\mathcal{T}'\). For \(\mathrm{rev}(\mathscr{P}')\), the contradiction is symmetric.

Let \(\mathscr{P}=(\mathcal{C},\mathcal{T})\) be a \(k\)-palette with \(d(\mathscr{P})>1/4\). For \(i\in\{1,k\}\), let \(A_i\) be the set of colors appearing in the \(i\)-th coordinate of some tuple in \(\mathcal{T}\). Then, \[\frac{|A_1||\mathcal{C}|^{k-2}|A_k|}{|\mathcal{C}|^k}\ge d(\mathscr{P})>\frac{1}{4}.\] By AM-GM inequality, \(A_1\cap A_k\neq\emptyset\). Let \(a\in A_1\cap A_k\), then there exist \((x_1,\dots,x_{k-1},a)\in\mathcal{T}\) (as \(a\in A_k\)) and \((a,y_1,\dots,y_{k-1})\in\mathcal{T}\) (as \(a\in A_1\)). Define \(f:[2k-1]\to\mathcal{C}\) by \((f(1),\dots,f(k))=(x_1,\dots,x_{k-1},a)\) and \((f(k),\dots,f(2k-1))=(a,y_1,\dots,y_{k-1})\). \(f\) is a homomorphism from \(\mathscr{P}_1\) to \(\mathscr{P}\). By 11, there exists a \(k\)-graph \(F_1\) with \(\pi_{k-2}(F_1)=1/4\) that is \(\mathscr{P}_1\)-colorable but not \(\mathscr{P}'\)-colorable.

Now let \(\mathscr{P}_2=([2k-1],\mathcal{T}_2)\) with \(\mathcal{T}_2=\left\{(1,2,\dots,k),(k+1,k-1,k+2,k+3,\dots,2k-1)\right\}\) (the second tuple has length \(k\), with second coordinate \(k-1\)). Let \(\mathscr{P}''=([2],\mathcal{T}'')\) with \(\mathcal{T}''=\{(x_1,1,x_3,\dots,x_{k-2},2,x_k):x_i\in\{1,2\}\;\text{for}\;i\in[k]\setminus\{2,k-1\}\}\). Then \(d(\mathscr{P}'')=2^{k-2}/2^k=1/4\).

Similarly, no homomorphism exists from \(\mathscr{P}_2\) to \(\mathscr{P}''\) or \(\mathrm{rev}(\mathscr{P}'')\): a homomorphism to \(\mathscr{P}''\) would require \(f(k-1)=2\) (from the first tuple in \(\mathcal{T}_2\)) and \(f(k-1)=1\) (from the second tuple in \(\mathcal{T}_2\)), a contradiction. Let \(\mathscr{P}=(\mathcal{C},\mathcal{T})\) be a \(k\)-palette with \(d(\mathscr{P})>1/4\). For \(i\in\{2,k-1\}\), let \(A_i\) be the set of colors appearing in the \(i\)-th coordinate of some tuple in \(\mathcal{T}\). By the same argument as for \(F_1\), we have \(A_2\cap A_{k-1}\neq \emptyset\), and there exists a homomorphism from \(\mathscr{P}_2\) to \(\mathscr{P}\). By 11, there exists a \(k\)-graph \(F_2\) with \(\pi_{k-2}(F_2)=1/4\) that is \(\mathscr{P}_2\)-colorable but not \(\mathscr{P}''\)-colorable.

Finally, we show \(\pi_{k-2}(\{F_1,F_2\})=1/16<1/4\).

For the upper bound, let \(\mathscr{P}_0=(\mathcal{C},\mathcal{T}_0)\) be a \(k\)-palette with \(d(\mathscr{P}_0)>1/16\). For \(i\in\{1,2,k-1,k\}\), let \(A_i\) be the set of colors appearing in the \(i\)-th coordinate of some tuple in \(\mathcal{T}_0\). Then, \[\frac{|A_1||A_2||\mathcal{C}|^{k-4}|A_{k-1}||A_k|}{|\mathcal{C}|^k}\ge d(\mathscr{P}_0)>\frac{1}{16}.\] Thus either \(|A_1||A_k|/|\mathcal{C}|^2>1/4\) or \(|A_2||A_{k-1}|/|\mathcal{C}|^2>1/4\) (otherwise their product is at most \(1/16\)). If the former holds, \(A_1\cap A_{k}\neq\emptyset\) by AM-GM inequality and there is a homomorphism \(f:\mathscr{P}_1\to\mathscr{P}_0\) (as before), which implies \(F_1\) is \(\mathscr{P}_0\)-colorable. If the latter holds, \(A_2\cap A_{k-1}\neq\emptyset\) by AM-GM inequality and there is a homomorphism \(f:\mathscr{P}_2\to\mathscr{P}_0\), which implies \(F_2\) is \(\mathscr{P}_0\)-colorable. By 1, \(\pi_{k-2}(\{F_1,F_2\})\le1/16\). For the lower bound, let \(\mathscr{P}_3=([2],\mathcal{T}_3)\) with \(\mathcal{T}_3=\{(1,1,x_3,\dots,x_{k-2},2,2):x_i\in\{1,2\}\;\text{for}\;i\in[3,k-2]\}\), where the first two coordinates are fixed to 1, the last two coordinates are fixed to 2, and the middle \(k-4\) coordinates are arbitrary element in \([2]\). Then \(|\mathcal{T}_3|=2^{k-4}\), so \(d(\mathscr{P}_3)=2^{k-4}/2^k=1/16\). The identity map is a homomorphism \(\mathscr{P}_3\to\mathscr{P}'\) and a homomorphism \(\mathscr{P}_3\to\mathscr{P}''\). Then neither \(F_1\) nor \(F_2\) is \(\mathscr{P}_3\)-colorable. Hence \(\pi_{k-2}(\{F_1,F_2\})\ge1/16\).

Combining bounds, \(\pi_{k-2}(\{F_1,F_2\})=1/16\), completing the case \(k\ge4\). ◻