= Solution
In natural logarithms, <Fano's inequality> for a uniform index $J$ among $N$ alternatives states $\mathbb P(\widehat J\ne J)\geq1-(I(J;G)+\log2)/\log N$. The <mutual information> is at most the average <Kullback-Leibler divergence> to any fixed reference law. With the supplied packing, nearest-neighbour decoding turns partition error below half the separation into correct decoding. Thus the packing alone proves a bound at radius $n(1/4-\varepsilon/2)$, with the unavoidable $\log2$ term. It does not automatically prove the much larger printed radius.
A <list-decoding Fano inequality> supplies the intended near-half error threshold. Assume $0<\varepsilon<1/4$, since otherwise that threshold is nonpositive and its event is automatic. Take a uniform prior on all $N=\binom n{n/2}/2$ unlabelled balanced partitions, and let $r=n(1/2-2\varepsilon)$. A <Hamming ball> of radius less than $r$ around any estimated partition contains at most $B=\sum_{j<r}\binom nj$ such partitions. This follows by selecting the representative closer to the estimated group; each unlabelled partition contributes at most one such representative because $r<n/2$. The <entropy bound for a Hamming ball> gives $\log B\leq n h(r/n)$, where $h$ is the <binary entropy function> measured in natural logarithms. Its curvature gives $\log2-h(1/2-2\varepsilon)\geq8\varepsilon^2$. Also $\binom n{n/2}\geq2^n/(n+1)$, so
$$
\log(N/B)\geq8\varepsilon^2n-\log(2(n+1)).
$$
Use the all-$1/2$ independent-edge law $P_*$ as a reference. Only the $n^2/4$ crossing pairs differ; the preceding <Bernoulli distribution> divergence estimate gives $D_{\mathrm{KL}}(P_S\Vert P_*)\leq nt^2$. Hence $I(J;G)\leq nt^2$. Whenever the denominator is positive, the <list-decoding Fano inequality> proves the finite-sample answer
$$
\boxed{\inf_{\widehat S}\max_S P_S\{\Delta(\widehat S,S)\geq r\}\geq1-\frac{nt^2+\log2}{8\varepsilon^2n-\log(2(n+1))}.}
$$
For $4\varepsilon^2n\geq\log(2(n+1))$, this is at least $1-t^2/(4\varepsilon^2)-\log2/(4\varepsilon^2n)$. If in addition $nt^2\geq\log2$, it implies the intended form with $c'=1/2$. This proves the claimed information-theoretic scale with its needed finite-sample qualifications.
\b[As a uniform finite-sample assertion for every positive $t$, the printed form is false.] At $t=0$ every partition has the same data law, and a uniformly random balanced guess has a positive chance of being correct, giving error strictly below one. Such randomness can also be extracted from the finite graph sample: assign distinct graph outcomes to the finitely many balanced partitions; under the common law every selected outcome has positive <probability>. The worst error remains strictly below one for sufficiently small positive $t$, by continuity. The printed lower bound tends to one as $t\downarrow0$ for any fixed universal $c'$, which contradicts this. The entropy correction cannot be dropped without an asymptotic or signal-size condition.
Back to article page
