Quasirandomness

Quasirandomness is a central concept in extremal combinatorics, and is likely to play an important role in any combinatorial proof of the density Hales-Jewett 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]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ \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 Hales-Jewett theorem.

Examples of quasirandomness definitions

Bipartite graphs

Let X and Y be two finite sets and let [math]\displaystyle{ f:X\times Y\rightarrow [-1,1]. }[/math] Then f is defined to be c-quasirandom if [math]\displaystyle{ \mathbb{E}_{x,x'\in X}\mathbb{E}_{y,y'\in Y}f(x,y)f(x,y')f(x',y)f(x',y')\leq c. }[/math]

Since the left-hand side is equal to [math]\displaystyle{ \mathbb{E}_{x,x'\in X}(\mathbb{E}_{y\in Y}f(x,y)f(x',y))^2, }[/math] it is always non-negative, and the condition that it should be small implies that [math]\displaystyle{ \mathbb{E}_{y\in Y}f(x,y)f(x',y) }[/math] is small for almost every pair [math]\displaystyle{ x,x'. }[/math]

If G is a bipartite graph with vertex sets X and Y and [math]\displaystyle{ \delta }[/math] is the density of G, then we can define [math]\displaystyle{ f(x,y) }[/math] to be [math]\displaystyle{ 1-\delta }[/math] if xy is an edge of G and [math]\displaystyle{ -\delta }[/math] otherwise. We call f the balanced function of G, and we say that G is c-quasirandom if its balanced function is c-quasirandom.

It can be shown that if H is any fixed graph and G is a large quasirandom graph, then the number of copies of H in G is approximately what it would be in a random graph of the same density as G.

Subsets of finite Abelian groups

If A is a subset of a finite Abelian group G and A has density [math]\displaystyle{ \delta, }[/math] then we define the balanced function f of A by setting [math]\displaystyle{ f(x)=1-\delta }[/math] when x\in A and [math]\displaystyle{ f(x)=-\delta }[/math] otherwise. Then A is c-quasirandom if and only if f is c-quasirandom, and f is defined to be c-quasirandom if [math]\displaystyle{ \mathbb{E}_{x,a,b\in G}f(x)f(x+a)f(x+b)f(x+a+b)\leq c. }[/math] Again, we can prove positivity by observing that the left-hand side is a sum of squares. In this case, it is [math]\displaystyle{ \mathbb{E}_{a\in G}(\mathbb{E}_{x\in G}f(x)f(x+a))^2. }[/math]

A possible definition of quasirandom subsets of [math]\displaystyle{ [3]^n }[/math]

(To be continued.)