2 added 156 characters in body

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 {\em 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}$ has Property B if we can color its vertices with two colors such that no hyperedge is monochromatic.

Is it true that shift-chains have Property B if $k$ is large enough?

$\bf Remarks.$ 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 brand new 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$.

$\bf Edit.$ I crossposted the question at theoryoverflow.

1

# Do Shift-chain have Property B?

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 {\em 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}$ has Property B if we can color its vertices with two colors such that no hyperedge is monochromatic.

Is it true that shift-chains have Property B if $k$ is large enough?

$\bf Remarks.$ 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 brand new 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$.