page_title: Lovász number
section_title: Relation to Shannon capacity
hierarchical_section_title: Lovász number / Relation to Shannon capacity
context_page_description: 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 ϑ. This quantity was first introduced by László Lovász in his 1979 paper On the Shannon Capacity of a Graph.
  Accurate numerical approximations to this number can be computed in polynomial time by semidefinite programming and the ellipsoid method.
  It is sandwiched between the chromatic number and clique number of any graph, and can be used to compute these numbers on graphs for which they are equal, including perfect graphs.
context_section_description: The Shannon capacity of graph G is defined as follows:
  where α(G) is the independence number of graph G (the size of a largest independent set of G) and Gᵏ is the strong graph product of G with itself k times. Clearly, Θ(G) ≥ α(G). However, the Lovász number provides an upper bound on the Shannon capacity of graph, hence
  For example, let the confusability graph of the channel be C₅, a pentagon. Since the original paper of Shannon (1956) it was an open problem to determine the value of Θ(C₅). It was first established by Lovász (1979) that Θ(C₅) = √5.
  Clearly, Θ(C₅) ≥ α(C₅) = 2. However, α(C₅²) ≥ 5, since "11", "23", "35", "54", "42" are five mutually non-confusable messages (forming a five-vertex independent set in the strong square of C₅), thus Θ(C₅) ≥ √5.
  To show that this bound is tight, let U = (u₁, ..., u₅) be the following orthonormal representation of the pentagon:
  and let c = (1, 0, 0). By using this choice in the initial definition of Lovász number, we get ϑ(C₅) ≤ √5. Hence, Θ(C₅) = √5.
  However, there exist graphs for which the Lovász number and Shannon capacity differ, so the Lovász number cannot in general be used to compute exact Shannon capacities.
caption: Pentagon graph
exif: {}