Probabilistic method: Difference between revisions

Revision as of 16:38, 18 May 2018

Revision as of 09:36, 26 September 2018

Line 40:

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

Consider what happens if this value is less than {{math|1}}. The number of monochromatic {{mvar|r}}-subgraphs in our random coloring will always be an integer, so ateach least onesingle coloring must have less than the expected value. But the only integer thatwhich satisfiesis thisless than criterion{{math|1}} is {{math|0}}. Thus if

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

(which holds, for example, for {{mvar|n}}=5 and {{mvar|r}}=4) then someeach coloring fitsis ournot desired criterionmonochromatic.<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.