Probabilidad de que pesos aleatorios en $K_n$ satisfacen la desigualdad triangular

Question

Dado $K_n$ si un peso real aleatorio entre $[0, 1]$ para cada arista, ¿cuál es la probabilidad de que el gráfico satisfaga la desigualdad del triángulo? ¿Y la versión discreta, en la que los pesos son enteros en $[0, k]$ ?

Es fácil ver que si $n = 3$ la probabilidad es $1/2$ y (empíricamente) que la probabilidad se aproxima a cero a medida que n va a $\infty$ . ¿Alguien ha estudiado el problema antes? Se agradecerá cualquier resultado exacto o asintótico.

Notas:

1. Esta pregunta se publicó en math.SE aquí . No obtuve respuestas y parece bastante inactivo por el momento.
2. Esta es mi primera pregunta en mathoverflow, así que lo siento si esto no es de nivel de investigación, pero me parece que lo es.

Answer 1

Esto es demasiado largo para un comentario. Es fácil probar el tipo sugerido por Anthony Quas en los comentarios. Para algunas constantes $c_1,c_2 \gt 0$ y $n \ge 3$ ,

$$e^{-c_1 n^2} \le P(n) \le e^{-c_2 n^2} .$$ .

Límite inferior: Cuando todas las distancias son mayores que $1/2$ se cumple la desigualdad triangular.

Límite superior: Tome $c n^2$ triángulos de bordes disjuntos en $K_n$ . La probabilidad de que la desigualdad de triángulos se cumpla en todas partes es como máximo la probabilidad de que se cumpla sólo en esos triángulos, $2^{-c n^2}$ ya que la integración simple ( $\int_0^1 \int_0^{1-y} (1-x-y) dx dy = 1/6$ ) comprueba que la probabilidad de un triángulo es $1/2$ .

Los mismos tipos de límites se mantienen en la versión discreta para $k \ge 1$ . Es posible que los valores exactos sean interesantes, y sugiero calcularlos exactamente para pequeños $n$ y comprobando los valores normalizados en la OEIS.

Answer 2

Una versión más eficiente del límite inferior de Doug:

Obtenemos la misma probabilidad $P(n)$ si suponemos que la arista más larga tiene longitud 1. En general, la arista más larga tiene alguna longitud $\alpha$ las demás aristas son entonces independientes y uniformes en $[0,\alpha]$ y, a continuación, puede reescalar los otros bordes mediante $1/\alpha$ . De hecho, sin pérdida de generalidad, sólo 1 arista tiene longitud $\alpha$ y puede especificar cuál.

Supongamos que el borde $\{1,2\}$ tiene longitud 1. Entonces hay $n-2$ triángulos que contienen esa arista, y con probabilidad independiente $1/2$ cada uno es bueno. Estos $n-2$ también son independientes de si el gráfico restante en $n-2$ vértices es buena, y esa probabilidad es $P(n-2)$ . En este cálculo, estamos ignorando los triángulos que sólo utiliza un vértice de $\{1,2\}$ . Así obtenemos la recurrencia $$P(n) \le 2^{2-n} P(n-2).$$ Así $$\frac{-n(n-1)}{2} \le \log_2 P(n) \le -\lfloor \frac{n}{2} \rfloor \lfloor \frac{n-1}2 \rfloor,$$ utilizando también el límite elemental de Doug de que el grafo es bueno si todas las longitudes de las aristas son al menos $1/2$ .

Answer 3

A partir de una conversación con Dan Romik, he aquí una generalización de los límites de volumen de Doug.

Sea $H(n,t)$ sea el hipergrafo de todos los $t$ -tuplas de un conjunto con $n$ y que $n > k > t$ sea otro número entero. Supongamos que cada hyperedge $T$ está coloreada por una variable aleatoria i.i.d. $x_T$ que toma valores en algún espacio de medidas $X$ . Supongamos además que para cada subconjunto de $k$ -subconjunto $K$ existe alguna restricción no trivial, simétrica y medible $R \subset X^{\binom{k}{t}}$ sobre los colores $x_T$ para $T \subseteq K$ . Sea $P(n)$ es la probabilidad de que todas las restricciones a la coloración de $H(n,t)$ se cumplen.

Teorema: Por cada $m \ge k$ , $$\limsup_{n \to \infty} \frac{\log P(n)}{n^t} \le \frac{\log P(m)}{m^t}.$$

Corolario: El límite $$\alpha = \lim_{n \to \infty} \frac{\log P(n)}{n^t}$$ existe, y se obtienen cada vez mejores límites sobre $\alpha$ por ordenador $P(m)$ para valores específicos de $m$ empezando por el caso $m=k$ lo que implica que $\alpha < 0$ . En general se obtiene $\alpha \in [-\infty,0)$ .

Prueba. El teorema es un corolario del teorema de Rödl de que existe un empaquetamiento de bloques de tamaño $k$ que son disjuntos en hiperedges de $H(n,t)$ y que cubren una fracción del $t$ -que converge a 1 a medida que $n \to \infty$ .

Teorema: (1) Si la condición $R$ contiene un cubo $I^{\binom{k}{t}}$ donde $I \subset X$ es algún suceso con medida positiva, entonces $\alpha > -\infty$ . (2) Si existe una partición finita $\{I_i\}$ de $X$ tal que $R$ es disjunta de cada $I_i^{\binom{k}{t}}$ entonces $\alpha = -\infty$ porque $P(n) = 0$ cuando $n$ es lo suficientemente grande.

Por ejemplo, supongamos que $X$ es una variedad riemanniana compacta con medida riemanniana. Entonces se cumple la condición (1) si el interior de $R$ contiene al menos un punto en la diagonal. La condición (2) se cumple si el cierre de $R$ es disjunta de la diagonal.

Demostración. El caso (1) no es más que la observación de que la probabilidad $P(n)$ es al menos la probabilidad de aterrizar en $I^{\binom{n}{t}}$ . El caso (2) se deduce del teorema de Ramsey.