Lovász number

Let ${\displaystyle G=(V,E)}$ be a graph on ${\displaystyle n}$ vertices. An ordered set of ${\displaystyle n}$ unit vectors ${\displaystyle U=(u_{i}\mid i\in V)\subset \mathbb {R} ^{N}}$ is called an orthonormal representation of ${\displaystyle G}$ in ${\displaystyle \mathbb {R} ^{N}}$, if ${\displaystyle u_{i}}$ and ${\displaystyle u_{j}}$ are orthogonal whenever vertices ${\displaystyle i}$ and ${\displaystyle j}$ are not adjacent in ${\displaystyle 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 ${\displaystyle N=n}$: just represent vertices by distinct vectors from the standard basis of ${\displaystyle \mathbb {R} ^{N}}$.[2] Depending on the graph it might be possible to take ${\displaystyle N}$ considerably smaller than the number of vertices ${\displaystyle n}$.

The Lovász number ${\displaystyle \vartheta }$ of graph ${\displaystyle G}$ is defined as follows:

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

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

Let ${\displaystyle G=(V,E)}$ be a graph on ${\displaystyle n}$ vertices. Let ${\displaystyle A}$ range over all ${\displaystyle n\times n}$ symmetric matrices such that ${\displaystyle a_{ij}=1}$ whenever ${\displaystyle i=j}$ or vertices ${\displaystyle i}$ and ${\displaystyle j}$ are not adjacent, and let ${\displaystyle \lambda _{\max }(A)}$ denote the largest eigenvalue of ${\displaystyle A}$. Then an alternative way of computing the Lovász number of ${\displaystyle G}$ is as follows:[5]

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

The following method is dual to the previous one. Let ${\displaystyle B}$ range over all ${\displaystyle n\times n}$ symmetric positive semidefinite matrices such that ${\displaystyle b_{ij}=0}$ whenever vertices ${\displaystyle i}$ and ${\displaystyle j}$ are adjacent, and such that the trace (sum of diagonal entries) of ${\displaystyle B}$ is ${\displaystyle \operatorname {Tr} (B)=1}$. Let ${\displaystyle J}$ be the ${\displaystyle n\times n}$ matrix of ones. Then[6]

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

Here, ${\displaystyle \operatorname {Tr} (BJ)}$ is just the sum of all entries of ${\displaystyle B}$.

The Lovász number can be computed also in terms of the complement graph ${\displaystyle {\bar {G}}}$. Let ${\displaystyle d}$ be a unit vector and ${\displaystyle U=(u_{i}\mid i\in V)}$ be an orthonormal representation of ${\displaystyle {\bar {G}}}$. Then[7]

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

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

Graph	Lovász number
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}}$

If ${\displaystyle G\boxtimes H}$ denotes the strong graph product of graphs ${\displaystyle G}$ and ${\displaystyle H}$, then[9]

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

If ${\displaystyle {\bar {G}}}$ is the complement of ${\displaystyle G}$, then[10]

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

with equality if ${\displaystyle G}$ is vertex-transitive.

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,

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

where ${\displaystyle \omega (G)}$ is the clique number of ${\displaystyle G}$ (the size of the largest clique) and ${\displaystyle \chi (G)}$ is the chromatic number of ${\displaystyle G}$ (the smallest number of colors needed to color the vertices of ${\displaystyle 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.[12] 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.

The Shannon capacity of graph ${\displaystyle 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 ${\displaystyle \alpha (G)}$ is the independence number of graph ${\displaystyle G}$ (the size of a largest independent set of ${\displaystyle G}$) and ${\displaystyle G^{k}}$ is the strong graph product of ${\displaystyle G}$ with itself ${\displaystyle k}$ times. Clearly, ${\displaystyle \Theta (G)\geq \alpha (G)}$. However, the Lovász number provides an upper bound on the Shannon capacity of graph,[13] hence

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

Pentagon graph

For example, let the confusability graph of the channel be ${\displaystyle C_{5}}$, a pentagon. Since the original paper of Shannon (1956) it was an open problem to determine the value of ${\displaystyle \Theta (C_{5})}$. It was first established by Lovász (1979) that ${\displaystyle \Theta (C_{5})={\sqrt {5}}}$.

Clearly, ${\displaystyle \Theta (C_{5})\geq \alpha (C_{5})=2}$. However, ${\displaystyle \alpha (C_{5}^{2})\geq 5}$, since "11", "23", "35", "54", "42" are five mutually non-confusable messages (forming a five-vertex independent set in the strong square of ${\displaystyle C_{5}}$), thus ${\displaystyle \Theta (C_{5})\geq {\sqrt {5}}}$.

To show that this bound is tight, let ${\displaystyle U=(u_{1},\dots ,u_{5})}$ 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 ${\displaystyle c=(1,0,0)}$. By using this choice in the initial definition of Lovász number, we get ${\displaystyle \vartheta (C_{5})\leq {\sqrt {5}}}$. Hence, ${\displaystyle \Theta (C_{5})={\sqrt {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.[14]

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]

• 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.

• Weisstein, Eric W., "Lovász Number" ("Sandwich Theorem") at MathWorld.