Quasirandomness: Difference between revisions

From Polymath Wiki
Jump to navigationJump to search
← Older editNewer edit →
Line 2: Line 2:
BZnmyM  <a href="http://wsmwsxvnhfws.com/">wsmwsxvnhfws</a>, [url=http://xfsvlyjckrzg.com/]xfsvlyjckrzg[/url], [link=http://afyogomumdwb.com/]afyogomumdwb[/link], http://ljfxoyxsnnwi.com/
BZnmyM  <a href="http://wsmwsxvnhfws.com/">wsmwsxvnhfws</a>, [url=http://xfsvlyjckrzg.com/]xfsvlyjckrzg[/url], [link=http://afyogomumdwb.com/]afyogomumdwb[/link], http://ljfxoyxsnnwi.com/


==Examples of quasirandomness definitions==
http://planeta.rambler.ru/users/hajgas/   ����� ���� �����������
 
====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.
 
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>\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>
 
If G has odd order, then it can be shown that a quasirandom set A contains approximately the same number of triples <math>(x,x+d,x+2d)</math> as a random subset A of the same density. However, it is decidedly ''not'' the case that A must contain approximately the same number of arithmetic progressions of higher length (regardless of torsion assumptions on G). For that one must use "higher uniformity".
 
====Hypergraphs====
 
====Subsets of grids====
 
A function f from <math>[n]^2</math> to [-1,1] is c-quasirandom if the "sum over rectangles" is at most c. The sum over rectangles is <math>\mathbb{E}_{x,y,a,b}f(x,y)f(x+a,y)f(x,y+b)f(x+a,y+b)</math>. Again, it is easy to show that this sum is non-negative by expressing it as a sum of squares. And again, one defines a subset <math>A\subset[n]^2</math> to be c-quasirandom if it has a balanced function that is c-quasirandom.
 
If A is a c-quasirandom set of density <math>\delta</math> and c is sufficiently small, then A contains roughly the same number of [[corners]] as a random subset of <math>[n]</math> of density <math>\delta.</math>


==A possible definition of quasirandom subsets of <math>[3]^n</math>==
==A possible definition of quasirandom subsets of <math>[3]^n</math>==

Revision as of 03:37, 12 March 2009

BZnmyM <a href="http://wsmwsxvnhfws.com/">wsmwsxvnhfws</a>, [url=http://xfsvlyjckrzg.com/]xfsvlyjckrzg[/url], [link=http://afyogomumdwb.com/]afyogomumdwb[/link], http://ljfxoyxsnnwi.com/

http://planeta.rambler.ru/users/hajgas/ ����� ���� �����������

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).

Retrieved from "https://michaelnielsen.org/polymath/index.php?title=Quasirandomness&oldid=808"