Bounds for codes on pentagon and other cycles

Abstract

The capacity of a graph is defined as the rate of exponential grow of independent sets in the strong powers of the graph. In strong power, an edge connects two sequences if at each position letters are equal or adjacent. We consider a variation of the problem where edges in the power graphs are removed among sequences which differ in more than a fraction $\delta$ of coordinates. For odd cycles, we derive an upper bound on the corresponding rate which combines Lovász' bound on the capacity with Delsarte's linear programming bounds on the minimum distance of codes in Hamming spaces. For the pentagon, this shows that for $\delta \ge 1-\frac{1}{\sqrt{5}}$ the Lovász rate is the best possible, while we prove by a Gilbert-Varshamov-type bound that a higher rate is achievable for $\delta <\frac{2}{5}$. Communication interpretation of this question is the problem of sending quinary symbols subject to $\pm 1\mathrm{mod}5$ disturbance. The maximal communication rate subject to the zero undetected-error equals capacity of a pentagon. The question addressed here is how much this rate can be increased if only a fraction $\delta$ of symbols is allowed to be disturbed

Cited by in corpus (1)

• Bounds on the reliability of typewriter channels