How to show the following:

Let $R(k,t)$ denote the Ramsey function, that is the minimal number $n$ so that if the edges of a complete graph $K_n$ on $n$ vertices are each colored red or blue, then either there is a red $K_k$ or a blue $K_t$. Show that if

${n \choose k} p ^{k \choose 2} + {n \choose t}(1-p)^{t \choose 2} < 1$

for some $p \in [0,1]$, then $R(k,t) > n$

I tried using the hint by coloring the edges of $K_n$ with probability $p$ and blue with probability $1-p$ but didnt see anything.

Thanks a lot!


If you colour the edges of $K_n$ red with probability $p$ and blue with probability $1-p$, then the expected number of red subgraphs $K_k$ is given by the first term in your inequality and the expected number of blue subgraphs $K_t$ is given by the second term. Thus the sum is the expected number of the subgraphs whose existence you're trying to enforce. If this is less than $1$, there must be at least one configuration in which the number of admissible subgraphs is $0$; thus $R(k,t)\gt n$.

You can read more about this probabilistic method e.g. at Wikipedia.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.