a repository of mathematical know-how

To increase the occurrence of a property in a set, try randomly refining that set in a way that favors the property

Quick description

Suppose one has some set A whose elements (or tuples of elements) obeys a desirable property P a small (but non-trivial) fraction of the time. One wants to then refine the set A (i.e. pass to a reasonably large subset A' of A) in such a way that a proportion of the elements (or tuples of elements) of A' that obey P is higher than that of A. One way to do this is by a probabilistic method: concoct a random way of refining the set A in such a way that elements (or tuples) obeying P are more likely to survive the process than elements that do not obey P. An application of the first moment method (or the pigeonhole principle) will then give at least one refinement A' with the required properties.

This method tends to be particularly useful in extremal graph theory and additive combinatorics.


Graph theory; probability theory

Example 1

(Baby Balog-Szemerédi-Gowers lemma) Let G = (V,E) be a graph with n vertices and at least \delta n^2 edges, where n is large and 0 < \delta < 1 is fixed. Then we expect many pairs of points in V to be connected by an edge, and even more pairs of points in V to be connected by a path of length two. But it is still quite possible to have many pairs which are not connected by such paths. For instance, if G is bipartite, then a vertex in the first partite class and the vertex in the second partite class will not be connected by any path of length two, even though the edge density \delta of a bipartite graph can be arbitrarily close to 1/2. Also, a pair of points might be connected by a path of length two, but the number of such paths might be unexpectedly small (much less than n).

However, one can refine the vertex set V to substantially increase the proportion of pairs of vertices which are connected by a path of length two, and furthermore to ensure that most pairs are in fact connected by many paths of length two. The key observation is that if a pair v, w are connected by a path passing through a third vertex u, then v, w both lie in the neighborhood V_u of u, defined as the set of all vertices in V connected to u by an edge. Conversely, if v, w are not connected by such a path, then v, w will not both lie in any such neighborhood V_u. More generally, if v, w are only connected by a few such paths, then it is unlikely that v,w will both lie in V_u for a randomly chosen u. So one way to ``favor'' pairs v,w that are connected by many paths of length two is to refine V to a randomly selected neighborhood V_u. As a first attempt to make this work, pick 0 < \epsilon < 1 and call a pair v, w good if there are more than \epsilon n paths of length two from v to w, and bad otherwise. Pick u uniformly at random from V. By construction, every bad pair (v,w) has a probability of at most \epsilon of lying in V_u; there are at most n^2 bad pairs overall, so by the linearity of expectation, the expected total number of bad pairs in V_u is at most \epsilon n^2.

Meanwhile, the total number of pairs in V_u (both good and bad) is |V_u|^2. As G has \delta n^2 edges, the expected value of |V_u| is at least \delta n (in fact we can improve this by a factor of two, since edges have two vertices, but we won't need this), so by Cauchy-Schwarz the expected value of |V_u|^2 is at least \delta^2 n^2. Thus, the quantity

 |V_u|^2 - \frac{\delta^2}{\epsilon} |\hbox{ bad pairs in } V_u \times V_u|

has non-negative expectation, which by the first moment method implies that one can find a u such that the proportion of bad pairs in V_u is O( \epsilon / \delta^2 ), i.e. 1 - O( \epsilon / \delta^2 ) of the pairs in V_u are connected by at least \epsilon n paths of length two.

In practice, this result is not so useful because we don't have a lower bound on the set V_u one is refining to. But this can be dealt with by a small tweak to the above argument: observe that the quantity

 |V_u|^2 - \frac{\delta^2}{2} n^2 - \frac{\delta^2}{2\epsilon} |\hbox{ bad pairs in } V_u \times V_u|

also has a non-negative expectation, which means that one can find a u with |V_u| \geq \delta n / \sqrt{2} such that 1-O(\epsilon/\delta^2) of the pairs in V_u are connected by at least \epsilon n paths of length two.

This argument can be elaborated further to establish the Balog-Szemerédi-Gowers lemma, which asserts under the same hypotheses that there exists a refinement V' of V of cardinality at least c \delta^C n for some absolute constants c, C > 0 such that every pair of vertices in V' is connected by at least c \delta^C n^2 paths of length three in V.

Example 2

(Improving the quality of a Freiman homomorphism) Let F_2 be the field of two elements. If A \subset F_2^n, a map  A \to F_2^m is said to be a Freiman homomorphism if one has the property that \phi(a_1)+\phi(a_2)=\phi(a_3)+\phi(a_4) whenever a_1,a_2,a_3,a_4 \in A with a_1+a_2=a_3+a_4.

Now suppose one has a map  A \to F_2^m on a reasonably large set A (say |A| \geq \delta |F_2^n| for some 0 < \delta < 1) which is only a Freiman homomorphism a fraction of the time, e.g. out of all the quadruples a_1,a_2,a_3,a_4 \in A with a_1+a_2=a_3+a_4, only a proportion \epsilon of these quadruples obey \phi(a_1)+\phi(a_2)=\phi(a_3)+\phi(a_4). One would like to refine the set A to improve the proportion of quadruples with this property.

Define an additive quadruple to be a quadruple a_1,a_2,a_3,a_4 \in A with a_1+a_2=a_3+a_4, and call the quadruple good if \phi(a_1)+\phi(a_2)=\phi(a_3)+\phi(a_4). A simple application of Cauchy-Schwarz shows that there are at least \delta^4 n^3 additive quadruples, and hence at least \epsilon \delta^4 n^3 good additive quadruples.

The key observation is this. Consider the graph  a \in A \} \subset F_2^n \times F_2^m of \phi, and take an affine subspace V of F_2^n \times F_2^m. If a_1,a_2,a_3,a_4 is a good additive quadruple with (a_1,\phi(a_1)), (a_2,\phi(a_2)), (a_3, \phi(a_3)) all lying in V, then the fourth point (a_4, \phi(a_4)) automatically lies in V also. In contrast, for a bad additive quadruple, there is no particular reason for (a_4,\phi(a_4)) to lie in V, particularly if the codimension of V is large.

To exploit this, we pick a codimension d (to be optimised later) and let V be a random affine subspace of F_2^n \times F_2^m of codimension d. Given an additive quadruple a_1,a_2,a_3,a_4 with all four elements distinct, we soon see that all the elements of this quadruple will lie in V with probability 2^{-3d} if the quadruple is good, and with probability about 2^{-4d} if the quadruple is bad. So if we refine A to the set  (a,\phi(a)) \in V \}, one expects the relative proportion of good quadruples to bad to increase by a factor of about 2^{-d}. Also, each element a \in A has a probability of about 2^{-d} of lying in A'. Applying the first moment method as in the previous example, one soon shows that one can find a set A' of size at least 2^{-d} |A| (up to constants) such that 1 - O( 2^{-d} \epsilon^{-C} \delta^{-C} ) of the additive quadruples in A are good, for some absolute constants C.

This type of argument is used in Gowers' proof of Szemerédi's theorem.

General discussion



Some of the Latex is not rendered appropirately.

Corrected, thanks!

Corrected, thanks!

Post new comment

(Note: commenting is not possible on this snapshot.)

Before posting from this form, please consider whether it would be more appropriate to make an inline comment using the Turn commenting on link near the bottom of the window. (Simply click the link, move the cursor over the article, and click on the piece of text on which you want to comment.)