çapraz Ramsey sayısı (4, k) alt sınır olasılık yöntemi asimptotik muhakeme
Bunu göstermek istiyorum $R(4,k)\ge\Omega((k/\ln k)^2)$, nerede $R(4,k)$ Ramsey numarasıdır.
Bu soru peşinde olduğum şeye oldukça yakın, asimptotik kısım sadece eksik (ve$3$ onun yerine $4$).
Tanımladığımız soruya benzer $Y$ ve $Z$ sayısı olarak $4-$klikler ve boş (kenarsız) boyut kümelerinin sayısı (köşe sayısı) $k$ rastgele bir Erdos-Renyi grafiğinde (bir grafik üzerinde $n$ kenar olasılığı olan köşeler $p$<- Bunların tümü, alıntılanan sorunun cevabında yazılır.
İşte bunu göstermek için yaptığım şey $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}=\Omega((k/\ln k)^2)$.
Not: $p^6$ alıntı sorudaki gibi benzer bir argümandan gelir, $6$ tam grafikteki kenarların sayısıdır $4$köşeler. Ve yazmayı da düşünüyorum$\ge\Omega (...)$ gereksiz, eşitlik sorun değil.
İlk önce kısıtlıyorum $n$ formda olmak $\frac{k^2}{(\ln k)^2}$ ve ben ayarladım $p:=1/n$. Biz alırız$${n\choose 4}{p^6}\le n^4p^6=n^{-2}\ll n$$ İkinci dönem için elimizde $${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}$$
Bu bölünür $n$ dır-dir $\frac{n^{k-1}}{k!}(\frac{1}{\sqrt k})^{\ln k}$sıfıra gitmek istediğimiz. Bu şu anlama gelir$o(n)$.
Bu değer eşittir $e^{2(k-1)\ln k-2(k-1)\ln\ln k -\ln k!-\frac{1}{2}\ln k\ln k}$ üs nereye gider $-\infty$ispatı sonuçlandıran.
Ama korkarım sadece gösterdim $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}= n-o(n)$ ki bunu göstermekle aynı şey değil $\Omega(n)$.
Ben (sanırım) bunu yaptım $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}=\Theta (n)$ alt sınıfı olan $\Omega(n)$.
Yanıtlar
Yaptığınız asimptotik iddialar gerçekten doğruysa, kanıtınız yeterli olacaktır. Özellikle:
- Evet, $n - o(n)$ dır-dir $\Omega(n)$. Bunu bile gösteriyor$\binom nk (1-p)^{\binom k2} < 0.99n$ yeterince büyük için $n$ iyi olurdu ve bunu göstermek $o(n)$ ondan daha güçlü.
- Evet, varsayarsak $n = (\frac{k}{\log k})^2$sabit olmadan iyidir - eğer işe yararsa. Ayarladık$n = c (\frac{k}{\log k})^2$ daha sonra esneklik için, böylece bir $c$bu bizim argümanımızı çalıştıracak. Eğer$c=1$ iyi olur, sorun değil.
Ancak asimptotik iddialarınız yanlıştır. Özellikle,$\frac{n^{k-1}}{k!}(\frac{1}{\sqrt k})^{\log k} \to \infty$ gibi $k \to \infty$. O yüzden
- $\log (n^{k-1}) \sim 2 k \log k$ gibi $k \to \infty$;
- $\log(k!) \sim k \log k$ gibi $k \to \infty$;
- $\log\left(\sqrt{k}^{\log k}\right) \sim \frac12(\log k)^2 \ll k \log k$ gibi $k \to \infty$.
Yani sahipsin $2 k \log k$ üs ile başlamak ve kabaca iptal etmek $k \log k$ onun.
Birincil hatanız ayarlamak $p = \frac1n$. Bu çok küçük. Ayarlaman gerekiyor$p$ yeterince küçük olmak için endişelenmenize gerek yok $\binom n4 p^6$terim; özellikle,$p = \frac1{\sqrt n}$yeterince iyi. Daha büyük$p$ son terimle uğraşmak o kadar kolay olacağı için, $p$ daha küçük.
Ancak, o zaman bile, ayar $n = (\frac{k}{\log k})^2$will not iş - sabiti burada önemli! Sana bunu söyleyebilirim$n = \frac14 (\frac{k}{\log k})^2$ ve $p = \frac1{\sqrt n}$çalışacak; bu vakanın asimptotik analizini kendiniz yapmalısınız. Sabitlerle oynayarak daha iyi sonuçlar elde edebilirsiniz.$n$ ve $p$.