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]

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.

Definition

edit

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

edit

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

edit

The Lovász number has been computed for the following graphs:[8]

Graph Lovász number
Complete graph  
Empty graph  
Pentagon graph  
Cycle graphs  
Petersen graph  
Kneser graphs  
Complete multipartite graphs  

Properties

edit

If   denotes the strong graph product of graphs   and  , then[9]  

If   is the complement of  , then[10]   with equality if   is vertex-transitive.

Lovász "sandwich theorem"

edit

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.

Relation to Shannon capacity

edit

The Shannon capacity of graph   is defined as follows:   where   is the independence number of graph   (the size of a largest independent set of  ) and   is the strong graph product of   with itself   times. Clearly,  . However, the Lovász number provides an upper bound on the Shannon capacity of graph,[13] hence  

 
Pentagon graph

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]

Quantum physics

edit

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

See also

edit

Notes

edit
  1. ^ Lovász (1979).
  2. ^ 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.
  3. ^ If   then one can always achieve a smaller objective value by restricting   to the subspace spanned by vectors  ; this subspace is at most  -dimensional.
  4. ^ Lovász (1995–2001), Proposition 5.1, p. 28.
  5. ^ Lovász (1979), Theorem 3.
  6. ^ Lovász (1979), Theorem 4.
  7. ^ Lovász (1979), Theorem 5.
  8. ^ Riddle (2003).
  9. ^ Lovász (1979), Lemma 2 and Theorem 7.
  10. ^ Lovász (1979), Corollary 2 and Theorem 8.
  11. ^ Knuth (1994).
  12. ^ Grötschel, Lovász & Schrijver (1981); Todd & Cheung (2012).
  13. ^ Lovász (1979), Theorem 1.
  14. ^ Haemers (1979).
  15. ^ Duan, Severini & Winter (2013).
  16. ^ Cabello, Severini & Winter (2014).
  17. ^ Howard et al. (2014).

References

edit
edit