Density increment method
The basic idea of the density increment method is as follows. Suppose that you have some structure [math]\displaystyle{ S }[/math] that has many substructures of a similar general nature to [math]\displaystyle{ S }[/math]. (Examples of such structures are combinatorial subspaces, grids, arithmetic progressions, complete graphs, etc.) Suppose also that you want to prove that every dense subset [math]\displaystyle{ A }[/math] of [math]\displaystyle{ S }[/math] contains a configuration of a certain kind. You try to prove it using a three-stage argument of the following kind.
- If [math]\displaystyle{ A }[/math] is quasirandom (in some sense that you have to devise), then [math]\displaystyle{ A }[/math] contains a configuration of the desired kind. Therefore, if [math]\displaystyle{ A }[/math] does not contain a configuration of the desired kind, then [math]\displaystyle{ A }[/math] is not quasirandom.
- If [math]\displaystyle{ A }[/math] is not quasirandom, then there is a set [math]\displaystyle{ T }[/math] of a kind one can describe such that [math]\displaystyle{ |A\cap T|/|T| }[/math] is significantly larger than the density of [math]\displaystyle{ A }[/math]. (More generally, we can find a function [math]\displaystyle{ f }[/math] of average zero that we can describe such that the average of [math]\displaystyle{ f }[/math] over [math]\displaystyle{ A }[/math] is bounded away from zero.)
- The characteristic function of [math]\displaystyle{ T }[/math] can be approximated by a positive linear combination of characteristic functions of substructures of [math]\displaystyle{ S }[/math]. Therefore, by averaging, there is a substructure [math]\displaystyle{ S' }[/math] of [math]\displaystyle{ S }[/math] such that [math]\displaystyle{ |A\cap S'|/|S'| }[/math] is significantly greater than the density of [math]\displaystyle{ A }[/math].
With these three steps in place, a simple iteration argument completes the proof.
A simple example of the method
Brief sketch of density-increment proof of Roth to come here.
Difficulties in applying the method to density Hales-Jewett
Summary of Varnavides thread and discussion of localization, alternative measures, etc.
Known obstructions to uniformity for density Hales-Jewett
Summary of obstructions-to-uniformity thread.
