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.
Just to be explicit about this, let us briefly describe how the iteration would go. We start with a line-free set [math]\displaystyle{ \mathcal{A} }[/math] of density [math]\displaystyle{ \delta }[/math] and hope ultimately to obtain a contradiction. To do this, we adopt as a more immediate aim to find a subspace S inside which [math]\displaystyle{ \mathcal{A} }[/math] has density at least [math]\displaystyle{ \delta+\eta(\delta)/2. }[/math] As a first step, we find a 12-subset of a subspace, inside which [math]\displaystyle{ \mathcal{A} }[/math] has density at least [math]\displaystyle{ \delta+\eta. }[/math] We now focus our attention on the subproblem of trying to use this to obtain a subspace inside which [math]\displaystyle{ \mathcal{A} }[/math] has density at least [math]\displaystyle{ \delta+\eta/2. }[/math] But here again we can use the same sort of idea. We do not have to find such a subspace directly: instead, we could prove that if no such subspace exists (so the density of [math]\displaystyle{ \mathcal{A} }[/math] inside all subspaces is at most [math]\displaystyle{ \delta+\eta/2,) }[/math] then we can find a 12-subset of some further subspace, inside which [math]\displaystyle{ \mathcal{A} }[/math] has density at least [math]\displaystyle{ \delta+\eta+\theta(\delta). }[/math] And then we can try again to find a subspace where the density is at least [math]\displaystyle{ \delta+\eta/2. }[/math] Repeating this argument leads to an iteration within the main iteration, which will eventually terminate with a density increase on a subspace (since the density within a 12-set cannot exceed 1). And then we have completed another step of the main iteration, so we are done.
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]
