off diagonalna liczba Ramseya (4, k) dolna granica probabilistyczna metoda wnioskowania asymptotycznego

Question

Chcę to pokazać $R(4,k)\ge\Omega((k/\ln k)^2)$, gdzie $R(4,k)$ to numer Ramseya.

To pytanie jest dość bliskie temu, czego szukam, brakuje tylko części asymptotycznej (o czym mówią$3$ zamiast $4$).

Podobnie jak to definiujemy $Y$ i $Z$ jako liczba $4-$kliki i liczba pustych (bez krawędzi) zestawów rozmiaru (liczba wierzchołków) $k$ na losowym wykresie Erdos-Renyi (wykres powyżej $n$ wierzchołki z prawdopodobieństwem krawędzi $p$). <- Wszystko to jest zapisane w odpowiedzi na zacytowane pytanie.

Oto, co zrobiłem, aby to pokazać $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}=\Omega((k/\ln k)^2)$.

Uwaga: $p^6$ pochodzi z analogicznego argumentu jak w zacytowanym pytaniu, $6$ jest liczbą krawędzi na całym wykresie $4$wierzchołki. Przypuszczam też, że piszę$\ge\Omega (...)$ jest zbędne, równość jest OK.

Najpierw ograniczam $n$ być w formie $\frac{k^2}{(\ln k)^2}$ i ustawiłem $p:=1/n$. Dostajemy$${n\choose 4}{p^6}\le n^4p^6=n^{-2}\ll n$$ Na drugą kadencję mamy $${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}$$

To podzielone przez $n$ jest $\frac{n^{k-1}}{k!}(\frac{1}{\sqrt k})^{\ln k}$które chcemy zejść do zera. Sugerowałoby to, że tak$o(n)$.

Ta wartość jest równa $e^{2(k-1)\ln k-2(k-1)\ln\ln k -\ln k!-\frac{1}{2}\ln k\ln k}$ gdzie wykładnik idzie do $-\infty$, co zawiera dowód.

Ale obawiam się, że tylko pokazałem $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}= n-o(n)$ co nie jest tym samym, co pokazanie, że jest $\Omega(n)$.

Chociaż (myślę, że) to zrobiłem $n-{n\choose 4}p^6-{n\choose k}(1-p)^{k\choose 2}=\Theta (n)$ który jest podklasą klasy $\Omega(n)$.

Answer 1

Jeśli asymptotyczne twierdzenia, które wypowiedziałeś, były prawdziwe, twój dowód byłby w porządku. W szczególności:

• Tak, $n - o(n)$ jest $\Omega(n)$. Nawet to pokazując$\binom nk (1-p)^{\binom k2} < 0.99n$ wystarczająco duże $n$ byłoby dobrze i pokazanie, że tak jest $o(n)$ jest silniejszy niż to.
• Tak, zakładając $n = (\frac{k}{\log k})^2$bez stałej jest w porządku - jeśli działa. Ustawiamy$n = c (\frac{k}{\log k})^2$ dla późniejszej elastyczności, abyśmy mogli wybrać plik $c$to sprawi, że nasza argumentacja zadziała. Jeśli$c=1$ tak się składa, że ​​jest w porządku, w porządku.

Jednak twoje asymptotyczne twierdzenia są fałszywe. W szczególności,$\frac{n^{k-1}}{k!}(\frac{1}{\sqrt k})^{\log k} \to \infty$ tak jak $k \to \infty$. To jest ponieważ

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

Więc masz $2 k \log k$ zacząć od wykładnika i z grubsza znosić $k \log k$ tego.

Twoim głównym błędem jest ustawienie $p = \frac1n$. To jest o wiele za małe. Musisz ustawić$p$ być na tyle mały, że nie musisz się martwić o plik $\binom n4 p^6$semestr; w szczególności,$p = \frac1{\sqrt n}$jest wystarczająco dobry. Większy$p$ jest to, że im łatwiej będzie uporać się z ostatnim semestrem, więc nie chcemy tego robić $p$ każdy mniejszy.

Jednak nawet wtedy ustawienie $n = (\frac{k}{\log k})^2$wola nie praca - stała się liczy tutaj! Mogę ci to powiedzieć$n = \frac14 (\frac{k}{\log k})^2$ i $p = \frac1{\sqrt n}$będzie działać; powinieneś samodzielnie przeprowadzić asymptotyczną analizę tego przypadku. Możesz uzyskać lepsze wyniki, bawiąc się stałymi$n$ i $p$.