Ahora, estoy estudiando sobre un Grafón propuesto por Lovasz. ¿Por qué se dice que un gráfico generado por un grafón es denso? No puedo imaginarme esto.
Respuesta
¿Demasiados anuncios?
Misha
Puntos
1723
Un $n$ -El gráfico de vértices es denso en este sentido si tiene $m = \Theta(n^2)$ bordes: si su densidad $m/\binom n2$ es positivo. Un gráfico así tiene una fracción constante de todas las aristas positivas que podría tener.
Supongamos que tenemos un grafo $W : [0,1]^2 \to [0,1]$ y excluyamos los ejemplos que son cero en casi todas partes (tales grafos producirán, en realidad, grafos vacíos casi con seguridad). Entonces hay un $\epsilon>0$ tal que el conjunto $S = \{(x,y) \in [0,1]^2 : W(x,y) \ge \epsilon\}$ tiene una medida positiva $\mu(S)$ .
Generamos un $n$ -de vértices de este grafón eligiendo valores $u_1, u_2, \dots, u_n \in [0,1]$ de forma independiente y uniforme al azar, y luego añadir el borde $(i,j)$ con probabilidad $W(u_i, u_j)$ (también de forma independiente para cada $(i,j)$ .) Tenemos $$ \Pr[(i,j) \in E] = \Pr[(i,j) \in E \mid (u_i, u_j) \in S] \cdot \Pr[(u_i, u_j) \in S] \ge \epsilon \cdot \mu(S). $$ Por lo tanto, el número esperado de aristas en el gráfico es al menos $\epsilon \mu(S) \binom n2$ .
De hecho, el número de aristas está muy concentrado en torno a la media. Podemos demostrarlo, por ejemplo, con La desigualdad de McDiarmid : cambiando cada $u_i$ puede cambiar el número de aristas como máximo $c_i = n-1$ Así que $$ \Pr\left[|E| \le (\epsilon \mu(S)- \delta) \binom n2 \right] \le \exp\left(\frac{2 (\delta \binom n2)^2}{\sum_{i=1}^n (n-1)^2}\right) = e^{-\delta^2 n/2}. $$ Por lo tanto, el gráfico tiene una densidad de al menos $\epsilon \mu(S)-\delta$ con probabilidad $1 - e^{-\delta n^2/2}$ que va a $1$ como $n \to \infty$ . Esto demuestra que el gráfico que obtenemos es denso asintóticamente casi seguro .
