Shannon capacity of a graph

In graph theory, the Shannon capacity of a graph is a graph invariant defined from the number of independent sets of strong graph products. It is named after American mathematician Claude Shannon. It measures the Shannon capacity of a communications channel defined from the graph, and is upper bounded by the Lovász number, which can be computed in polynomial time. However, the computational complexity of the Shannon capacity itself remains unknown. The Shannon capacity models the amount of information that can be transmitted across a noisy communication channel in which certain signal values can be confused with each other. In this application, the confusion graph or confusability graph describes the pairs of values that can be confused. For instance, suppose that a communications channel has five discrete signal values, any one of which can be transmitted in a single time step. These values may be modeled mathematically as the five numbers 0, 1, 2, 3, or 4 in modular arithmetic modulo 5. However, suppose that when a value is sent across the channel, the value that is received is (mod 5) where represents the noise on the channel and may be any real number in the open interval from −1 to 1. Thus, if the recipient receives a value such as 3.6, it is impossible to determine whether it was originally transmitted as a 3 or as a 4; the two values 3 and 4 can be confused with each other. This situation can be modeled by a graph, a cycle of length 5, in which the vertices correspond to the five values that can be transmitted and the edges of the graph represent values that can be confused with each other. For this example, it is possible to choose two values that can be transmitted in each time step without ambiguity, for instance, the values 1 and 3. These values are far enough apart that they can't be confused with each other: when the recipient receives a value between 0 and 2, it can deduce that the value that was sent must have been 1, and when the recipient receives a value in between 2 and 4, it can deduce that the value that was sent must have been 3.