오프 대각선 램지 수 (4, k) 하한 확률 적 방법 점근 적 추론
나는 그것을 보여주고 싶다 $R(4,k)\ge\Omega((k/\ln k)^2)$, 어디 $R(4,k)$ Ramsey 번호입니다.
이 질문 은 제가 추구하는 것에 매우 가깝습니다. 점근 부분 만 누락되었습니다.$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 (...)$ 중복, 평등은 괜찮습니다.
먼저 제한 $n$ 형태로 $\frac{k^2}{(\ln k)^2}$ 그리고 나는 설정 $p:=1/n$. 우리는$${n\choose 4}{p^6}\le n^4p^6=n^{-2}\ll n$$ 두 번째 학기에는 $${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}$0으로 가고 싶습니다. 이것은 의미합니다$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$.