off diagonal nomor Ramsey (4, k) metode probabilistik batas bawah penalaran asimtotik

Question

Saya ingin menunjukkan itu $R(4,k)\ge\Omega((k/\ln k)^2)$, dimana $R(4,k)$ adalah nomor Ramsey.

Pertanyaan ini cukup dekat dengan apa yang saya cari, bagian asimtotik hanya hilang (dan mereka bicarakan$3$ dari pada $4$).

Mirip dengan pertanyaan yang kami definisikan $Y$ dan $Z$ sebagai jumlah $4-$klik dan jumlah set ukuran kosong (tanpa tepi) (jumlah simpul) $k$ dalam grafik Erdos-Renyi acak (grafik di atas $n$ simpul dengan probabilitas tepi $p$). <- Semua itu tertulis dalam jawaban pertanyaan yang dikutip.

Jadi inilah yang saya lakukan untuk menunjukkannya $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}=\Omega((k/\ln k)^2)$.

catatan: $p^6$ berasal dari argumen analog seperti dalam pertanyaan yang dikutip, $6$ adalah jumlah tepi pada grafik lengkap di $4$sudut. Dan saya juga mengira menulis$\ge\Omega (...)$ mubazir, kesetaraan tidak apa-apa.

Pertama saya batasi $n$ menjadi bentuk $\frac{k^2}{(\ln k)^2}$ dan saya set $p:=1/n$. Kita mendapatkan$${n\choose 4}{p^6}\le n^4p^6=n^{-2}\ll n$$ Untuk istilah kedua yang kami miliki $${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}$$

Ini dibagi dengan $n$ aku s $\frac{n^{k-1}}{k!}(\frac{1}{\sqrt k})^{\ln k}$yang kami ingin pergi ke nol. Ini menyiratkan bahwa memang demikian$o(n)$.

Nilai ini sama dengan $e^{2(k-1)\ln k-2(k-1)\ln\ln k -\ln k!-\frac{1}{2}\ln k\ln k}$ ke mana eksponen pergi $-\infty$, yang mencakup buktinya.

Tapi saya khawatir saya hanya menunjukkan $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}= n-o(n)$ yang tidak sama dengan menunjukkannya $\Omega(n)$.

Meskipun saya (pikir saya) melakukan itu $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}=\Theta (n)$ yang merupakan subclass dari $\Omega(n)$.

Answer 1

Jika klaim asimtotik yang Anda buat benar-benar benar, maka bukti Anda akan baik-baik saja. Secara khusus:

• Iya, $n - o(n)$ aku s $\Omega(n)$. Bahkan menunjukkan itu$\binom nk (1-p)^{\binom k2} < 0.99n$ cukup besar $n$ akan baik-baik saja, dan menunjukkan bahwa itu $o(n)$ lebih kuat dari itu.
• Ya, dengan asumsi $n = (\frac{k}{\log k})^2$tanpa konstanta baik-baik saja - jika berhasil. Kami mengatur$n = c (\frac{k}{\log k})^2$ untuk fleksibilitas nantinya, sehingga kita bisa memilih a $c$yang akan membuat argumen kita berhasil. Jika$c=1$ kebetulan baik-baik saja, tidak apa-apa.

Namun, klaim asimtotik Anda salah. Secara khusus,$\frac{n^{k-1}}{k!}(\frac{1}{\sqrt k})^{\log k} \to \infty$ sebagai $k \to \infty$. Itu karena

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

Jadi kamu punya $2 k \log k$ untuk memulai dengan eksponen, dan menghapus secara kasar $k \log k$ dari itu.

Kesalahan utama Anda adalah pengaturan $p = \frac1n$. Ini terlalu kecil. Anda perlu mengatur$p$ menjadi cukup kecil sehingga Anda tidak perlu khawatir tentang $\binom n4 p^6$istilah; secara khusus,$p = \frac1{\sqrt n}$cukup baik. Yang lebih besar$p$ adalah, semakin mudah menangani istilah terakhir, jadi kami tidak ingin membuatnya $p$ lebih kecil.

Namun, meski begitu, setting $n = (\frac{k}{\log k})^2$tidak akan berhasil - masalah konstan di sini! Aku bisa memberitahumu itu$n = \frac14 (\frac{k}{\log k})^2$ dan $p = \frac1{\sqrt n}$akan bekerja; Anda harus melakukan analisis asimtotik untuk kasus itu sendiri. Anda bisa mendapatkan hasil yang lebih baik dengan bermain-main dengan konstanta$n$ dan $p$.