1.Previous
3.Next

colored the same color).

To do so, we color the graph randomly. Color each edge independently with probability of being red and of being blue. We calculate the expected number of monochromatic subgraphs on vertices as follows:

For any set of vertices from our graph, define the variable to be if every edge amongst the vertices is the same color, and otherwise. Note that the number of monochromatic -subgraphs is the sum of over all possible subsets . For any individual set , the expected value

1.Previous
3.Next