Lovász number ($\vartheta (G)$)

The Lovász number of a finite simple graph is the semidefinite program valuewhere $J$ is the all-ones matrix. Its value on the complement graph gives a lower bound for the chromatic number.

Assign a real unit vector $u_v$ to each graph vertex, with $u_v\perp u_w$ whenever distinct vertices are nonadjacent. A handle is a further unit vector $h$. In the handle formulation of the Lovász number, one minimizes ${\max }_v|h\cdot u_v{|}^{-2}$ over representations and handles. Orthonormal here does not mean every pair of assigned vectors is orthogonal.

Tensor products of the assigned vectors represent strong graph powers, and tensor products of the handle have squared inner products equal to products of the original ones. The vectors assigned to an independent set are orthonormal. Bessel inequality then bounds its size by the largest inverse squared handle inner product. Taking roots and minimizing proves $c(G)\le \vartheta (G)$.

For a finite simple graph with at least one vertex, the complement theta number has the equivalent semidefinite program formulationsandThe Schur complement and $U=tZ-J$ prove the equivalence; any feasible $t$ is at least one, so division by $t$ is valid. For a graph with an edge, $U/(t-1)$ is the Gram matrix of a strict vector coloring. Consequently $\bar{\vartheta }(G)$ is the strict vector chromatic number, and an ordinary $k$-graph colouring gives $\bar{\vartheta }(G)\le k$ by assigning the colors the vertices of a regular simplex.