Número previsto de $k$ -cliques en $G(n, 1/2) \ge 1$

Question

Sea el número esperado de $k$ -se denotarán por

$$f(k) = \binom{n}{k} (\frac{1}{2})^{- \binom{k}{2}}$$

deje $k_0$ denotan el mayor $k$ tal que $f(k) \ge 1$ .

Quiero demostrar que $k_0 = (1+o(1)2log_{2}n$ y $n = \Theta(k_0 2^{k_0/2})$ .

Puedo probar que $G(m, 0.5)$ no tiene ninguna camarilla de tamaño $2log_{2}(n)$ casi seguro usando Markov, pero ¿ayuda esto?

Agradecemos cualquier ayuda.

Answer 1

Esto es sólo un esbozo, quedan los detalles (escabrosos) de los cálculos.

Tenga en cuenta que $f(k)/f(k+1)=\frac{n-k}{k+1} (\frac{1}{2})^{k}$ que es una función decreciente de $k$ . Así pues, el cociente es como mínimo 1 hasta un cierto valor, luego es como máximo 1. Entonces tenemos que $f$ aumenta de $f(0)=1, f(1)=n, \dots$ (un valor determinado), entonces disminuye.

Teniendo en cuenta lo anterior, en lugar de tomar $k_0$ podemos considerar $k_1=\min \{k: f(k)<1\}$ y mostrar $k_1 \sim 2\log_2(n)$ como $n$ llega hasta el infinito.

Para demostrarlo, utilice las estimaciones clásicas sobre los coeficientes binomiales (véase la primera fórmula en "Límites y fórmulas asintóticas" AQUÍ ) y considere la $k$ -enésima raíz de $f(k)$ . Los límites indicados en el enlace implican $f(k)^{1/k}= \Theta(\frac{n}{k} (\frac{1}{2})^{k/2})$

Fijar $\epsilon >0$ y mostrar: si $k\leq (1-\epsilon)2 \log_2(n)$ entonces $f(k)>1$ (de ahí $k_1 \geq k$ ) y si $k\geq (1+\epsilon)2 \log_2(n)$ entonces $f(k)<1$ (de ahí $k_1 \leq k$ ).

La prueba del primer caso es la siguiente: si $k\leq (1-\epsilon)2 \log_2(n)$ entonces $(1/2)^{k/2} \leq n^{1- \epsilon}$ . Por lo tanto $f(k)^{1/k} \geq Cn(n^{-1+\epsilon})/\log(n)$ donde $C$ es una constante. Es mayor que 1 para $n$ lo suficientemente grande.

Un argumento similar demuestra que $f(k)<1$ para $k\geq (1+\epsilon)2 \log_2(n)$ .