Difference between revisions of "Quasirandomness"
(Wrote introduction and some section and subsection headings) 
(No difference)

Revision as of 12:19, 16 February 2009
Quasirandomness is a central concept in extremal combinatorics, and is likely to play an important role in any combinatorial proof of the density HalesJewett theorem. This will be particularly true if that proof is based on the density increment method or on some kind of generalization of Szemerédi's regularity lemma.
In general, one has some kind of parameter associated with a set, which in our case will be the number of combinatorial lines it contains, and one would like a deterministic definition of the word "quasirandom" with the following key property.
 Every quasirandom set [math]\mathcal{A}[/math] has roughly the same value of the given parameter as a random set of the same density.
Needless to say, this is not the only desirable property of the definition, since otherwise we could just define [math]\mathcal{A}[/math] to be quasirandom if it has roughly the same value of the given parameter as a random set of the same density. The second key property is this.
 Every set [math]\mathcal{A}[/math] that fails to be quasirandom has some other property that we can exploit.
These two properties are already discussed in some detail in the article on the density increment method: this article concentrates more on examples of quasirandomness in other contexts, and possible definitions of quasirandomness connected with the density HalesJewett theorem.
Contents
Examples of quasirandomness definitions
Graphs
Subsets of finite Abelian groups
Hypergraphs
Subsets of grids
A possible definition of quasirandom subsets of [math][3]^n[/math]
(To be continued.)