0
$\begingroup$

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!

$\endgroup$
0

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .