De Cauchy-Schwarz prueba de Sidorenko para 3-borde de la ruta (Blakely-Roy desigualdad)

Question

Es de Cauchy-Schwarz prueba" de la siguiente desigualdad?

Teorema. Dado $f \colon [0,1]^2 \to [0,1]$, uno tiene $$ \int_{[0,1]^4} f(x,y)f(z,y)f(z,w) \, dxdydzdw \geq \left(\int_{[0,1]^2} f(x,y) \, dxdy\right)^3. $$

De fondo. Esta desigualdad se debe a Blakely y Roy (1965). De hecho, resultó aún más, es decir, cuando el lado izquierdo corresponde a un camino de longitud $k$ (por encima de $k=3$) y el lado derecho es $(\int f)^k$.

Este es un caso especial de una más general Sidorenko la conjetura, la cual se dice que $t(H,W) \geq (\int W)^{e(H)}$ para cualquier gráfico bipartito $H$. El caso general de Sidorenko la conjetura está todavía abierto. Ver, por ejemplo, esta nota por Conlon, Fox, y Sudakov (aunque ha habido algunos avances desde entonces).

Szegedy y Li da una diferente de la prueba de la desigualdad anterior, el uso de la convexidad de la función logaritmo.

Ver también el papel de Kim, Lee, y Lee de otro enfoque.

En la página 28 de Lovasz libro en el gráfico límites, afirma esta desigualdad sin pruebas, y luego dice:

... y esto ya es bastante duro, aunque de corta pruebas con un complicado aplicación de Cauchy–Schwarz desigualdad son conocidos.

Así que mi pregunta es: ¿cómo hace uno para demostrar la desigualdad sobre el uso de Cauchy-Schwarz?

Actualización: Se ha demostrado que no es de vainilla suma de cuadrados de la prueba de la desigualdad https://arxiv.org/abs/1812.08820

Answer 1

aunque a corto pruebas con un complicado aplicación de Cauchy–Schwarz desigualdad son conocidos.

Erm... ¿Cuál es el punto de utilizar este tipo de alta tecnología como de Cauchy-Schwarz en un problema de álgebra elemental?

WLOG $\iint f(x,y)dxdy=1$. Poner $A(x)=\int f(x,y)dy-1$, $B(y)=\int f(x,y)dx-1$, $C(x,y)=f(x,y)-A(x)-B(y)-1$. Entonces $\int A(x)dx=0$, $\int B(y)dy=0$ y $C$ integra a $0$ en cada una de las variables con el otro fijo (esto es, probablemente, la primera descomposición, uno debe tratar en multilineal integral doble de las desigualdades).

Ahora $f(x,y)f(z,y)f(z,w)=(1+A(x)+B(y)+C(x,y))(1+A(z)+B(y)+C(z,y))(1+A(z)+B(w)+C(z,w))$. La integración por Fubini tanto como sea posible, vemos que sólo tenemos que demostrar que
$$ \int a(x)^2dx+\int B(y)^2dy+\iint Una(x)C(x,y)B(y)dxdy\ge 0 $$ Por supuesto, queremos obtener una integral de una no-negativo cantidad aquí. Los rangos son $A,B\ge -1$, $C\ge -1-A-B$. Tenga en cuenta que podemos agregar a los términos de la clase $C H(A)$, $C H(B)$ en cualquier momento que desee, ya que van a integrar a$0$, de todos modos. Nuestra expresión es lineal en $C$. Por lo tanto, debemos encontrar una función de $H$ tal que $H(A)+H(B)+ AB\ge 0$ (por lo que el $+\infty$ final es ACEPTAR) y $A^2+B^2+(-1-A-B)(H(A)+H(B)+AB)\ge 0$ hasta algo que se integra a $0$, por lo que podemos ignorar $(1+A+B)AB$, $AH(B)$ y $BH(A)$ también. Por lo tanto, necesitamos $(1+x)H(x)\le x^2$ de todos modos ($A=B=x$), por lo que lo mejor que podemos esperar es $H(x)=\frac{x^2}{1+x}$. Ahora tenemos la suerte de si
$$ \frac{A^2}{1+A}+\frac{B^2}{1+B}+AB\ge 0 $$ al $a=1+A,b=1+B\ge 0$. Esto sugiere un evidente cambio de variable y obtenemos $$ a-2+\frac 1a+b 2+\frac 1b+ab-a-b+1\ge 0\, $$ así $$ \frac 1a+\frac 1b+ab\ge 3\, $$ que es AM-GM para tres variables (también me parece un poco más natural que el C-S, que es AM-GM para 2 variables, porque, después de todo, tenemos una trilineal integral).

Answer 2

Antes de dar una muy breve de Cauchy-Schwarz desigualdad de la prueba para el 3-borde de la ruta (se puede hacer en una manera similar para cualquier árbol), déjame un comentario sobre la autoría de la desigualdad en cuestión.

En 1959, Mulholland y Smith https://doi.org/10.2307/2309342 demostró que para cualquier simétrica no negativo de la matriz $A$ y la de no-vector negativo $z$ de la misma orden $$ (z^{*} A^k z) \cdot (z^{*} z)^{k-1} \; \geq \; (z^{*} z)^k \; , $$ donde la igualdad se lleva a cabo si y sólo si $z$ es un autovector de $A$ o un vector cero.

Casi al mismo tiempo, Atkinson, Watterson y Moran https://doi.org/10.1093/qmath/11.1.137 resultó $ nm \cdot s(a^{*} A) \; \geq \; s(A)^3 $ para una relación asimétrica no negativo $(n \times m)$-matriz $A$, y la conjetura de que esa desigualdad se cumple para un $k$-borde de la ruta con $k>3$. (Aquí se $s(A)$ denota la suma de las entradas de $A$). Se presenta este desigualdad, tanto de la matriz y de forma integral.

Siendo conscientes de estos resultados, Blakely y Roy en 1965 publicó el suyo: https://doi.org/10.1090/S0002-9939-1965-0184950-9.

Aquí es mi favorito de la prueba de la "Mulholland-Smith / Atkinson-Watterson-Moran / Blakley-Roy desigualdad". Deje $g(x) = \int f(x,y) \: dy$. Entonces \begin{multline*} \int\int\int\int f(x_1,y_1) \; f(x_2,y_1) \; f(x_2,y_2) \; dx_1 \; dx_2 \; dy_1 \; dy_2 \\ \shoveleft = \int\int\int f(x_1,y_1) \; f(x_2,y_1) \; g(x_2) \; dx_1 \; dx_2 \; dy_1 \\ \shoveleft \geq`\int\int\int g^{1/2}(x_1) \; f(x_1,y_1) \; f(x_2,y_1) \; g^{1/2}(x_2) \; dx_1 \; dx_2 \; dy_1 \\ \shoveleft = \int \left( \int g^{1/2}(x) \; f(x,y) \; dx \right)^2 \; dy \\ \shoveleft \geq \left( \int\int g^{1/2}(x) \; f(x,y) \; dx \; dy \right)^2 \; = \; \left( \int g^{1/2}(x) \; g(x) \; dx \right)^2 \\ \shoveleft \geq \left( \int g(x) \; dx \right)^3 \; = \; \left( \int f(x,y) \; dx \; dy \right)^3 \; . \\ \end{multline*}

Answer 3

Permítanme añadir, posiblemente, la más corta de la prueba de la desigualdad a la que se le pidió, aunque no por Cauchy-Schwarz. Siguiente Sasha la notación, vamos a $g(x)=\int f(x,y) dy$. A continuación, por parte del Titular de la desigualdad, \begin{align*} \int f(x,y)f(y,z)f(z,w) &= \int g(y)f(y,z)g(z)\\ &=\int g(y)f(y,z)g(z) \int \frac{f(y,z)}{g(y)} \int \frac{f(y,z)}{g(z)}\\ &\geq \left(\int f(y,z) \right)^3. \end{align*}

Como los dos de nosotros ya sabíamos, se demostró que la bandera de álgebra caculus no da la respuesta a esta desigualdad. Añado también que la referencia para aquellos lectores que no conocen el reciente resultado por Blekherman, Raymond, Singh, y Thomas: https://arxiv.org/pdf/1812.08820.pdf