Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

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.

share|improve this answer
    
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? –  domotorp Nov 25 '10 at 7:53
    
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). –  Nicolai Hähnle Nov 25 '10 at 9:10
    
We might have one on the summer as well. Then have a nice trip, see you in the spring hopefully. –  domotorp Nov 25 '10 at 14:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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