Desigualdad de Grothendieck

En matemáticas , la desigualdad de Grothendieck establece que existe una constante universal con la siguiente propiedad. Si Mij _es una matriz n  ×  n ( real o compleja ) con ${\displaystyle K_{G}}$

${\displaystyle {\Big |}\sum _{i,j}M_{ij}s_{i}t_{j}{\Big |}\leq 1}$

para todos los números (reales o complejos) s _i , t _j de valor absoluto como máximo 1, entonces

${\displaystyle {\Big |}\sum _{i,j}M_{ij}\langle S_{i},T_{j}\rangle {\Big |}\leq K_{G}}$

para todos los vectores Si , T _j en la _bola unitaria B ( H ) de un espacio de Hilbert (real o complejo) H , siendo la constante independiente de n . Para un espacio fijo de Hilbert de dimensión d , la constante más pequeña que satisface esta propiedad para todas las matrices n  ×  n se llama constante de Grothendieck y se denota . De hecho, existen dos constantes de Grothendieck, y , dependiendo de si se trabaja con números reales o complejos, respectivamente. ^[1] ${\displaystyle K_{G}}$ ${\displaystyle K_{G}(d)}$ ${\displaystyle K_{G}^{\mathbb {R} }(d)}$ ${\displaystyle K_{G}^{\mathbb {C} }(d)}$

La desigualdad de Grothendieck y las constantes de Grothendieck llevan el nombre de Alexander Grothendieck , quien demostró la existencia de las constantes en un artículo publicado en 1953. ^[2]

Motivación y formulación del operador.

Sea una matriz. Luego define un operador lineal entre los espacios normados y for . La norma de es la cantidad. ${\displaystyle A=(a_{ij})}$ ${\displaystyle m\times n}$ ${\displaystyle A}$ ${\displaystyle (\mathbb {R} ^{m},\|\cdot \|_{p})}$ ${\displaystyle (\mathbb {R} ^{n},\|\cdot \|_{q})}$ ${\displaystyle 1\leq p,q\leq \infty }$ ${\displaystyle (p\to q)}$ ${\displaystyle A}$

${\displaystyle \|A\|_{p\to q}=\max _{x\in \mathbb {R} ^{n}:\|x\|_{p}=1}\|Ax\|_{q}.}$

Si , denotamos la norma por . ${\displaystyle p=q}$ ${\displaystyle \|A\|_{p}}$

Se puede considerar la siguiente pregunta: ¿Para qué valor de y se maximiza? Como es lineal, basta con considerar aquel que contenga tantos puntos como sea posible, y también aquel que sea lo más grande posible. Al comparar para , uno ve eso para todos . ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle \|A\|_{p\to q}}$ ${\displaystyle A}$ ${\displaystyle p}$ ${\displaystyle \{x\in \mathbb {R} ^{n}:\|x\|_{p}\leq 1\}}$ ${\displaystyle q}$ ${\displaystyle \|Ax\|_{q}}$ ${\displaystyle \|x\|_{p}}$ ${\displaystyle p=1,2,\ldots ,\infty }$ ${\displaystyle \|A\|_{\infty \to 1}\geq \|A\|_{p\to q}}$ ${\displaystyle 1\leq p,q\leq \infty }$

Una forma de calcular es resolviendo el siguiente programa entero cuadrático : ${\displaystyle \|A\|_{\infty \to 1}}$

${\displaystyle {\begin{aligned}\max &\qquad \sum _{i,j}A_{ij}x_{i}y_{j}\\{\text{s.t.}}&\qquad (x,y)\in \{-1,1\}^{m+n}\end{aligned}}}$

Para ver esto, tenga en cuenta que y tomar el máximo da . Luego, tomando el máximo se obtiene por la convexidad de y por la desigualdad del triángulo. Este programa entero cuadrático se puede relajar al siguiente programa semidefinido : ${\displaystyle \sum _{i,j}A_{ij}x_{i}y_{j}=\sum _{i}(Ay)_{i}x_{i}}$ ${\displaystyle x\in \{-1,1\}^{m}}$ ${\displaystyle \|Ay\|_{1}}$ ${\displaystyle y\in \{-1,1\}^{n}}$ ${\displaystyle \|A\|_{\infty \to 1}}$ ${\displaystyle \{x\in \mathbb {R} ^{m}:\|x\|_{\infty }=1\}}$

${\displaystyle {\begin{aligned}\max &\qquad \sum _{i,j}A_{ij}\langle x^{(i)},y^{(j)}\rangle \\{\text{s.t.}}&\qquad x^{(1)},\ldots ,x^{(m)},y^{(1)},\ldots ,y^{(n)}{\text{ are unit vectors in }}(\mathbb {R} ^{d},\|\cdot \|_{2})\end{aligned}}}$

Se sabe que calcular exactamente para es NP-difícil , mientras que calcular exactamente es NP-difícil para . ${\displaystyle \|A\|_{p\to q}}$ ${\displaystyle 1\leq q<p\leq \infty }$ ${\displaystyle \|A\|_{p}}$ ${\displaystyle p\not \in \{1,2,\infty \}}$

Entonces podemos plantearnos la siguiente pregunta natural: ¿Qué tan bien se aproxima una solución óptima del programa semidefinido ? La desigualdad de Grothendieck proporciona una respuesta a esta pregunta: existe una constante fija tal que, para cualquier matriz y para cualquier espacio de Hilbert , ${\displaystyle \|A\|_{\infty \to 1}}$ ${\displaystyle C>0}$ ${\displaystyle m,n\geq 1}$ ${\displaystyle m\times n}$ ${\displaystyle A}$ ${\displaystyle H}$

${\displaystyle \max _{x^{(i)},y^{(i)}\in H{\text{ unit vectors}}}\sum _{i,j}A_{ij}\left\langle x^{(i)},y^{(j)}\right\rangle _{H}\leq C\|A\|_{\infty \to 1}.}$

Límites de las constantes

Se ve fácilmente que las secuencias y son crecientes, y el resultado de Grothendieck establece que están acotadas , ^{[2] [3]} por lo que tienen límites . ${\displaystyle K_{G}^{\mathbb {R} }(d)}$ ${\displaystyle K_{G}^{\mathbb {C} }(d)}$

Grothendieck demostró que dónde se define ser . ^[4] ${\displaystyle 1.57\approx {\frac {\pi }{2}}\leq K_{G}^{\mathbb {R} }\leq \operatorname {sinh} {\frac {\pi }{2}}\approx 2.3,}$ ${\displaystyle K_{G}^{\mathbb {R} }}$ ${\displaystyle \sup _{d}K_{G}^{\mathbb {R} }(d)}$

Krivine (1979) ^[5] mejoró el resultado demostrando que , conjeturando que el límite superior es ajustado. Sin embargo, esta conjetura fue refutada por Braverman et al. (2011). ^[6] ${\displaystyle K_{G}^{\mathbb {R} }\leq {\frac {\pi }{2\ln(1+{\sqrt {2}})}}\approx 1.7822}$

Constante de Grothendieck de orden d

Boris Tsirelson demostró que las constantes de Grothendieck desempeñan un papel esencial en el problema de la no localidad cuántica : el límite de Tsirelson de cualquier desigualdad de Bell bipartita de correlación completa para un sistema cuántico de dimensión d tiene un límite superior de . ^{[7] [8]} ${\displaystyle K_{G}^{\mathbb {R} }(d)}$ ${\displaystyle K_{G}^{\mathbb {R} }(2d^{2})}$

límites inferiores

En la siguiente tabla se resumen algunos datos históricos sobre los límites inferiores más conocidos . ${\displaystyle K_{G}^{\mathbb {R} }(d)}$

Límites superiores

Algunos datos históricos sobre los límites superiores más conocidos de : ${\displaystyle K_{G}^{\mathbb {R} }(d)}$

Aplicaciones

Estimación de la norma de corte

Dada una matriz real , la norma de corte de está definida por ${\displaystyle m\times n}$ ${\displaystyle A=(a_{ij})}$ ${\displaystyle A}$

${\displaystyle \|A\|_{\square }=\max _{S\subset [m],T\subset [n]}\left|\sum _{i\in S,j\in T}a_{ij}\right|.}$

La noción de norma de corte es esencial en el diseño de algoritmos de aproximación eficientes para matrices y gráficos densos. De manera más general, la definición de norma de corte se puede generalizar para funciones medibles simétricas de modo que la norma de corte de esté definida por ${\displaystyle W:[0,1]^{2}\to \mathbb {R} }$ ${\displaystyle W}$

${\displaystyle \|W\|_{\square }=\sup _{S,T\subset [0,1]}\left|\int _{S\times T}W\right|.}$

Esta definición generalizada de norma de corte es crucial en el estudio del espacio de grafones , y las dos definiciones de norma de corte se pueden vincular mediante la matriz de adyacencia de un gráfico .

Una aplicación de la desigualdad de Grothendieck es dar un algoritmo eficiente para aproximar la norma de corte de una matriz real dada ; específicamente, dada una matriz real, se puede encontrar un número tal que ${\displaystyle A}$ ${\displaystyle m\times n}$ ${\displaystyle \alpha }$

${\displaystyle \|A\|_{\square }\leq \alpha \leq C\|A\|_{\square },}$

donde es una constante absoluta. ^[18] Este algoritmo de aproximación utiliza programación semidefinida . ${\displaystyle C}$

Damos un bosquejo de este algoritmo de aproximación. Sea una matriz definida por ${\displaystyle B=(b_{ij})}$ ${\displaystyle (m+1)\times (n+1)}$

${\displaystyle {\begin{pmatrix}a_{11}&a_{12}&\ldots &a_{1n}&-\sum _{k=1}^{n}a_{1k}\\a_{21}&a_{22}&\ldots &a_{2n}&-\sum _{k=1}^{n}a_{2k}\\\vdots &\vdots &\ddots &\vdots &\vdots \\a_{m1}&a_{m2}&\ldots &a_{mn}&-\sum _{k=1}^{n}a_{mk}\\-\sum _{\ell =1}^{m}a_{\ell 1}&-\sum _{\ell =1}^{m}a_{\ell 2}&\ldots &-\sum _{\ell =1}^{m}a_{\ell n}&\sum _{k=1}^{n}\sum _{\ell =1}^{m}a_{\ell k}\end{pmatrix}}.}$

Se puede verificar que observando, si se forma un maximizador para la norma de corte de , entonces ${\displaystyle \|A\|_{\square }=\|B\|_{\square }}$ ${\displaystyle S\in [m+1],T\in [n+1]}$ ${\displaystyle B}$

${\displaystyle S^{*}={\begin{cases}S,&{\text{if }}m+1\not \in S,\\{[m]}\setminus S,&{\text{otherwise}},\end{cases}}\qquad T^{*}={\begin{cases}T,&{\text{if }}n+1\not \in T,\\{[n]}\setminus S,&{\text{otherwise}},\end{cases}}\qquad }$

Forme un maximizador para la norma de corte de . A continuación se puede verificar que , donde ${\displaystyle A}$ ${\displaystyle \|B\|_{\square }=\|B\|_{\infty \to 1}/4}$

${\displaystyle \|B\|_{\infty \to 1}=\max \left\{\sum _{i=1}^{m+1}\sum _{j=1}^{n+1}b_{ij}\varepsilon _{i}\delta _{j}:\varepsilon _{1},\ldots ,\varepsilon _{m+1}\in \{-1,1\},\delta _{1},\ldots ,\delta _{n+1}\in \{-1,1\}\right\}.}$^[19]

Aunque no es importante en esta prueba, se puede interpretar como la norma de cuando se ve como un operador lineal de a . ${\displaystyle \|B\|_{\infty \to 1}}$ ${\displaystyle B}$ ${\displaystyle \ell _{\infty }^{m}}$ ${\displaystyle \ell _{1}^{m}}$

Ahora basta con diseñar un algoritmo eficiente para la aproximación . Consideremos el siguiente programa semidefinido : ${\displaystyle \|A\|_{\infty \to 1}}$

${\displaystyle {\text{SDP}}(A)=\max \left\{\sum _{i=1}^{m}\sum _{j=1}^{n}a_{ij}\left\langle x_{i},y_{j}\right\rangle :x_{1},\ldots ,x_{m},y_{1},\ldots ,y_{n}\in S^{n+m-1}\right\}.}$

Entonces . La desigualdad de Grothedieck implica que . Se sabe que muchos algoritmos (como los métodos de punto interior , los métodos de primer orden, el método del paquete, el método lagrangiano aumentado ) generan el valor de un programa semidefinido hasta un error aditivo  en el tiempo que es polinómico en el tamaño de la descripción del programa y . ^[20] Por lo tanto, se puede obtener un resultado que satisfaga ${\displaystyle {\text{SDP}}(A)\geq \|A\|_{\infty \to 1}}$ ${\displaystyle {\text{SDP}}(A)\leq K_{G}^{\mathbb {R} }\|A\|_{\infty \to 1}}$ ${\displaystyle \varepsilon }$ ${\displaystyle \log(1/\varepsilon )}$ ${\displaystyle \alpha ={\text{SDP}}(B)}$

${\displaystyle \|A\|_{\square }\leq \alpha \leq C\|A\|_{\square }\qquad {\text{with}}\qquad C=K_{G}^{\mathbb {R} }.}$

Lema de regularidad de Szemerédi

El lema de regularidad de Szemerédi es una herramienta útil en la teoría de grafos, ya que afirma (informalmente) que cualquier gráfico se puede dividir en un número controlado de piezas que interactúan entre sí de forma pseudoaleatoria . Otra aplicación de la desigualdad de Grothendieck es producir una partición del conjunto de vértices que satisfaga la conclusión del lema de regularidad de Szemerédi , mediante el algoritmo de estimación de la norma de corte, en un tiempo que es polinomio en el límite superior del tamaño de partición regular de Szemerédi pero independiente del número de vértices en el gráfico. ^[19]

Resulta que el principal "cuello de botella" al construir una partición regular de Szemeredi en tiempo polinómico es determinar en tiempo polinómico si un par dado está cerca de ser -regular , lo que significa que para todos con , tenemos ${\displaystyle (X,Y)}$ ${\displaystyle \varepsilon }$ ${\displaystyle S\subset X,T\subset Y}$ ${\displaystyle |S|\geq \varepsilon |X|,|T|\geq \varepsilon |Y|}$

${\displaystyle \left|{\frac {e(S,T)}{|S||T|}}-{\frac {e(X,Y)}{|X||Y|}}\right|\leq \varepsilon ,}$

donde para todos y son los conjuntos de vértices y aristas del gráfico, respectivamente. Para ello, construimos una matriz , donde , definida por ${\displaystyle e(X',Y')=|\{(u,v)\in X'\times Y':uv\in E\}|}$ ${\displaystyle X',Y'\subset V}$ ${\displaystyle V,E}$ ${\displaystyle n\times n}$ ${\displaystyle A=(a_{xy})_{(x,y)\in X\times Y}}$ ${\displaystyle n=|V|}$

${\displaystyle a_{xy}={\begin{cases}1-{\frac {e(X,Y)}{|X||Y|}},&{\text{if }}xy\in E,\\-{\frac {e(X,Y)}{|X||Y|}},&{\text{otherwise}}.\end{cases}}}$

Entonces para todos , ${\displaystyle S\subset X,T\subset Y}$

${\displaystyle \left|\sum _{x\in S,y\in T}a_{xy}\right|=|S||T|\left|{\frac {e(S,T)}{|S||T|}}-{\frac {e(X,Y)}{|X||Y|}}\right|.}$

Por lo tanto, si no es -regular, entonces . De ello se deduce que utilizando el algoritmo de aproximación de la norma de corte junto con la técnica de redondeo, se puede encontrar en tiempo polinómico tal que ${\displaystyle (X,Y)}$ ${\displaystyle \varepsilon }$ ${\displaystyle \|A\|_{\square }\geq \varepsilon ^{3}n^{2}}$ ${\displaystyle S\subset X,T\subset Y}$

${\displaystyle \min \left\{n|S|,n|T|,n^{2}\left|{\frac {e(S,T)}{|S||T|}}-{\frac {e(X,Y)}{|X||Y|}}\right|\right\}\geq \left|\sum _{x\in S,y\in T}a_{xy}\right|\geq {\frac {1}{K_{G}^{\mathbb {R} }}}\varepsilon ^{3}n^{2}\geq {\frac {1}{2}}\varepsilon ^{3}n^{2}.}$

Entonces, el algoritmo para producir una partición regular de Szemerédi se deriva del argumento constructivo de Alon et al. ^[21]

Variantes de la desigualdad de Grothendieck

Desigualdad de Grothendieck de una gráfica

La desigualdad de Grothendieck de un gráfico establece que para cada gráfico sin bucles propios, existe una constante universal tal que toda matriz satisface que ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle G=(\{1,\ldots ,n\},E)}$ ${\displaystyle K>0}$ ${\displaystyle n\times n}$ ${\displaystyle A=(a_{ij})}$

${\displaystyle \max _{x_{1},\ldots ,x_{n}\in S^{n-1}}\sum _{ij\in E}a_{ij}\left\langle x_{i},x_{j}\right\rangle \leq K\max _{\varepsilon _{1},\ldots ,\varepsilon _{n}\in \{-1,1\}}\sum _{ij\in E}a_{ij}\varepsilon _{1}\varepsilon _{n}.}$^[22]

La constante de Grothendieck de un gráfico , denotada , se define como la constante más pequeña que satisface la propiedad anterior. ${\displaystyle G}$ ${\displaystyle K(G)}$ ${\displaystyle K}$

La desigualdad de Grothendieck de un gráfico es una extensión de la desigualdad de Grothendieck porque la primera desigualdad es el caso especial de la última desigualdad cuando es un gráfico bipartito con dos copias de como clases de bipartición. De este modo, ${\displaystyle G}$ ${\displaystyle \{1,\ldots ,n\}}$

${\displaystyle K_{G}=\sup _{n\in \mathbb {N} }\{K(G):G{\text{ is an }}n{\text{-vertex bipartite graph}}\}.}$

Para el gráfico completo de vértices, la desigualdad de Grothendieck se convierte en ${\displaystyle G=K_{n}}$ ${\displaystyle n}$ ${\displaystyle G}$

${\displaystyle \max _{x_{1},\ldots ,x_{n}\in S^{n-1}}\sum _{i,j\in \{1,\ldots ,n\},i\neq j}a_{ij}\left\langle x_{i},x_{j}\right\rangle \leq K(K_{n})\max _{\varepsilon _{1},\ldots ,\varepsilon _{n}\in \{-1,1\}}\sum _{i,j\in \{1,\ldots ,n\},i\neq j}a_{ij}\varepsilon _{i}\varepsilon _{j}.}$

Resulta que . Por un lado tenemos . ^{[23] [24] [25]} De hecho, la siguiente desigualdad es cierta para cualquier matriz , lo que implica que por la desigualdad de Cauchy-Schwarz : ^[22] ${\displaystyle K(K_{n})\asymp \log n}$ ${\displaystyle K(K_{n})\lesssim \log n}$ ${\displaystyle n\times n}$ ${\displaystyle A=(a_{ij})}$ ${\displaystyle K(K_{n})\lesssim \log n}$

${\displaystyle \max _{x_{1},\ldots ,x_{n}\in S^{n-1}}\sum _{i,j\in \{1,\ldots ,n\},i\neq j}a_{ij}\left\langle x_{i},x_{j}\right\rangle \leq \log \left({\frac {\sum _{i\in \{1,\ldots ,n\}}\sum _{j\in \{1,\ldots ,n\}\setminus \{i\}}|a_{ij}|}{\sqrt {\sum _{i\in \{1,\ldots ,n\}}\sum _{j\in \{1,\ldots ,n\}\setminus \{i\}}a_{ij}^{2}}}}\right)\max _{\varepsilon _{1},\ldots ,\varepsilon _{n}\in \{-1,1\}}\sum _{i,j\in \{1,\ldots ,n\},i\neq j}a_{ij}\varepsilon _{1}\varepsilon _{n}.}$

Por otro lado, el límite inferior correspondiente se debe a Alon , Makarychev, Makarychev y Naor en 2006. ^[22] ${\displaystyle K(K_{n})\gtrsim \log n}$

La desigualdad de Grothendieck de una gráfica depende de la estructura de . Se sabe que ${\displaystyle K(G)}$ ${\displaystyle G}$ ${\displaystyle G}$

${\displaystyle \log \omega \lesssim K(G)\lesssim \log \vartheta ,}$^[22]

y

${\displaystyle K(G)\leq {\frac {\pi }{2\log \left({\frac {1+{\sqrt {(\vartheta -1)^{2}+1}}}{\vartheta -1}}\right)}},}$^[26]

¿Dónde está el número de camarilla de , es decir, el mayor tal que existe con tal que para todos los distintos , y ${\displaystyle \omega }$ ${\displaystyle G}$ ${\displaystyle k\in \{2,\ldots ,n\}}$ ${\displaystyle S\subset \{1,\ldots ,n\}}$ ${\displaystyle |S|=k}$ ${\displaystyle ij\in E}$ ${\displaystyle i,j\in S}$

${\displaystyle \vartheta =\min \left\{\max _{i\in \{1,\ldots ,n\}}{\frac {1}{\langle x_{i},y\rangle }}:x_{1},\ldots ,x_{n},y\in S^{n},\left\langle x_{i},x_{j}\right\rangle =0\;\forall ij\in E\right\}.}$

El parámetro se conoce como función theta de Lovász del complemento de . ^{[27] [28] [22]} ${\displaystyle \vartheta }$ ${\displaystyle G}$

L^p Desigualdad de Grothendieck

En la aplicación de la desigualdad de Grothendieck para aproximar la norma de corte, hemos visto que la desigualdad de Grothendieck responde a la siguiente pregunta: ¿Qué tan bien se aproxima una solución óptima al programa semidefinido , que puede verse como un problema de optimización sobre el cubo unitario? De manera más general, podemos hacer preguntas similares sobre cuerpos convexos distintos del cubo unitario. ${\displaystyle {\text{SDP}}(A)}$ ${\displaystyle \|A\|_{\infty \to 1}}$

Por ejemplo, la siguiente desigualdad se debe a Naor y Schechtman ^[29] e independientemente a Guruswami et al: ^[30] Para cada matriz y cada , ${\displaystyle n\times n}$ ${\displaystyle A=(a_{ij})}$ ${\displaystyle p\geq 2}$

${\displaystyle \max _{x_{1},\ldots ,x_{n}\in \mathbb {R} ^{n},\sum _{k=1}^{n}\|x_{k}\|_{2}^{p}\leq 1}\sum _{i=1}^{n}\sum _{j=1}^{n}a_{ij}\left\langle x_{i},x_{j}\right\rangle \leq \gamma _{p}^{2}\max _{t_{1},\ldots ,t_{n}\in \mathbb {R} ,\sum _{k=1}^{n}|t_{k}|^{p}\leq 1}\sum _{i=1}^{n}\sum _{j=1}^{n}a_{ij}t_{i}t_{j},}$

dónde

${\displaystyle \gamma _{p}={\sqrt {2}}\left({\frac {\Gamma ((p+1)/2)}{\sqrt {\pi }}}\right)^{1/p}.}$

La constante es aguda en la desigualdad. La fórmula de Stirling implica que como . ${\displaystyle \gamma _{p}^{2}}$ ${\displaystyle \gamma _{p}^{2}=p/e+O(1)}$ ${\displaystyle p\to \infty }$

Ver también

• Desigualdad de Pisier-Ringrose

Referencias

1. Pisier, Gilles (abril de 2012), "Teorema de Grothendieck, pasado y presente", Boletín de la Sociedad Estadounidense de Matemáticas , 49 (2): 237–323, arXiv : 1101.4195 , doi :10.1090/S0273-0979-2011-01348- 9, S2CID  119162963.
2. Grothendieck, Alexander (1953), "Résumé de la théorie métrique des produits tensoriels topologiques", Bol. Soc. Estera. São Paulo , 8 : 1–79, SEÑOR  0094682.
3. Blei, Ron C. (1987), "Una prueba elemental de la desigualdad de Grothendieck", Actas de la Sociedad Matemática Estadounidense , Sociedad Matemática Estadounidense, 100 (1): 58–60, doi : 10.2307/2046119 , ISSN  0002-9939 , JSTOR  2046119, SEÑOR  0883401.
4. Finch, Steven R. (2003), Constantes matemáticas , Cambridge University Press , ISBN 978-0-521-81805-6.
5. Krivine, J.-L. (1979), "Constantes de Grothendieck et fonctions de type positif sur les sphères", Avances en Matemáticas , 31 (1): 16–30, doi : 10.1016/0001-8708(79)90017-3 , ISSN  0001-8708, Señor  0521464.
6. Braverman, Mark; Makarychev, Konstantin; Makarychev, Yuri; Naor, Assaf (2011), "La constante de Grothendieck es estrictamente más pequeña que la límite de Krivine", 52º Simposio anual del IEEE sobre fundamentos de la informática (FOCS) , págs. 453–462, arXiv : 1103.6161 , doi : 10.1109/FOCS.2011.77, S2CID  7803437.
7. Boris Tsirelson (1987). "Análogos cuánticos de las desigualdades de Bell. El caso de dos dominios espacialmente separados" (PDF) . Revista de Matemáticas Soviéticas . 36 (4): 557–570. doi :10.1007/BF01663472. S2CID  119363229.
8. Acín, Antonio; Gisin, Nicolás; Toner, Benjamin (2006), "Modelos locales y constantes de Grothendieck para estados cuánticos entrelazados ruidosos", Physical Review A , 73 (6): 062105, arXiv : quant-ph/0606138 , Bibcode : 2006PhRvA..73f2105A, doi : 10.1103/ PhysRevA.73.062105, S2CID  2588399.
9. Davie, AM (1984), inédito.
10. Fishburn, ordenador personal; Reeds, JA (1994), "Desigualdades de Bell, constante de Grothendieck y raíz dos", Revista SIAM de Matemáticas Discretas , 7 (1): 48–56, doi :10.1137/S0895480191219350.
11. Vértesi, Tamás (2008), "Desigualdades de Bell más eficientes para los estados de Werner", Physical Review A , 78 (3): 032112, arXiv : 0806.0096 , Bibcode :2008PhRvA..78c2112V, doi :10.1103/PhysRevA.78.032112, S2CID  1191 19134.
12. Briët, Jop; Buhrman, Harry; Toner, Ben (2011), "Una desigualdad de Grothendieck generalizada y correlaciones no locales que requieren un alto entrelazamiento", Comunicaciones en física matemática , 305 (3): 827, Bibcode :2011CMaPh.305..827B, doi : 10.1007/s00220-011- 1280-3.
13. Hua, Bobo; Li, Ming; Zhang, Tinggui; Zhou, Chunqin; Li-Jost, Xianqing; Fei, Shao-Ming (2015), "Hacia las constantes de Grothendieck y los modelos LHV en mecánica cuántica", Journal of Physics A: Mathematical and Theoretical , Journal of Physics A , 48 (6): 065302, arXiv : 1501.05507 , Bibcode :2015JPhA. ..48f5302H, doi :10.1088/1751-8113/48/6/065302, S2CID  1082714.
14. Diviánszky, Péter; Bene, Erika; Vértesi, Tamás (2017), "Testigo de Qutrit de la constante de Grothendieck de orden cuatro", Physical Review A , 96 (1): 012113, arXiv : 1707.04719 , Bibcode :2017PhRvA..96a2113D, doi :10.1103/PhysRevA.96.012113, S2CID  119079607.
15. Sébastien Designolle; Gabriele Iommazzo; Mathieu Besanzón; Sebastián Knebel; Patrick Gelß; Sebastián Pokutta (2023). "Modelos locales mejorados y nuevas desigualdades de Bell mediante algoritmos de Frank-Wolfe". arXiv : 2302.04721 . {{cite journal}}: Citar diario requiere |journal=( ayuda )
16. Rietz, Ronald E. (1974), "Una prueba de la desigualdad de Grothendieck", Israel Journal of Mathematics , 19 (3): 271–276, doi :10.1007/BF02757725.
17. Hirsch, Flavien; Quintino, Marco Túlio; Vertesi, Tamás; Navascués, Miguel; Brunner, Nicolas (2017), "Mejores modelos locales de variables ocultas para estados Werner de dos qubits y un límite superior en la constante de Grothendieck", Quantum , 1 : 3, arXiv : 1609.06114 , Bibcode : 2017Quant...1.... 3H, doi :10.22331/q-2017-04-25-3, S2CID  14199122.
18. Alon, Noga; Naor, Assaf (enero de 2006). "Aproximación a la norma de corte a través de la desigualdad de Grothendieck". Revista SIAM de Computación . 35 (4): 787–803. doi :10.1137/S0097539704441629. ISSN  0097-5397.
19. Khot, Subhash; Naor, Assaf (25 de abril de 2012). "Desigualdades de tipo Grothendieck en optimización combinatoria". Comunicaciones sobre Matemática Pura y Aplicada . 65 (7): 992–1035. arXiv : 1108.2464 . doi :10.1002/cpa.21398. ISSN  0010-3640. S2CID  3175317.
20. P., Boyd, Stephen (2011). Optimizacion convexa. Universidad de Cambridge. Pr. ISBN 978-0-521-83378-3. OCLC  767754283.{{cite book}}: CS1 maint: multiple names: authors list (link)
21. Alon, N. (1992). "Los aspectos algorítmicos del lema de regularidad". Actas., 33º Simposio Anual sobre Fundamentos de la Informática . IEEE. págs. 473–481. doi :10.1109/sfcs.1992.267804. ISBN 0-8186-2900-2. S2CID  2222009.
22. , Noga; Makarychev, Konstantin; Makarychev, Yuri; Naor, Assaf (1 de marzo de 2006). "Formas cuadráticas en gráficas" . Invenciones Mathematicae . 163 (3): 499–522. doi :10.1007/s00222-005-0465-9. ISSN  1432-1297.
23. Nemirovski, A.; Roos, C.; Terlaky, T. (1 de diciembre de 1999). "Sobre la maximización de la forma cuadrática sobre la intersección de elipsoides con el centro común". Programación Matemática . 86 (3): 463–473. doi :10.1007/s101070050100. ISSN  1436-4646. S2CID  2988923.
24. Megretski, Alexandre (2001). "Relajaciones de programas cuadráticos en teoría de operadores y análisis de sistemas". En Borichev, Alexander A.; Nikolski, Nikolai K. (eds.). Sistemas, aproximación, operadores integrales singulares y temas relacionados . Teoría del operador: avances y aplicaciones. Basilea: Birkhäuser. págs. 365–392. doi :10.1007/978-3-0348-8362-7_15. ISBN 978-3-0348-8362-7.
25. Charikar, M.; Wirth, A. (2004). "Maximizar los programas cuadráticos: ampliar la desigualdad de Grothendieck". 45º Simposio Anual del IEEE sobre Fundamentos de la Informática . IEEE. págs. 54–60. doi :10.1109/focs.2004.39. ISBN 0-7695-2228-9. S2CID  7036076.
26. Breve, Jop; de Oliveira Filho, Fernando Mario; Vallentin, Frank (2014). "Desigualdades de Grothendieck para programas semidefinidos con restricción de rango". Teoría de la Computación . 10 (1): 77–105. arXiv : 1011.1754 . doi : 10.4086/toc.2014.v010a004 . ISSN  1557-2862. S2CID  1004947.
27. Lovasz, L. (enero de 1979). "Sobre la capacidad de Shannon de un gráfico". Transacciones IEEE sobre teoría de la información . 25 (1): 1–7. doi :10.1109/TIT.1979.1055985. ISSN  0018-9448.
28. Karger, David; Motwani, Rajeev; Sudán, Madhu (1 de marzo de 1998). "Coloración aproximada de gráficos mediante programación semidefinida". Revista de la ACM . 45 (2): 246–265. doi :10.1145/274787.274791. ISSN  0004-5411.
29. Naor, A. y Schechtman, G. (2009). Un esquema de aproximación para la maximización de formas cuadráticas en cuerpos convexos. Manuscrito , 1 (4), 8.
30. Guruswami, Venkatesan; Raghavendra, Prasad; Saket, Rishi; Wu, Yi (17 de enero de 2012). "Evitar UGC de algunos resultados óptimos de inaproximabilidad geométrica". Actas del vigésimo tercer simposio anual ACM-SIAM sobre algoritmos discretos . Filadelfia, PA: Sociedad de Matemáticas Industriales y Aplicadas: 699–717. doi :10.1137/1.9781611973099.58. ISBN 978-1-61197-210-8.

enlaces externos

• Weisstein, Eric W. "La constante de Grothendieck". MundoMatemático .(NB: la parte histórica no es exacta allí.)