View source for Gradually varied surface

In [[graph theory]], the '''Lovász number''' of a [[graph (mathematics)|graph]] is a [[real number]] that is an [[upper bound]] on the [[Shannon capacity of a graph|Shannon capacity]] of the graph. It is also known as '''Lovász theta function''' and is commonly denoted by [[ϑ]](''G''). This quantity was first introduced by [[László Lovász]] in his 1979 paper ''On the Shannon Capacity of a Graph''.<ref>{{harvtxt|Lovász|1979}}.</ref>

== Definition ==

Let ''G''&nbsp;=&nbsp;(''V'',&nbsp;''E'') be a [[graph (mathematics)|graph]] on ''n'' vertices. An ordered set of ''n'' [[unit vector]]s ''U''&nbsp;=&nbsp;(''u''<sub>''i''</sub>&nbsp;|&nbsp;''i''&nbsp;∈&nbsp;''V'')&nbsp;⊂&nbsp;'''R'''<sup>''N''</sup> is called an '''orthonormal representation''' of ''G'' in '''R'''<sup>''N''</sup>, if ''u''<sub>''i''</sub> and ''u''<sub>''j''</sub> are orthogonal whenever vertices ''i'' and ''j'' are ''not'' adjacent in ''G'':
:<math>
  u_i^\mathrm{T} u_j =
  \begin{cases}
    1, & \mbox{if }i = j, \\
    0, & \mbox{if }ij \notin E.
  \end{cases}
</math>
Clearly, every graph admits an orthonormal representation with ''N'' = ''n'' (just represent vertices by distinct vectors from the [[standard basis]] of '''R'''<sup>''n''</sup>), but in general it might be possible to take ''N'' considerably smaller than the number of vertices ''n''.

The '''Lovász number''' ϑ of graph ''G'' is defined as follows:
:<math>
  \vartheta(G) = \min_{c, U} \max_{i \in V} \frac{1}{(c^\mathrm{T} u_i)^2},
</math>
where ''c'' is a unit vector in '''R'''<sup>''N''</sup> and ''U'' is an orthonormal representation of ''G'' in '''R'''<sup>''N''</sup>. Here minimization implicitly is performed also over the dimension ''N'', however without loss of generality it suffices to consider ''N''&nbsp;=&nbsp;''n''.<ref>If ''N''&nbsp;>&nbsp;''n'' then one can always achieve a smaller objective value by restricting ''c'' to the subspace spanned by vectors ''u''<sub>''i''</sub> which is at most ''n''-dimensional.</ref> Intuitively, this corresponds to minimizing the half-angle of a rotational [[cone (geometry)|cone]] containing all representing vectors of an orthonormal representation of ''G''. If the optimal angle is ϕ, then ϑ(''G'')&nbsp;=&nbsp;1/cos<sup>2</sup>(ϕ) and ''c'' corresponds to the symmetry axis of the cone.<ref>See Proposition 5.1 in {{harvtxt|Lovász|1995&ndash;2001}}, pp. 28.</ref>

== Equivalent expressions ==

Let ''G''&nbsp;=&nbsp;(''V'',&nbsp;''E'') be a graph on ''n'' vertices. Let ''A'' range over all ''n''&nbsp;&times;&nbsp;''n'' [[symmetric matrix|symmetric matrices]] such that ''a''<sub>''ij''</sub>&nbsp;=&nbsp;1 whenever ''i''&nbsp;=&nbsp;''j'' or ''ij''&nbsp;∉&nbsp;''E'', and let λ<sub>max</sub>(''A'') denote the largest [[eigenvalue]] of ''A''. Then an alternative way of computing the Lovász number of ''G'' is as follows:<ref>See Theorem 3 in {{harvtxt|Lovász|1979}}.</ref>
:<math>
  \vartheta(G) = \min_A \lambda_\text{max}(A).
</math>

The following method is dual to the previous one. Let ''B'' range over all ''n''&nbsp;&times;&nbsp;''n'' symmetric [[positive semidefinite matrix|positive semidefinite matrices]] such that ''b''<sub>''ij''</sub>&nbsp;=&nbsp;0 for every ''ij''&nbsp;∈&nbsp;''E'' and Tr(''B'')&nbsp;=&nbsp;1. Here Tr denotes [[trace (linear algebra)|trace]] (the sum of diagonal entries) and ''J'' is the ''n''&nbsp;&times;&nbsp;''n'' [[matrix of ones]]. Then<ref>See Theorem 4 in {{harvtxt|Lovász|1979}}.</ref>
:<math>
  \vartheta(G) = \max_B \operatorname{Tr}(BJ).
</math>
Note that Tr(''BJ'') is just the sum of all entries of ''B''.

The Lovász number can be computed also in terms of the [[complement graph]] {{overline|''G''}}. Let ''d'' be a unit vector and ''V'' = (''v''<sub>''i''</sub> | ''i'' ∈ ''V'') be an orthonormal representation of {{overline|''G''}}. Then<ref>See Theorem 5 in {{harvtxt|Lovász|1979}}.</ref>
:<math>
  \vartheta(G) = \max_{d,V} \sum_{i \in V} (d^\mathrm{T} v_i)^2.
</math>

== Value of &thetasym; for some well-known graphs ==

{| class="wikitable"
! Graph || Value of ϑ<ref>{{harvtxt|Riddle|2003}}.</ref>
|-
| [[Complete graph]] || <math> \vartheta(K_n) = 1 </math>
|-
| [[Empty graph]]    || <math> \vartheta(\bar{K}_n) = n </math>
|-
| [[Pentagon]] graph || <math> \vartheta(C_5) = \sqrt{5} </math>
|-
| [[Cycle graph]]s   || <math> \vartheta(C_n) =
\begin{cases}
  \frac{n \cos(\pi/n)}{1 + \cos(\pi/n)} & \text{for odd }  n, \\
  \frac{n}{2}                           & \text{for even } n
\end{cases}
</math>
|-
| [[Petersen graph]] || <math> \vartheta(KG_{5,2}) = 4 </math>
|-
| [[Kneser graph]]s  || <math> \vartheta(KG_{n,k}) = \binom{n-1}{k-1} </math>
|-
| Complete multipartite graphs || <math> \vartheta(K_{n_1,\dots,n_k}) = \max_{1 \leq i \leq k} n_i </math>
|}

== Properties ==

If ''G''&nbsp;⊠&nbsp;''H'' denotes the [[strong graph product]] of graphs ''G'' and ''H'', then<ref>See Lemma 2 and Theorem 7 in {{harvtxt|Lovász|1979}}.</ref>
:<math> \vartheta(G \boxtimes H) = \vartheta(G) \vartheta(H). </math>

If {{overline|''G''}} is the [[complement graph|complement]] of ''G'', then<ref>See Corollary 2 in {{harvtxt|Lovász|1979}}.</ref>
:<math> \vartheta(G) \vartheta(\bar{G}) \geq n. </math>

== Lovász "sandwich theorem" ==

The Lovász "sandwich theorem" states that the Lovász number always lies between two other numbers that are [[NP-complete]] to compute.<ref>{{harvtxt|Knuth|1994}}.</ref> More precisely,
:<math> \omega(G) \leq \vartheta(\bar{G}) \leq \chi(G), </math>
where ω(''G'') is the [[clique number]] of ''G'' (the size of the largest [[clique]]) and χ(''G'') is the [[chromatic number]] of ''G'' (the smallest number of colors needed to color the vertices of ''G'' so that no two adjacent vertices receive the same color). However, the value of ϑ(''G'') can be approximated by the [[ellipsoid method]] in time bounded by a [[polynomial time|polynomial]] in the number of vertices of ''G''.<ref>{{harvtxt|Grötschel|Lovász|Schrijver|1981}}.</ref>

== Relation to Shannon capacity ==
The [[Shannon capacity of a graph|Shannon capacity]] of graph ''G'' is defined as follows:
:<math>
 \Theta(G)
 = \sup_k \sqrt[k]{\alpha(G^k)}
 = \lim_{k \rightarrow \infty} \sqrt[k]{\alpha(G^k)},
</math>
where α(''G'') is the [[independence number]] of [[graph (mathematics)|graph]] ''G'' (the size of a largest [[independent set (graph theory)|independent set]] of ''G'') and ''G''<sup>k</sup> is the [[strong graph product]] of ''G'' with itself ''k'' times. Clearly, Θ(''G'') ≥ α(''G''). However, the Lovász number provides an upper bound on the Shannon capacity of graph,<ref>See Theorem 1 in {{harvtxt|Lovász|1979}}.</ref> hence
:<math> \alpha(G) \leq \Theta(G) \leq \vartheta(G). </math>

[[File:Cycle graph C5.png|thumb|100px|Pentagon graph]]
For example, let the confusability graph of the channel be ''C''<sub>5</sub>, a [[pentagon]]. Since the original paper due {{harvtxt|Shannon|1956}} it was an open problem to determine the value of Θ(''C''<sub>5</sub>). It was first established by {{harvtxt|Lovász|1979}} that Θ(''C''<sub>5</sub>)&nbsp;=&nbsp;{{math|{{mrad|5}}}}.

Clearly, Θ(''C''<sub>5</sub>)&nbsp;≥&nbsp;α(''C''<sub>5</sub>)&nbsp;=&nbsp;2. However, α(''C''<sub>5</sub><sup>2</sup>)&nbsp;≥&nbsp;5, since "11", "23", "35", "54", "42" are five mutually non-confusable messages, thus Θ(''C''<sub>5</sub>)&nbsp;≥&nbsp;{{math|{{mrad|5}}}}.

To show that this bound is tight, let ''U''&nbsp;=&nbsp;(''u''<sub>''1''</sub>, ..., ''u''<sub>''5''</sub>) be the following orthonormal representation of the pentagon:
:<math>
  u_k =
  \begin{pmatrix}
    \cos{\theta} \\
    \sin{\theta} \cos{\varphi_k} \\
    \sin{\theta} \sin{\varphi_k}
  \end{pmatrix}, \quad
  \cos{\theta} = \frac{1}{\sqrt[4]{5}}, \quad
  \varphi_k = \frac{2 \pi k}{5}
</math>
and let ''c''&nbsp;=&nbsp;(1,&nbsp;0,&nbsp;0). By using this choice in the initial definition of Lovász number, we get ϑ(''C''<sub>5</sub>)&nbsp;≤&nbsp;{{math|{{mrad|5}}}}. Hence, Θ(''C''<sub>5</sub>)&nbsp;=&nbsp;{{math|{{mrad|5}}}}.

However, there exist graphs for which the Lovász number and Shannon capacity differ, so the Lovász number cannot in general be used to compute exact Shannon capacities.<ref>{{harvtxt|Haemers|1979}}.</ref>

== Generalizations ==

The Lovász number has been generalized for "non-commutative graphs" in the context of [[quantum channel|quantum communication]].<ref>{{harvtxt|Duan|Severini|Winter|2010}}.</ref>

== Notes ==

{{Reflist}}

== References ==

{{refbegin}}
* {{cite arxiv | first1 = Runyao | last1 = Duan | first2 = Simone | last2 = Severini | first3 = Andreas | last3 = Winter | authorlink3 = Andreas Winter | title = Zero-error communication via quantum channels, non-commutative graphs and a quantum Lovász &thetasym; function | year = 2010 | eprint = 1002.2514 }}.
* {{citation | first1 = Martin | last1 = Grötschel | authorlink1 = Martin Grötschel | first2 = László | last2 = Lovász | authorlink2 = László Lovász | first3 = Alexander | last3 = Schrijver | authorlink3 = Alexander Schrijver | title = The ellipsoid method and its consequences in combinatorial optimization | journal = Combinatorica | volume = 1 | issue = 2 | pages = 169–197 | year = 1981 | doi = 10.1007/BF02579273 | url = http://oai.cwi.nl/oai/asset/10046/10046A.pdf}}.
* {{citation | first1 = Martin | last1 = Grötschel | authorlink1 = Martin Grötschel | first2 = László | last2 = Lovász | authorlink2 = László Lovász | first3 = Alexander | last3 = Schrijver | authorlink3 = Alexander Schrijver | title = Geometric Algorithms and Combinatorial Optimization | publisher = Springer | edition = 2 | year = 1988 | isbn = 978-0-387-13624-0}}, Chapter 9.3. Orthonormal Representations, pp.&nbsp;285.
* {{citation | first = Willem H. | last = Haemers | title = On Some Problems of Lovász Concerning the Shannon Capacity of a Graph | journal = IEEE Transactions on Information Theory | volume = 25 |pages = 231–232  | year = 1979 | url = http://arno.uvt.nl/show.cgi?fid=80311}}.
* {{citation | first = Donald E. | last = Knuth | authorlink = Donald Knuth | title = The sandwich theorem | arxiv = math/9312214  | journal = [[Electronic Journal of Combinatorics]] | pages = A1 | year = 1994 | url = http://www.combinatorics.org/Volume_1/PDFFiles/v1i1a1.pdf}}.
* {{citation | first = László | last = Lovász | authorlink = László Lovász | title = On the Shannon Capacity of a Graph | journal = [[IEEE Transactions on Information Theory]] | volume = IT-25 | issue = 1 | year = 1979}}.
* {{citation | first = László | last = Lovász | authorlink = László Lovász | title = An Algorithmic Theory of Numbers, Graphs and Convexity | publisher = SIAM | year = 1986 | isbn = 978-0-89871-203-2}}, Chapter 3.2. Chromatic number, cliques, and perfect graphs, [http://books.google.com/books?id=NWa5agInx0gC&pg=PA75 pp. 75].
* {{citation | first = László | last = Lovász | authorlink = László Lovász | title = Semidefinite programs and combinatorial optimization | year = 1995&ndash;2001 | url = http://www.cs.elte.hu/~lovasz/semidef.ps}}, lecture notes.
* {{citation | first = Claude | last = Shannon | authorlink = Claude Shannon | title = The zero error capacity of a noisy channel | journal = IRE Transactions on Information Theory | volume = 2 | issue = 3 | pages = 8–19 | year = 1956 | doi = 10.1109/TIT.1956.1056798 | url = http://ieeexplore.ieee.org/stampPDF/getPDF.jsp?tp=&arnumber=1056798}}.
{{refend}}

== External links ==

* {{MathWorld | title = Lovász Number | urlname = LovaszNumber}}
* {{MathWorld | title = Sandwich Theorem | urlname = SandwichTheorem}}
* {{MathWorld | title = Shannon Capacity | urlname = ShannonCapacity}}

{{DEFAULTSORT:Lovasz number}}
[[Category:Graph invariants]]
[[Category:Information theory]]