Probabilistic method: Difference between revisions

Revision as of 09:36, 26 September 2018

Revision as of 15:02, 16 October 2018

Line 40:

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

Consider what happens if this value is less than {{math|1}}. Since Thethe expected number of monochromatic {{mvar|r}}-subgraphs inis ourstrictly randomless coloringthan will1, alwaysit must be anthat integer,a sospecific each singlerandom coloring mustsatisfies that the number of monochromatic {{mvar|r}}-subgraphs is havestrictly less than the1. expected value.The Butnumber theof onlymonochromatic {{mvar|r}}-subgraphs in this random coloring is a non-negative integer, whichhence 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|1n}}=5 isand {{mathmvar|0r}}=4) there must exist a coloring in which there are no monochromatic {{mvar|r}}-subgraphs. Thus if<ref>The same fact can be proved without probability, using a simple counting argument:

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

(which holds, for example, for {{mvar|n}}=5 and {{mvar|r}}=4) then each coloring is not monochromatic.<ref>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.