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.[1]
Let be a
graph on vertices. An ordered set of unit vectors is called an orthonormal representation of in , if and are orthogonal whenever vertices and are not adjacent in :
Clearly, every graph admits an orthonormal representation with : just represent vertices by distinct vectors from the
standard basis of .[2] Depending on the graph it might be possible to take considerably smaller than the number of vertices .
The Lovász number of graph is defined as follows:
where is a unit vector in and is an orthonormal representation of in . Here minimization implicitly is performed also over the dimension , however without loss of generality it suffices to consider .[3] Intuitively, this corresponds to minimizing the half-angle of a rotational
cone containing all representing vectors of an orthonormal representation of . If the optimal angle is , then and corresponds to the symmetry axis of the cone.[4]
Equivalent expressions
Let be a graph on vertices. Let range over all symmetric matrices such that whenever or vertices and are not adjacent, and let denote the largest
eigenvalue of . Then an alternative way of computing the Lovász number of is as follows:[5]
The following method is dual to the previous one. Let range over all symmetric
positive semidefinite matrices such that whenever vertices and are adjacent, and such that the
trace (sum of diagonal entries) of is . Let be the matrix of ones. Then[6]
Here, is just the sum of all entries of .
The Lovász number can be computed also in terms of the
complement graph. Let be a unit vector and be an orthonormal representation of . Then[7]
Value for well-known graphs
The Lovász number has been computed for the following graphs:[8]
The Lovász "sandwich theorem" states that the Lovász number always lies between two other numbers that are
NP-complete to compute.[11] More precisely,
where is the
clique number of (the size of the largest
clique) and is the
chromatic number of (the smallest number of colors needed to color the vertices of so that no two adjacent vertices receive the same color).
The value of 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.[12]
For
perfect graphs, the chromatic number and clique number are equal, and therefore are both equal to . By computing an approximation of and then rounding to the nearest integer value, the chromatic number and clique number of these graphs can be computed in polynomial time.
For example, let the confusability graph of the channel be , a
pentagon. Since the original paper of
Shannon (1956) it was an open problem to determine the value of . It was first established by
Lovász (1979) that .
Clearly, . However, , since "11", "23", "35", "54", "42" are five mutually non-confusable messages (forming a five-vertex independent set in the strong square of ), thus .
To show that this bound is tight, let be the following orthonormal representation of the pentagon:
and let . By using this choice in the initial definition of Lovász number, we get . Hence, .
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.[14]
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 monotone
circuit complexity.
^A representation of vertices by standard basis vectors will not be faithful, meaning that adjacent vertices are represented by non-orthogonal vectors, unless the graph is edgeless. A faithful representation in 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 closed neighbourhood.
^If then one can always achieve a smaller objective value by restricting to the subspace spanned by vectors ; this subspace is at most -dimensional.