The Lovász number 
of a finite simple graph 
with at least one graph
vertex, sometimes also called its theta function, was introduced by Lovász
(1979) to estimate its Shannon capacity. For
a graph 
that is not a complete graph,
let 
be the family of nonzero real
symmetric matrices 
such that 
if 
or 
and 
are adjacent in 
, with the other entries unconstrained. Write the eigenvalues as 
,
where 
is the vertex count. 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, also valid for a complete graph, considers the family 
of real symmetric matrices 
such that 
if 
or 
and 
are nonadjacent in 
, with the other entries unconstrained.
Then
 |
(2)
|
Let 
be the Lovász number of a graph 
. 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)
|
For a perfect graph,
 |
(6)
|
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,
 |
(7)
|
(Lovász 1979, Brimkov et al. 2000).
Self-complementary vertex-transitive graphs-including the Paley graphs--have 
, where 
is the vertex count. A
Kneser graph 
, for positive
integers 
and 
with 
, has
 |
(8)
|
(Lovász 1979).
Fung (2011, p. 36) gives the Lovász numbers of the Keller graphs 
, 
, ..., as 4, 6, 28/3, 
, 
, ....
For a random graph 
sampled from 
, Potechin and Xu (2026)
proved that, with high probability,
 |
(9)
|
as 
. This gives the asymptotic value up to vanishing
relative error.
A related asymptotic concerns the expectation value in a dependent-edge model. For odd 
, independently include each cyclic
distance 
, ..., 
with probability 
, and join vertices
of 
whose cyclic distance is included.
For the resulting random circulant graph 
, Chen et al. (2026) proved
 |
(10)
|
as 
through odd integers,
including composite orders. This is an expectation
value result and does not assert concentration with high probability.
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
 |  | ![n{1-(1/2-cos(ax)-cos[x(a+1)])/([cos(ax)-1][cos[x(a+1)]-1])}](/images/equations/LovaszNumber/Inline72.svg) |
(11)
|
 |  | ![n{1-(cos^2y-cosycos(bx)+cos^2(bx)-1)/((cosy+1)[cos(bx)-1][1-cosy+cos(bx)])}](/images/equations/LovaszNumber/Inline75.svg) |
(12)
|
for odd 
in the first formula and odd 
in the second, where 
, 
, 
, and ![b=[(n-3)/6]](/images/equations/LovaszNumber/Inline81.svg)
. Here 
is the floor function,
and ![[z]](/images/equations/LovaszNumber/Inline83.svg)
is the ceiling function. These are special cases
of the formula for integers 
and 
with 
odd and 
 |
(13)
|
where
 |  |  |
(14)
|
 |  |  |
(15)
|
for 
, 2, ..., 
.
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/NumberedEquation12.svg) |
(16)
|
where ![G□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]H](/images/equations/LovaszNumber/Inline96.svg)
denotes the graph strong product (Lovász
1979). In addition, if 
is vertex-transitive, then
 |
(17)
|
where 
denotes the graph complement of 
and 
is its vertex count.
The Haemers number sometimes gives a better bound on the Shannon capacity than does the Lovász number.
