Lovász Number

The Lovász number, also called the Lovász theta function and written as theta of G, is a real number associated with a graph that gives an upper bound on the graph's Shannon capacity, a measure from information theory of how much information can be reliably sent over a noisy communication channel modeled by that graph. It was introduced by the mathematician László Lovász in his 1979 paper On the Shannon Capacity of a Graph. Although the exact Shannon capacity of a graph is generally hard to compute, the Lovász number can be closely approximated in polynomial time using semidefinite programming and the ellipsoid method, which makes it a practical computational tool. Beyond information theory, the Lovász number has applications in computer science for problems related to graph coloring and to finding a graph's independence number.