número de lovász

En teoría de grafos , el número de Lovász de un gráfico es un número real que es un límite superior de la capacidad de Shannon del gráfico. También se conoce como función theta de Lovász y comúnmente se denota con , utilizando una forma escrita de la letra griega theta 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 gráfico . ^[1] ${\displaystyle \vartheta (G)}$

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 gráfico se intercala entre el número cromático y el número de camarilla del gráfico, y se puede utilizar para calcular estos números en gráficos en los que son iguales, incluidos los gráficos perfectos .

Definición

Sea un gráfico sobre vértices. Un conjunto ordenado de vectores unitarios se llama representación ortonormal de in , si y son ortogonales siempre que los vértices y no sean adyacentes en : Claramente, todo gráfico admite una representación ortonormal con : simplemente representa los vértices mediante vectores distintos de la base estándar de . ^[2] Dependiendo del gráfico, es posible que sea considerablemente menor que el número de vértices  . ${\displaystyle G=(V,E)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle U=(u_{i}\mid i\in V)\subset \mathbb {R} ^{N}}$ ${\displaystyle G}$ ${\displaystyle \mathbb {R} ^{N}}$ ${\displaystyle u_{i}}$ ${\displaystyle u_{j}}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle G}$ $${\displaystyle u_{i}^{\mathrm {T} }u_{j}={\begin{cases}1,&{\text{if }}i=j,\\0,&{\text{if }}ij\notin E.\end{cases}}}$$ ${\displaystyle N=n}$ ${\displaystyle \mathbb {R} ^{N}}$ ${\displaystyle N}$ ${\displaystyle n}$

El número de Lovász del gráfico se define de la siguiente manera: donde es un vector unitario en y es una representación ortonormal de en . Aquí la minimización implícita también se realiza sobre la dimensión , sin embargo, sin pérdida de generalidad, es suficiente considerarla . ^[3] Intuitivamente, esto corresponde a minimizar el semiángulo de un cono de rotación que contiene todos los vectores representativos de una representación ortonormal de . Si el ángulo óptimo es , entonces y corresponde al eje de simetría del cono. ^[4] ${\displaystyle \vartheta }$ ${\displaystyle G}$ $${\displaystyle \vartheta (G)=\min _{c,U}\max _{i\in V}{\frac {1}{(c^{\mathrm {T} }u_{i})^{2}}},}$$ ${\displaystyle c}$ ${\displaystyle \mathbb {R} ^{N}}$ ${\displaystyle U}$ ${\displaystyle G}$ ${\displaystyle \mathbb {R} ^{N}}$ ${\displaystyle N}$ ${\displaystyle N=n}$ ${\displaystyle G}$ ${\displaystyle \phi }$ ${\displaystyle \vartheta (G)=1/\cos ^{2}\phi }$ ${\displaystyle c}$

Expresiones equivalentes

Sea un gráfico sobre vértices. Dejemos abarcar todas las matrices simétricas de modo que siempre que los vértices y no sean adyacentes, y denotemos el valor propio más grande de . Entonces, una forma alternativa de calcular el número de Lovász es la siguiente: ^[5] ${\displaystyle G=(V,E)}$ ${\displaystyle n}$ ${\displaystyle A}$ ${\displaystyle n\times n}$ ${\displaystyle a_{ij}=1}$ ${\displaystyle i=j}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle \lambda _{\max }(A)}$ ${\displaystyle A}$ ${\displaystyle G}$ $${\displaystyle \vartheta (G)=\min _{A}\lambda _{\max }(A).}$$

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

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

Valor para gráficos conocidos

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

Propiedades

Si denota el producto gráfico fuerte de los gráficos y , entonces ^[9] ${\displaystyle G\boxtimes H}$ ${\displaystyle G}$ ${\displaystyle H}$ $${\displaystyle \vartheta (G\boxtimes H)=\vartheta (G)\vartheta (H).}$$

Si es complemento de , entonces ^[10] con igualdad si es transitivo de vértice . ${\displaystyle {\bar {G}}}$ ${\displaystyle G}$ $${\displaystyle \vartheta (G)\vartheta ({\bar {G}})\geq n,}$$ ${\displaystyle G}$

"Teorema del sándwich" de Lovász

El "teorema del sándwich" de Lovász establece que el número de Lovász siempre se encuentra entre otros dos números que son NP-completos para calcular. ^[11] Más precisamente, donde es el número de camarilla de (el tamaño de la camarilla más grande ) y es el número cromático de (el número más pequeño de colores necesarios para colorear los vértices de modo que no haya dos vértices adyacentes que reciban el mismo color). $${\displaystyle \omega (G)\leq \vartheta ({\bar {G}})\leq \chi (G),}$$ ${\displaystyle \omega (G)}$ ${\displaystyle G}$ ${\displaystyle \chi (G)}$ ${\displaystyle G}$ ${\displaystyle G}$

El valor de puede formularse como un programa semidefinido y aproximarse numéricamente mediante el método del elipsoide en el tiempo acotado por un polinomio en el número de vértices de G. ^[12] Para gráficos perfectos , el número cromático y el número de camarilla son iguales y, por lo tanto, ambos son iguales a . Al calcular una aproximación y luego redondear al valor entero más cercano, el número cromático y el número de camarilla de estos gráficos se pueden calcular en tiempo polinómico. ${\displaystyle \vartheta (G)}$ ${\displaystyle \vartheta ({\bar {G}})}$ ${\displaystyle \vartheta ({\bar {G}})}$

Relación con la capacidad de Shannon

La capacidad de Shannon del gráfico se define de la siguiente manera: donde es el número de independencia del gráfico (el tamaño de un conjunto independiente más grande de ) y es el producto del gráfico fuerte de consigo mismo . Claramente, . Sin embargo, el número de Lovász proporciona un límite superior a la capacidad de Shannon del gráfico, ^[13] por lo tanto ${\displaystyle G}$ $${\displaystyle \Theta (G)=\sup _{k}{\sqrt[{k}]{\alpha (G^{k})}}=\lim _{k\rightarrow \infty }{\sqrt[{k}]{\alpha (G^{k})}},}$$ ${\displaystyle \alpha (G)}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G^{k}}$ ${\displaystyle G}$ ${\displaystyle k}$ ${\displaystyle \Theta (G)\geq \alpha (G)}$ $${\displaystyle \alpha (G)\leq \Theta (G)\leq \vartheta (G).}$$

gráfico del pentágono

Por ejemplo, supongamos que el gráfico de confusión del canal sea un pentágono . Desde el artículo original de Shannon (1956) era un problema abierto determinar el valor de . Lovász (1979) estableció por primera vez que . ${\displaystyle C_{5}}$ ${\displaystyle \Theta (C_{5})}$ ${\displaystyle \Theta (C_{5})={\sqrt {5}}}$

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

Para demostrar que este límite es estrecho, sea la siguiente representación ortonormal del pentágono: y sea . Al utilizar esta elección en la definición inicial del número de Lovász, obtenemos . Por eso, . ${\displaystyle U=(u_{1},\dots ,u_{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}}}$$ ${\displaystyle c=(1,0,0)}$ ${\displaystyle \vartheta (C_{5})\leq {\sqrt {5}}}$ ${\displaystyle \Theta (C_{5})={\sqrt {5}}}$

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

Física cuántica

El número de Lovász se ha generalizado para "gráficos no conmutativos" en el contexto de la comunicación cuántica . ^[15] El número de Lovasz también surge en la contextualidad cuántica ^[16] en un intento de explicar el poder de las computadoras cuánticas . ^[17]

Ver también

• Función Tardos , una aproximación monótona al número de Lovász del gráfico de complemento que se puede calcular en tiempo polinómico y se ha utilizado para demostrar límites inferiores en la complejidad de circuitos monótonos .

Notas

1. Lovász (1979).
2. Una representación de vértices mediante vectores de base estándar no será fiel, lo que significa que los vértices adyacentes están representados por vectores no ortogonales, a menos que el gráfico no tenga aristas. También es posible una representación fiel asociando cada vértice a un vector base como antes, pero asignando cada vértice a la suma de vectores base asociados con su vecindad cerrada. ${\displaystyle N=n}$
3. Si entonces siempre se puede lograr un valor objetivo más pequeño restringiendo al subespacio abarcado por vectores ; este subespacio es como mucho -dimensional. ${\displaystyle N>n}$ ${\displaystyle c}$ ${\displaystyle u_{i}}$ ${\displaystyle n}$
4. Lovász (1995-2001), Proposición 5.1, p. 28.
5. Lovász (1979), Teorema 3.
6. Lovász (1979), Teorema 4.
7. Lovász (1979), Teorema 5.
8. Acertijo (2003).
9. Lovász (1979), Lema 2 y Teorema 7.
10. Lovász (1979), Corolario 2 y Teorema 8.
11. Knuth (1994).
12. Grötschel, Lovász y Schrijver (1981); Todd y Cheung (2012).
13. Lovász (1979), Teorema 1.
14. Haemers (1979).
15. Duan, Severini y invierno (2013).
16. Cabello, Severini e invierno (2014).
17. Howard y col. (2014).

Referencias

• Cabello, Adán; Severini, Simone ; Winter, Andreas (27 de enero de 2014), "Enfoque teórico de grafos para las correlaciones cuánticas", Physical Review Letters , 112 (4): 040401, arXiv : 1401.7081 , doi : 10.1103/PhysRevLett.112.040401, PMID  24580419, S2CID  8
• Duan, Runyao; Severini, Simone ; Winter, Andreas (2013), "Comunicación sin error a través de canales cuánticos, gráficos no conmutativos y una función cuántica de Lovász ϑ", IEEE Transactions on Information Theory , 59 (2): 1164–1174, arXiv : 1002.2514 , doi : 10.1109 /TIT.2012.2221677, S2CID  4690143
• Grötschel, Martín ; Lovász, László ; Schrijver, Alexander (1981), "El método del elipsoide y sus consecuencias en la optimización combinatoria" (PDF) , Combinatorica , 1 (2): 169–197, doi :10.1007/BF02579273, S2CID  43787103, archivado desde el original (PDF) en 2011-07-18
• Grötschel, Martín ; Lovász, László ; Schrijver, Alexander (1993), Algoritmos geométricos y optimización combinatoria, Algoritmos y combinatoria, vol. 2 (2ª ed.), Springer-Verlag, Berlín, doi :10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, señor  1261419, página 285
• Haemers, Willem H. (1979), "Sobre algunos problemas de Lovász sobre la capacidad de Shannon de un gráfico", IEEE Transactions on Information Theory , 25 (2): 231–232, doi :10.1109/tit.1979.1056027, archivado desde original el 2012-03-05
• Howard, Marcos; Wallman, Joel; Veitch, Víctor; Emerson, Joseph (19 de junio de 2014), "La contextualidad proporciona la 'magia' para la computación cuántica", Nature , 510 (7505): 351–5, arXiv : 1401.4174 , Bibcode :2014Natur.510..351H, doi :10.1038/nature13460 , PMID  24919152, S2CID  4463585
• Knuth, Donald E. (1994), "El teorema del sándwich", Electronic Journal of Combinatorics , 1 : A1, arXiv : math/9312214 , doi : 10.37236/1193
• Lovász, László (1979), "Sobre la capacidad de Shannon de un gráfico", IEEE Transactions on Information Theory , IT-25 (1): 1–7, doi :10.1109/tit.1979.1055985
• Lovász, László (1986), "Capítulo 3.2: Número cromático, camarillas y gráficos perfectos", Una teoría algorítmica de números, gráficos y convexidad , Sociedad de Matemática Industrial y Aplicada , p. 75, ISBN 978-0-89871-203-2
• Lovász, László (1995-2001), Programas semidefinidos y optimización combinatoria (apuntes de conferencias)
• Riddle, Marcia Ling (2003), Teorema del sándwich y cálculo de la función theta para varios gráficos (tesis de maestría), Universidad Brigham Young, hdl :1877/etd181
• Shannon, Claude (1956), "La capacidad de error cero de un canal ruidoso", IRE Transactions on Information Theory , 2 (3): 8–19, doi :10.1109/TIT.1956.1056798
• Todd, Mike; Cheung, Sin-Shuen (21 de febrero de 2012), "Conferencia 9: Formulaciones SDP de la función theta de Lovász", Notas de la conferencia para OR6327, Programación semidefinida (PDF) , Universidad de Cornell

enlaces externos

• Weisstein, Eric W. , "Número de Lovász" ("Teorema del sándwich") en MathWorld .