Lovász number

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 ϑ(G). This quantity was first introduced by László Lovász in his 1979 paper On the Shannon Capacity of a Graph.^[1]

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.

Definition[]

Let G = (V, E) be a graph on n vertices. An ordered set of n unit vectors U = (u_i | i ∈ V) ⊂ R^N is called an orthonormal representation of G in R^N, if u_i and u_j are orthogonal whenever vertices i and j are not adjacent in G:

${\displaystyle u_{i}^{\mathrm {T} }u_{j}={\begin{cases}1,&{\text{if }}i=j,\\0,&{\text{if }}ij\notin E.\end{cases}}}$

Clearly, every graph admits an orthonormal representation with N = n (just represent vertices by distinct vectors from the standard basis of Rⁿ, though this will not in general be faithful unless the graph is edgeless; a faithful representation in N = n is also possible by associating each vertex to a basis vector as before, but mapping each vertex to the sum of basis vectors associated with its neighbourhood), but in general it might be possible to take N considerably smaller than the number of vertices n.

The Lovász number ϑ of graph G is defined as follows:

${\displaystyle \vartheta (G)=\min _{c,U}\max _{i\in V}{\frac {1}{(c^{\mathrm {T} }u_{i})^{2}}},}$

where c is a unit vector in R^N and U is an orthonormal representation of G in R^N. Here minimization implicitly is performed also over the dimension N, however without loss of generality it suffices to consider N = n.^[2] Intuitively, this corresponds to minimizing the half-angle of a rotational cone containing all representing vectors of an orthonormal representation of G. If the optimal angle is ϕ, then ϑ(G) = 1/cos²(ϕ) and c corresponds to the symmetry axis of the cone.^[3]

Equivalent expressions[]

Let G = (V, E) be a graph on n vertices. Let A range over all n × n symmetric matrices such that a_ij = 1 whenever i = j or ij ∉ E, and let λ_max(A) denote the largest eigenvalue of A. Then an alternative way of computing the Lovász number of G is as follows:^[4]

${\displaystyle \vartheta (G)=\min _{A}\lambda _{\max }(A).}$

The following method is dual to the previous one. Let B range over all n × n symmetric positive semidefinite matrices such that b_ij = 0 for every ij ∈ E and Tr(B) = 1. Here Tr denotes trace (the sum of diagonal entries) and J is the n × n matrix of ones. Then^[5]

${\displaystyle \vartheta (G)=\max _{B}\operatorname {Tr} (BJ).}$

Tr(BJ) is just the sum of all entries of B.

The Lovász number can be computed also in terms of the complement graph G. Let d be a unit vector and V = (v_i | i ∈ V) be an orthonormal representation of G. Then^[6]

${\displaystyle \vartheta (G)=\max _{d,V}\sum _{i\in V}(d^{\mathrm {T} }v_{i})^{2}.}$

Value of ϑ for some well-known graphs[]

Graph	Value of ϑ[7]
Complete graph	${\displaystyle \vartheta (K_{n})=1}$
Empty graph	${\displaystyle \vartheta ({\bar {K}}_{n})=n}$
Pentagon graph	${\displaystyle \vartheta (C_{5})={\sqrt {5}}}$
Cycle graphs	${\displaystyle \vartheta (C_{n})={\begin{cases}{\frac {n\cos(\pi /n)}{1+\cos(\pi /n)}}&{\text{for odd }}n,\\{\frac {n}{2}}&{\text{for even }}n\end{cases}}}$
Petersen graph	${\displaystyle \vartheta (KG_{5,2})=4}$
Kneser graphs	${\displaystyle \vartheta (KG_{n,k})={\binom {n-1}{k-1}}}$
Complete multipartite graphs	${\displaystyle \vartheta (K_{n_{1},\dots ,n_{k}})=\max _{1\leq i\leq k}n_{i}}$

Properties[]

If G ⊠ H denotes the strong graph product of graphs G and H, then^[8]

${\displaystyle \vartheta (G\boxtimes H)=\vartheta (G)\vartheta (H).}$

If G is the complement of G, then^[9]

${\displaystyle \vartheta (G)\vartheta ({\bar {G}})\geq n,}$

with equality if G is vertex-transitive.

Lovász "sandwich theorem"[]

The Lovász "sandwich theorem" states that the Lovász number always lies between two other numbers that are NP-complete to compute.^[10] More precisely,

${\displaystyle \omega (G)\leq \vartheta ({\bar {G}})\leq \chi (G),}$

where ω(G) is the clique number of G (the size of the largest clique) and χ(G) is the chromatic number of G (the smallest number of colors needed to color the vertices of G so that no two adjacent vertices receive the same color).

The value of ${\displaystyle \vartheta (G)}$ can be formulated as a semidefinite program and numerically approximated by the ellipsoid method in time bounded by a polynomial in the number of vertices of G.^[11] For perfect graphs, the chromatic number and clique number are equal, and therefore are both equal to ${\displaystyle \vartheta ({\bar {G}})}$. By computing an approximation of ${\displaystyle \vartheta ({\bar {G}})}$ and then rounding to the nearest integer value, the chromatic number and clique number of these graphs can be computed in polynomial time.

Relation to Shannon capacity[]

The Shannon capacity of graph G is defined as follows:

${\displaystyle \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. Clearly, Θ(G) ≥ α(G). However, the Lovász number provides an upper bound on the Shannon capacity of graph,^[12] hence

${\displaystyle \alpha (G)\leq \Theta (G)\leq \vartheta (G).}$

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:

${\displaystyle u_{k}={\begin{pmatrix}\cos {\theta }\\\sin {\theta }\cos {\varphi _{k}}\\\sin {\theta }\sin {\varphi _{k}}\end{pmatrix}},\quad \cos {\theta }={\frac {1}{\sqrt[{4}]{5}}},\quad \varphi _{k}={\frac {2\pi k}{5}}}$

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.^[13]

Quantum physics[]

The Lovász number has been generalized for "non-commutative graphs" in the context of quantum communication.^[14] The Lovasz number also arises in quantum contextuality^[15] in an attempt to explain the power of quantum computers.^[16]

See also[]

• Tardos function, a monotone approximation to the Lovász number of the complement graph that can be computed in polynomial time and has been used to prove lower bounds in circuit complexity

Notes[]

References[]

External links[]

• Weisstein, Eric W. "Lovász Number". MathWorld.
• Weisstein, Eric W. "Sandwich Theorem". MathWorld.
• Weisstein, Eric W. "Shannon Capacity". MathWorld.