fuera de la diagonal número de Ramsey (4, k) límite inferior método probabilístico razonamiento asintótico

Question

Quiero mostrar eso $R(4,k)\ge\Omega((k/\ln k)^2)$, dónde $R(4,k)$ es el número de Ramsey.

Esta pregunta se acerca bastante a lo que busco, la parte asintótica solo falta (y hablan de$3$ en vez de $4$).

Similar a esa pregunta definimos $Y$ y $Z$ como el número de $4-$camarillas y el número de conjuntos de tamaño vacíos (sin bordes) (número de vértices) $k$ en un gráfico Erdos-Renyi aleatorio (un gráfico sobre $n$ vértices con probabilidad de borde $p$). <- Todo eso está escrito en la respuesta a la pregunta citada.

Así que esto es lo que hice para demostrar que $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}=\Omega((k/\ln k)^2)$.

Nota: $p^6$ proviene de un argumento análogo al de la pregunta citada, $6$ es el número de aristas en el gráfico completo en $4$vértices. Y también supongo que escribiendo$\ge\Omega (...)$ es redundante, la igualdad está bien.

Primero restrinjo $n$ ser de la forma $\frac{k^2}{(\ln k)^2}$ y me puse $p:=1/n$. Obtenemos$${n\choose 4}{p^6}\le n^4p^6=n^{-2}\ll n$$ Para el segundo trimestre tenemos $${n\choose k}(1-p)^{k\choose 2}\le \frac{n^k}{k!}(1-\frac{\frac{1}{2}(\ln k)^2}{\frac{1}{2}k^2})^{k(k-1)/2}\\ \sim \frac{n^k}{k!} (\frac{1}{\sqrt k})^{\ln k}$$

Esta dividido por $n$ es $\frac{n^{k-1}}{k!}(\frac{1}{\sqrt k})^{\ln k}$que queremos ir a cero. Esto implicaría que es$o(n)$.

Este valor es igual a $e^{2(k-1)\ln k-2(k-1)\ln\ln k -\ln k!-\frac{1}{2}\ln k\ln k}$ donde va el exponente $-\infty$, que concluye la prueba.

Pero me temo que solo mostré $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}= n-o(n)$ que no es lo mismo que mostrarlo $\Omega(n)$.

Aunque yo (creo que) hice eso $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}=\Theta (n)$ que es una subclase de $\Omega(n)$.

Answer 1

Si las afirmaciones asintóticas que ha hecho realmente fueran ciertas, entonces su prueba estaría bien. En particular:

• Si, $n - o(n)$ es $\Omega(n)$. Incluso mostrando eso$\binom nk (1-p)^{\binom k2} < 0.99n$ para lo suficientemente grande $n$ estaría bien, y demostrar que es $o(n)$ es más fuerte que eso.
• Si, asumiendo $n = (\frac{k}{\log k})^2$sin una constante está bien, si funciona. Establecimos$n = c (\frac{k}{\log k})^2$ para flexibilidad más adelante, de modo que podamos elegir un $c$eso hará que nuestro argumento funcione. Si$c=1$ está bien, está bien.

Sin embargo, sus afirmaciones asintóticas son falsas. En particular,$\frac{n^{k-1}}{k!}(\frac{1}{\sqrt k})^{\log k} \to \infty$ como $k \to \infty$. Eso es porque

• $\log (n^{k-1}) \sim 2 k \log k$ como $k \to \infty$;
• $\log(k!) \sim k \log k$ como $k \to \infty$;
• $\log\left(\sqrt{k}^{\log k}\right) \sim \frac12(\log k)^2 \ll k \log k$ como $k \to \infty$.

Así que tienes $2 k \log k$ para empezar en el exponente y cancelar aproximadamente $k \log k$ de ella.

Tu principal error es configurar $p = \frac1n$. Esto es demasiado pequeño. Necesitas configurar$p$ ser lo suficientemente pequeño para que no tenga que preocuparse por el $\binom n4 p^6$término; en particular,$p = \frac1{\sqrt n}$es bastante bueno. El mas largo$p$ es decir, más fácil será lidiar con el último período, por lo que no queremos hacer $p$ más pequeño.

Sin embargo, incluso entonces, establecer $n = (\frac{k}{\log k})^2$lo hará sin trabajo - la constante que importa aquí! Te puedo decir que$n = \frac14 (\frac{k}{\log k})^2$ y $p = \frac1{\sqrt n}$trabajará; debe realizar el análisis asintótico de ese caso usted mismo. Puede obtener mejores resultados jugando con las constantes en$n$ y $p$.