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 , 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. Accurate numerical approximations to this number can be computed in polynomial time by semidefinite programming and the ellipsoid method. The Lovász number of the complement of any graph is sandwiched between the chromatic number and clique number of the graph, and can be used to compute these numbers on graphs for which they are equal, including perfect graphs. 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 . 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 . 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. 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: 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 .