# Background

I have come across two definitions with similar names in the quantum information literature (although both relate to classical information problems). I can see that in some instances the confusion graph and confusability graph are the same. Is there a more deep connection that has been studied? Are the terms named similarly on purpose or is it a coincidence?

# Confusability graph

As defined in [1] (although it was defined long ago by Shannon).

Let $N:X \to Y$ be a classical channel, and let $N(y|x)$ be the probability of output $y$ given input $x$. The confusability graph has vertex set $X$ and edges $E = \{(x,x')|\exists y \textrm{ s.t. } N(y|x) \ne 0, N(y|x') \ne 0\}$. In other words, there is an edge if $x$ and $x'$ might both go to the same output.

# Confusion graph

As defined in [2] (reference given is Kushilevitz and Nisan, who more or less describe this on page 65, but do not assign a name to the concept).

Consider a game where Alice gets input from set $X$ and Bob gets input from set $Y$. It is promised that the inputs are in $P \subseteq X \times Y$. Bob must output $f(x,y)$ for some given function $f$. Alice and Bob both know $P$ and $f$. This is a communication complexity problem. The confusion graph has vertex set $X$ and edges $E = \{(x,x')|\exists y \in Y \textrm{ s.t. } (x,y) \in P, (x',y) \in P, f(x,y) \ne f(x',y) \}$.

# The connection between the two

If $f(\cdot,y)$ is injective for all $y \in Y$, and if $P$ is thought of as a channel that tells Bob something about Alice's input, then the confusion graph is equal to the confusability graph. Is this why they have similar names, or is it a coincidence? Is there some deeper connection that has been studied?

# References

[1] R. Duan, S. Severini, A. Winter, Zero-error communication via quantum channels and a quantum Lovasz theta function, 2011 IEEE International Symposium on Information Theory (IEEE ISIT 2011).

[2] Ziv Bar-yossef, T. S. Jayram, Iordanis Kerenidis, Exponential Separation of Quantum and Classical One-way Communication Complexity, SIAM Journal on Computing, 2008.

-