0
$\begingroup$

Currently, I'm reading The Probabilistic Method by Noga Alon. I'm just at the beginning of it, but I have problems with understanding the different probabilities for certain events that the author gives in various proofs. For example, look at the following theorem:

If ${n \choose k}2^{1-{k \choose 2}} < 1$, then $R(k, k) > n$. Thus $R(k, k) > \lfloor 2^{k/2} \rfloor$.

$R(k,k)$ denotes the Ramsey number of course.

The proof starts the following way:

Consider a random two-coloring of the edges of $K_n$ obtained by coloring each edge independently either red or blue, where each color is equally likely. For any fixed set $R$ of $k$ vertices, let $A_R$ be the event that the induced subgraph of $K_n$ on $R$ is monochromatic. Clearly, $Pr(A_R) = 2^{1-{k \choose 2}}$.

I am missing why the last argument is true, even though the author states that it is "clear". Of course I can find examples such that the statement is true, but I lack the intuition about how the author finds such a probability so easily. How does one deduce this?

$\endgroup$

1 Answer 1

1
$\begingroup$

The induced subgraph of $K_n$ on $R$ is a clique of size $k$, which means it contains $\displaystyle \binom{k}{2}$ edges. Now consider one of those edges: its color will be either blue or red, and without loss of generality we can assume it's blue. The induces subgraph on $R$ is monochromatic if and only if every other edge is blue as well. For one edge, the probability that it be blue is $\dfrac{1}{2}$ and, since the total number of other edges is $\displaystyle \binom{k}{2} - 1$, the probability that each one of those is blue is $\displaystyle \left(\frac{1}{2}\right)^{\binom{k}{2} - 1}$, or $\displaystyle 2^{1 - \binom{k}{2}}$.

$\endgroup$

You must log in to answer this question.

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