çapraz Ramsey sayısı (4, k) alt sınır olasılık yöntemi asimptotik muhakeme

Dec 23 2020

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

2 MishaLavrov Dec 28 2020 at 18:10

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$.