Desigualdad de Grothendieck

En matemáticas , la desigualdad de Grothendieck establece que existe una constante universal con la siguiente propiedad. Si M _ij 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 S _i , 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 de Hilbert fijo de dimensión d , la constante más pequeña que satisface esta propiedad para todas las matrices n  ×  n se denomina constante de Grothendieck y se denota . De hecho, hay 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 reciben su 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. Entonces se define un operador lineal entre los espacios normados y para . 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 plantear la siguiente pregunta: ¿Para qué valor de y se maximiza? Como es lineal, entonces basta con considerar que contenga tantos puntos como sea posible, y también que sea lo más grande posible. Al comparar para , se ve que para todo . ${\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 calcularlo 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, observe que , y tomando el máximo sobre da . Luego, tomando el máximo sobre da por la convexidad de y por la desigualdad triangular. 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 el cálculo exacto para es NP-difícil , mientras que el cálculo exacto 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 \}}$

Se puede entonces plantear la siguiente pregunta natural: ¿Qué tan bien se aproxima una solución óptima al programa semidefinido a ? La desigualdad de Grothendieck proporciona una respuesta a esta pregunta: existe una constante fija tal que, para cualquier , 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 donde se define como . ^[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 al demostrar que , conjeturando que el límite superior es estricto. 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 orden de Grothendieckd

Boris Tsirelson demostró que las constantes de Grothendieck juegan 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 está acotado superiormente por . ^{[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 se define 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 para diseñar algoritmos de aproximación eficientes para matrices y gráficos densos. En términos más generales, la definición de norma de corte se puede generalizar para funciones medibles simétricas , de modo que la norma de corte de se define 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 a través de 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 esbozo 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 }$

Formar 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, puede interpretarse 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 aproximar . 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 de paquete, el método lagrangiano aumentado ) generan el valor de un programa semidefinido hasta un error aditivo  en el tiempo que es polinomial en el tamaño de la descripción del programa y . ^[20] Por lo tanto, se puede generar que satisface ${\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, que afirma (informalmente) que cualquier grafo puede ser dividido en un número controlado de piezas que interactúan entre sí de manera pseudoaleatoria . Otra aplicación de la desigualdad de Grothendieck es producir una partición del conjunto de vértices que satisface la conclusión del lema de regularidad de Szemerédi , a través del algoritmo de estimación de norma de corte, en un tiempo que es polinomial en el límite superior del tamaño de la partición regular de Szemerédi pero independiente del número de vértices en el grafo. ^[19]

Resulta que el principal "cuello de botella" de la construcción de una partición regular de Szemeredi en tiempo polinomial es determinar en tiempo polinomial si un par dado está o no 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 grafo, 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 norma de corte junto con la técnica de redondeo, se puede encontrar en tiempo polinomial 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 desprende del argumento constructivo de Alon et al. ^[21].

Variantes de la desigualdad de Grothendieck

Desigualdad de Grothendieck de un gráfico

La desigualdad de Grothendieck de un gráfico establece que para cada gráfico sin bucles propios, existe una constante universal tal que cada 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 grafo es una extensión de la desigualdad de Grothendieck porque la primera desigualdad es el caso especial de la segunda cuando es un grafo bipartito con dos copias de como sus clases de bipartición. Por lo tanto, ${\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értice, la desigualdad de Grothendieck de 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 verdadera 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 otra parte, 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 un gráfico 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]

donde es el número de camarilla de , es decir, el más grande 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}$

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 a , lo 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 nítida en la desigualdad. La fórmula de Stirling implica que cuando . ${\displaystyle \gamma _{p}^{2}}$ ${\displaystyle \gamma _{p}^{2}=p/e+O(1)}$ ${\displaystyle p\to \infty }$

Véase también

• Desigualdad de Pisier-Ringrose

Referencias

1. Pisier, Gilles (abril de 2012), "El teorema de Grothendieck, pasado y presente", Boletín de la American Mathematical Society , 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 American Mathematical Society , 100 (1), American Mathematical Society: 58–60, doi : 10.2307/2046119 , ISSN  0002-9939, JSTOR  2046119, MR  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, Yury; Naor, Assaf (2011), "La constante de Grothendieck es estrictamente menor que el 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 separados espacialmente" (PDF) . Revista de Matemáticas Soviéticas . 36 (4): 557–570. doi :10.1007/BF01663472. S2CID  119363229.
8. Acín, Antonio; Gisin, Nicolas; Toner, Benjamin (2006), "Modelos constantes y locales 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, PC; Reeds, JA (1994), "Desigualdades de Bell, constante de Grothendieck y raíz dos", SIAM Journal on Discrete Mathematics , 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  119134.
12. Briët, Jop; Buhrman, Harry; Toner, Ben (2011), "Una desigualdad de Grothendieck generalizada y correlaciones no locales que requieren un alto entrelazamiento", Communications in Mathematical Physics , 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 , 48 (6), Journal of Physics A : 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 Besançon; Sebastian Knebel; Patrick Gelß; Sebastian Pokutta (2023), "Modelos locales mejorados y nuevas desigualdades de Bell mediante algoritmos de Frank-Wolfe", Physical Review Research , 5 (4): 043059, arXiv : 2302.04721 , doi :10.1103/PhysRevResearch.5.043059
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; Vértesi, Tamás; Navascués, Miguel; Brunner, Nicolas (2017), "Mejores modelos locales de variables ocultas para estados de Werner de dos qubits y un límite superior para 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 de la norma de corte mediante 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". Communications on Pure and Applied Mathematics . 65 (7): 992–1035. arXiv : 1108.2464 . doi :10.1002/cpa.21398. ISSN  0010-3640. S2CID  3175317.
20. P., Boyd, Stephen (2011). Optimización convexa. Universidad de Cambridge. 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.S2CID2222009  .​
22. Alon, Noga; Makarychev, Konstantin; Makarychev, Yury; Naor, Assaf (1 de marzo de 2006). "Formas cuadráticas en gráficos" . Inventiones Mathematicae . 163 (3): 499–522. doi :10.1007/s00222-005-0465-9. ISSN  1432-1297.
23. Nemirovski, A.; Roos, C.; Terlaky, T. (1999-12-01). "Sobre la maximización de la forma cuadrática sobre la intersección de elipsoides con 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 de operadores: 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). "Maximización de programas cuadráticos: extensión de 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. Briet, 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 grafo". IEEE Transactions on Information Theory . 25 (1): 1–7. doi :10.1109/TIT.1979.1055985. ISSN  0018-9448.
28. Karger, David; Motwani, Rajeev; Sudan, Madhu (1998-03-01). "Coloración aproximada de grafos mediante programación semidefinida". Revista de la ACM . 45 (2): 246–265. doi :10.1145/274787.274791. ISSN  0004-5411.
29. Naor, A., & Schechtman, G. (2009). Un esquema de aproximación para la maximización de la forma cuadrática en cuerpos convexos. Manuscrito , 1 (4), 8.
30. Guruswami, Venkatesan; Raghavendra, Prasad; Saket, Rishi; Wu, Yi (17 de enero de 2012). "Evitar el UGC a partir de algunos resultados de inaproximabilidad geométrica óptima". Actas del vigésimo tercer simposio anual ACM-SIAM sobre algoritmos discretos . Filadelfia, PA: Society for Industrial and Applied Mathematics: 699–717. doi :10.1137/1.9781611973099.58. ISBN 978-1-61197-210-8.

Enlaces externos

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