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}$ is two-colorable 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. 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:



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$.

Edit. I crossposted the question at cstheory.SE.

Permanent bounty! I'm happy to award a 500 bounty for a solution anytime!


This is perhaps a somewhat silly observation, but can't you always find a non-monochromatic coloring with 3 colors?

First of all, if we can find a good coloring for any shift-chain with sets of size $k_0$, then we can find good colorings for any shift-chain with sets of size $k > k_0$, simply by taking the shift-chain that contains the lowest (or highest) $k_0$ elements of each of the sets. So it's enough to show the claim for $k=2$.

We can also assume that neighboring sets in the shift-chain differ by only one element that increases by one step (otherwise we can simply introduce intermediate sets).

So the case of $k=2$ can be thought of as alternating sequences of the higher element $b$ racing ahead and the lower element $a$ trying to catch up. Let us construct a coloring in a greedy way. The invariant is that there are always at most two colors in the interval $[a,b)$.

As long as $b$ increases, we keep its color constant. When $b$ reaches the point where it "rests" for a while, we have to do some case distinction. In the case where $a$ would catch up until it has the same color that $b$ used to have, we change the color of $b$ to the third available color (remember the invariant!). Thus there will be no monochromatic $\{a,b\}$ in the phase where $a$ tries to keep up. If $a$ does not reach the region where it would have the same color as $b$, then we keep $b$'s color the same even though it is waiting, so that the invariant is not violated when $b$ starts racing ahead again.

| cite | improve this answer | |
  • $\begingroup$ Yes, you are right. In fact, Rado also proved this, I don't know why they did not include it in the booklet, there you can find the statement that cyclic shift-chains are 5 colorable. Did you think about coming to the 2nd Emlektabla? $\endgroup$ – domotorp Nov 25 '10 at 7:53
  • $\begingroup$ Yes, but unfortunately it looks like I won't be able to make it since I'm already travelling for most of January. Perhaps next year (well, 2012, that is). $\endgroup$ – Nicolai Hähnle Nov 25 '10 at 9:10
  • $\begingroup$ We might have one on the summer as well. Then have a nice trip, see you in the spring hopefully. $\endgroup$ – domotorp Nov 25 '10 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.