número de Ramsey fora da diagonal (4, k) método probabilístico de limite inferior raciocínio assintótico
Eu quero mostrar isso $R(4,k)\ge\Omega((k/\ln k)^2)$, Onde $R(4,k)$ é o número de Ramsey.
Essa questão é bem parecida com o que procuro, só falta a parte assintótica (e eles falam sobre$3$ em vez de $4$)
Semelhante a essa pergunta, nós definimos $Y$ e $Z$ como o número de $4-$cliques e o número de conjuntos vazios (sem arestas) de tamanho (número de vértices) $k$ em um gráfico Erdos-Renyi aleatório (um gráfico sobre $n$ vértices com probabilidade de borda $p$). <- Tudo isso está escrito na resposta à pergunta citada.
Então aqui está o que eu fiz para mostrar que $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}=\Omega((k/\ln k)^2)$.
Nota: $p^6$ vem de um argumento análogo ao da pergunta citada, $6$ é o número de arestas no gráfico completo em $4$vértices. E eu também suponho que escrever$\ge\Omega (...)$ é redundante, a igualdade está OK.
Primeiro eu restrinjo $n$ ser da forma $\frac{k^2}{(\ln k)^2}$ e eu configurei $p:=1/n$. Nós temos$${n\choose 4}{p^6}\le n^4p^6=n^{-2}\ll n$$ Para o segundo mandato, temos $${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}$$
Este dividido por $n$ é $\frac{n^{k-1}}{k!}(\frac{1}{\sqrt k})^{\ln k}$que queremos ir para zero. Isso implicaria que é$o(n)$.
Este valor é igual a $e^{2(k-1)\ln k-2(k-1)\ln\ln k -\ln k!-\frac{1}{2}\ln k\ln k}$ onde o expoente vai $-\infty$, que conclui a prova.
Mas receio que só mostrei $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}= n-o(n)$ o que não é o mesmo que mostrar que é $\Omega(n)$.
Embora eu (acho que) tenha feito isso $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}=\Theta (n)$ que é uma subclasse de $\Omega(n)$.
Respostas
Se as afirmações assintóticas que você fez realmente fossem verdadeiras, sua prova seria adequada. Em particular:
- Sim, $n - o(n)$ é $\Omega(n)$. Mesmo mostrando isso$\binom nk (1-p)^{\binom k2} < 0.99n$ para grande o suficiente $n$ ficaria bem, e mostrando que é $o(n)$ é mais forte do que isso.
- Sim, supondo $n = (\frac{k}{\log k})^2$sem uma constante está bem - se funcionar. Montamos$n = c (\frac{k}{\log k})^2$ para flexibilidade mais tarde, para que possamos escolher um $c$isso fará nosso argumento funcionar. E se$c=1$ está bem, tudo bem.
No entanto, suas afirmações assintóticas são falsas. Em particular,$\frac{n^{k-1}}{k!}(\frac{1}{\sqrt k})^{\log k} \to \infty$ Como $k \to \infty$. Isso é 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$.
Então você tem $2 k \log k$ para começar no expoente, e cancelar aproximadamente $k \log k$ disso.
Seu principal erro é definir $p = \frac1n$. Isso é muito pequeno. Você precisa definir$p$ ser pequeno o suficiente para que você não precise se preocupar com o $\binom n4 p^6$prazo; em particular,$p = \frac1{\sqrt n}$é bom o suficiente. O maior$p$ é, mais fácil será lidar com o último período, então não queremos fazer $p$ qualquer menor.
No entanto, mesmo assim, definir $n = (\frac{k}{\log k})^2$não vai funcionar - o constante importa aqui! Posso dizer-lhe isso$n = \frac14 (\frac{k}{\log k})^2$ e $p = \frac1{\sqrt n}$vai funcionar; você deve fazer a análise assintótica desse caso sozinho. Você pode obter melhores resultados brincando com as constantes em$n$ e $p$.