Are shift-chains two-colorable? For $A\subset [n]$ denote by $a_i$ the $i^{th}$ smallest element of $A$.

For two $k$-element sets, $A,B\subset [n]$, we say that $A\le B$ if $a_i\le b_i$ for every $i$.

A $k$-uniform hypergraph ${\mathcal H}\subset [n]$ is called a shift-chain if for any hyperedges, $A, B \in {\mathcal H}$, we have $A\le B$ or $B\le A$. (So a shift-chain has at most $k(n-k)+1$ hyperedges.)

We say that a hypergraph  ${\mathcal H}$ is two-colorable (or that it has Property B) if we can color its vertices with two colors such that no hyperedge is monochromatic.

Is it true that shift-chains are two-colorable if $k$ is large enough?

Remarks. I first posted this problem on mathoverflow, but nobody commented on it.

The problem was investigated on the 1st Emlektabla Workshop for some partial results, see the booklet.

The question is motivated by decomposition of multiple coverings of the plane by translates of convex shapes, there are many open questions in this area. (For more, see my PhD thesis.)

For $k=2$ there is a trivial counterexample: (12),(13),(23).

A very magical counterexample was given for $k=3$ by Radoslav Fulek with a computer program:

(123),(124),(125),(135),(145),(245),(345),(346),(347),(357),

(367),(467),(567),(568),(569),(579),(589),(689),(789).

If we allow the hypergraph to be the union of two shift-chains (with the same order), then there is a counterexample for any $k$.

Update. I have recently managed to show that more restricted version of shift-chains are two-colorable in this preprint.  

Permanent bounty! I'm happy to award a 500 bounty for a solution anytime!
This is not an answer.  What follows is a simple proof that the construction for k=3 is indeed a counterexample.  I think that the asker knows this proof, but I will post it anyway because the proof is nice and this might be useful when people consider the case of larger k.

It is easy to verify that it is a shift-chain.  Let’s show that it does not have Property B.

In fact, the subhypergraph {(123), (145), (245), (345), (346), (347), (357), (367), (467), (567), (568), (569), (789)} already fails to satisfy Property B.  To see this, suppose that this hypergraph has a 2-coloring and let ci be the color of the vertex i.  Look at three hyperedges (145), (245), (345).  If c4=c5, then all of 1, 2 and 3 must be the opposite color to c4, but this would give a monochromatic hyperedge (123).  Therefore, it must be the case that c4≠c5.  Similarly,


c3≠c4 by comparing the three hyperedges (345), (346), (347) and noticing a hyperedge (567).
c6≠c7 by comparing the three hyperedges (367), (467), (567) and noticing a hyperedge (345).
c5≠c6 by comparing the three hyperedges (567), (568), (569) and noticing a hyperedge (789).


Therefore, we have c3≠c4≠c5≠c6≠c7.  But this implies c3=c5=c7, making the hyperedge (357) monochromatic.  This contradicts the assumption of the 2-coloring.