Are shift-chains two-colorable?

Question

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!

Answer 1

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 c_i be the color of the vertex i. Look at three hyperedges (145), (245), (345). If c₄=c₅, then all of 1, 2 and 3 must be the opposite color to c₄, but this would give a monochromatic hyperedge (123). Therefore, it must be the case that c₄≠c₅. Similarly,

• c₃≠c₄ by comparing the three hyperedges (345), (346), (347) and noticing a hyperedge (567).
• c₆≠c₇ by comparing the three hyperedges (367), (467), (567) and noticing a hyperedge (345).
• c₅≠c₆ by comparing the three hyperedges (567), (568), (569) and noticing a hyperedge (789).

Therefore, we have c₃≠c₄≠c₅≠c₆≠c₇. But this implies c₃=c₅=c₇, making the hyperedge (357) monochromatic. This contradicts the assumption of the 2-coloring.

Answer 2

Perhaps I'm missing something but I think there is a good lower bound with the probabilistic method:

If you color each vertex indepedently with probability $1/2$ for each color then your have a monochromatic edge with probability $2 \cdot (\dfrac{1}{2})^k = 2^{-k+1}$. With the Lovasz local lemma you get that the shift-chain has property $B$ if $$k(n-k)+1 \leq \dfrac{2^{k-1}}{e}-1.$$ I can't directly solve this inequality but if you have $k = \Omega(\log(n))$ then you get on the left hand side somethink like $n \log(n)$ and on the right hand side $n^c$ (so the inequality is true for $n$ large enough).

There is a better bound of $O(\sqrt{k/\ln(k)} \cdot 2^k)$ on the number of edges for a $k$-uniform hypergraph so that the graph has property $B$.