Tidy problem page: Difference between revisions
New page: There is already a page devoted to unsolved problems related to the polymath1 project. This page is intended as a more polished page for unsolved problems. Contributions are welcome: t... |
No edit summary |
||
| Line 7: | Line 7: | ||
Now the corners result is a natural generalization of Szemerédi's theorem for progressions of length 2, but so is Szemerédi's theorem itself. So a natural question (with potential applications to the project) arises: what generalization of Sperner's theorem relates to Sperner's theorem itself in the way that the general case of Szemerédi's theorem relates to the trivial case of progressions of length 2? | Now the corners result is a natural generalization of Szemerédi's theorem for progressions of length 2, but so is Szemerédi's theorem itself. So a natural question (with potential applications to the project) arises: what generalization of Sperner's theorem relates to Sperner's theorem itself in the way that the general case of Szemerédi's theorem relates to the trivial case of progressions of length 2? | ||
One theorem that does the job is the following: let <math>\mathcal{A}</math> be a subset of <math>[2]^n</math> such that the average density of <math>\mathcal{A}</math> in each slice of <math>[2]^n</math> is at least <math>\delta</math>. Then there are disjoint sets <math>A,D_1,\dots,D_k</math> all of the same size such that <math>A\cup D_1\cup\dots\cup D_j< | One theorem that does the job is the following: let <math>\mathcal{A}</math> be a subset of <math>[2]^n</math> such that the average density of <math>\mathcal{A}</math> in each slice of <math>[2]^n</math> is at least <math>\delta</math>. Then there are disjoint sets <math>A,D_1,\dots,D_k</math> all of the same size such that <math>A\cup D_1\cup\dots\cup D_j</math> belongs to <math>\mathcal{A}</math> for every <math>0\leq j\leq k</math>. | ||
'''Proof:''' Pick a random permutation of <math>[n]</math>. Then on average there will be </math>\delta n</math> initial segments of the permuted set that belong to <math>\mathcal{A}</math>. By Szemerédi's theorem we can find an arithmetic progression of these of length <math>k</math>. | '''Proof:''' Pick a random permutation of <math>[n]</math>. Then on average there will be </math>\delta n</math> initial segments of the permuted set that belong to <math>\mathcal{A}</math>. By Szemerédi's theorem we can find an arithmetic progression of these of length <math>k</math>. | ||
There is one aspect of this statement that seems a bit artificial, which is the assumption that the <math>D_j</math> 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 <math>A\cup D_1\cup\dots\cup A_j</math> but all sets of the form <math>A\cup\bigcup_{j\in S}D_j< | There is one aspect of this statement that seems a bit artificial, which is the assumption that the <math>D_j</math> 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 <math>A\cup D_1\cup\dots\cup A_j</math> but all sets of the form <math>A\cup\bigcup_{j\in S}D_j</math>? | ||
Revision as of 07:45, 13 February 2009
There is already a page devoted to unsolved problems related to the polymath1 project. This page is intended as a more polished page for unsolved problems. Contributions are welcome: they should be problems that are formulated precisely enough for others to think about without having to worry about what they mean. Additional commentary about the problems is also very useful. Also, it would be good if this page were reasonably organized: if you want to add a problem then try to put it near other related problems, and if there are two or three problems that could fit under a general heading, then add such a heading, and so on.
What is the correct one-dimensional generalization of Sperner's theorem?
As has been observed several times, if you apply the density Hales-Jewett theorem to sets [math]\displaystyle{ A }[/math] of sequences such that whether or not [math]\displaystyle{ x }[/math] belongs to [math]\displaystyle{ A }[/math] depends only on the number of 1s, 2s and 3s in [math]\displaystyle{ x }[/math], then you can easily deduce the corners theorem: that a dense subset of [math]\displaystyle{ [n]^2 }[/math] contains a triple of the form [math]\displaystyle{ (x,y),(x+d,y),(x,y+d) }[/math]. If you try the same thing with Sperner's theorem, you deduce the trivial one-dimensional result that a dense subset of [math]\displaystyle{ [n] }[/math] contains a pair of the form [math]\displaystyle{ (x),(x+d) }[/math]. (I have written these as "ordered singletons" to make the analogy clearer.) This is Szemerédi's theorem for arithmetic progressions of length 2.
Now the corners result is a natural generalization of Szemerédi's theorem for progressions of length 2, but so is Szemerédi's theorem itself. So a natural question (with potential applications to the project) arises: what generalization of Sperner's theorem relates to Sperner's theorem itself in the way that the general case of Szemerédi's theorem relates to the trivial case of progressions of length 2?
One theorem that does the job is the following: let [math]\displaystyle{ \mathcal{A} }[/math] be a subset of [math]\displaystyle{ [2]^n }[/math] such that the average density of [math]\displaystyle{ \mathcal{A} }[/math] in each slice of [math]\displaystyle{ [2]^n }[/math] is at least [math]\displaystyle{ \delta }[/math]. Then there are disjoint sets [math]\displaystyle{ A,D_1,\dots,D_k }[/math] all of the same size such that [math]\displaystyle{ A\cup D_1\cup\dots\cup D_j }[/math] belongs to [math]\displaystyle{ \mathcal{A} }[/math] for every [math]\displaystyle{ 0\leq j\leq k }[/math].
Proof: Pick a random permutation of [math]\displaystyle{ [n] }[/math]. Then on average there will be </math>\delta n</math> initial segments of the permuted set that belong to [math]\displaystyle{ \mathcal{A} }[/math]. By Szemerédi's theorem we can find an arithmetic progression of these of length [math]\displaystyle{ k }[/math].
There is one aspect of this statement that seems a bit artificial, which is the assumption that the [math]\displaystyle{ D_j }[/math] 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 [math]\displaystyle{ A\cup D_1\cup\dots\cup A_j }[/math] but all sets of the form [math]\displaystyle{ A\cup\bigcup_{j\in S}D_j }[/math]?
