  Three science and engineering problems of recent interests -index coding,
locally recoverable distributed storage, and guessing games on graphs- are
discussed and the connection between their optimal solutions is elucidated. By
generalizing recent results by Shanmugam and Dimakis and by Mazumdar on the
complementarity between the optimal broadcast rate of an index coding problem
on a directed graph and the normalized rate of a locally recoverable
distributed storage problem on the same graph, it is shown that the capacity
region and the optimal rate region of these two problems are complementary. The
main ingredients in establishing this result are the notion of confusion graph
introduced by Alon et al. (2008), the vertex transitivity of a confusion graph,
the characterization of the index coding capacity region via the fractional
chromatic number of confusion graphs, and the characterization of the optimal
rate region of the locally recoverable distributed storage via the independence
number of confusion graphs. As the third and final facet of the
complementarity, guessing games on graphs by Riis are discussed as special
cases of the locally recoverable distributed storage problem, and it is shown
that the winning probability of the optimal strategy for a guessing game and
the ratio between the winning probabilities of the optimal strategy and a
random guess can be characterized, respectively, by the capacity region for
index coding and the optimal rate region for distributed storage.
