Ramsey Numbers and the Probabilistic Method

Question

I am trying to prove that if there exists a real number $0 < p <1$ such that $$\binom{n}{k}p^k + \binom{n}{q}(1-p)^q < 1$$ for some $k, q \in [n],$ Then $R(k,q) > n.$ I see by the construction of this problem that they are suggesting some form of probabilistic method, i.e. on a random edge 2-coloring of the graph $K_n,$ where the probability of an edge getting the color $1$ is $p$ (and thus the probability of an edge getting the color $2$ is $1-p$), $P(\text{Getting a monochromatic } K_k \vee \text{Getting a monochromatic } K_q) < 1.$ The tough part is finding this particular probability. I can see by the definition of a union of events that $$P(\text{Getting a monochromatic } K_k \vee \text{Getting a monochromatic } K_q)$$ $$\leq P(\text{Getting a monochromatic } K_k) + P(\text{Getting a monochromatic } K_q),$$ But I am having issues with both of the counting proofs for this particular part of the problem. Any suggestions?

Answer 1

I think your statement is false, for example it would imply $R(k,2)>k$. I could only show that $R(k,q)>n$ when given that for some $p\in(0,1)$ we have the weaker inequality $${n\choose k}p^{k(k-1)/2}+{n\choose q}(1-p)^{q(q-1)/2}<1.$$ In $K_n$, colour every edge independently, with probability $p$ colour it blue and red otherwise. For every $K_k\subset K_n$, there is a probability of $p^{k(k-1)/2}$ that $K_k$ is completely blue. Hence the expected number of blue $K_k$'s is ${n\choose k}p^{k(k-1)/2}$. Similarly, the expected number of red $K_q$'s is ${n\choose q}(1-p)^{q(q-1)/2}$.

Because ${n\choose k}p^{k(k-1)/2}+{n\choose q}(1-p)^{q(q-1)/2}<1$, there is a particular colouring of $K_n$ with no blue $K_k$ or red $K_q$, thus $R(k,q)> n$.