オフ対角ラムゼー数（4、k）下限確率的手法漸近推論
それを見せたい $R(4,k)\ge\Omega((k/\ln k)^2)$、 どこ $R(4,k)$ ラムゼーの数です。
この質問は私が求めているものに非常に近く、漸近的な部分が欠けているだけです（そして彼らは話します$3$ の代わりに $4$）。
私たちが定義するその質問と同様に $Y$ そして $Z$ の数として $4-$クリークとサイズの空の（エッジのない）セットの数（頂点の数） $k$ ランダムなErdos-Renyiグラフ（上のグラフ $n$ エッジ確率のある頂点 $p$）。<-そのすべてが引用された質問への回答に書かれています。
これが私がそれを示すためにしたことです $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}=\Omega((k/\ln k)^2)$。
注意： $p^6$ 引用された質問のように類似した議論から来ています、 $6$ 上の完全グラフのエッジの数です $4$頂点。そして私も書くと思います$\ge\Omega (...)$ 冗長で、平等はOKです。
まず制限します $n$ 形になる $\frac{k^2}{(\ln k)^2}$ そして私は設定しました $p:=1/n$。我々が得る$${n\choose 4}{p^6}\le n^4p^6=n^{-2}\ll n$$ 第2期は $${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}$$
これをで割ったもの $n$ です $\frac{n^{k-1}}{k!}(\frac{1}{\sqrt k})^{\ln k}$これをゼロにします。これはそれが$o(n)$。
この値はに等しい $e^{2(k-1)\ln k-2(k-1)\ln\ln k -\ln k!-\frac{1}{2}\ln k\ln k}$ 指数がどこに行くか $-\infty$、これで証明が終わります。
しかし、私は私が示しただけだと思います $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}= n-o(n)$ それを示すことと同じではありません $\Omega(n)$。
私は（私が思うに）それをしましたが $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}=\Theta (n)$ これはのサブクラスです $\Omega(n)$。
回答
あなたが行った漸近的な主張が本当に真実であるならば、あなたの証明は大丈夫でしょう。特に：
- はい、 $n - o(n)$ です $\Omega(n)$。それを示しても$\binom nk (1-p)^{\binom k2} < 0.99n$ 十分な大きさのために $n$ 大丈夫だろう、そしてそれが $o(n)$ それよりも強いです。
- はい、仮定します $n = (\frac{k}{\log k})^2$定数がなくても問題ありません-それが機能する場合。設定しました$n = c (\frac{k}{\log k})^2$ 後で柔軟性を持たせるために、 $c$それは私たちの議論を機能させるでしょう。場合$c=1$ たまたま大丈夫です、それは大丈夫です。
ただし、漸近的な主張は誤りです。特に、$\frac{n^{k-1}}{k!}(\frac{1}{\sqrt k})^{\log k} \to \infty$ なので $k \to \infty$。それは
- $\log (n^{k-1}) \sim 2 k \log k$ なので $k \to \infty$;
- $\log(k!) \sim k \log k$ なので $k \to \infty$;
- $\log\left(\sqrt{k}^{\log k}\right) \sim \frac12(\log k)^2 \ll k \log k$ なので $k \to \infty$。
だからあなたは持っています $2 k \log k$ 指数で開始し、大まかにキャンセルします $k \log k$ それの。
あなたの主な間違いは設定です $p = \frac1n$。これは小さすぎます。設定する必要があります$p$ あなたが心配する必要がないようにちょうど十分に小さいこと $\binom n4 p^6$期間; 特に、$p = \frac1{\sqrt n}$十分です。大きい$p$ つまり、前学期の扱いが簡単になるので、作りたくない $p$ 小さいもの。
ただし、それでも設定 $n = (\frac{k}{\log k})^2$意志ない仕事-定数は、ここで問題！私はあなたにそれを言うことができます$n = \frac14 (\frac{k}{\log k})^2$ そして $p = \frac1{\sqrt n}$働くでしょう; その場合の漸近解析を自分で行う必要があります。定数を試してみると、より良い結果を得ることができます$n$ そして $p$。