The Maximum-Likelihood Decoding Threshold for Cycle Codes of Graphs

For a class C of binary linear codes, we write θ
_C
: (0, 1) → [0, (1/2)] for the maximum-likelihood decoding threshold function of C, the function whose value at R ∈ (0, 1) is the largest bit-error rate p that the codes in C can tolerate with a negligible probability of maximum-likelihood decoding error across a binary symmetric channel. We show that, if C is the class of cycle codes of graphs, then θ
_C
(R) ≤ ((1 - √R)
²
/2(1 + R)) for each R, and show that equality holds only when R is asymptotically achieved by the cycle codes of regular graphs.