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.

Prerequisites

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$ .