außerhalb der Diagonale Ramsey Nummer (4, k) untere Grenze probabilistische Methode asymptotisches Denken

Question

Das möchte ich zeigen $R(4,k)\ge\Omega((k/\ln k)^2)$, wo $R(4,k)$ ist die Ramsey-Nummer.

Diese Frage ist ziemlich nah an dem, wonach ich suche, der asymptotische Teil fehlt nur (und sie reden darüber$3$ Anstatt von $4$).

Ähnlich wie bei dieser Frage definieren wir $Y$ und $Z$ als die Anzahl von $4-$Cliquen und die Anzahl der leeren (keine Kanten) Größengruppen (Anzahl der Eckpunkte) $k$ in einem zufälligen Erdos-Renyi-Diagramm (ein Diagramm über $n$ Eckpunkte mit Kantenwahrscheinlichkeit $p$). <- All das steht in der Antwort auf die zitierte Frage.

Also hier ist, was ich getan habe, um das zu zeigen $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}=\Omega((k/\ln k)^2)$.

Hinweis: $p^6$ kommt von einem analogen Argument wie in der zitierten Frage, $6$ ist die Anzahl der Kanten im gesamten Diagramm $4$Eckpunkte. Und ich nehme auch an zu schreiben$\ge\Omega (...)$ ist überflüssig, Gleichheit ist OK.

Zuerst beschränke ich mich $n$ von der Form sein $\frac{k^2}{(\ln k)^2}$ und ich setze $p:=1/n$. Wir bekommen$${n\choose 4}{p^6}\le n^4p^6=n^{-2}\ll n$$ Für die zweite Amtszeit haben wir $${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}$$

Dies geteilt durch $n$ ist $\frac{n^{k-1}}{k!}(\frac{1}{\sqrt k})^{\ln k}$was wir auf Null gehen wollen. Dies würde bedeuten, dass es so ist$o(n)$.

Dieser Wert ist gleich $e^{2(k-1)\ln k-2(k-1)\ln\ln k -\ln k!-\frac{1}{2}\ln k\ln k}$ wohin der Exponent geht $-\infty$, was den Beweis schließt.

Aber ich fürchte, ich habe nur gezeigt $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}= n-o(n)$ Das ist nicht dasselbe wie es zu zeigen $\Omega(n)$.

Obwohl ich das glaube $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}=\Theta (n)$ Das ist eine Unterklasse von $\Omega(n)$.

Answer 1

Wenn die asymptotischen Behauptungen, die Sie gemacht haben, wirklich wahr wären, wäre Ihr Beweis in Ordnung. Speziell:

• Ja, $n - o(n)$ ist $\Omega(n)$. Sogar das zu zeigen$\binom nk (1-p)^{\binom k2} < 0.99n$ für groß genug $n$ wäre in Ordnung und zu zeigen, dass es ist $o(n)$ ist stärker als das.
• Ja, vorausgesetzt $n = (\frac{k}{\log k})^2$ohne Konstante ist in Ordnung - wenn es funktioniert. Legen wir fest$n = c (\frac{k}{\log k})^2$ für Flexibilität später, damit wir eine wählen können $c$das wird unsere Argumentation funktionieren lassen. Wenn$c=1$ zufällig in Ordnung, das ist okay.

Ihre asymptotischen Behauptungen sind jedoch falsch. Speziell,$\frac{n^{k-1}}{k!}(\frac{1}{\sqrt k})^{\log k} \to \infty$ wie $k \to \infty$. Das ist, weil

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

Also hast du $2 k \log k$ Beginnen Sie mit dem Exponenten und heben Sie ihn grob auf $k \log k$ davon.

Ihr Hauptfehler ist das Einstellen $p = \frac1n$. Das ist viel zu klein. Sie müssen einstellen$p$ um gerade klein genug zu sein, dass man sich keine Sorgen machen muss $\binom n4 p^6$Begriff; speziell,$p = \frac1{\sqrt n}$ist gut genug. Der größere$p$ ist, desto einfacher wird es sein, mit der letzten Amtszeit umzugehen, also wollen wir nicht machen $p$ kleiner.

Allerdings auch dann Einstellung $n = (\frac{k}{\log k})^2$wird nicht funktionieren - die Konstante zählt hier! Das kann ich dir sagen$n = \frac14 (\frac{k}{\log k})^2$ und $p = \frac1{\sqrt n}$wird funktionieren; Sie sollten die asymptotische Analyse dieses Falls selbst durchführen. Sie können bessere Ergebnisse erzielen, indem Sie mit den Konstanten herumspielen$n$ und $p$.