# Difference between revisions of "Quasirandomness"

m (→Subsets of finite Abelian groups) |
m (→Bipartite graphs) |
||

Line 17: | Line 17: | ||

Let X and Y be two finite sets and let <math>f:X\times Y\rightarrow [-1,1].</math> Then f is defined to be c-quasirandom if <math>\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> | Let X and Y be two finite sets and let <math>f:X\times Y\rightarrow [-1,1].</math> Then f is defined to be c-quasirandom if <math>\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>\mathbb{E}_{x,x'\in X} | + | Since the left-hand side is equal to <math>\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>\mathbb{E}_{y\in Y}f(x,y)f(x',y)</math> is small for almost every pair <math>x,x'.</math> |

If G is a bipartite graph with vertex sets X and Y and <math>\delta</math> is the density of G, then we can define <math>f(x,y)</math> to be <math>1-\delta</math> if xy is an edge of G and <math>-\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. | If G is a bipartite graph with vertex sets X and Y and <math>\delta</math> is the density of G, then we can define <math>f(x,y)</math> to be <math>1-\delta</math> if xy is an edge of G and <math>-\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. |

## Revision as of 11:45, 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 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]\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 Hales-Jewett theorem.

## Contents

## Examples of quasirandomness definitions

#### Bipartite graphs

Let X and Y be two finite sets and let [math]f:X\times Y\rightarrow [-1,1].[/math] Then f is defined to be c-quasirandom if [math]\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]\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]\mathbb{E}_{y\in Y}f(x,y)f(x',y)[/math] is small for almost every pair [math]x,x'.[/math]

If G is a bipartite graph with vertex sets X and Y and [math]\delta[/math] is the density of G, then we can define [math]f(x,y)[/math] to be [math]1-\delta[/math] if xy is an edge of G and [math]-\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.

#### Subsets of finite Abelian groups

If A is a subset of a finite Abelian group G and A has density [math]\delta,[/math] then we define the balanced function f of A by setting [math]f(x)=1-\delta[/math] when x\in A and [math]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]\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]\mathbb{E}_{a\in G}(\mathbb{E}_{x\in G}f(x)f(x+a))^2.[/math]

#### Hypergraphs

#### Subsets of grids

## A possible definition of quasirandom subsets of [math][3]^n[/math]

(To be continued.)