Editing Probabilistic method (section)

===First example===
Suppose we have a [[complete graph]] on {{mvar|n}} [[vertex (graph theory)|vertices]]. We wish to show (for small enough values of {{mvar|n}}) that it is possible to color the [[edge (graph theory)|edges]] of the [[graph (discrete mathematics)|graph]] in two colors (say red and blue) so that there is no complete [[subgraph (graph theory)|subgraph]] on {{mvar|r}} vertices which is monochromatic (every edge colored the same color).

To do so, we color the graph randomly. Color each edge independently with probability {{math|1/2}} of being red and {{math|1/2}} of being blue. We calculate the expected number of monochromatic subgraphs on {{mvar|r}} vertices as follows:

For any set <math>S_r</math> of <math>r</math> vertices from our graph, define the variable <math>X(S_r)</math> to be {{math|1}} if every edge amongst the <math>r</math> vertices is the same color, and {{math|0}} otherwise. Note that the number of monochromatic <math>r</math>-subgraphs is the sum of <math>X(S_r)</math> over all possible [[subset]]s <math>S_r</math>. For any individual set <math>S_r^i</math>, the [[expected value]] of <math>X(S_r^i)</math> is simply the probability that all of the <math>C(r, 2)</math> edges in <math>S_r^i</math> are the same color:

:<math>E[X(S_r^i)] = 2 \cdot 2^{-{r \choose 2}}</math>

(the factor of {{math|2}} comes because there are two possible colors).

This holds true for any of the <math>C(n, r)</math> possible subsets we could have chosen, i.e. <math>i</math> ranges from {{math|1}} to <math>C(n,r)</math>. So we have that the sum of <math>E[X(S_r^i)]</math> over all <math>S_r^i</math> is

:<math>\sum_{i=1}^{C(n,r)} E[X(S_r^i)] = {n \choose r}2^{1-{r \choose 2}}.</math>

The sum of expectations is the expectation of the sum (''regardless'' of whether the variables are [[statistical independence|independent]]), so the expectation of the sum (the expected number of all monochromatic <math>r</math>-subgraphs) is

:<math>E[X(S_r)] = {n \choose r}2^{1-{r \choose 2}}.</math>

Consider what happens if this value is less than {{math|1}}. Since the expected number of monochromatic {{mvar|r}}-subgraphs is strictly less than {{math|1}}, there exists a coloring satisfying the condition that the number of monochromatic {{mvar|r}}-subgraphs is strictly less than {{math|1}}. The number of monochromatic {{mvar|r}}-subgraphs in this random coloring is a non-negative [[integer]], hence it must be {{math|0}} ({{math|0}} is the only non-negative integer less than {{math|1}}). It follows that if

:<math>E[X(S_r)] = {n \choose r}2^{1-{r \choose 2}} < 1</math>

(which holds, for example, for {{math|''n'' {{=}} 5}} and {{math|''r'' {{=}} 4}}), there must exist a coloring in which there are no monochromatic {{mvar|r}}-subgraphs.{{efn|
The same fact can be proved without probability, using a simple counting argument:
* The total number of ''r''-subgraphs is <math>{n \choose r}</math>.
* Each ''r''-subgraphs has <math>{r \choose 2}</math> edges and thus can be colored in <math>2^{r \choose 2}</math> different ways.
* Of these colorings, only 2 colorings are 'bad' for that subgraph (the colorings in which all vertices are red or all vertices are blue).
* Hence, the total number of colorings that are bad for some (at least one) subgraph is at most <math>2 {n \choose r} 2^{{n \choose 2} - {r \choose 2}}</math>.
* Hence, if <math>2 {n \choose r} 2^{{n \choose 2} - {r \choose 2}} < 2^{n \choose 2} \Leftrightarrow {n \choose r}2^{1-{r \choose 2}} < 1</math>, there must be at least one coloring which is not 'bad' for any subgraph.
}}

By definition of the [[Ramsey number]], this implies that {{math|''R''(''r'', ''r'')}} must be bigger than {{mvar|n}}. In particular, {{math|''R''(''r'', ''r'')}} must grow at least [[exponential growth|exponentially]] with {{mvar|r}}.

A weakness of this argument is that it is entirely [[nonconstructive proof|nonconstructive]]. Even though it proves (for example) that almost every coloring of the complete graph on {{math|(1.1)<sup>''r''</sup>}} vertices contains no monochromatic {{mvar|r}}-subgraph, it gives no explicit example of such a coloring. The problem of finding such a coloring has been [[open problem|open]] for more than 50 years.