An outline of a density-increment argument

Introduction

One of the proof strategies we have considered seriously is the density-increment method. The idea here is to prove that if [math]\displaystyle{ \mathcal{A} }[/math] is a subset of [math]\displaystyle{ [3]^n }[/math] of density [math]\displaystyle{ \delta }[/math] with no combinatorial line then there is a combinatorial subspace S of dimension tending to infinity with n such that the density of [math]\displaystyle{ \mathcal{A} }[/math] inside S is larger than [math]\displaystyle{ \delta }[/math] by an amount that depends on [math]\displaystyle{ \delta }[/math] only. If we can prove such a result, then we can drop down to S and repeat the argument. If the initial dimension n is large enough, then we push the density up to 1 before we run out of dimensions, and thereby obtain a contradiction.

Notation and definitions

Let x be an element of [math]\displaystyle{ [3]^n. }[/math] Write [math]\displaystyle{ U(x),V(x) }[/math] and [math]\displaystyle{ W(x) }[/math] for the sets of i such that [math]\displaystyle{ x_i=1,2 }[/math] and 3, respectively. These are called the 1-set, the 2-set and the 3-set of x. The map [math]\displaystyle{ x\mapsto(U(x),V(x),W(x)) }[/math] is a one-to-one correspondence between [math]\displaystyle{ [3]^n }[/math] and the set of all triples [math]\displaystyle{ (U,V,W) }[/math] of sets that partition [math]\displaystyle{ [n]. }[/math] We shall use the notation x and also the notation [math]\displaystyle{ (U,V,W) }[/math] and will pass rapidly between them.

Let [math]\displaystyle{ \mathcal{U} }[/math] and [math]\displaystyle{ \mathcal{V} }[/math] be collections of subsets of [math]\displaystyle{ [n]. }[/math] We shall write [math]\displaystyle{ mathcal{U}\otimes\mathcal{V} }[/math] for the collection of all sequences [math]\displaystyle{ x }[/math] such that [math]\displaystyle{ U(x)\in\mathcal{U} }[/math] and [math]\displaystyle{ V(x)\in\mathcal{V}. }[/math] A set of the form [math]\displaystyle{ \mathcal{U}\otimes\mathcal{V} }[/math] will be called a 12-set.

In general, if X is a finite set and A and B are subsets of X, we define the density of A in B to be [math]\displaystyle{ |A\cap B|/|B|. }[/math]

A very broad overview of the argument

One of the main features of the argument is that it is local in character. In other words, it does not try to understand fully the obstructions to uniformity that cause a set to fail to have the expected number of combinatorial lines. Instead, we are content to find non-quasirandom behaviour inside small subspaces of [math]\displaystyle{ [3]^n. }[/math] This happens right from the start. A conjecture that one might hope to be true is that if a set [math]\displaystyle{ \mathcal{A} }[/math] is line-free, then there is a dense 12-set [math]\displaystyle{ \mathcal{U}\otimes\mathcal{V} }[/math] such that the density of [math]\displaystyle{ \mathcal{A} }[/math] inside [math]\displaystyle{ \mathcal{U}\otimes\mathcal{V} }[/math] is a bit larger than the density of [math]\displaystyle{ \mathcal{A} }[/math] in [math]\displaystyle{ [3]^n. }[/math] However, this is not in fact our first step. Instead, we argue that this kind of correlation happens when one restricts to an appropriate subspace. This part of the argument is given in some detail on a different page, (where what we are calling 12-sets are called special sets of complexity 1).

Once we have correlation with a 12-set (even if we have had to pass to a subspace to get it) it is natural to try to prove that a 12-set can be partitioned into combinatorial subspaces, since then by averaging we could show that [math]\displaystyle{ \mathcal{A} }[/math] correlated with one of those subspaces, and we would be done. An argument similar to the proof of the multidimensional Sperner theorem can be used to prove that a dense 12-set contains many combinatorial subspaces. However, it is not at all obvious that one can partition the 12-set into such subspaces (even if small errors are allowed).

However, a different principle comes to the rescue. It is the observation that there are two kinds of density increment that will be good enough for us. One is a density increment on a subspace, as we already know. The other is a density increment on a 12-set (obtained after passing to a subspace if necessary). Let us spell this out in more detail. Suppose that [math]\displaystyle{ \mathcal{A} }[/math] is a line-free set of density [math]\displaystyle{ \delta }[/math] and we want to obtain a contradiction. We know two things. First, we can find a 12-subset of a subspace in which [math]\displaystyle{ \mathcal{A} }[/math] has increased density [math]\displaystyle{ \delta+\eta }[/math], and secondly, if we can ever prove that there is increased density [math]\displaystyle{ \delta+\eta/2 }[/math] (say) on a subspace then we are done. However, we can add a third principle, which is that if we can find a 12-subset of a subspace on which the density goes up from [math]\displaystyle{ \delta+\eta }[/math] then we are again done. Why? Because we are in the same position as we were in before, but with a slightly higher density, so we can iterate.

To be continued.

[math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math][math]\displaystyle{ }[/math]