Density increment method: Difference between revisions
New page: The basic idea of the density increment method is as follows. Suppose that you have some structure <math>S</math> that has many substructures of a similar general nature to <math>S</math>.... |
No edit summary |
||
| Line 8: | Line 8: | ||
With these three steps in place, a simple iteration argument completes the proof. | 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. | |||
Revision as of 04:37, 14 February 2009
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.
