= Solution
Put $d=d_H(A,B)=\min\{d_H(\alpha,\beta):\alpha\in A,\ \beta\in B\}$, and define $f(\sigma)=d_H(\sigma,A)$. The triangle inequality shows that $f$ is <Lipschitz continuous> with <Lipschitz constant> one. It vanishes on $A$, and $f\geq d$ on $B$. Let $\mu=\mathbb Ef$ for a uniform <permutation>.
If $\mu\geq d/2$, apply the lower-tail bound proved in part (i):
$$
\frac{|A|}{n!}=\mathbb P(\sigma\in A)
\leq\mathbb P(f-\mu\leq-\mu)
\leq e^{-\mu^2/(2n)}\leq e^{-d^2/(8n)}.
$$
If $\mu<d/2$, apply its upper-tail bound:
$$
\frac{|B|}{n!}\leq\mathbb P(f-\mu\geq d-\mu)
\leq e^{-(d-\mu)^2/(2n)}\leq e^{-d^2/(8n)}.
$$
For $d=0$ the desired inequality is simply $\min\{|A|,|B|\}\leq n!$. Hence in all cases
$$
\boxed{\min\{|A|,|B|\}\leq n!\exp\!\left(-\frac{d_H(A,B)^2}{8n}\right).}
$$
This uses only the precise one-sided <concentration inequality> from part (i) and the <Hamming distance> triangle inequality. The normalization of the distance matters: it counts mismatching coordinates, rather than dividing their number by $n$.
Back to article page
