Shannon capacity of a graph

Last updated

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.

Contents

Graph models of communication channels

A five-vertex cycle, modeling a set of five values that can be transmitted across a noisy communications channel and the pairs of values that can be confused with each other Cycle graph C5.png
A five-vertex cycle, modeling a set of five values that can be transmitted across a noisy communications channel and the pairs of values that can be confused with each other

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 [1] 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. In this way, in steps of communication, the sender can communicate up to different messages. Two is the maximum number of values that the recipient can distinguish from each other: every subset of three or more of the values 0, 1, 2, 3, 4 includes at least one pair that can be confused with each other. Even though the channel has five values that can be sent per time step, effectively only two of them can be used with this coding scheme.

However, more complicated coding schemes allow a greater amount of information to be sent across the same channel, by using codewords of length greater than one. For instance, suppose that in two consecutive steps the sender transmits one of the five code words "11", "23", "35", "54", or "42". (Here, the quotation marks indicate that these words should be interpreted as strings of symbols, not as decimal numbers.) Each pair of these code words includes at least one position where its values differ by two or more modulo 5; for instance, "11" and "23" differ by two in their second position, while "23" and "42" differ by two in their first position. Therefore, a recipient of one of these code words will always be able to determine unambiguously which one was sent: no two of these code words can be confused with each other. By using this method, in steps of communication, the sender can communicate up to messages, significantly more than the that could be transmitted with the simpler one-digit code. The effective number of values that can be transmitted per unit time step is . In graph-theoretic terms, this means that the Shannon capacity of the 5-cycle is at least . As Lovász (1979) showed, this bound is tight: it is not possible to find a more complicated system of code words that allows even more different messages to be sent in the same amount of time, so the Shannon capacity of the 5-cycle is exactly .

Relation to independent sets

If a graph represents a set of symbols and the pairs of symbols that can be confused with each other, then a subset of symbols avoids all confusable pairs if and only if is an independent set in the graph, a subset of vertices that does not include both endpoints of any edge. The maximum possible size of a subset of the symbols that can all be distinguished from each other is the independence number of the graph, the size of its maximum independent set. For instance, ': the 5-cycle has independent sets of two vertices, but not larger.

For codewords of longer lengths, one can use independent sets in larger graphs to describe the sets of codewords that can be transmitted without confusion. For instance, for the same example of five symbols whose confusion graph is , there are 25 strings of length two that can be used in a length-2 coding scheme. These strings may be represented by the vertices of a graph with 25 vertices. In this graph, each vertex has eight neighbors, the eight strings that it can be confused with. A subset of length-two strings forms a code with no possible confusion if and only if it corresponds to an independent set of this graph. The set of code words {"11", "23", "35", "54", "42"} forms one of these independent sets, of maximum size.

If is a graph representing the signals and confusable pairs of a channel, then the graph representing the length-two codewords and their confusable pairs is , where the symbol represents the strong product of graphs. This is a graph that has a vertex for each pair of a vertex in the first argument of the product and a vertex in the second argument of the product. Two distinct pairs and are adjacent in the strong product if and only if and are identical or adjacent, and and are identical or adjacent. More generally, the codewords of length  can be represented by the graph , the -fold strong product of with itself, and the maximum number of codewords of this length that can be transmitted without confusion is given by the independence number . The effective number of signals transmitted per unit time step is the th root of this number, .

Using these concepts, the Shannon capacity may be defined as

the limit (as becomes arbitrarily large) of the effective number of signals per time step of arbitrarily long confusion-free codes.

Computational complexity

Unsolved problem in mathematics:

What is the Shannon capacity of a 7-cycle?

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

A natural approach to this problem would be to compute a finite number of powers of the given graph , 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 implies that this approach cannot be used to accurately approximate the Shannon capacity. [4]

Upper bounds

In part because the Shannon capacity is difficult to compute, researchers have looked for other graph invariants that are easy to compute and that provide bounds on the Shannon capacity.

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). [5] In some cases, ϑ(G) and the Shannon capacity coincide; for instance, for the graph of a pentagon, both are equal to 5. However, there exist other graphs for which the Shannon capacity and the Lovász number differ. [6]

Haemers' bound

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

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

Related Research Articles

<span class="mw-page-title-main">Huffman coding</span> Technique to compress data

In computer science and information theory, a Huffman code is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code is Huffman coding, an algorithm developed by David A. Huffman while he was a Sc.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes".

<span class="mw-page-title-main">Tetrahedron</span> Polyhedron with 4 faces

In geometry, a tetrahedron, also known as a triangular pyramid, is a polyhedron composed of four triangular faces, six straight edges, and four vertex corners. The tetrahedron is the simplest of all the ordinary convex polyhedra.

<span class="mw-page-title-main">Hamming distance</span> Number of bits that differ between two strings

In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of substitutions required to change one string into the other, or the minimum number of errors that could have transformed one string into the other. In a more general context, the Hamming distance is one of several string metrics for measuring the edit distance between two sequences. It is named after the American mathematician Richard Hamming.

<span class="mw-page-title-main">Snub cube</span> Archimedean solid with 38 faces

In geometry, the snub cube, or snub cuboctahedron, is an Archimedean solid with 38 faces: 6 squares and 32 equilateral triangles. It has 60 edges and 24 vertices.

In computer science, the Floyd–Warshall algorithm is an algorithm for finding shortest paths in a directed weighted graph with positive or negative edge weights. A single execution of the algorithm will find the lengths of shortest paths between all pairs of vertices. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm. Versions of the algorithm can also be used for finding the transitive closure of a relation , or widest paths between all pairs of vertices in a weighted graph.

<span class="mw-page-title-main">Diagonal</span> In geometry a line segment joining two nonconsecutive vertices of a polygon or polyhedron

In geometry, a diagonal is a line segment joining two vertices of a polygon or polyhedron, when those vertices are not on the same edge. Informally, any sloping line is called diagonal. The word diagonal derives from the ancient Greek διαγώνιος diagonios, "from angle to angle" ; it was used by both Strabo and Euclid to refer to a line connecting two vertices of a rhombus or cuboid, and later adopted into Latin as diagonus.

<span class="mw-page-title-main">Graph coloring</span> Methodic assignment of colors to elements of a graph

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

In mathematics, spectral graph theory is the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix.

<span class="mw-page-title-main">Strongly regular graph</span> Regular graph where all linked node pairs have same degree, as do all unlinked node pairs

In graph theory, a strongly regular graph (SRG) is defined as follows. Let G = (V, E) be a regular graph with v vertices and degree k. G is said to be strongly regular if there are also integers λ and μ such that:

In mathematics and computer science, in the field of coding theory, the Hamming bound is a limit on the parameters of an arbitrary block code: it is also known as the sphere-packing bound or the volume bound from an interpretation in terms of packing balls in the Hamming metric into the space of all possible words. It gives an important limitation on the efficiency with which any error-correcting code can utilize the space in which its code words are embedded. A code that attains the Hamming bound is said to be a perfect code.

<span class="mw-page-title-main">Kneser graph</span>

In graph theory, the Kneser graphK(n, k) (alternatively KGn,k) is the graph whose vertices correspond to the k-element subsets of a set of n elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. Kneser graphs are named after Martin Kneser, who first investigated them in 1956.

The expander mixing lemma intuitively states that the edges of certain -regular graphs are evenly distributed throughout the graph. In particular, the number of edges between two vertex subsets and is always close to the expected number of edges between them in a random -regular graph, namely .

In coding theory, list decoding is an alternative to unique decoding of error-correcting codes for large error rates. The notion was proposed by Elias in the 1950s. The main idea behind list decoding is that the decoding algorithm instead of outputting a single possible message outputs a list of possibilities one of which is correct. This allows for handling a greater number of errors than that allowed by unique decoding.

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of vertices from an n-vertex graph can partition the graph into disjoint subgraphs each of which has at most vertices.

In graph theory, the Lovász number of a graph is a real number that is an upper bound on the Shannon capacity of the graph. It is also known as Lovász theta function and is commonly denoted by , using a script form of the Greek letter theta to contrast with the upright theta used for Shannon capacity. This quantity was first introduced by László Lovász in his 1979 paper On the Shannon Capacity of a Graph.

In coding theory, Zemor's algorithm, designed and developed by Gilles Zemor, is a recursive low-complexity approach to code construction. It is an improvement over the algorithm of Sipser and Spielman.

<span class="mw-page-title-main">Hyperbolic geometric graph</span>

A hyperbolic geometric graph (HGG) or hyperbolic geometric network (HGN) is a special type of spatial network where (1) latent coordinates of nodes are sprinkled according to a probability density function into a hyperbolic space of constant negative curvature and (2) an edge between two nodes is present if they are close according to a function of the metric (typically either a Heaviside step function resulting in deterministic connections between vertices closer than a certain threshold distance, or a decaying function of hyperbolic distance yielding the connection probability). A HGG generalizes a random geometric graph (RGG) whose embedding space is Euclidean.

In mathematics, the incompressibility method is a proof method like the probabilistic method, the counting method or the pigeonhole principle. To prove that an object in a certain class satisfies a certain property, select an object of that class that is incompressible. If it does not satisfy the property, it can be compressed by computable coding. Since it can be generally proven that almost all objects in a given class are incompressible, the argument demonstrates that almost all objects in the class have the property involved. To select an incompressible object is ineffective, and cannot be done by a computer program. However, a simple counting argument usually shows that almost all objects of a given class can be compressed by only a few bits.

Quantum counting algorithm is a quantum algorithm for efficiently counting the number of solutions for a given search problem. The algorithm is based on the quantum phase estimation algorithm and on Grover's search algorithm.

<span class="mw-page-title-main">Locally linear graph</span> Graph where every edge is in one triangle

In graph theory, a locally linear graph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighbors are each adjacent to exactly one other neighbor, so the neighbors can be paired up into an induced matching. Locally linear graphs have also been called locally matched graphs. Their triangles form the hyperedges of triangle-free 3-uniform linear hypergraphs and the blocks of certain partial Steiner triple systems, and the locally linear graphs are exactly the Gaifman graphs of these hypergraphs or partial Steiner systems.

References

  1. Erickson, Martin J. (2014). Introduction to Combinatorics. Discrete Mathematics and Optimization. Vol. 78 (2nd ed.). John Wiley & Sons. p. 134. ISBN   978-1118640210.
  2. Regan, Kenneth W. (July 10, 2013), "Rough problems", Gödel's Lost Letter and P=NP.
  3. tchow (February 19, 2009), "Shannon capacity of the seven-cycle", Open Problem Garden.
  4. Alon, Noga; Lubetzky, Eyal (2006), "The Shannon capacity of a graph and the independence numbers of its powers", IEEE Transactions on Information Theory, 52 (5): 2172–2176, arXiv: cs/0608021 , doi:10.1109/tit.2006.872856, S2CID   889 .
  5. Lovász, László (1979), "On the Shannon Capacity of a Graph", IEEE Transactions on Information Theory , IT-25 (1): 1–7, doi:10.1109/TIT.1979.1055985, Zbl   0395.94021 .
  6. Haemers, Willem H. (1979), "On Some Problems of Lovász Concerning the Shannon Capacity of a Graph", IEEE Transactions on Information Theory, 25 (2): 231–232, doi:10.1109/tit.1979.1056027, Zbl   0402.94029 .
  7. Haemers, Willem H. (1978), "An upper bound for the Shannon capacity of a graph" (PDF), Colloquia Mathematica Societatis János Bolyai, 25: 267–272. The definition here corrects a typo in this paper.