hors diagonale nombre de Ramsey (4, k) borne inférieure méthode probabiliste raisonnement asymptotique

Dec 23 2020

Je veux montrer ça $R(4,k)\ge\Omega((k/\ln k)^2)$, où $R(4,k)$ est le nombre de Ramsey.

Cette question est assez proche de ce que je cherche, la partie asymptotique ne fait que manquer (et ils parlent de$3$ au lieu de $4$).

Similaire à cette question que nous définissons $Y$ et $Z$ comme le nombre de $4-$cliques et le nombre d'ensembles de taille vides (sans arêtes) (nombre de sommets) $k$ dans un graphe aléatoire Erdos-Renyi (un graphe sur $n$ sommets avec probabilité d'arête $p$) <- Tout cela est écrit dans la réponse à la question citée.

Alors voici ce que j'ai fait pour montrer que $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}=\Omega((k/\ln k)^2)$.

Remarque: $p^6$ provient d'un argument analogue à celui de la question citée, $6$ est le nombre d'arêtes dans le graphique complet sur $4$sommets. Et je suppose aussi que l'écriture$\ge\Omega (...)$ est redondant, l'égalité est OK.

Je limite d'abord $n$ être de la forme $\frac{k^2}{(\ln k)^2}$ et j'ai mis $p:=1/n$. On a$${n\choose 4}{p^6}\le n^4p^6=n^{-2}\ll n$$ Pour le deuxième mandat, nous avons $${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}$$

Ceci divisé par $n$ est $\frac{n^{k-1}}{k!}(\frac{1}{\sqrt k})^{\ln k}$dont nous voulons aller à zéro. Cela impliquerait que c'est$o(n)$.

Cette valeur est égale à $e^{2(k-1)\ln k-2(k-1)\ln\ln k -\ln k!-\frac{1}{2}\ln k\ln k}$ où va l'exposant $-\infty$, qui conclut la preuve.

Mais j'ai peur de ne montrer que $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}= n-o(n)$ ce qui n'est pas la même chose que de le montrer $\Omega(n)$.

Bien que je (pense que j'ai) fait ça $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}=\Theta (n)$ qui est une sous-classe de $\Omega(n)$.

Réponses

2 MishaLavrov Dec 28 2020 at 18:10

Si les affirmations asymptotiques que vous avez faites étaient vraiment vraies, alors votre preuve serait bonne. En particulier:

  • Oui, $n - o(n)$ est $\Omega(n)$. Même en montrant ça$\binom nk (1-p)^{\binom k2} < 0.99n$ pour assez grand $n$ serait bien, et montrer que c'est $o(n)$ est plus fort que ça.
  • Oui, en supposant $n = (\frac{k}{\log k})^2$sans constante, c'est bien - si cela fonctionne. Nous fixons$n = c (\frac{k}{\log k})^2$ pour plus de flexibilité plus tard, afin que nous puissions choisir un $c$cela fera fonctionner notre argumentation. Si$c=1$ se trouve être bien, ce n'est pas grave.

Cependant, vos affirmations asymptotiques sont fausses. En particulier,$\frac{n^{k-1}}{k!}(\frac{1}{\sqrt k})^{\log k} \to \infty$ comme $k \to \infty$. C'est parce que

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

Alors tu as $2 k \log k$ pour commencer dans l'exposant, et annuler à peu près $k \log k$ de celui-ci.

Votre principale erreur est de définir $p = \frac1n$. C'est bien trop petit. Vous devez définir$p$ être juste assez petit pour ne pas avoir à vous soucier de la $\binom n4 p^6$terme; en particulier,$p = \frac1{\sqrt n}$est assez bon. Le plus grand$p$ c'est que plus il sera facile de gérer le dernier mandat, donc nous ne voulons pas $p$ tout plus petit.

Cependant, même alors, le réglage $n = (\frac{k}{\log k})^2$sera pas le travail - le compte constant ici! Je peux te dire ça$n = \frac14 (\frac{k}{\log k})^2$ et $p = \frac1{\sqrt n}$marchera; vous devriez faire vous-même l'analyse asymptotique de ce cas. Vous pouvez obtenir de meilleurs résultats en jouant avec les constantes sur$n$ et $p$.