A second 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. A 1-set is a set of the form [math]\displaystyle{ \mathcal{U}\otimes[2]^n=\{x:U(x)\in\mathcal{U}\}, }[/math] and similarly for a 2-set. The 12-set [math]\displaystyle{ \mathcal{U}\otimes\mathcal{V} }[/math] is the intersection of the 1-set defined by [math]\displaystyle{ \mathcal{U} }[/math] and the 2-set defined by [math]\displaystyle{ \mathcal{V}. }[/math]

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 outline of the proof

The idea is to exploit the fact, proved on a different page, that if [math]\displaystyle{ \mathcal{A} }[/math] is a dense subset of [math]\displaystyle{ [3]^n }[/math] that contains no combinatorial lines, then there is a subspace S, and a 12-subset of that subspace, inside which [math]\displaystyle{ \mathcal{A} }[/math] has an increased density. We show also that any 12-set can be almost entirely partitioned into subspaces, so by averaging this density increase is passed down to one of those subspaces, and the proof is complete. In order to prove that [math]\displaystyle{ \mathcal{U}\otimes\mathcal{V} }[/math] can be almost entirely partitioned into subspaces, we show first that [math]\displaystyle{ \mathcal{U}\otimes[2]^n }[/math] can be almost entirely partitioned into subspaces, and then for each of those subspaces S we apply the same argument to [math]\displaystyle{ S\cap([2]^n\otimes\mathcal{V}, }[/math] which is a 2-subset of S.

This proof is modelled on a modification of the Ajtai-Szemerédi argument. It may be helpful to read that argument first.