Tricki

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

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

### Prerequisites

Graph theory; probability theory

### Example 1

(Baby Balog-Szemerédi-Gowers lemma) Let be a graph with vertices and at least edges, where is large and is fixed. Then we expect many pairs of points in to be connected by an edge, and even more pairs of points in 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 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 of a bipartite graph can be arbitrarily close to . 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 ).

However, one can refine the vertex set 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 are connected by a path passing through a third vertex , then both lie in the neighborhood of , defined as the set of all vertices in connected to by an edge. Conversely, if are not connected by such a path, then will not both lie in any such neighborhood . More generally, if are only connected by a few such paths, then it is unlikely that will both lie in for a randomly chosen . So one way to favor'' pairs that are connected by many paths of length two is to refine to a randomly selected neighborhood . As a first attempt to make this work, pick and call a pair good if there are more than paths of length two from to , and bad otherwise. Pick uniformly at random from . By construction, every bad pair has a probability of at most of lying in ; there are at most bad pairs overall, so by the linearity of expectation, the expected total number of bad pairs in is at most .

Meanwhile, the total number of pairs in (both good and bad) is . As has edges, the expected value of is at least (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 is at least . Thus, the quantity

has non-negative expectation, which by the first moment method implies that one can find a such that the proportion of bad pairs in is , i.e. of the pairs in are connected by at least paths of length two.

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

also has a non-negative expectation, which means that one can find a with such that of the pairs in are connected by at least 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 of of cardinality at least for some absolute constants such that every pair of vertices in is connected by at least paths of length three in .

### Example 2

(Improving the quality of a Freiman homomorphism) Let be the field of two elements. If , a map is said to be a Freiman homomorphism if one has the property that whenever with .

Now suppose one has a map on a reasonably large set (say for some ) which is only a Freiman homomorphism a fraction of the time, e.g. out of all the quadruples with , only a proportion of these quadruples obey . One would like to refine the set to improve the proportion of quadruples with this property.

The key observation is this. Consider the graph of , and take an affine subspace of . If is a good additive quadruple with all lying in , then the fourth point automatically lies in also. In contrast, for a bad additive quadruple, there is no particular reason for to lie in , particularly if the codimension of is large.

To exploit this, we pick a codimension (to be optimised later) and let be a random affine subspace of of codimension . Given an additive quadruple with all four elements distinct, we soon see that all the elements of this quadruple will lie in with probability if the quadruple is good, and with probability about if the quadruple is bad. So if we refine to the set , one expects the relative proportion of good quadruples to bad to increase by a factor of about . Also, each element has a probability of about of lying in . Applying the first moment method as in the previous example, one soon shows that one can find a set of size at least (up to constants) such that of the additive quadruples in are good, for some absolute constants .

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