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. 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. 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. Let G = (V, E) be a graph on n vertices. An ordered set of n unit vectors U = (ui | i ∈ V) ⊂ RN is called an orthonormal representation of G in RN, if ui and uj are orthogonal whenever vertices i and j are not adjacent in G: Clearly, every graph admits an orthonormal representation with N = n (just represent vertices by distinct vectors from the standard basis of Rn, 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: where c is a unit vector in RN and U is an orthonormal representation of G in RN. Here minimization implicitly is performed also over the dimension N, however without loss of generality it suffices to consider N = n. 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/cos2(ϕ) and c corresponds to the symmetry axis of the cone. Let G = (V, E) be a graph on n vertices. Let A range over all n × n symmetric matrices such that aij = 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: The following method is dual to the previous one. Let B range over all n × n symmetric positive semidefinite matrices such that bij = 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 Tr(BJ) is just the sum of all entries of B.