The Lovász number 
of a graph 
,
sometimes also called the theta function of 
, was introduced by Lovász (1979) with the explicit
goal of estimating the Shannon capacity of a
graph. Let 
be a graph and let 
be the family of real matrices 
such that 
if 
and 
are adjacent in 
, where the other elements are unconstrained. Let the eigenvalues
of 
be denoted 
. Then
![theta(G)=max_(A in A)[1-(lambda_1(A))/(lambda_n(A))]](/images/equations/LovaszNumber/NumberedEquation1.svg) |
(1)
|
(Lovász 1979, Knuth 1994, Brimkov et al. 2000).
An equivalent definition considers 
the family of real matrices 
such that 
if 
or 
and 
are adjacent in 
and other elements unconstrained. Then
 |
(2)
|
Let 
be the Lovász number of a graph of 
. Then
 |
(3)
|
where 
is the clique number and 
is the chromatic number
of 
. This is the sandwich
theorem. It can be rewritten by changing the role of graph complements, giving
 |
(4)
|
which can be written using 
with 
the independence number and 
the clique
covering number as
 |
(5)
|
Despite much work on the problem of determining 
, finding explicit values for interesting special cases
of graphs remains an open problem (Brimkov et al. 2000). However, explicit
formulas are known for 
for several families of simple graphs. For example, for the cycle
graph 
with 
and odd,
 |
(6)
|
(Lovász 1979, Brimkov et al. 2000).
Self-complementary vertex-transitive graphs-including the Paley graphs--have 
and a Kneser
graph 
has
 |
(7)
|
(Lovász 1979).
Fung (2011) gives the Lovász numbers of the Keller graphs 
,
, ..., as 4, 6, 28/3, 
, 
, ....
The following table gives some special cases.
graph  |  |
cocktail
party graph  | 2 |
complete
graph  | 1 |
complete
k-partite graph  |  |
cycle graph  |  |
empty graph  |  |
Kneser
graph  |  |
| Paley graph |  |
cycle graph  |  |
Petersen
graph  | 4 |
Brimkov et al. (2000) determined the additional closed forms for quartic circulant graphs, namely
![theta(Ci_(1,2)(n))=n{1-(1/2-cos(ax)-cos[x(a+1)])/([cos(ax)-1][cos(ax+1)-1])}
theta(Ci_(1,3)(n))
=n{1-(cos^2y-cosycos(bx)+cos^2(bx)-1)/((cosy+1)[cos(bx)-1][1-cosy+cos(bx)])}](/images/equations/LovaszNumber/NumberedEquation8.svg) |
(8)
|
for odd 
,
where
 |  |  |
(9)
|
 |  |  |
(10)
|
 |  |  |
(11)
|
 |  | ![[(n-3)/6],](/images/equations/LovaszNumber/Inline66.svg) |
(12)
|
is the floor
function, and ![[z]](/images/equations/LovaszNumber/Inline68.svg)
is the ceiling function. These are special cases
of the formula
 |
(13)
|
where
 |  |  |
(14)
|
 |  |  |
(15)
|
The Lovász number satisfies
![theta(G□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]H)<=theta(G)theta(H),](/images/equations/LovaszNumber/NumberedEquation10.svg) |
(16)
|
where ![G□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]H](/images/equations/LovaszNumber/Inline75.svg)
denotes the graph strong product (Lovász
1979). In addition, if 
is vertex-transitive, then
 |
(17)
|
where 
denotes the graph complement of 
.
The Haemers number sometimes gives a better bound on the Shannon capacity than does the Lovász number.
