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 en la capacidad de Shannon del gráfico. También se conoce como función theta de Lovász y comúnmente se denota por ϑ ( G ). 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]
Se pueden calcular aproximaciones numéricas precisas a este número en tiempo polinomial mediante programación semidefinida y el método elipsoide . Se intercala entre el número cromático y el número de clique de cualquier 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 G = ( V , E ) una gráfica de n vértices. Un conjunto ordenado de n vectores unitarios U = ( u i | i ∈ V ) ⊂ R N se denomina representación ortonormal de G en R N , si u i y u j son ortogonales siempre que los vértices i y j no sean adyacentes en G :
Claramente, cada gráfico admite una representación ortonormal con N = n (solo represente los vértices por vectores distintos de la base estándar de R n , aunque esto en general no será fiel a menos que el gráfico no tenga bordes; una representación fiel en N = n también es posible asociando cada vértice a un vector base como antes, pero mapeando cada vértice a la suma de vectores base asociados con su vecindad), pero en general podría ser posible tomar N considerablemente más pequeño que el número de vértices n .
El número de Lovász ϑ del gráfico G se define de la siguiente manera:
donde c es un vector unidad en R N y U es una representación ortonormal de G en R N . Aquí la minimización implícitamente se realiza también sobre la dimensión N , sin embargo, sin pérdida de generalidad, basta con considerar N = n . [2] Intuitivamente, esto corresponde a minimizar el medio-ángulo de una rotación del cono que contiene todos los vectores que representan de una representación ortonormal de G . Si el ángulo óptimo es ϕ, entonces ϑ ( G ) = 1 / cos 2 (ϕ) yc corresponde al eje de simetría del cono. [3]
Expresiones equivalentes
Sea G = ( V , E ) una gráfica de n vértices. Deje Un rango sobre todo n × n matrices simétricas de tal manera que un ij = 1 cuando i = j o ij ∉ E , y dejar que λ max ( A ) denota el mayor valor propio de A . Entonces, una forma alternativa de calcular el número de Lovász de G es la siguiente: [4]
El siguiente método es dual al anterior. Deje B rango sobre todo n × n simétricas matrices semidefinida positiva de tal manera que b ij = 0 para cada ij ∈ E y Tr ( B ) = 1. Aquí Tr denota traza (la suma de entradas diagonales) y J es el n × n matriz de unos . Entonces [5]
Tr ( BJ ) es simplemente la suma de todas las entradas de B .
El número Lovász puede calcularse también en términos de la gráfica complemento G . Let d ser un vector unidad y V = ( v i | i ∈ V ) ser una representación ortonormal de G . Entonces [6]
Valor de ϑ para algunos gráficos conocidos
Grafico | Valor de ϑ [7] |
---|---|
Gráfico completo | |
Gráfico vacío | |
Gráfico del Pentágono | |
Gráficos de ciclo | |
Gráfico de Petersen | |
Gráficos de Kneser | |
Gráficos multipartitos completos |
Propiedades
Si G ⊠ H denota el producto gráfico fuerte de las gráficas G y H , entonces [8]
Si G es el complemento de G , entonces [9]
con igualdad si G es transitivo por vértice .
"Teorema del sándwich" de Lovász
El "teorema 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. [10] Más precisamente,
donde ω ( G ) es el número de clique de G (el tamaño del clique más grande ) y χ ( G ) es el número cromático de G (el número más pequeño de colores necesarios para colorear los vértices de G de modo que no se reciban dos vértices adyacentes el mismo color).
El valor de se pueden formular como un programa semidefinida y numéricamente aproximado por el método elipsoide en el tiempo limitado por un polinomio en el número de vértices de G . [11] Para gráficos perfectos , el número cromático y el número de clique son iguales y, por lo tanto, ambos son iguales a. Calculando una aproximación de y luego redondeando al valor entero más cercano, el número cromático y el número de clique de estos gráficos se pueden calcular en tiempo polinomial.
Relación con la capacidad de Shannon
La capacidad de Shannon del gráfico G se define de la siguiente manera:
donde α ( G ) es el número de independencia del gráfico G (el tamaño de un conjunto independiente más grande de G ) y G k es el producto gráfico fuerte de G consigo mismo k veces. Claramente, Θ ( G ) ≥ α ( G ). Sin embargo, el número de Lovász proporciona un límite superior en la capacidad de Shannon del gráfico, [12] por lo tanto
Por ejemplo, supongamos que el gráfico de capacidad de confusión del canal sea C 5 , un pentágono . Desde el artículo original de Shannon (1956) era un problema abierto determinar el valor de Θ ( C 5 ). Lovász (1979) estableció por primera vez que Θ ( C 5 ) = √ 5 .
Claramente, Θ ( C 5 ) ≥ α ( C 5 ) = 2. Sin embargo, α ( C 5 2 ) ≥ 5, ya que "11", "23", "35", "54", "42" son cinco en conjunto mensajes no confusables (que forman un conjunto independiente de cinco vértices en el cuadrado fuerte de C 5 ), por lo que Θ ( C 5 ) ≥ √ 5 .
Para mostrar que este límite es estrecho, sea U = ( u 1 , ..., u 5 ) la siguiente representación ortonormal del pentágono:
y sea c = (1, 0, 0). Al usar esta opción en la definición inicial del número de Lovász, obtenemos ϑ ( C 5 ) ≤ √ 5 . Por lo tanto, Θ ( C 5 ) = √ 5 .
Sin embargo, existen gráficos para los que el número de Lovász y la capacidad de Shannon difieren, por lo que el número de Lovász no se puede utilizar en general para calcular las capacidades de Shannon exactas. [13]
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 . [14] El número de Lovasz también surge en la contextualidad cuántica [15] en un intento de explicar el poder de las computadoras cuánticas . [dieciséis]
Ver también
- Función de Tardos , una aproximación monótona al número de Lovász del gráfico de complemento que se puede calcular en tiempo polinomial y se ha utilizado para demostrar límites inferiores en la complejidad del circuito.
Notas
- ^ Lovász (1979) .
- ^ Si N > n, entonces siempre se puede lograr un valor objetivo menor restringiendo c al subespacio generado por los vectores u i, que es como mucho n- dimensional.
- ^ Ver Proposición 5.1 en Lovász y 1995-2001 , págs. 28.
- ^ Ver Teorema 3 en Lovász (1979) .
- ^ Ver Teorema 4 en Lovász (1979) .
- ^ Ver Teorema 5 en Lovász (1979) .
- ^ Acertijo (2003) .
- ^ Ver Lema 2 y Teorema 7 en Lovász (1979) .
- ^ Ver Corolario 2 y Teorema 8 en Lovász (1979) .
- ^ Knuth (1994) .
- ^ Grötschel, Lovász y Schrijver (1981) ; Todd y Cheung (2012) .
- ^ Ver Teorema 1 en Lovász (1979) .
- ^ Haemers (1979) .
- ^ Duan, Runyao; Severini, Simone; Invierno, Andreas (2013). "Comunicación de error cero a través de canales cuánticos, gráficos no conmutativos y un número de Lovász cuántico". IEEE Trans. Inf. Teoría . 59 (2): 1164-1174. arXiv : 1002.2514 . doi : 10.1109 / TIT.2012.2221677 . S2CID 4690143 .
- ^ Cabello, Adán; Severini, Simone; Invierno, Andreas (27 de enero de 2014). "Enfoque teórico de gráficos a las correlaciones cuánticas" . Cartas de revisión física . 112 (4): 040401. arXiv : 1401.7081 . doi : 10.1103 / PhysRevLett.112.040401 . PMID 24580419 . S2CID 34998358 .
- ^ Howard, Mark; Wallman, Joel; Veitch, Víctor; Emerson, Joseph (19 de junio de 2014), "La contextualidad proporciona la 'magia' de 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
Referencias
- Duan, Runyao; Severini, Simone; Winter, Andreas (2013) [2010], "Comunicación de error cero a través de canales cuánticos, gráficos no conmutativos y una función cuántica de Lovász ϑ", IEEE Trans. Inf. Teoría , 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 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, Martin ; Lovász, László ; Schrijver, Alexander (1988), Algoritmos geométricos y optimización combinatoria (2 ed.), Springer, ISBN 978-0-387-13624-0, Capítulo 9.3. Representaciones ortonormales, págs. 285.
- Haemers, Willem H. (1979), "On Some Problems of Lovász Concerning the Shannon Capacity of a Graph" , IEEE Transactions on Information Theory , 25 (2): 231-232, doi : 10.1109 / tit.1979.1056027 , archivado de la original el 2012-03-05.
- Knuth, Donald E. (1994), "El teorema del sándwich" (PDF) , Electronic Journal of Combinatorics , 1 : A1, arXiv : math / 9312214 , Bibcode : 1993math ..... 12214K , doi : 10.37236 / 1193 , S2CID 18152765.
- Lovász, László (1979), "On the Shannon Capacity of a Graph", IEEE Transactions on Information Theory , IT-25 (1): 1–7, doi : 10.1109 / tit.1979.1055985.
- Lovász, László (1986), Una teoría algorítmica de números, gráficos y convexidad , SIAM, ISBN 978-0-89871-203-2, Capítulo 3.2. Número cromático, camarillas y gráficas perfectas, págs.75 .
- Lovász, László (1995-2001), Programas semidefinidos y optimización combinatoria, notas de lectura.
- 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 semidefinita (PDF) , Universidad de Cornell.
enlaces externos
- Weisstein, Eric W. "Número de Lovász" . MathWorld .
- Weisstein, Eric W. "Teorema de Sandwich" . MathWorld .
- Weisstein, Eric W. "Capacidad de Shannon" . MathWorld .