Usando el teorema de Mantel para probar una desigualdad probabilística

Question

Usando el teorema de Mantel para probar una desigualdad probabilística

geometría
Matemáticas
probabilidad
Teoría de grafos
integral-desigualdad
Teoría de grafos extremos

silas wang

Estoy autoaprendiendo "Teoría de grafos y combinatoria aditiva" de Yufei Zhao , un problema que encuentro es el siguiente:

El siguiente ejercicio puede resolverse mediante una aplicación ordenada del teorema de Mantel.
Ejercicio 1.1.10. Dejar $X$ y $Y$ ser vectores aleatorios independientes e idénticamente distribuidos en $\mathbb{R}^{d}$ de acuerdo con alguna distribución de probabilidad arbitraria. Pruebalo
$PAG (| X + Y | \geq 1) \geq \frac{1}{2} PAG (| X | \geq 1)^{2} .$ $\mathbb{P}(|X+Y| \geq 1) \geq \frac{1}{2} \mathbb{P}(|X| \geq 1)^{2} .$

El teorema de Mantel . Cada $n$ -el grafo libre de triángulos de vértices tiene como máximo $\left\lfloor n^{2} / 4\right\rfloor$ bordes alias
$ex (norte, H) = ⌊ \frac{{norte}^{2}}{4} ⌋ .$ $\operatorname{ex}(n, H)=\left\lfloor\frac{n^{2}}{4}\right\rfloor \text {. }$

No tengo ni idea de cómo esta desigualdad de la integral está conectada con la teoría de grafos, al menos dame una pista. La prueba de que no se usa el teorema de Mantel también es bienvenida.

Andreas Lenz

Sería útil si agregara algo de contexto y antecedentes sobre el capítulo del libro. A veces, un ejercicio utiliza una idea presentada en el capítulo o es una versión más complicada de un ejercicio anterior.

Misha Lavrov

Está relacionado con el infame ejercicio del Capítulo 1 del Método probabilístico de Alon y Spencer .

Respuestas (1)

Usando el teorema de Mantel para probar una desigualdad probabilística

Sería útil si agregara algo de contexto y antecedentes sobre el capítulo del libro. A veces, un ejercicio utiliza una idea presentada en el capítulo o es una versión más complicada de un ejercicio anterior.
Está relacionado con el infame ejercicio del Capítulo 1 del Método probabilístico de Alon y Spencer .

Misha Lavrov · Answer 1

Aquí hay un esquema de la estrategia.

Primero, demuestre que cuando $x,y,z \in \mathbb R^d$ es imposible tener $|x|, |y|, |z| \ge 1$ pero $|x+y|, |x+z|, |y+z| < 1$ . Este es nuestro hecho geométrico "libre de triángulos".

A continuación, considere $n$ puntos $x_1, \dots, x_n$ en $\mathbb R^d$ , de los cuales $|x_1|, \dots, |x_k| \ge 1$ y $|x_{k+1}|, \dots, |x_n| < 1$ . Use el teorema de Mantel para probar que hay al menos $\frac12 k^2$ pares ordenados $(x_i, x_j)$ con $|x_i + x_j| \ge 1$ , incluidos los pares $(x_i, x_i)$ .

Ahora, aplica esto a $n$ puntos dibujados independientemente de la distribución en el problema. En expectativa, obtenemos al menos $n(n-1) \Pr[|X+Y| \ge 1]$ pares $(x_i, x_j)$ con $|x_i + x_j| \ge 1$ y $n \Pr[|X| \ge 1]$ elementos $x_i$ con $|x_i| \ge 1$ . La aplicación del teorema de Mantel anterior nos da la desigualdad que queremos, con un término de error que desaparece como $n \to \infty$ .

Usando el teorema de Mantel para probar una desigualdad probabilística

silas wang

Andreas Lenz

Misha Lavrov

Respuestas (1)

Misha Lavrov

silas wang

dadas n líneas aleatorias en un plano 2d, ¿cuál es la probabilidad de tener menos de k puntos de intersección?

Una pregunta sobre la expectativa del número cromático

¿La probabilidad de que los vértices de un grafo bipartito completo estén desconectados de modo que no quede ningún camino de longitud 2 entre ellos?

Probabilidad de obtener un triángulo obtuso al elegir tres puntos en un círculo.

¿Cuál es la probabilidad de que el centro de un polígono regular de lados impares se encuentre dentro de un triángulo formado por los vértices del polígono?

¿Qué significa "probabilidad media" en esta definición del coeficiente de agrupamiento?

¿Referencia para el teorema? Desigualdad de integrales de función creciente sobre dos distribuciones

Estimación del valor de eee usando una función aleatoria

Dibujar curvas (o segmentos) que no se intersecan conectando vértices no adyacentes en un polígono regular

Número máximo de miembros en el club de matemáticas