en>Gandalf61: Add examples

2013-07-03T12:42:22Z

Add examples

New page

In [[graph theory]], the '''Shannon capacity of a graph''' is a [[graph invariant]] defined from the number of [[independent set (graph theory)|independent set]]s of [[strong graph product]]s. 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 <ref name="sh56">{{citation | first = Claude E. | last = Shannon | title = The Zero-Error Capacity of a Noisy Channel | journal = IRE Trans. Inform. Th. | volume = 2 |pages = 8–19 | year = 1956 }}. Reprinted in Key papers in the development of information theory (D. Slepian, Ed.), New York: IEEE Press, 1974, 112--123.</ref> of a graph ''G'' is defined as
:<math>
\Theta(G)
= \sup_k \sqrt[k]{\alpha(G^k)}
= \lim_{k \rightarrow \infty} \sqrt[k]{\alpha(G^k)},
</math>

where α(''G'') is the [[independence number]] of [[graph (mathematics)|graph]] ''G'' (the size of a largest [[independent set (graph theory)|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 (graph theory)|independent set]] of ''Gk'', 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==
[[File:Cycle graph C5.png|thumb|100px|Pentagon graph]]
Let ''C''5 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''52, showing that Θ(''C''5) ≥ {{sqrt|5}}. But as {{harvtxt|Lovász|1979}} showed, this bound is tight:
Θ(''C''5) = {{sqrt|5}}.

==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'').<ref name="l79">{{citation | first = László | last = Lovász | authorlink = László Lovász | title = On the Shannon Capacity of a Graph | journal = [[IEEE Transactions on Information Theory]] | volume = IT-25 | issue = 1 | year = 1979}}.</ref> In some cases, ϑ(''G'') and the Shannon capacity coincide; for instance, for the graph of a [[pentagon]], both are equal to {{sqrt|5}}. However, there exist other graphs for which the Shannon capacity and the Lovász number differ.<ref name="h79">{{citation | first = Willem H. | last = Haemers | title = On Some Problems of Lovász Concerning the Shannon Capacity of a Graph | journal = IEEE Transactions on Information Theory | volume = 25 |pages = 231–232 | year = 1979 | url = http://arno.uvt.nl/show.cgi?fid=80311}}.</ref>

==Haemers' bound==
Haemers provided another bound on the Shannon capacity, which is sometimes better than Lovász bound:<ref>{{citation | first = Willem H. | last = Haemers | title = An upper bound for the Shannon capacity of a graph | journal = Colloquia Mathematica Societatis János Bolyai | volume = 25 | pages = 267–272 | year = 1978 | url = http://arno.uvt.nl/show.cgi?fid=80314}}. The definition here corrects a typo in this paper.</ref>
:<math>
\Theta(G) \leq R(G) = \min_{B} \operatorname{rank}(B),
</math>
where ''B'' is an ''n'' × ''n'' matrix over some [[field (mathematics)|field]], such that ''bii'' ≠ 0 and ''bij'' = 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''7 (a [[cycle graph]] of seven vertices) remains unknown.<ref>{{citation|title=Rough problems|work=Gödel's Lost Letter and P=NP|first=Kenneth W.|last=Regan|date=July 10, 2013|url=http://rjlipton.wordpress.com/2013/07/10/rough-problems/}}.</ref>

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.<ref>{{citation|title=The Shannon capacity of a graph and the independence numbers of its powers|arxiv=cs/0608021|first1=Noga|last1=Alon|author1-link=Noga Alon|first2=Eyal|last2=Lubetzky|journal=IEEE Transactions on Information Theory|volume=52|year=2006|pages=2172–2176}}.</ref>

==References==
{{reflist}}

[[Category:Graph invariants]]
[[Category:Information theory]]

Integer-valued function - Revision history

en>Gandalf61: Add examples