Probabilistic method: Difference between revisions

Revision as of 16:42, 3 May 2020

Revision as of 20:38, 10 July 2020

Line 21:

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 {{mvar|S}}<math>S_r</math> of {{mvar|<math>r}}</math> vertices from our graph, define the variable {{<math|''>X''(''S''S_r)}}</math> to be {{math|1}} if every edge amongst the {{mvar|<math>r}}</math> vertices is the same color, and {{math|0}} otherwise. Note that the number of monochromatic {{mvar|<math>r}}</math>-subgraphs is the sum of {{<math|''>X''(''S''S_r)}}</math> over all possible subsets <math>S_r</math>. For any {{mvar|S}}individual set <math>S_r^i</math>, the [[expected value]] of {{<math|''>X''(''S''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).

edges in {{mvar|S}} are the same color,

This holds true for any of the {{<math|''>C''(''n'', ''r'')}}</math> possible subsets we could have chosen, soi.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''S_r^i)]}}</math> over all {{mvar|S}}<math>S_r^i</math> is

:<math>2 \cdot 2^{-{r \choose 2}}</math>

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

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

The sum of an expectationexpectations 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 {{mvar|<math>r}}</math>-subgraphs) is

This holds true for any of the {{math|''C''(''n'', ''r'')}} possible subsets we could have chosen, so we have that the sum of {{math|''E''[''X''(''S'')]}} over all {{mvar|S}} 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}}, it must be that a specific random coloring satisfies 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 1). It follows that if :<math>{n \choose r}2^{1-{r \choose 2}} < 1 ,</math>, (which holds, for example, for {{mvar|n1}}=5 and {{mvar|r}}=4) there must exist a coloring in which there are no monochromatic {{mvar|r}}-subgraphs. It follows <ref>Thethat same fact can be proved without probability, using a simple counting argument:if

The sum of an expectation 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 monochromatic {{mvar|r}}-subgraphs) is

:<math>{n \choose r}2^{1-{r \choose 2}}. < 1</math>

(which holds, for example, for {{mvar|n}}=5 and {{mvar|r}}=4), there must exist a coloring in which there are no monochromatic {{mvar|r}}-subgraphs. {{efn|

Consider what happens if this value is less than {{math|1}}. Since the expected number of monochromatic {{mvar|r}}-subgraphs is strictly less than 1, it must be that a specific random coloring satisfies that the number of monochromatic {{mvar|r}}-subgraphs is strictly less than 1. The number of monochromatic {{mvar|r}}-subgraphs in this random coloring is a non-negative integer, hence it must be 0 (0 is the only non-negative integer less than 1). It follows that if :<math>{n \choose r}2^{1-{r \choose 2}} < 1 ,</math>, (which holds, for example, for {{mvar|n}}=5 and {{mvar|r}}=4) there must exist a coloring in which there are no monochromatic {{mvar|r}}-subgraphs. <ref>The same fact can be proved without probability, using a simple counting argument:

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 ''all''some subgraphs(at least one) subgraph is at most <math>2 {n \choose r}</math>.

* Hence, if <math>2^{r \choose 2} > 2 {n \choose r}</math>, there must be at least one coloring which is not 'bad' for any subgraph.

}}

</ref>

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 [[exponential growth|grow at least exponentially]] with {{mvar|r}}.

A peculiarity 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)^''r''}} 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 for more than 50 years.

===Second example===