\section{Proof of robust local separation}
\label{app:local}

\begin{proof}[Proof of Lemma~\ref{lem:local}]
Put
\begin{align*}
\Lambda&=4K,\quad \nu_w=2w(4w+1),\quad
\tau_K=\sum_{w=1}^K w!\nu_w,\quad \upsilon_K=\sum_{w=1}^K w\,w!\nu_w,\\
\omega_K&=2\Lambda(\tau_K+\upsilon_K),\qquad m_0(K)=\max\{2\Lambda,8,8\Lambda\omega_K\}.
\end{align*}
An index pattern consists of a $w$-cell window, a permutation of its variables and a nonempty contiguous subword in the resulting window.
It has at most $4w$ entries and $\nu_w$ subwords.
There are at most $m\tau_K$ patterns, and every original random slot belongs to at most $\upsilon_K$ patterns.
In rotation majority, at most $f\upsilon_K$ patterns meet a reflection slot.
Pull the random entries of each subword back to their original slots; this pullback is injective and remains within the window.

Discard deterministically nonidentity patterns.
In rotation majority, a subword without rotations lies in a run of at most two distinct reflections and is nonidentity.
A retained pattern uses $a\ge1$ rotations; if $a=1$, it uses an even number $b\ge2$ of reflections.
In reflection majority, a subword without reflections contains at most one rotation, so a retained pattern uses an even number $h\ge2$ of reflections.
Identity in a retained pattern is one affine equation in the random coordinates, each with coefficient $+1$ or $-1$.
The coefficients depend only on the type pattern.
A canonical bad event specifies an injective assignment to the used random slots satisfying that equation.
Its index includes the pattern, so identical events may occur as different vertices.
Their simultaneous avoidance is exactly $\mathcal L_K$.

Write $(N)_a=N(N-1)\cdots(N-a+1)$, with $(N)_0=1$.
In rotation majority, an assignment using $a,b$ slots has probability $[(m)_a(f)_b]^{-1}$.
Solving the affine equation for one rotation bounds the total event weight of one pattern by
\begin{equation}
\label{eq:local-pattern-weight}
\frac1{m-a+1}\le\frac2m.
\end{equation}
For a fixed rotation value $\rho$ and $a\ge2$, choose its slot and solve for another rotation.
There are at most $a(m-1)_{a-2}(f)_b$ assignments, of weight at most
\begin{equation*}
\frac a{m(m-a+1)}\le\frac{2\Lambda}{m^2}.
\end{equation*}
If $a=1$, solve instead for a reflection after fixing $\rho$ and the other reflections; the weight is at most
\begin{equation*}
\frac1{m(f-b+1)}\le\frac \Lambda{mf},
\end{equation*}
since $f/(f-b+1)\le b\le \Lambda$ for every feasible $f\ge b$.
For a fixed reflection value, choose its slot and solve for a rotation, obtaining weight at most
\begin{equation*}
\frac b{f(m-a+1)}\le\frac{2\Lambda}{fm}.
\end{equation*}

In reflection majority, solving for one reflection gives pattern weight at most
\begin{equation*}
\frac1{f-h+1}\le\frac2f\le\frac2m.
\end{equation*}
If a fixed reflection value must occur, choose its slot and solve for another reflection, giving weight at most
\begin{equation*}
\frac h{f(f-h+1)}\le\frac{2\Lambda}{f^2}\le\frac{2\Lambda}{m^2}.
\end{equation*}
These inequalities use $a,h\le \Lambda$, $m\ge2\Lambda$ and $f\ge m$ in reflection majority.
Only feasible patterns contribute denominators.

Let $p_E=\Pr(E)$.
Summing pattern weights gives $\sum_Ep_E\le2\tau_K$.
Every position label has event weight at most $2\upsilon_K/m$.
In rotation majority, a rotation-value label has weight at most $2\Lambda\tau_K/m+\Lambda\upsilon_K/m$: use all $m\tau_K$ patterns when $a\ge2$ and the at most $f\upsilon_K$ reflection-using patterns when $a=1$.
A reflection-value label has weight at most $2\Lambda\upsilon_K/m$.
In reflection majority its weight is at most $2\Lambda\tau_K/m$.
Thus every position or value label $\lambda$ satisfies
\begin{equation}
\label{eq:local-label-weight}
\sum_{E:\lambda\text{ used by }E}p_E\le \omega_K/m.
\end{equation}
A value label includes its permutation-factor tag, even when rotation and reflection coordinates coincide.
For $f=0$, reflection cases are absent; for $f=1$, retained rotation-majority patterns have no reflections, so the case $a=1$ is absent.
For every other bounded $f$, the number $f\upsilon_K$ of reflection-using patterns cancels the small-pool denominator.

Join events sharing a position or value label in one permutation factor.
This overlap graph is a negative dependency graph, as in the permutation framework of \citep[Section~1.1]{Harris2017}.
For completeness, force the prescribed matches of one event $E$ successively by swapping each desired value into its prescribed position.
Injectivity of the prescribed assignment preserves all previously forced matches.
With $t$ matches already forced in a factor of size $N$, each permutation satisfying the next match has exactly $N-t$ preimages satisfying the preceding matches.
The resulting law is the product-permutation law conditioned on $E$.
An occurring non-neighbour survives each swap: its prescribed positions include neither the forced position nor the current position of the desired value.
Hence, for avoidance $C$ of any collection of non-neighbours, $\Pr(C\mid E)\le\Pr(C)$.
Bayes' formula gives $\Pr(E\mid C)\le\Pr(E)$ whenever $\Pr(C)>0$.
This argument also applies to two independent factors or an empty factor.

The quantitative lopsided local lemma \citep[Lemma~3]{Lu2007} gives an avoidance probability at least $\prod_E(1-z_E)$ if
\begin{equation*}
p_E\le z_E\prod_{E'\sim E}(1-z_{E'}),\qquad 0\le z_E<1.
\end{equation*}
Each event uses at most $\Lambda$ matches and $2\Lambda$ labels, so \eqref{eq:local-label-weight} gives
\begin{equation*}
\sum_{E'\sim E}p_{E'}\le2\Lambda\omega_K/m.
\end{equation*}
Take $z_E=2p_E$.
The pattern bound \eqref{eq:local-pattern-weight} and its reflection-majority analogue give $z_E\le4/m\le1/2$, while $m\ge8\Lambda\omega_K$ gives $\sum_{E'\sim E}z_{E'}\le1/2$.
Thus $\prod_{E'\sim E}(1-z_{E'})\ge1-\sum_{E'\sim E}z_{E'}\ge1/2$, proving the local-lemma hypothesis.
Finally $\log(1-z)\ge-2z$ for $0\le z\le1/2$ yields
\begin{align*}
\Pr(\mathcal L_K)&\ge\prod_E(1-2p_E) \\
&\ge\exp\left(-4\sum_Ep_E\right) \\
&\ge e^{-8\tau_K}=:c_K>0.\qedhere
\end{align*}
\end{proof}