Lovas number

The Lovas number of a graph is a real number , which is the upper boundary of the . The Lovas number is also known as the Lovas theta function and is usually referred to as $\vartheta (G)$ ${\ displaystyle \ vartheta (G)}$ ${\ displaystyle \ vartheta (G)}$ . This number was first introduced by Laszlo Lovas in a 1979 article, “On the Shannon Capacity of a Graph” ^[1] .

Content

Definition

Let G = ( V , E ) be a graph with n vertices. Ordered set of n unit vectors $U=(u_{i}\mid i\in V)\subset \mathbf {R} ^{N}$ ${\ displaystyle U = (u_ {i} \ mid i \ in V) \ subset \ mathbf {R} ^ {N}}$ is called the orthonormal representation of the graph G in R ^N if u _i and u _{j are} orthogonal when the vertices i and j are not adjacent in G :

u_{i}^{\mathrm {T} }u_{j}={\begin{cases}1,&i=j,\\0,&ij\notin E.\end{cases}}

{\ displaystyle u_ {i} ^ {\ mathrm {T}} u_ {j} = {\ begin {cases} 1, & i = j, \\ 0, & ij \ notin E. \ end {cases}}}

It is clear that any graph admits an orthonormal representation with N = n (just to the vertices we associate the vertices of different vectors of the space R ⁿ , although such a representation is not correct (the product of the vectors is zero, even if the corresponding vertices are adjacent), unless the graph It has no edges at all.The correct representation for N = n is possible, however, in the general case, N can be significantly less than the number of vertices n .

The Lovas number ϑ of the graph G is defined as follows:

\vartheta (G)=\min _{c,U}\max _{i\in V}{\frac {1}{(c^{\mathrm {T} }u_{i})^{2}}},

{\ displaystyle \ vartheta (G) = \ min _ {c, U} \ max _ {i \ in V} {\ frac {1} {(c ^ {\ mathrm {T}} u_ {i}) ^ { 2}}},}

where c is the unit vector in R ^N and U is the orthonormal representation of G in R ^N. Here minimization is also implicitly assumed with respect to dimension N , however, without loss of generality, it suffices to assume N = n ^[2] . Intuitively, this corresponds to minimizing half the angle of a circular cone containing the vectors of the orthonormal representation of the graph G. If the optimal angle is $\phi$ ${\ displaystyle \ phi}$ then $\theta (G)=1/cos^{2}(\phi )$ ${\ displaystyle \ theta (G) = 1 / cos ^ {2} (\ phi)}$ and c corresponds to the axis of symmetry of the cone ^[3] .

Equivalent Expressions

Let G = ( V , E ) be a graph with n vertices. Let A be n × n symmetric matrices such that a _ij = 1 whenever i = j or $ij\notin E$ ${\ displaystyle ij \ notin E}$ , let it go $\lambda _{max}(A)$ ${\ displaystyle \ lambda _ {max} (A)}$ denotes the largest eigenvalue of the matrix A. Then an alternative way to calculate the Lovas number of the graph G is the following ^[4] :

\vartheta (G)=\min _{A}\lambda _{\max(}A).

{\ displaystyle \ vartheta (G) = \ min _ {A} \ lambda _ {\ max (} A).}

The following method is dual to the previous one. Let B be n × n symmetric positive definite matrices such that b _ij = 0 for any $ij\in E$ ${\ displaystyle ij \ in E}$ and Tr ( B ) = 1. Here Tr is the trace (the sum of the diagonal elements), and J is the n × n matrix of units . Then ^[5]

\vartheta (G)=\max _{B}\operatorname {Tr} (BJ).

{\ displaystyle \ vartheta (G) = \ max _ {B} \ operatorname {Tr} (BJ).}

Tr ( BJ ) is simply equal to the sum of all elements of B.

The Lovas number can be calculated in terms of the complement of the graph G. Let d be the unit vector and $V=(v_{i}\mid i\in V)$ ${\ displaystyle V = (v_ {i} \ mid i \ in V)}$ Is the orthonormal representation of the graph G ^[6] .

\vartheta (G)=\max _{d,V}\sum _{i\in V}(d^{\mathrm {T} }v_{i})^{2}.

{\ displaystyle \ vartheta (G) = \ max _ {d, V} \ sum _ {i \ in V} (d ^ {\ mathrm {T}} v_ {i}) ^ {2}.}

Θ value for some well-known graphs

Graph	Value $\theta$ ${\ displaystyle \ theta}$
Full graph	$\vartheta (K_{n})=1$ ${\ displaystyle \ vartheta (K_ {n}) = 1}$
Count without edges	$\vartheta ({\bar {K}}_{n})=n$ ${\ displaystyle \ vartheta ({\ bar {K}} _ {n}) = n}$
Pentagon graph	$\vartheta (C_{5})={\sqrt {5}}$ ${\ displaystyle \ vartheta (C_ {5}) = {\ sqrt {5}}}$
Cycles	$\vartheta (C_{n})={\begin{cases}{\frac {n\cos(\pi /n)}{1+\cos(\pi /n)}}&n\equiv 1\mod 2,\\{\frac {n}{2}}&n\equiv 0\mod 2\end{cases}}$ ${\ displaystyle \ vartheta (C_ {n}) = {\ begin {cases} {\ frac {n \ cos (\ pi / n)} {1+ \ cos (\ pi / n)}} & n \ equiv 1 \ mod 2, \\ {\ frac {n} {2}} & n \ equiv 0 \ mod 2 \ end {cases}}}$
Count Petersen	$\vartheta (KG_{5,2})=4$ ${\ displaystyle \ vartheta (KG_ {5,2}) = 4}$
Kneserian graphs	$\vartheta (KG_{n,k})={\binom {n-1}{k-1}}$ ${\ displaystyle \ vartheta (KG_ {n, k}) = {\ binom {n-1} {k-1}}}$
Multi-part graphs	$\vartheta (K_{n_{1},\dots ,n_{k}})=\max _{1\leq i\leq k}n_{i}$ ${\ displaystyle \ vartheta (K_ {n_ {1}, \ dots, n_ {k}}) = \ max _ {1 \ leq i \ leq k} n_ {i}}$

Properties

If a $G\boxtimes H$ ${\ displaystyle G \ boxtimes H}$ denotes a strong product of graphs of graphs G and H , then ^[7]

\vartheta (G\boxtimes H)=\vartheta (G)\vartheta (H).

{\ displaystyle \ vartheta (G \ boxtimes H) = \ vartheta (G) \ vartheta (H).}

If G is a complement of the graph G , then ^[8]

\vartheta (G)\vartheta ({\bar {G}})\geq n,

{\ displaystyle \ vartheta (G) \ vartheta ({\ bar {G}}) \ geq n,}

and the inequality turns into equality if the graph G is vertex-transitive .

Sandwich Theorem by Lovas

Lovas' Sandwich Theorem states that the Lovas number lies between two other numbers, the calculation of which is an NP-complete problem ^[9] . More precisely,

\omega (G)\leq \vartheta ({\bar {G}})\leq \chi (G),

{\ displaystyle \ omega (G) \ leq \ vartheta ({\ bar {G}}) \ leq \ chi (G),}

Where $\omega (G)$ ${\ displaystyle \ omega (G)}$ - clique number of graph G (size of the largest clique ) a $\chi (G)$ ${\ displaystyle \ chi (G)}$ - the chromatic number of the graph G (the smallest number of colors needed to color the vertices of G so that no two adjacent vertices are painted the same color). However value $\theta (G)$ ${\ displaystyle \ theta (G)}$ can be approximated by the ellipsoid method in a time limited by a polynomial function of the number of vertices of graph G ^[10] .

Shannon Link

G is defined as follows:

\Theta (G)=\sup _{k}{\sqrt[{k}]{\alpha (G^{k})}}=\lim _{k\rightarrow \infty }{\sqrt[{k}]{\alpha (G^{k})}},

{\ displaystyle \ Theta (G) = \ sup _ {k} {\ sqrt [{k}] {\ alpha (G ^ {k})}} = \ lim _ {k \ rightarrow \ infty} {\ sqrt [ {k}] {\ alpha (G ^ {k})}},}

Where $\alpha (G)$ ${\ displaystyle \ alpha (G)}$ is the independence number of the graph G (the size of the largest independent set of the graph G ), and G ^k is the strong product of the graph G by itself k times. It's clear that $\Theta (G)\geq \alpha (G)$ ${\ displaystyle \ Theta (G) \ geq \ alpha (G)}$ . However, the Lovas number gives the upper bound on the capacity of the Shannon graph ^[11] , since

\alpha (G)\leq \Theta (G)\leq \vartheta (G).

{\ displaystyle \ alpha (G) \ leq \ Theta (G) \ leq \ vartheta (G).}

Pentagon graph

For example, let C ₅ , the pentagon , be the graph of fuzzy messages for a channel. Since the advent of Shannon's article ^{[12], the} task of determining the value $\Theta (C_{5})$ ${\ displaystyle \ Theta (C_ {5})}$ . Lovas was the first ^{[1] to} establish that $\Theta (C_{5})={\sqrt {(}}5)$ ${\ displaystyle \ Theta (C_ {5}) = {\ sqrt {(}} 5)}$ .

It's clear that $\Theta (C_{5})\geq \alpha (C_{5})=2$ ${\ displaystyle \ Theta (C_ {5}) \ geq \ alpha (C_ {5}) = 2}$ . But, $\alpha (C_{5}^{2})\geq 5$ ${\ displaystyle \ alpha (C_ {5} ^ {2}) \ geq 5}$ , since “11”, “23”, “35”, “54”, “42” are five mutually distinct messages (forming an independent set of five vertices in a strong square of the graph C ₅ , i.e. $C_{5}\boxtimes C_{5}$ ${\ displaystyle C_ {5} \ boxtimes C_ {5}}$ ), so that $\Theta (C_{5})\geq {\sqrt {5}}$ ${\ displaystyle \ Theta (C_ {5}) \ geq {\ sqrt {5}}}$ .

To show that this boundary is exact, let $U=(u_{1},u_{2},u_{3},u4,u_{5})$ ${\ displaystyle U = (u_ {1}, u_ {2}, u_ {3}, u4, u_ {5})}$ will be the orthonormal representation of the pentagon:

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}}

{\ displaystyle 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}}}

Let it go $c=(1,0,0)$ ${\ displaystyle c = (1,0,0)}$ . If we use these quantities in determining the Lovas number, we get $\theta (C_{5})\leq {\sqrt {5}}$ ${\ displaystyle \ theta (C_ {5}) \ leq {\ sqrt {5}}}$ . Consequently, $\Theta (C_{5})={\sqrt {5}}$ ${\ displaystyle \ Theta (C_ {5}) = {\ sqrt {5}}}$ .

However, there are graphs for which the Lovas number and Shannon capacity are different, so the Lovas number cannot be used, in the general case, to calculate the exact Shannon capacity for a graph ^[13] .

Quantum Physics

The Lovas number was generalized to “non-commutative graphs” in the context of ^[14] . The Lovas number also arises in when trying to explain the power of quantum computers ^[15] .

Notes

↑ ¹ ² Lovász, 1979 .
↑ If N > n , then one can always get a smaller value by restricting it to a subspace spanned by vectors u _i whose dimension does not exceed n .
↑ Lovász, 1995–2001 , p. 28 Proposition 5.1.
↑ Lovász, 1979 , p. Theorem 3.
↑ Lovász, 1979 , p. Theorem 4.
↑ Lovász, 1979 , p. Theorem 5.
↑ Lovász, 1979 , p. Lemma 2, Theorem 7.
↑ Lovász, 1979 , p. Corollary 2, Theorem 8.
↑ Knuth, 1994 .
↑ Grötschel, Lovász, Schrijver, 1981 .
↑ Lovász, 1979 , p. Theorem 1.
↑ Shannon, 1956 .
↑ Haemers, 1979 .
↑ Duan, Severini, Winter, 2013 .
↑ Howard, Wallman, Veitch, Emerson, 2014 , p. 351.

Literature

Mark Howard, Joel Wallman, Victor Veitch, Joseph Emerson. Contextuality supplies the 'magic' for quantum computation // Nature . - 2014 .-- June ( t. 510 ). - S. 351 . - DOI : 10.1038 / nature13460 . - PMID 24919152 .
Runyao Duan, Simone Severini, Andreas Winter. Zero-error communication via quantum channels, non-commutative graphs and a quantum Lovász ϑ function // IEEE Trans. Inf. Theory. - 2013 .-- T. 59 , no. 2 . - S. 1164–1174 . - DOI : 10.1109 / TIT.2012.2221677 . - arXiv : 1002.2514 .
Martin Grötschel, László Lovász , Alexander Schrijver . The ellipsoid method and its consequences in combinatorial optimization // Combinatorica. - 1981. - T. 1 , no. 2 . - S. 169–197 . - DOI : 10.1007 / BF02579273 . Archived July 18, 2011.
Martin Grötschel, László Lovász , Alexander Schrijver . Chapter 9.3. Orthonormal Representations // Geometric Algorithms and Combinatorial Optimization. - Springer, 1988.- S. 285. - ISBN 978-0-387-13624-0 .
Willem H. Haemers. On Some Problems of Lovász Concerning the Shannon Capacity of a Graph // IEEE Transactions on Information Theory. - 1979.- T. 25 . - S. 231–232 . - DOI : 10.1109 / tit . 1979.1056027 . Archived on March 5, 2012.
Donald E. Knuth . The sandwich theorem // Electronic Journal of Combinatorics . - 1994 .-- S. A1 . - arXiv : math / 9312214 .
László Lovász . On the Shannon Capacity of a Graph // IEEE Transactions on Information Theory . - 1979. - T. IT-25 , no. 1 . - S. 1–7 . - DOI : 10.1109 / tit . 1979.1055985 .
László Lovász . Chapter 3.2. Chromatic number, cliques, and perfect graphs // An Algorithmic Theory of Numbers, Graphs and Convexity. - SIAM, 1986. - S. pp. 75. - ISBN 978-0-89871-203-2 .
László Lovász . Semidefinite programs and combinatorial optimization . - 1995-2001. Lectures.
- László Lovász . Semidefinite programs and combinatorial optimization // Recent Advances in Algorithms and Combinatorics / Reed, Sales. - 2003.
Claude Shannon. The zero error capacity of a noisy channel // IRE Transactions on Information Theory. - 1956. - T. 2 , no. 3 . - S. 8–19 . - DOI : 10.1109 / TIT.1956.1056798 .

Links

Weisstein, Eric W. Lovász Number on the Wolfram MathWorld website.
Weisstein, Eric W. Sandwich Theorem on Wolfram MathWorld .
Weisstein, Eric W. Shannon Capacity on Wolfram MathWorld .

[_dc58a2afa16b78fd-1] ¹ ² Lovász, 1979 .

[2] If N > n , then one can always get a smaller value by restricting it to a subspace spanned by vectors u _i whose dimension does not exceed n .

[_c5e9b6b17fd15357-3] Lovász, 1995–2001 , p. 28 Proposition 5.1.

[_4eff3eb9b6d71588-4] Lovász, 1979 , p. Theorem 3.

[_4eff3eb9b6d7158f-5] Lovász, 1979 , p. Theorem 4.

[_4eff3eb9b6d7158e-6] Lovász, 1979 , p. Theorem 5.

[_7dddbcc8ac7816ac-7] Lovász, 1979 , p. Lemma 2, Theorem 7.

[_48fbd28acf21b51a-8] Lovász, 1979 , p. Corollary 2, Theorem 8.

[_d5b73caa59a8710e-9] Knuth, 1994 .

[_6244f98682969a71-10] Grötschel, Lovász, Schrijver, 1981 .

[_4eff3eb9b6d7158a-11] Lovász, 1979 , p. Theorem 1.

[_76857528df41e7f3-12] Shannon, 1956 .

[_7d47fb7b22f18af2-13] Haemers, 1979 .

[_3a28c09de4d51f73-14] Duan, Severini, Winter, 2013 .

[_aa754eaac4ce1b92-15] Howard, Wallman, Veitch, Emerson, 2014 , p. 351.