Discrete isoperimetric inequalities and the probability of a decoding error (Q2709849)

The authors derive improved isoperimetric inequalities of Margulis, Talagrand, Bobkov and Goetze for discrete product measures on the \(n\)-dimensional cube. This yields improved criteria for the threshold behaviour of monotone sets. The authors further extend the scope of the method which Margulis originally devised to prove the threshold behaviour of the probability of disconnecting a graph. This is applied to coding theory, and the authors prove and measure the threshold behaviour of the probability of a decoding error, thereby significantly improving the approach to coding initiated by Zémor in 1994.