Lovász Number

👁 DOWNLOAD Mathematica Notebook
Download Wolfram Notebook

The Lovász number 👁 theta(G)
of a graph 👁 G
, sometimes also called the theta function of 👁 G
, was introduced by Lovász (1979) 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_(ij))
such that 👁 a_(ij)=0
if 👁 i
and 👁 j
are adjacent in 👁 G
, where the other elements are unconstrained. Let the eigenvalues of 👁 A
be denoted 👁 lambda_1(A)>=lambda_2(A)>=...>=lambda_n(A)
. Then

(Lovász 1979, Knuth 1994, Brimkov et al. 2000).

An equivalent definition considers 👁 B
the family of real matrices 👁 B=(b_(ij))
such that 👁 b_(ij)=0
if 👁 i=j
or 👁 i
and 👁 j
are adjacent in 👁 G
and other elements unconstrained. Then

Let 👁 theta(G)
be the Lovász number of a graph of 👁 G
. Then

where 👁 omega(G)
is the clique number and 👁 chi(G)
is the chromatic number of 👁 G
. This is the sandwich theorem. It can be rewritten by changing the role of graph complements, giving

which can be written using 👁 omega(G^_)=alpha(G)
with 👁 alpha
the independence number and 👁 theta(G)=chi(G^_)
the clique covering number as

For a perfect graph,

Despite much work on the problem of determining 👁 theta(G)
, finding explicit values for interesting special cases of graphs remains an open problem (Brimkov et al. 2000). However, explicit formulas are known for 👁 theta(G)
for several families of simple graphs. For example, for the cycle graph 👁 C_n
with 👁 n>=3
and odd,

(Lovász 1979, Brimkov et al. 2000).

Self-complementary vertex-transitive graphs-including the Paley graphs--have 👁 theta(G)=sqrt(V(G))
and a Kneser graph 👁 K(n,r)
has

(Lovász 1979).

Fung (2011) gives the Lovász numbers of the Keller graphs 👁 G_1
, 👁 G_2
, ..., as 4, 6, 28/3, 👁 2^4
, 👁 2^5
, ....

The following table gives some special cases.

Brimkov et al. (2000) determined the additional closed forms for quartic circulant graphs, namely

for odd 👁 n
, where

👁 |_z_|
is the floor function, and 👁 [z]
is the ceiling function. These are special cases of the formula

where

The Lovász number satisfies

where 👁 G□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]H
denotes the graph strong product (Lovász 1979). In addition, if 👁 G
is vertex-transitive, then

where 👁 G^_
denotes the graph complement of 👁 G
.

The Haemers number sometimes gives a better bound on the Shannon capacity than does the Lovász number.

See also

Clique Number, Coloring, Haemers Number, Sandwich Theorem, Shannon Capacity

Explore with Wolfram|Alpha

References

Brimkov, V. E.; Codenotti, B.; Crespi, V.; and Leoncini, M. "On the Lovász Number of Certain Circulant Graphs." In Algorithms and Complexity. Papers from the 4th Italian Conference (CIAC 2000) Held in Rome, March 1-3, 2000 (Ed. G. Bongiovanni, G. Gambosi, and R. Petreschi). Berlin: Springer-Verlag, pp. 291-305, 2000.Fung, M. "The Lovász Number of the Keller Graphs." Master thesis. Universiteit Leiden: Mathematisch Instituut, 2011.Knuth, D. E. "The Sandwich Theorem." Electronic J. Combinatorics 1, No. 1, A1, 1-48, 1994. http://www.combinatorics.org/Volume_1/Abstracts/v1i1a1.html.Lovász, L. "On the Shannon Capacity of a Graph." IEEE Trans. Inform. Th. IT-25, 1-7, 1979.Schrijver, A. "A Comparison of the Delsarte and Lovász Bounds." IEEE Trans. Inform. Th. 25, 425-429, 1979.Shannon, C. E. "The Zero-Error Capacity of a Noisy Channel." IRE Trans. Inform. Th. 2, 8-19, 1956.Skarakis, C. "The Sandwich Theorem." §4.2.3 in "Convex Optimization: Theory and Practice." MSc dissertation. York, UK: Department of Mathematics, University of York, pp. 43-46, Aug. 22, 2008. http://keithbriggs.info/documents/Skarakis_MSc.pdf.

Referenced on Wolfram|Alpha

Lovász Number

Cite this as:

Weisstein, Eric W. "Lovász Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/LovaszNumber.html

Subject classifications