Número de Lovász

En teoría de grafos, el número de Lovász de un grafo es un número real que es una cota superior de la capacidad de Shannon del grafo. También se conoce como función theta de Lovász y se denota comúnmente por ${\displaystyle \vartheta (G)}$, utilizando una forma de escritura de la letra griega θ para contrastar con la theta vertical utilizada para la capacidad de Shannon. Esta cantidad fue introducida por primera vez por László Lovász en su artículo de 1979 Sobre la capacidad de Shannon de un grafo.^[1]​

Se pueden calcular aproximaciones numéricas precisas a este número en tiempo polinómico mediante programación semidefinida y el método del elipsoide. El número de Lovász del complemento de cualquier grafo se encuentra entre el número cromático y el número de clique del grafo, y puede utilizarse para calcular estos números en grafos para los que son iguales, incluyendo los grafos perfectos.

Sea ${\displaystyle G=(V,E)}$ un grafo con ${\displaystyle n}$ vértices. Un conjunto ordenado de ${\displaystyle n}$ vectores unitarios, ${\displaystyle U=(u_{i}\mid i\in V)\subset \mathbb {R} ^{N}}$ se denomina representación ortonormal de ${\displaystyle G}$ en ${\displaystyle \mathbb {R} ^{N}}$, si ${\displaystyle u_{i}}$ y ${\displaystyle u_{j}}$ son ortogonales siempre que los vértices ${\displaystyle i}$ y ${\displaystyle j}$ no sean adyacentes en ${\displaystyle G}$:

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

Claramente, todo grafo admite una representación ortonormal con ${\displaystyle N=n}$: basta con representar los vértices mediante vectores distintos de la base canónica de ${\displaystyle \mathbb {R} ^{N}}$.^[2]​ Dependiendo del grafo, podría ser posible que ${\displaystyle N}$ sea considerablemente menor que el número de vértices ${\displaystyle n}$.

El número de Lovász ${\displaystyle \vartheta }$ del grafo ${\displaystyle G}$ se define como sigue:

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

donde ${\displaystyle c}$ es un vector unitario en ${\displaystyle \mathbb {R} ^{N}}$ y ${\displaystyle U}$ es una representación ortonormal de ${\displaystyle G}$ en ${\displaystyle \mathbb {R} ^{N}}$. Aquí, la minimización se realiza implícitamente también sobre la dimensión ${\displaystyle N}$. Sin embargo, sin pérdida de generalidad, basta con considerar ${\displaystyle N=n}$.^[3]​ Intuitivamente, esto corresponde a minimizar el semiángulo de un cono de rotación que contiene todos los vectores que componen una representación ortonormal de ${\displaystyle G}$. Si el ángulo óptimo es ${\displaystyle \phi }$, entonces ${\displaystyle \vartheta (G)=1/\cos ^{2}\phi }$ y ${\displaystyle c}$ corresponden al eje de simetría del cono.^[4]​

Sea ${\displaystyle G=(V,E)}$ un grafo con ${\displaystyle n}$ vértices. Sea ${\displaystyle A}$ un rango sobre todas las matrices simétricas de orden ${\displaystyle n\times n}$ tales que ${\displaystyle a_{ij}=1}$ siempre que ${\displaystyle i=j}$ o los vértices ${\displaystyle i}$ y ${\displaystyle j}$ no sean adyacentes, y sea ${\displaystyle \lambda _{\max }(A)}$ el mayor autovalor de ${\displaystyle A}$. Entonces, una forma alternativa de calcular el número de Lovász de ${\displaystyle G}$ es la siguiente:^[5]​

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

El siguiente método es dual al anterior. Sea ${\displaystyle B}$ un rango sobre todos las matrices semidefinidas positivas simétricas de orden ${\displaystyle n\times n}$ tales que ${\displaystyle b_{ij}=0}$ siempre que los vértices ${\displaystyle i}$ y ${\displaystyle j}$ sean adyacentes, y tal que la traza (suma de las entradas diagonales) de ${\displaystyle B}$ sea ${\displaystyle \operatorname {Tr} (B)=1}$. Sea ${\displaystyle J}$ una matriz de unos de orden ${\displaystyle n\times n}$. Entonces,^[6]​

$${\displaystyle \vartheta (G)=\max _{B}\operatorname {Tr} (BJ).}$$ Aquí, ${\displaystyle \operatorname {Tr} (BJ)}$ es simplemente la suma de todas las entradas de ${\displaystyle B}$.

El número de Lovász también se puede calcular en términos del grafo complemento ${\displaystyle {\bar {G}}}$. Sea ${\displaystyle d}$ un vector unitario y ${\displaystyle U=(u_{i}\mid i\in V)}$ una representación ortonormal de ${\displaystyle {\bar {G}}}$. Entonces,^[7]​

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

El número de Lovász se ha calculado para los siguientes grafos:^[8]​

Grafo	Número de Lovász
Grafo completo	${\displaystyle \vartheta (K_{n})=1}$
Grafo nulo	${\displaystyle \vartheta ({\bar {K}}_{n})=n}$
Pentágono graph	${\displaystyle \vartheta (C_{5})={\sqrt {5}}}$
Grafos cíclicos	${\displaystyle \vartheta (C_{n})={\begin{cases}{\frac {n\cos(\pi /n)}{1+\cos(\pi /n)}}&{\text{para }}n{\text{ impar}},\\{\frac {n}{2}}&{\text{para }}n{\text{ par}}\end{cases}}}$
Grafo de Petersen	${\displaystyle \vartheta (KG_{5,2})=4}$
Grafos de Kneser	${\displaystyle \vartheta (KG_{n,k})={\binom {n-1}{k-1}}}$
Grafo multipartito completo	${\displaystyle \vartheta (K_{n_{1},\dots ,n_{k}})=\max _{1\leq i\leq k}n_{i}}$

Si ${\displaystyle G\boxtimes H}$ denota el producto de grafos fuerte de los grafos ${\displaystyle G}$ y ${\displaystyle H}$, entonces^[9]​

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

Si ${\displaystyle {\bar {G}}}$ es el complemento de ${\displaystyle G}$, entonces^[10]​

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

con igualdad si ${\displaystyle G}$ es transitivo de vértices.

El teorema del "sándwich" de Lovász establece que el número de Lovász siempre se encuentra entre dos números que cuyo cálculo es NP-completo.^[11]​. Más precisamente,

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

donde ${\displaystyle \omega (G)}$ es el número de clique de ${\displaystyle G}$ (el tamaño del clique más grande del grafo) y ${\displaystyle \chi (G)}$ es el número cromático de ${\displaystyle G}$ (el menor número de colores necesario para colorear los vértices de ${\displaystyle G}$ de modo que ningún vértice adyacente reciba el mismo color).

El valor de ${\displaystyle \vartheta (G)}$ puede formularse por programación semidefinida y aproximarse numéricamente mediante el método del elipsoide en un tiempo acotado polinómicamnete según el número de vértices de G.^[12]​

Para un grafo perfecto, el número cromático y el número de clique son iguales y, por lo tanto, ambos son iguales a ${\displaystyle \vartheta ({\bar {G}})}$. Al calcular una aproximación de ${\displaystyle \vartheta ({\bar {G}})}$ y redondearla al valor del número entero más cercano, se pueden calcular el número cromático y el número de clique de estos grafos en tiempo polinómico.

La capacidad de Shannon del grafo ${\displaystyle G}$ se define como sigue:

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

donde ${\displaystyle \alpha (G)}$ es el número de independencia del grafo ${\displaystyle G}$ (el tamaño del mayor conjunto independiente de ${\displaystyle G}$) y ${\displaystyle G^{k}}$ es el producto de grafos fuerte de ${\displaystyle G}$ consigo mismo ${\displaystyle k}$ veces. Claramente, ${\displaystyle \Theta (G)\geq \alpha (G)}$. Sin embargo, el número de Lovász proporciona un límite superior para la capacidad de Shannon del grafo,^[13]​ y por lo tanto:

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

Por ejemplo, supóngase que el grafo de confusibilidad del canal es ${\displaystyle C_{5}}$, un pentágono. Desde el artículo original de Shannon (1956), se ha utilizado problema no resuelto para determinar el valor de ${\displaystyle \Theta (C_{5})}$. Lovász (1979) estableció primero que ${\displaystyle \Theta (C_{5})={\sqrt {5}}}$.

Claramente, ${\displaystyle \Theta (C_{5})\geq \alpha (C_{5})=2}$. Sin embargo, ${\displaystyle \alpha (C_{5}^{2})\geq 5}$, dado que "11", "23", "35", "54", "42" son cinco mensajes mutuamente no confundibles (formando un conjunto independiente de cinco vértices en el cuadrado fuerte de ${\displaystyle C_{5}}$), entonces, ${\displaystyle \Theta (C_{5})\geq {\sqrt {5}}}$.

Para demostrar que esta cota es estricta, sea ${\displaystyle U=(u_{1},\dots ,u_{5})}$ la siguiente representación ortonormal del pentágono:

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

y sea ${\displaystyle c=(1,0,0)}$. Al usar esta opción en la definición inicial del número de Lovász, se obtiene ${\displaystyle \vartheta (C_{5})\leq {\sqrt {5}}}$. Por lo tanto, ${\displaystyle \Theta (C_{5})={\sqrt {5}}}$.

Sin embargo, existen grafos para los cuales el número de Lovász y la capacidad de Shannon difieren, por lo que, en general, el número de Lovász no puede usarse para calcular las capacidades de Shannon exactas.^[14]​

El número de Lovász se ha generalizado para grafos no conmutativos en el contexto de la comunicación cuántica.^[15]​. El número de Lovasz también surge en contextualidad cuántica,^[16]​ en un intento de explicar la potencia de la computación cuántica.^[17]​

• Función de Tardos, una aproximación monótona al número de Lovasz del grafo complemento que se puede calcular en tiempo polinómico y se ha utilizado para demostrar cotas inferiores en complejidad de circuitos monótona.

• Weisstein, Eric W. «Lovász Number». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Weisstein, Eric W. «Sandwich Theorem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.