Capacity of a Structural Binary Symmetric Channel

Information theory traditionally deals with the problem of transmitting sequences over a communication channel and finding the maximum number of messages that a transmitter can send so that the receiver recovers these messages with arbitrarily small probability of error. However, databases of various sorts have come into existence in recent years that require the transmission of new sources of data (e.g., graphs and sets) over communication channels. Here, we investigate a communication model transmitting Erdos-Rényi (unlabeled) graphs to a destination over a Binary Symmetric Channel (BSC). We find the capacity of such a channel - called the Structural Binary Symmetric Channel (SBSC) - to be C = 1 - h(ε) where h(ε) is the binary entropy of the error bit rate ε.