Quick description
Given real numbers with average , there must be some such that , and there must also be some such that . This extremely simple principle is also very useful indeed. In particular, it sometimes leads to proofs in situations where it is very hard to give an explicit example of an that works.
Prerequisites
Basic definitions of graph theory.
Example 1
Let be a graph with vertices and edges. Is it possible to partition the vertices into two sets and in such a way that the number of edges from to is at least ?
Here are two proofs that show that the answer is yes. For the first, we enumerate the vertices as , and then assign each vertex in turn to either or . We do the assignment as follows. If we have already assigned , let be the set of vertices we have assigned to , and let be the set of vertices we have assigned to . Now assign to if it is joined to more vertices in than in , and assign to otherwise. This ensures that at least half the new edges (that is, edges from to the already assigned vertices) are between and . Therefore, when the process is complete, we have at least edges between and .
That was not an averaging argument. Here is how to do it with an averaging argument. Let us randomly decide, for each vertex, whether to put it into or . Given any edge , the probability that it goes between and is the probability that we made different decisions for and , which is . Therefore, the expected number of edges between and is . But then, by the basic principle above, there must be a way of assigning vertices to and such that the number of edges between the two is at least .
The advantage of the first argument above is that it is algorithmic: it actually tells you how to partition the vertices. The advantage of the second is that it is so short and conceptual that it makes it obvious that the result is true. And in fact, though that is another story, the second argument can easily be "derandomized".
General discussion
The method we have just applied can be described as follows. You would like to build a structure with a certain property, and that property can be expressed as the requirement that a certain real parameter must take at least (or at most) a certain value. In order to achieve this, you define a random structure (according to a probability distribution of your choice) and prove that the expected value of the parameter is at least (or at most) the given value. It follows that there must exist a structure with the property you want.
Example 2
The following is a famous argument of Paul Erdős. Suppose you take the complete graph with vertices and you colour its edges randomly in the simplest possible way: for each edge you toss a coin and you colour it red if the coin comes up heads and blue if it comes up tails. Given vertices in the graph, we say that they form a monochromatic clique if all the edges with have the same colour.
The probability that any given collection of vertices forms a monochromatic clique is , since the probability that they form a red clique is (as there are edges that all independently require the coin to come up heads), and the probability that they form a blue clique is also . Therefore, by linearity of expectation, the expected number of monochromatic cliques is
So far we have not used the simple principle, but now we do. If the average number of monochromatic cliques is then there must exist a red/blue colouring of the complete graph with vertices that contains at most s monochromatic cliques of size . In particular, if the parameters and are chosen in such a way that then there must exist a red/blue colouring with no monochromatic cliques.
A small calculation shows that there is therefore a red/blue colouring of the complete graph on vertices with no monochromatic clique of size . Indeed, the requirement can be rearranged to If we use the inequality and take logs to base 2, then we see that it is sufficient if which is certainly the case if
The remarkable thing about this argument is that, although it is extremely simple, nobody knows how to define a red/blue colouring with this property.
See also "If a parameter is generating undesirable boundary terms, try averaging over many choices of that parameter".
Comments
Post new comment
(Note: commenting is not possible on this snapshot.)