# Difference between revisions of "Tidy problem page"

(→Influence and obstructions in Sperner's theorem) |
(→Influence and obstructions in Sperner's theorem: Changed final paragraph to something more sensible) |
||

Line 49: | Line 49: | ||

Define an "equal-slices" density on pairs <math>A\subset B</math> of subsets of <math>[n]</math> as follows: to choose a random such pair, let <math>\pi</math> be a random permutation of <math>[n]</math>, let r and s be a random pair of integers with <math>0\leq r<s\leq n</math> and let <math>A=\{\pi(1),\dots,\pi(r)\}</math> and <math>B=\{\pi(1),\dots,\pi(s)\}.</math> | Define an "equal-slices" density on pairs <math>A\subset B</math> of subsets of <math>[n]</math> as follows: to choose a random such pair, let <math>\pi</math> be a random permutation of <math>[n]</math>, let r and s be a random pair of integers with <math>0\leq r<s\leq n</math> and let <math>A=\{\pi(1),\dots,\pi(r)\}</math> and <math>B=\{\pi(1),\dots,\pi(s)\}.</math> | ||

− | Let <math>\mathcal{A}\subset[2]^n</math> be a set of density <math>\delta</math> in the [[equal-slices measure]]. If <math>\mathcal{A}\subset[2]^n</math> is a random set, then we expect that the density of the set of pairs <math>A\subset B</math> such that <math>A,B\in\mathcal{A}</math> will be close to <math>\delta^2.</math> If it differs from <math>\delta^2</math> by some constant <math>\eta,</math> then | + | Let <math>\mathcal{A}\subset[2]^n</math> be a set of density <math>\delta</math> in the [[equal-slices measure]]. If <math>\mathcal{A}\subset[2]^n</math> is a random set, then we expect that the density of the set of pairs <math>A\subset B</math> such that <math>A,B\in\mathcal{A}</math> will be close to <math>\delta^2.</math> If it differs from <math>\delta^2</math> by some constant <math>\eta,</math> then what can we say about <math>\mathcal{A}</math>? |

− | + | A major source of examples is ''monotone sets'', that is, sets <math>\mathcal{A}</math> such that if <math>A\in\mathcal{A}</math> and <math>A\subset B</math> then <math>B\in\mathcal{A}.</math> If we choose a monotone set that contains a significant fraction of one layer and misses a significant fraction of a much higher layer then when we choose a random permutation <math>\pi</math> of <math>[n],</math> then the first initial segment that belongs to <math>\mathcal{A}</math> comes at a point with significant variance. An example of such a monotone set is the set of all sets that contain the element 1. It seems possible that for monotone sets that work there will always be a variable with high [[influence_of_variables|influence]]. | |

== Moser's cube problem == | == Moser's cube problem == |

## Revision as of 16:29, 19 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.

## Contents

## 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]A[/math] of sequences such that whether or not [math]x[/math] belongs to [math]A[/math] depends only on the number of 1s, 2s and 3s in [math]x[/math], then you can easily deduce the corners theorem: that a dense subset of [math][n]^2[/math] contains a triple of the form [math](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][n][/math] contains a pair of the form [math](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]\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].

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 D_j[/math] but all sets of the form [math]A\cup\bigcup_{j\in S}D_j[/math]?

Closely related to this last question is the same question but without the requirement that the [math]D_i[/math] have the same cardinality:

- If [math]\mathcal{A}[/math] is dense (either in the uniform probability measure on [math][2]^n[/math] or in the equal-slices measure) then must there exist disjoint sets [math]A,D_1\dots,D_k[/math] such that [math]A\cup\bigcup_{j\in S}D_j\in\mathcal{A}[/math] for every [math]S\subset\{1,2,\dots,k\}[/math]?

It is possible to deduce a positive answer to this last question by using DHJ([math]2^k[/math]) and considering binary expansions of numbers in [math][2^k][/math]. This gives sets [math]D_i[/math] of the same cardinality. Is there a more elementary argument, either for this assertion if you are allowed to use Szemerédi's theorem, or for the assertion with sets of differing cardinalities if you are not?

## How difficult is DHJ(j,k)?

One might expect that proving DHJ(j,k) is about as difficult as proving DHJ(j+1). But is this the case? In particular, is there a reasonably simple Sperner-style proof of DHJ(1,3)? (There is at least a proof of a fairly general case of this theorem, but it would be good to prove the whole thing in an elementary way.) If you are allowed to use DHJ(j+1) as a black box, can you give a combinatorial proof of DHJ(j,k) for all k?

## Hyper-optimistic conjectures

*Full article: Hyper-optimistic conjecture*

The proof of Sperner's theorem yields the following stronger result.

**Theorem.** If [math]\mathcal{A}\subset[2]^n[/math] has equal-slices density greater than [math]1/(n+1)[/math] then [math]\mathcal{A}[/math] contains two distinct sets A and B with [math]A\subset B.[/math]

The proof makes use of the following trivial fact: if [math]A\subset\{0,1,\dots,n\}[/math] has density greater than [math]1/(n+1)[/math] then A contains two distinct numbers x and y with [math]x\lty.[/math]

The trivial fact can be generalized to the corners theorem. For each n, let [math]\delta_n[/math] be the minimal density needed to guarantee a corner. By analogy with the above two results, one might be "hyper-optimistic" and hope for the following to be true. (However, there is no good evidence for the conjecture that is to follow.)

**Conjecture.** If [math]\mathcal{A}\subset[3]^n[/math] has equal-slices density greater than [math]\delta_n[/math] then [math]\mathcal{A}[/math] contains a combinatorial line.

## Influence and obstructions in Sperner's theorem

Define an "equal-slices" density on pairs [math]A\subset B[/math] of subsets of [math][n][/math] as follows: to choose a random such pair, let [math]\pi[/math] be a random permutation of [math][n][/math], let r and s be a random pair of integers with [math]0\leq r\lts\leq n[/math] and let [math]A=\{\pi(1),\dots,\pi(r)\}[/math] and [math]B=\{\pi(1),\dots,\pi(s)\}.[/math]

Let [math]\mathcal{A}\subset[2]^n[/math] be a set of density [math]\delta[/math] in the equal-slices measure. If [math]\mathcal{A}\subset[2]^n[/math] is a random set, then we expect that the density of the set of pairs [math]A\subset B[/math] such that [math]A,B\in\mathcal{A}[/math] will be close to [math]\delta^2.[/math] If it differs from [math]\delta^2[/math] by some constant [math]\eta,[/math] then what can we say about [math]\mathcal{A}[/math]?

A major source of examples is *monotone sets*, that is, sets [math]\mathcal{A}[/math] such that if [math]A\in\mathcal{A}[/math] and [math]A\subset B[/math] then [math]B\in\mathcal{A}.[/math] If we choose a monotone set that contains a significant fraction of one layer and misses a significant fraction of a much higher layer then when we choose a random permutation [math]\pi[/math] of [math][n],[/math] then the first initial segment that belongs to [math]\mathcal{A}[/math] comes at a point with significant variance. An example of such a monotone set is the set of all sets that contain the element 1. It seems possible that for monotone sets that work there will always be a variable with high influence.

## Moser's cube problem

*Full article: Moser's cube problem*

Let [math]c'_n[/math] be the size of the largest subset of [math][3]^n[/math] which does not contain a geometric line. As a consequence of DHJ(3), we know that [math]c'_n = o(3^n)[/math]. Open question: is there a combinatorial proof (and/or an effective bound) of this result?