La camarilla de los números y el Teorema 4.5.1 en "El Método de probabilidades" por Alon y Spencer

Question

Mi pregunta es "¿Cuál es la formulación exacta de la siguiente teorema de Alon y Spencer del libro El Método de probabilidades?"

Para el contexto,

1. Deje $G(n,1/2)$ la probabilidad en el espacio de grafos aleatorios , donde los bordes son elegidos de manera uniforme y de forma independiente con una probabilidad de $1/2$.

2. La cantidad de $f(k)$ es el número esperado de las camarillas de tamaño $k$ entre los elementos de $G(n,1/2)$, es decir,$f(k) = {n \choose k}2^{-{k\choose 2}}$.

3. Los autores señalan que, si $k \sim 2\log_2n$, entonces la función de $f(k)$ "cae por debajo de uno," lo que significa, y $f(k)$ es "muy groso como $n^k2^{-k^2/2}$," lo que eso significa.

4. Si $G$ es un gráfico, vamos a $\omega(G)$ ser el tamaño de la más grande de la camarilla en el $G$, (es decir, el tamaño del conjunto de vértices correspondientes a los mayores subgrafo completo de $G$).

Aquí está el teorema:

Teorema 4.5.1 Deje $k = k(n)$ satisfacer $k \sim 2\log_2n$$f(k) \to \infty$. Entonces casi siempre $\omega(G) \ge k$.

Lo que (creo yo) entender ya:

1. $k\sim 2\log_2n$ $k(n)/2\log_2n\to 1$ $n\to\infty$.

2. "casi siempre $\omega(G)\ge k$" significa que para cada una de las $\epsilon > 0$ hay un $N = N(\epsilon)$ que si $n\ge N$, entonces para cualquier $G(n,1/2)$, la probabilidad de que el evento $\{\text{$G\in G(n,1/2)$ satisfies $\omega(G)\ge k$}\}$ es mayor que $1-\epsilon$.

Lo que no entiendo:

1. ¿Cómo podemos suponer que $f(k)\to \infty$ $n\to\infty$ si asumimos que $k\sim 2\log_2n$? En el punto 3 anterior en el contexto, me dio, suponiendo que $k\sim 2\log_2n$ " $f(k)$ cae por debajo de uno," así que, ¿cómo puede $f(k)$ también ir hasta el infinito? (Basado en este punto, una adecuada respuesta a mi pregunta tendrá que hacer frente a lo que se dice precisamente en el punto 3 del contexto).

Muchas gracias.

Answer 1

Una más precisa declaración del teorema sería

Deje $k(n)$ ser una función de la $n$ tal que $k(n) \sim 2 \log_2 n$ $n \to \infty$ (es decir,$\lim\limits_{n \to \infty} \frac{k(n)}{2 \log_2 n} = 1 )$$f(k(n)) \to \infty$$n \to \infty$. Entonces $$\lim_{n \to \infty} \left(\Pr[\omega(G) \ge k(n)]\right) = 1$$ where $G$ has the $G(n,\tfrac12)$ de distribución.

Por lo que parece entender el teorema correctamente.

Para aclarar la afirmación de que parece ser confusa: diciendo:

La función de $f(k)$ cae por debajo de uno en $k \sim 2 \log_2 n$

significa que si dejamos $k^*(n)$ ser el menos valor de $k$ (para un valor fijo de $n$) tal que $f(k) < 1$,$k^*(n) \sim 2 \log_2 n$.

Hay un montón de funciones $k(n)$ satisfacción $k(n) \sim 2 \log_2 n$. Algunos de ellos va a satisfacer $f(k(n)) < 1$ todos los $n$, y algunas otras tienen $f(k(n)) \to \infty$$n \to \infty$. De hecho, para$k$, $f(k)$ cambia tan rápidamente que podemos definir una función de $k(n)$$f(k(n)+1) \to \infty$$n\to\infty$, y sin embargo $f(k(n)-1) \to 0$$n\to\infty$. El teorema requiere que escoger un "va-a -$\infty$"$k$.

También, la declaración de

$f(k)$ es muy groso como $n^k 2^{-k^2/2}$

es, como se dice, una muy áspera asintótica estimado: no es exacto dentro de un $1+o(1)$ factor o incluso dentro de un factor constante, pero cerca de la verdad. Más precisamente, pasando de $\binom nk$ $n^k$e de $2^{-\binom k2}$ $2^{-k^2/2}$tanto la caída de un factor que es una función exponencial de la $k$: mucho menos importante que cualquiera de los factores que mantener.

Podemos hacer que la instrucción precisa diciendo algo como: $\log f(k) \sim \log (n^k 2^{-k^2})$ si $k \sim 2 \log_2 n$ (como $n \to \infty$), pero que falta el punto: la razón por la que hacer esta estimación es para tener una idea aproximada de cómo de grande $f(k)$ es antes de analizar de manera más precisa.