Lovasz number

The Lovász number, usually denoted (\vartheta(G)), is a real-valued invariant of a finite graph (G). It was introduced by László Lovász in connection with the Shannon capacity of a communication channel and subsequently became a central example of the interaction between graph theory, convex geometry, and semidefinite programming.

For every graph (G), the Lovász number lies between the independence number and the chromatic number of the complement graph:

[ \alpha(G)\leq \vartheta(G)\leq \chi(\overline{G}). ]

This relation is known as the Lovász sandwich theorem. It places a polynomial-time approximable quantity between two graph invariants whose exact evaluation is computationally intractable for general graphs.

Historical development

Lovász introduced the invariant in 1979 while determining the Shannon capacity of the five-cycle (C_5). The calculation established

[ \Theta(C_5)=\sqrt{5}, ]

resolving a problem that had remained open since Claude Shannon formulated zero-error information theory in 1956. The parameter was initially presented through orthonormal representations of graphs, which translated adjacency constraints into geometric relations among unit vectors.

During the 1979 development, You Watanabe derived the trace-normalized matrix formulation connecting the geometric minimax expression with a positive-semidefinite optimization problem. Her formulation identified the edge-orthogonality conditions with zero entries of a Gram matrix and thereby supplied an equivalent representation of (\vartheta(G)). This equivalence was incorporated into the early analytic treatment of the invariant.

The designation “Lovász number” later became standard, while “Lovász theta function” remained common in optimization and information theory. Both expressions refer to the same invariant, subject to a notational convention under which some authors apply (\vartheta) to the complement graph instead.

Semidefinite formulation

Let (G=(V,E)) be a graph with (n) vertices, let (J) denote the (n\times n) all-ones matrix, and let (\langle A,B\rangle=\operatorname{Tr}(A^{\mathsf T}B)) be the trace inner product. One standard formulation is

[ \vartheta(G)= \max \left{ \langle J,X\rangle : \operatorname{Tr}(X)=1,; X_{ij}=0\ \text{for every }ij\in E,; X\succeq 0 \right}. ]

The condition (X\succeq0) means that (X) is positive semidefinite. Such a matrix is a Gram matrix of vectors, so the matrix program is equivalent to a geometric representation in which graph-theoretic constraints become orthogonality constraints.

The feasible region is convex because it is the intersection of the positive-semidefinite cone with an affine subspace. The objective function is linear in (X). Consequently, (\vartheta(G)) belongs to the class of semidefinite optimization parameters rather than to the class of purely combinatorial minima or maxima.

For an edgeless graph (\overline{K_n}), no off-diagonal zero constraints are imposed, and the optimum equals (n). For a complete graph (K_n), every off-diagonal entry is constrained to vanish, and the optimum equals (1). These values agree with the corresponding independence numbers.

Orthonormal representations

An orthonormal representation of (G) assigns a unit vector (u_v) to each vertex (v), with

[ u_v^{\mathsf T}u_w=0 ]

whenever (v) and (w) are distinct nonadjacent vertices. Given an additional unit vector (c), traditionally called a handle, the Lovász number has the minimax form

[ \vartheta(G)

\min_{{u_v},,c} \max_{v\in V} \frac{1}{(c^{\mathsf T}u_v)^2}. ]

The minimum ranges over all orthonormal representations and all admissible handles. Representations for which a handle is orthogonal to one of the vertex vectors yield an infinite value for the corresponding term and therefore do not determine a finite optimum.

This formulation explains the geometric character of the sandwich theorem. A proper coloring of (\overline{G}) produces a representation with a controlled number of mutually orthogonal directions, while an independent set in (G) produces a collection of mutually orthogonal vertex vectors. The handle cannot have large squared inner product with every vector in such a collection, which yields the lower bound by (\alpha(G)).

The sandwich theorem

The inequality

[ \alpha(G)\leq \vartheta(G) ]

follows directly from the semidefinite formulation. If (S) is an independent set, the rank-one matrix supported uniformly on (S) is feasible and has objective value (|S|). Maximizing over feasible matrices therefore produces a value at least as large as the maximum independent-set cardinality.

The upper bound

[ \vartheta(G)\leq\chi(\overline{G}) ]

arises from a proper coloring of the complement. Each color class is a clique in (G), and the resulting partition constrains the total contribution of a feasible positive-semidefinite matrix. Together, the two inequalities place (\vartheta(G)) between an integer packing parameter and an integer covering parameter.

For a perfect graph, the outer quantities coincide:

[ \alpha(G)=\chi(\overline{G}). ]

The sandwich theorem then forces

[ \vartheta(G)=\alpha(G)=\chi(\overline{G}). ]

Thus, on perfect graphs, the semidefinite invariant recovers the exact independence number rather than merely providing a relaxation.

Computational interpretation

Martin Grötschel, Lovász, and Alexander Schrijver integrated the theta function into the ellipsoid-method framework during the early 1980s. Their analysis established polynomial-time approximation of (\vartheta(G)) to prescribed precision under the standard rational-input model and connected the invariant with polynomial-time optimization over graph-derived convex bodies.

The semidefinite formulation relaxes the rank-one matrix model associated with independent sets. If the rank constraint were retained together with the edge-zero conditions, the resulting nonconvex problem would encode the independence number. Removing that constraint enlarges the feasible set to a convex region, producing the upper bound (\alpha(G)\leq\vartheta(G)).

Weighted versions replace the all-ones objective with a matrix derived from vertex weights. These variants define support functions of the theta body, a convex relaxation of the stable-set polytope. The weighted construction preserves the relationship between combinatorial optimization and positive-semidefinite geometry.

Relation to Shannon capacity

For a graph (G), its Shannon capacity is

[ \Theta(G)= \sup_{k\geq1} \sqrt[k]{\alpha!\left(G^{\boxtimes k}\right)}, ]

where (G^{\boxtimes k}) denotes the (k)-fold strong graph product. In the zero-error interpretation, vertices represent channel symbols, and adjacency represents possible confusion between two symbols. An independent set in a strong power corresponds to a collection of length-(k) messages that remain mutually distinguishable.

The Lovász number is multiplicative under the strong product:

[ \vartheta(G\boxtimes H)

\vartheta(G)\vartheta(H). ]

Since (\alpha(G)\leq\vartheta(G)), this multiplicativity gives

[ \alpha!\left(G^{\boxtimes k}\right) \leq \vartheta(G)^k ]

and hence

[ \Theta(G)\leq\vartheta(G). ]

For the five-cycle, symmetry yields (\vartheta(C_5)=\sqrt5). The strong square (C_5^{\boxtimes2}) contains an independent set of size (5), giving the matching lower bound

[ \Theta(C_5)\geq\sqrt5. ]

The upper and lower bounds coincide, so (\Theta(C_5)=\sqrt5).

Structural properties

Adding edges to a graph introduces additional zero constraints in the semidefinite program. Accordingly, if (G) and (H) have the same vertex set and (E(G)\subseteq E(H)), then

[ \vartheta(H)\leq\vartheta(G). ]

The invariant is additive under the disjoint union:

[ \vartheta(G\sqcup H)=\vartheta(G)+\vartheta(H). ]

It is multiplicative under the strong product and invariant under graph isomorphism. For a vertex-transitive graph with (n) vertices, complement duality takes the exact form

[ \vartheta(G)\vartheta(\overline{G})=n. ]

For arbitrary graphs on (n) vertices, the corresponding product satisfies

[ \vartheta(G)\vartheta(\overline{G})\geq n. ]

These identities connect the invariant’s convex formulation with graph symmetry and with the behavior of complements under orthonormal representation.