# Difference between revisions of "Tidy problem page"

As has been observed several times, if you apply the density Hales-Jewett theorem to sets $A$ of sequences such that whether or not $x$ belongs to $A$ depends only on the number of 1s, 2s and 3s in $x$, then you can easily deduce the corners theorem: that a dense subset of $[n]^2$ contains a triple of the form $(x,y),(x+d,y),(x,y+d)$. If you try the same thing with Sperner's theorem, you deduce the trivial one-dimensional result that a dense subset of $[n]$ contains a pair of the form $(x),(x+d)$. (I have written these as "ordered singletons" to make the analogy clearer.) This is Szemerédi's theorem for arithmetic progressions of length 2.
One theorem that does the job is the following: let $\mathcal{A}$ be a subset of $^n$ such that the average density of $\mathcal{A}$ in each slice of $^n$ is at least $\delta$. Then there are disjoint sets $A,D_1,\dots,D_k$ all of the same size such that $A\cup D_1\cup\dots\cup D_j$ belongs to $\mathcal{A}$ for every $0\leq j\leq k$.
Proof: Pick a random permutation of $[n]$. Then on average there will be [/itex]\delta n[/itex] initial segments of the permuted set that belong to $\mathcal{A}$. By Szemerédi's theorem we can find an arithmetic progression of these of length $k$.
There is one aspect of this statement that seems a bit artificial, which is the assumption that the $D_j$ all have the same cardinality. Is it possible to justify this as a natural assumption (e.g. by showing that the theorem is useful)? Is there a more set-theoretic generalization of the statement? Can one find not just the sets of the form $A\cup D_1\cup\dots\cup A_j$ but all sets of the form $A\cup\bigcup_{j\in S}D_j$?