DHJ(1,3)

Statement of the problem

Recall that DHJ(1,3) is the following problem.

• Let [math]\displaystyle{ \mathcal{U}, \mathcal{V} }[/math] and [math]\displaystyle{ \mathcal{W} }[/math] be three collections of subsets of [math]\displaystyle{ [n] }[/math] and let [math]\displaystyle{ \mathcal{A} }[/math] be the set of all sequences [math]\displaystyle{ x\in[3]^n }[/math] such that the 1-set, 2-set and 3-set of [math]\displaystyle{ x }[/math] belongs to [math]\displaystyle{ \mathcal{U}, \mathcal{V} }[/math] and [math]\displaystyle{ \mathcal{W}, }[/math] respectively. If [math]\displaystyle{ \mathcal{A} }[/math] is dense, does it follow that it contains a combinatorial line?

The answer is of course yes, since it is just DHJ(3) with an extra restriction on the dense set that one would like to contain a combinatorial line. The reasons for considering the question are (i) that it ought to be amenable to the kinds of techniques used to prove Sperner's theorem, and (ii) that sets of this special kind need to be understood, as they appear to be an important class of obstructions to uniformity in DHJ(3). Since Sperner's theorem is most naturally proved using equal-slices measure on [math]\displaystyle{ [2]^n, }[/math] we shall use it here.

An easy version of the problem

Since any element [math]\displaystyle{ x\in[3]^n }[/math] is determined by just its 1-set and its 2-set, it is natural to consider the yet simpler variant of DHJ(1,3) where [math]\displaystyle{ \mathcal{W} }[/math] consists of all subsets of [math]\displaystyle{ [n]. }[/math] This problem can be solved by an easy adaptation of one of the proofs of Sperner's theorem.

To see this, note first that if the equal-slices measure of [math]\displaystyle{ \mathcal{A} }[/math] is greater than n+1, then there must exist c such that the sum over [math]\displaystyle{ a+b=n-c }[/math] of the densities of [math]\displaystyle{ \mathcal{A} }[/math] in the slices [math]\displaystyle{ \Gamma_{a,b,c} }[/math] is greater than 1. Now choose a random permutation [math]\displaystyle{ \pi }[/math] of [math]\displaystyle{ [n]. }[/math] Then the expected number of [math]\displaystyle{ a }[/math] such that the first [math]\displaystyle{ a }[/math] elements of [math]\displaystyle{ \pi([n]) }[/math] form an element of [math]\displaystyle{ \mathcal{U} }[/math] and the next [math]\displaystyle{ n-c-a }[/math] elements form an element of [math]\displaystyle{ \mathcal{V} }[/math] is greater than 1. So there must exist a permutation such that this number is greater than 1, and hence at least 2. That gives us two pairs of disjoint sets [math]\displaystyle{ (U_1,V_1) }[/math] and [math]\displaystyle{ (U_2,V_2) }[/math] belonging to [math]\displaystyle{ \mathcal{U}\times\mathcal{V} }[/math] such that [math]\displaystyle{ U_1\cup V_1=U_2\cup V_2 }[/math] and [math]\displaystyle{ U_1\subset U_2. }[/math] But then, writing [math]\displaystyle{ W }[/math] for [math]\displaystyle{ [n]\setminus(U\cup V), }[/math] the three triples [math]\displaystyle{ (U_1,V_1,W), (U_2,V_2,W) }[/math] and [math]\displaystyle{ (U_1,V_2,W\cup(U_2\cap V_1) }[/math] determine sequences that form a combinatorial line in [math]\displaystyle{ \mathcal{A}. }[/math]