Integer-valued function

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 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.

Definition

The Shannon capacity of a graph G is defined as

$\Theta (G)=\sup _{k}{\sqrt[{k}]{\alpha (G^{k})}}=\lim _{k\rightarrow \infty }{\sqrt[{k}]{\alpha (G^{k})}},$

where α(G) is the independence number of graph G (the size of a largest independent set of G) and G^k is the strong graph product of G with itself k times.

This quantity measures the Shannon capacity of a communication channel in which the vertices of G represent distinct symbols that may be transmitted on the channel in each time step, and the edges of G represent pairs of symbols that may be confused with each other. A code of length k using these symbols has no two mutually confusable codewords if and only if it corresponds to an independent set of G^k, so the Shannon capacity of the graph represents the effective number of distinct symbols that may be used per time step, for sufficiently long codes.

Example

Pentagon graph

Let C₅ be the graph of the pentagon. There exists a five-symbol code of length 2 for this graph, consisting of the five code words "11", "23", "35", "54", "42". Every two of these words contain two non-adjacent symbols in the same positions as each other: for instance, for the two words "11" and "23", the symbols in the second position, "1" and "3", are non-adjacent. Therefore, these words form an independent set in C₅², showing that Θ(C₅) ≥ Template:Sqrt. But as Template:Harvtxt showed, this bound is tight: Θ(C₅) = Template:Sqrt.

Relation to Lovász number

The Lovász number ϑ(G) is a different graph invariant, that can be computed numerically to high accuracy in polynomial time by an algorithm based on the ellipsoid method. The Shannon capacity of a graph G is bounded from below by α(G), and from above by ϑ(G). In some cases, ϑ(G) and the Shannon capacity coincide; for instance, for the graph of a pentagon, both are equal to Template:Sqrt. However, there exist other graphs for which the Shannon capacity and the Lovász number differ.

Haemers' bound

Haemers provided another bound on the Shannon capacity, which is sometimes better than Lovász bound:

$\Theta (G)\leq R(G)=\min _{B}\operatorname {rank} (B),$

where B is an n × n matrix over some field, such that b_ii ≠ 0 and b_ij = 0 if vertices i and j are not adjacent.

Computational complexity

The computational complexity of the Shannon capacity is unknown, and even the value of the Shannon capacity for certain small graphs such as C₇ (a cycle graph of seven vertices) remains unknown.

A natural approach to this problem would be to compute a finite number of powers of the given graph G, find their independence numbers, and infer from these numbers some information about the limiting behavior of the sequence from which the Shannon capacity is defined. However (even ignoring the computational difficulty of computing the independence numbers of these graphs, an NP-hard problem) the unpredictable behavior of the sequence of independence numbers of powers of G implies that this approach cannot be used to accurately approximate the Shannon capacity.

References

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.