The Lovász number ϑ(G) of a graph G, sometimes also called the theta function of G, was introduced by Lovász with the explicit goal of estimating the Shannon capacity of a graph. Let G be a graph and let A be the family of real matrices A = (a_(i j)) such that a_(i j) = 0 if i and j are adjacent in G, where the other elements are unconstrained. Let the eigenvalues of A be denoted λ_1(A)>=λ_2(A)>=...>=λ_n(A). Then ϑ(G) = max_(A element A)[1 - (λ_1(A))/(λ_n(A))] .

clique number | coloring | sandwich theorem | Shannon capacity