Probabilistic method: Difference between revisions

Content deleted Content added
Line 38:
:<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}}, itthere must be thatexists a specific random coloring satisfiessatisfying 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>