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 por , 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]
Sea un gráfico sobre vértices. Un conjunto ordenado de vectores unitarios se denomina representación ortonormal de in , si y son ortogonales siempre que los vértices y no sean adyacentes en :
El número de Lovász del gráfico se define de la siguiente manera:
[3]cono[4]
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]
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]
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]
Valor para gráficos conocidos
El número de Lovász se ha calculado para los siguientes gráficos: [8]
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,
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.
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 .
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 .
Para demostrar que este límite es estrecho, sea la siguiente representación ortonormal del pentágono:
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]
^ 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.
^ 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.
^ Lovász (1995-2001), Proposición 5.1, p. 28.
^ Lovász (1979), Teorema 3.
^ Lovász (1979), Teorema 4.
^ Lovász (1979), Teorema 5.
^ Acertijo (2003).
^ Lovász (1979), Lema 2 y Teorema 7.
^ Lovász (1979), Corolario 2 y Teorema 8.
^ Knuth (1994).
^ Grötschel, Lovász y Schrijver (1981); Todd y Cheung (2012).
^ Lovász (1979), Teorema 1.
^ Haemers (1979).
^ Duan, Severini y invierno (2013).
^ Cabello, Severini e invierno (2014).
^ 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
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
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
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