























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 $δ$ 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 $δ\ge {1-{1\over\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 $δ< {2\over 5}$. Communication interpretation of this question is the problem of sending quinary symbols subject to $\pm 1\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 $δ$ of symbols is allowed to be disturbed
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。