On the Capacity of Sequences of Coloring Channels
2026-04-09 • Information Theory
Information Theory
AI summaryⓘ
The authors study a problem where certain letters are allowed through special filters called coloring channels, and the goal is to understand how much information can be reliably sent through sequences of these filters. They find exact capacities for some specific patterns of filters and show that these capacities depend on a graph they define, named the pairs graph. Using this graph, the authors create formulas that give bounds on how much information can be transmitted. Their results fully solve the problem for alphabets with 4 letters except for one specific cyclic case, where they only find approximate limits.
coloring channelsequence reconstructioncapacityinformation theorygraph theorypairs graphuniform sunflowerintersecting setscyclealphabet size
Authors
Wenjun Yu, Moshe Schwartz
Abstract
A single coloring channel is defined by a subset of letters it allows to pass through, while deleting all others. A sequence of coloring channels provides multiple views of the same transmitted letter sequence, forming a type of sequence-reconstruction problem useful for protein identification and information storage at the molecular level. We provide exact capacities of several sequences of coloring channels: uniform sunflowers, two arbitrary intersecting sets, and paths. We also show how this capacity depends solely on a related graph we define, called the pairs graph. Using this equivalence, we prove lower and upper bounds on the capacity, and a tailored bound for a coloring-channel sequence forming a cycle. In particular, for an alphabet of size $4$, these results give the exact capacity of all coloring-channel sequences except for a cycle of length $4$, for which we only provide bounds.