Quasirandomness: Difference between revisions
m Undo spam revision 3148 by XavierErnandez (Talk) |
|||
| (27 intermediate revisions by 17 users not shown) | |||
| Line 1: | Line 1: | ||
==Introduction== | |||
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]]. | 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]]. | ||
| Line 11: | Line 13: | ||
These two properties are already discussed in some detail in the [[density increment method|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. | These two properties are already discussed in some detail in the [[density increment method|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. | ||
== | ==A possible definition of quasirandom subsets of <math>[3]^n</math>== | ||
As with all the examples above, it is more convenient to give a definition for quasirandom functions. However, in this case it is not quite so obvious what should be meant by a balanced function. | |||
Here, first, is a possible definition of a quasirandom function from <math>[2]^n\times [2]^n</math> to <math>[-1,1].</math> We say that f is c-quasirandom if <math>\mathbb{E}_{A,A',B,B'}f(A,B)f(A,B')f(A',B)f(A',B')\leq c.</math> However, the expectation is not with respect to the uniform distribution over all quadruples (A,A',B,B') of subsets of <math>[n].</math> Rather, we choose them as follows. (Several variants of what we write here are possible: it is not clear in advance what precise definition will be the most convenient to use.) First we randomly permute <math>[n]</math> using a permutation <math>\pi</math>. Then we let A, A', B and B' be four random intervals in <math>\pi([n]),</math> where we allow our intervals to wrap around mod n. (So, for example, a possible set A is <math>\{\pi(n-2),\pi(n-1),\pi(n),\pi(1),\pi(2)\}.</math>) | |||
As ever, it is easy to prove positivity. To apply this definition to subsets <math>\mathcal{A}</math> of <math>[3]^n,</math> define f(A,B) to be 0 if A and B intersect, <math>1-\delta</math> if they are disjoint and the sequence x that is 1 on A, 2 on B and 3 elsewhere belongs to <math>\mathcal{A},</math> and <math>-\delta</math> otherwise. Here, <math>\delta</math> is the probability that (A,B) belongs to <math>\mathcal{A}</math> if we choose (A,B) randomly by taking two random intervals in a random permutation of <math>[n]</math> (in other words, we take the marginal distribution of (A,B) from the distribution of the quadruple (A,A',B,B') above) and condition on their being disjoint. It follows from this definition that <math>\mathbb{E}f=0</math> (since the expectation conditional on A and B being disjoint is 0 and f is zero whenever A and B intersect). | |||
( | Nothing that one would really like to know about this definition has yet been fully established, though an argument that looks as though it might work has been proposed to show that if f is quasirandom in this sense then the expectation <math>\mathbb{E}f(A,B)f(A\cup D,B)f(A,B\cup D)</math> is small (if the distribution on these "set-theoretic corners" is appropriately defined). | ||
Latest revision as of 05:08, 8 July 2010
Introduction
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.
A possible definition of quasirandom subsets of [math]\displaystyle{ [3]^n }[/math]
As with all the examples above, it is more convenient to give a definition for quasirandom functions. However, in this case it is not quite so obvious what should be meant by a balanced function.
Here, first, is a possible definition of a quasirandom function from [math]\displaystyle{ [2]^n\times [2]^n }[/math] to [math]\displaystyle{ [-1,1]. }[/math] We say that f is c-quasirandom if [math]\displaystyle{ \mathbb{E}_{A,A',B,B'}f(A,B)f(A,B')f(A',B)f(A',B')\leq c. }[/math] However, the expectation is not with respect to the uniform distribution over all quadruples (A,A',B,B') of subsets of [math]\displaystyle{ [n]. }[/math] Rather, we choose them as follows. (Several variants of what we write here are possible: it is not clear in advance what precise definition will be the most convenient to use.) First we randomly permute [math]\displaystyle{ [n] }[/math] using a permutation [math]\displaystyle{ \pi }[/math]. Then we let A, A', B and B' be four random intervals in [math]\displaystyle{ \pi([n]), }[/math] where we allow our intervals to wrap around mod n. (So, for example, a possible set A is [math]\displaystyle{ \{\pi(n-2),\pi(n-1),\pi(n),\pi(1),\pi(2)\}. }[/math])
As ever, it is easy to prove positivity. To apply this definition to subsets [math]\displaystyle{ \mathcal{A} }[/math] of [math]\displaystyle{ [3]^n, }[/math] define f(A,B) to be 0 if A and B intersect, [math]\displaystyle{ 1-\delta }[/math] if they are disjoint and the sequence x that is 1 on A, 2 on B and 3 elsewhere belongs to [math]\displaystyle{ \mathcal{A}, }[/math] and [math]\displaystyle{ -\delta }[/math] otherwise. Here, [math]\displaystyle{ \delta }[/math] is the probability that (A,B) belongs to [math]\displaystyle{ \mathcal{A} }[/math] if we choose (A,B) randomly by taking two random intervals in a random permutation of [math]\displaystyle{ [n] }[/math] (in other words, we take the marginal distribution of (A,B) from the distribution of the quadruple (A,A',B,B') above) and condition on their being disjoint. It follows from this definition that [math]\displaystyle{ \mathbb{E}f=0 }[/math] (since the expectation conditional on A and B being disjoint is 0 and f is zero whenever A and B intersect).
Nothing that one would really like to know about this definition has yet been fully established, though an argument that looks as though it might work has been proposed to show that if f is quasirandom in this sense then the expectation [math]\displaystyle{ \mathbb{E}f(A,B)f(A\cup D,B)f(A,B\cup D) }[/math] is small (if the distribution on these "set-theoretic corners" is appropriately defined).
