IP-Szemerédi theorem

2009-04-03T09:42:55Z

148.233.239.24: /* Relationship with DHJ(3) */

'''IP-Szemerédi theorem''': If n is sufficiently large depending on <math>\delta > 0</math>, then any subset of <math>[2]^n \times [2]^n</math> of density at least <math>\delta</math> contains a corner <math>(x,y), (x+r,y), (x,y+r)</math>, where x, y, x+r, y+r all lie in <math>[2]^n</math> and r lies in <math>[2]^n \backslash 0^n</math>.

Implies the [[corners theorem]], and hence [[Roth's theorem]]. Is implied in turn by the [[density Hales-Jewett theorem]], and may thus be a simpler test case.

No combinatorial proof of this theorem is currently known.

Randall McCutcheon proposes a slightly weaker version of this theorem in which <math>[2]^n</math> is replaced by <math>[n]^n</math>, but r is still constrained to <math>[2]^n \backslash 0^n</math>.

EB2LDh <a href="http://oxqbrgthvfxy.com/">oxqbrgthvfxy</a>, [url=http://qcdzavuwjcxb.com/]qcdzavuwjcxb[/url], [link=http://ydgmdetqojqn.com/]ydgmdetqojqn[/link], http://akjmiperxpvj.com/

== Motivation for considering the IP-Szemerédi theorem ==

When trying to solve a problem, one good strategy is to look for the simplest related problem that involves the same difficulties (or some of the same difficulties) that one is facing. The IP-Szemerédi theorem is a good candidate for a result that has this relationship with DHJ(3). Since no combinatorial proof is known, it clearly involves some serious difficulties. However, if we drop the condition that A and B have to be disjoint, then the bipartite graph formed by joining A to B if and only if <math>(A,B)\in\mathcal{A}</math> is dense if <math>\mathcal{A}</math> is dense. This means that one third of the natural tripartite graph associated with the problem (see the article on the [[triangle removal lemma]] for details) is dense, which should make it easier, but not too much easier, to analyse than the tripartite graph naturally associated with DHJ(3).

== Unorganised discussion ==

'''Solymosi.2:''' In this note I will try to argue that we should consider a variant of the original problem first. If the removal technique doesn’t work here, then it won’t work in the more difficult setting. If it works, then we have a nice result! Consider the Cartesian product of an IP_d set. (An IP_d set is generated by d numbers by taking all the <math>2^d</math> possible sums. So, if the n numbers are independent then the size of the IP_d set is <math>2^d</math>. In the following statements we will suppose that our IP_d sets have size <math>2^n</math>.)

Prove that for any <math>c>0</math> there is a <math>d</math>, such that any <math>c</math>-dense subset of the Cartesian product of an IP_d set (it is a two dimensional pointset) has a corner.

The statement is true. One can even prove that the dense subset of a Cartesian product contains a square, by using the density HJ for <math>k=4</math>. (I will sketch the simple proof later) What is promising here is that one can build a not-very-large tripartite graph where we can try to prove a removal lemma. The vertex sets are the vertical, horizontal, and slope -1 lines, having intersection with the Cartesian product. Two vertices are connected by an edge if the corresponding lines meet in a point of our <math>c</math>-dense subset. Every point defines a triangle, and if you can find another, non-degenerate, triangle then we are done. This graph is still sparse, but maybe it is well-structured for a removal lemma.

Finally, let me prove that there is square if <math>d</math> is large enough compare to <math>c</math>. Every point of the Cartesian product has two coordinates, a 0,1 sequence of length <math>d</math>. It has a one to one mapping to <math>[4]^d</math>; Given a point <math>( (x_1,…,x_d),(y_1,…,y_d) )</math> where <math>x_i,y_j</math> are 0 or 1, it maps to <math>(z_1,…,z_d)</math>, where <math>z_i=0</math> if <math>x_i=y_i=0</math>, <math>z_i=1</math> if <math>x_i=1</math> and <math>y_i=0, z_i=2</math> if <math>x_i=0</math> and <math>y_i=1</math>, and finally <math>z_i=3</math> if <math>x_i=y_i=1</math>. Any combinatorial line in <math>[4]^d</math> defines a square in the Cartesian product, so the density HJ implies the statement.

'''Gowers.7:''' With reference to Jozsef’s comment, if we suppose that the <math>d</math> numbers used to generate the set are indeed independent, then it’s natural to label a typical point of the Cartesian product as <math>(\epsilon,\eta)</math>, where each of <math>\epsilon</math> and <math>\eta</math> is a 01-sequence of length <math>d</math>. Then a corner is a triple of the form <math>(\epsilon,\eta)</math>, <math>(\epsilon,\eta+\delta)</math>, <math>(\epsilon+\delta,\eta)</math>, where <math>\delta</math> is a <math>\{-1,0,1\}</math>-valued sequence of length <math>d</math> with the property that both <math>\epsilon+\delta</math> and <math>\eta+\delta</math> are 01-sequences. So the question is whether corners exist in every dense subset of the original Cartesian product.

This is simpler than the density Hales-Jewett problem in at least one respect: it involves 01-sequences rather than 012-sequences. But that simplicity may be slightly misleading because we are looking for corners in the Cartesian product. A possible disadvantage is that in this formulation we lose the symmetry of the corners: the horizontal and vertical lines will intersect this set in a different way from how the lines of slope -1 do.

I feel that this is a promising avenue to explore, but I would also like a little more justification of the suggestion that this variant is likely to be simpler.

'''Gowers.22:''' A slight variant of the problem you propose is this. Let’s take as our ground set the set of all pairs <math>(U,V)</math> of subsets of <math>[n]</math>, and let’s take as our definition of a corner a triple of the form <math>(U,V), (U\cup D,V), (U,V\cup D)</math>, where both the unions must be disjoint unions. This is asking for more than you asked for because I insist that the difference <math>D</math> is positive, so to speak. It seems to be a nice combination of Sperner’s theorem and the usual corners result. But perhaps it would be more sensible not to insist on that positivity and instead ask for a triple of the form <math>(U,V), ((U\cup D)\setminus C,V), (U, (V\cup D)\setminus C</math>, where <math>D</math> is disjoint from both <math>U</math> and <math>V</math> and <math>C</math> is contained in both <math>U</math> and <math>V</math>. That is your original problem I think.

I think I now understand better why your problem could be a good toy problem to look at first. Let’s quickly work out what triangle-removal statement would be needed to solve it. (You’ve already done that, so I just want to reformulate it in set-theoretic language, which I find easier to understand.) We let all of <math>X</math>, <math>Y</math> and <math>Z</math> equal the power set of <math>[n]</math>. We join <math>U\in X</math> to <math>V\in Y</math> if <math>(U,V)\in A</math>.

Ah, I see now that there’s a problem with what I’m suggesting, which is that in the normal corners problem we say that <math>(x,y+d)</math> and <math>(x+d,y)</math> lie in a line because both points have the same coordinate sum. When should we say that <math>(U,V\cup D)</math> and <math>(U\cup D,V)</math> lie in a line? It looks to me as though we have to treat the sets as 01-sequences and take the sum again. So it’s not really a set-theoretic reformulation after all.

'''O'Donnell.35:''' Just to confirm I have the question right…

There is a dense subset <math>A</math> of <math>\{0,1\}^n x \{0,1\}^n</math>. Is it true that it must contain three nonidentical strings <math>(x,x’), (y,y’), (z,z’)</math> such that for each <math>i = 1…n,</math> the 6 bits

<math>[ x_i x'_i ]</math>

<math>[ y_i y'_i ]</math>

<math>[ z_i z'_i ]</math>

are equal to one of the following:

<math>[ 0 0 ] [ 0 0 ] [ 0, 1 ] [ 1 0 ] [ 1 1 ] [ 1 1 ]</math>

<math>[ 0 0 ], [ 0 1 ], [ 0, 1 ], [ 1 0 ], [ 1 0 ], [ 1 1 ],</math>

<math>[ 0 0 ] [ 1 0 ] [ 0, 1 ] [ 1 0 ] [ 0 1 ] [ 1 1 ]</math>

?

'''McCutcheon.469:''' IP Roth:

Just to be clear on the formulation I had in mind (with apologies for the unprocessed code): for every <math>\delta>0</math> there is an <math>n</math> such that any <math>E\subset [n]^{[n]}\times [n]^{[n]}</math> having relative density at least <math>\delta</math> contains a corner of the form <math>\{a, a+(\sum_{i\in \alpha} e_i ,0),a+(0, \sum_{i\in \alpha} e_i)\}</math>. Here <math>(e_i)</math> is the coordinate basis for <math>[n]^{[n]}</math>, i.e. <math>e_i(j)=\delta_{ij}</math>.

Presumably, this should be (perhaps much) simpler than DHJ, <math>k=3</math>.

Polymath Wiki - User contributions [en]

IP-Szemerédi theorem