Content deleted Content added
→First example: left sides of formulas, some cleanup Tag: references removed |
→First example: added notelist, left side in last inequality |
||
Line 37:
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 {{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 {{mvar|n}}=5 and {{mvar|r}}=4), there must exist a coloring in which there are no monochromatic {{mvar|r}}-subgraphs. {{efn|
Line 51:
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)<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 for more than 50 years.
----
{{notelist}}
===Second example===
| |||