Tidy problem 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: 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]\displaystyle{ \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 D_j }[/math] but all sets of the form [math]\displaystyle{ 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]\displaystyle{ D_i }[/math] have the same cardinality:

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

It is possible to deduce a positive answer to this last question by using DHJ([math]\displaystyle{ 2^k }[/math]) and considering binary expansions of numbers in [math]\displaystyle{ [2^k] }[/math]. Is there a more elementary argument?

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

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

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

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

The trivial fact can be generalized to the corners theorem. For each n, let [math]\displaystyle{ \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]\displaystyle{ \mathcal{A}\subset[3]^n }[/math] has equal slices density greater than [math]\displaystyle{ \delta_n }[/math] then [math]\displaystyle{ \mathcal{A} }[/math] contains a combinatorial line.

Influence and obstructions in Sperner's theorem

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

Let [math]\displaystyle{ \mathcal{A}\subset[2]^n }[/math] be a set of density [math]\displaystyle{ \delta }[/math] in the equal-slices measure. If [math]\displaystyle{ \mathcal{A}\subset[2]^n }[/math] is a random set, then we expect that the density of the set of pairs [math]\displaystyle{ A\subset B }[/math] such that [math]\displaystyle{ A,B\in\mathcal{A} }[/math] will be close to [math]\displaystyle{ \delta^2. }[/math] If it differs from [math]\displaystyle{ \delta^2 }[/math] by some constant [math]\displaystyle{ \eta, }[/math] then must there be a variable [math]\displaystyle{ x_i }[/math] of influence at least [math]\displaystyle{ c(\eta)\gt 0 }[/math]?

With this question one should first decide how to define the influence of a variable [math]\displaystyle{ x_i }[/math]. Presumably it should be something like the equal-slices density of the set of points such that flipping [math]\displaystyle{ x_i }[/math] changes whether or not you are in [math]\displaystyle{ \mathcal{A}. }[/math] So a preliminary exercise might be to look at what happens to Fourier analysis when you change the measure from the uniform density to the equal-slices density.