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 un límite 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 , utilizando una forma de escritura 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 grafo . ^[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 encuentra entre el número cromático y el número de clique del gráfico, y se puede utilizar para calcular estos números en gráficos para los que son iguales, incluidos los gráficos perfectos .

Definición

Sea un grafo sobre vértices. Un conjunto ordenado de vectores unitarios se denomina representación ortonormal de en , si y son ortogonales siempre que los vértices y no sean adyacentes en : Claramente, cada grafo admite una representación ortonormal con : solo representa los vértices mediante vectores distintos de la base estándar de . ^[2] Dependiendo del grafo, podría ser posible tomar 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 de un grafo se define de la siguiente manera: donde es un vector unitario en y es una representación ortonormal de en . Aquí la minimización se realiza implícitamente también sobre la dimensión , sin embargo, sin pérdida de generalidad, basta con considerar . ^[3] Intuitivamente, esto corresponde a minimizar el semiángulo de un cono rotacional que contiene todos los vectores que representan 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 grafo de vértices. Sea un rango de todas las matrices simétricas tales que siempre que o vértices y no sean adyacentes, y sea el valor propio más grande de . Entonces, una forma alternativa de calcular el número de Lovász de 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 el rango de todas las matrices semidefinidas positivas simétricas tales que siempre que los vértices y sean adyacentes, y tal que la traza (suma de las entradas diagonales) de sea . Sea la matriz de unos . Entonces ^[6] Aquí, es simplemente 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 complementario . 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

Se ha calculado el número de Lovász 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 el complemento de , entonces ^[10] con igualdad si es transitivo-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 (la menor cantidad de colores necesarios para colorear los vértices de de modo que ningún par de vértices adyacentes reciba 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 se puede formular como un programa semidefinido y aproximarse numéricamente mediante el método del elipsoide en un tiempo acotado por un polinomio en el número de vértices de G . ^[12] Para grafos 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 de y luego redondear al valor entero más cercano, el número cromático y el número de camarilla de estos grafos se pueden calcular en tiempo polinomial. ${\displaystyle \vartheta (G)}$ ${\displaystyle \vartheta ({\bar {G}})}$ ${\displaystyle \vartheta ({\bar {G}})}$

Relación con la capacidad de Shannon

La capacidad de Shannon de un grafo se define de la siguiente manera: donde es el número de independencia del grafo (el tamaño de un conjunto independiente más grande de ) y es el producto gráfico fuerte de consigo mismo por . Claramente, . Sin embargo, el número de Lovász proporciona un límite superior para la capacidad de Shannon de un grafo, ^[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 confusibilidad del canal es , un pentágono . Desde el artículo original de Shannon (1956), determinar el valor de era un problema abierto . 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 confundibles (que forman un conjunto independiente de cinco vértices en el cuadrado fuerte de ), entonces . ${\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 estricto, sea la siguiente representación ortonormal del pentágono: y sea . Al usar esta opción en la definición inicial del número de Lovász, obtenemos . Por lo tanto, . ${\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 para los cuales el número de Lovász y la capacidad de Shannon difieren, por lo que el número de Lovász en general no se puede utilizar para calcular capacidades de Shannon exactas. ^[14]

Física cuántica

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 Lovász también surge en la contextualidad cuántica ^[16] en un intento de explicar el poder de las computadoras cuánticas . ^[17]

Véase también

• Función Tardos , una aproximación monótona al número de Lovász del gráfico complementario que se puede calcular en tiempo polinomial 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 base estándar no será fiel, lo que significa que los vértices adyacentes se representan mediante vectores no ortogonales, a menos que el gráfico no tenga aristas. Una representación fiel también es posible asociando cada vértice a un vector base como antes, pero asignando cada vértice a la suma de los vectores base asociados con su entorno cerrado. ${\displaystyle N=n}$
3. Si entonces siempre se puede lograr un valor objetivo más pequeño restringiéndose al subespacio abarcado por vectores ; este subespacio es como máximo -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 otros (2014).

Referencias

• Cabello, Adán; Severini, Simone ; Winter, Andreas (27 de enero de 2014), "Enfoque grafo-teórico para las correlaciones cuánticas", Physical Review Letters , 112 (4): 040401, arXiv : 1401.7081 , doi :10.1103/PhysRevLett.112.040401, PMID  24580419, S2CID  34998358
• 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 ϑ de Lovász cuántica", IEEE Transactions on Information Theory , 59 (2): 1164–1174, arXiv : 1002.2514 , doi :10.1109/TIT.2012.2221677, S2CID  4690143
• Grötschel, Martin ; 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) el 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, Sr.  1261419, página 285
• Haemers, Willem H. (1979), "Sobre algunos problemas de Lovász relacionados con la capacidad de Shannon de un grafo", IEEE Transactions on Information Theory , 25 (2): 231–232, doi :10.1109/tit.1979.1056027, archivado desde el original el 5 de marzo de 2012
• Howard, Mark; Wallman, Joel; Veitch, Victor; 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", Revista electrónica de combinatoria , 1 : A1, arXiv : math/9312214 , doi : 10.37236/1193
• Lovász, László (1979), "Sobre la capacidad de Shannon de un grafo", 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 grafos perfectos", Una teoría algorítmica de números, grafos y convexidad , Society for Industrial and Applied Mathematics , pág. 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 de 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 de OR6327, Programación semidefinida (PDF) , Universidad de Cornell

Enlaces externos

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