Multiple unicasts, graph guessing games, and non-Shannon inequalities

Guessing games for directed graphs were introduced by Riis [8] for studying multiple unicast network coding problems. It can be shown that protocols for a multiple unicast network can be directly converted into a strategy for a guessing game. The performance of the optimal strategy for a graph is measured by the guessing number, and this number can be bounded from above using information inequalities. Christofides and Markstrom [4] developed a guessing strategy for undirected graphs based on the fractional clique cover, and they conjectured that this strategy is optimal for undirected graphs. In this paper we disprove this conjecture. We also provide an example of an undirected graph for which non-Shannon inequalities provide a better bound on the guessing number than Shannon inequalities. Finally, we construct a counterexample to a conjecture we raised during our work which we referred to as the Superman conjecture.