Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. 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 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.

share|improve this question
2  
Property B is more commonly called 2-colourability. –  Colin McQuillan Nov 12 '10 at 9:05
1  
@Colin McQuillan: I thought so too because I had never heard the name “Property B”. However, it seems that “Property B” is a common name in the literature. en.wikipedia.org/wiki/Property_B –  Tsuyoshi Ito Nov 12 '10 at 16:53
1  
I stand corrected. I have deleted my wrong answer as well. –  Colin McQuillan Nov 12 '10 at 21:30

2 Answers 2

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 c4c5. Similarly,

  • c3c4 by comparing the three hyperedges (345), (346), (347) and noticing a hyperedge (567).
  • c6c7 by comparing the three hyperedges (367), (467), (567) and noticing a hyperedge (345).
  • c5c6 by comparing the three hyperedges (567), (568), (569) and noticing a hyperedge (789).

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

share|improve this answer
1  
Very nicely put, the asker likes your proof. Thanks for writing it down! –  domotorp Nov 13 '10 at 8:52

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

share|improve this answer
    
You are right that if k is big enough compared to n, then the statement is true (e.g. k=n trivially). The problem is to prove that if k is bigger than some absolute constant, i.e. 4, then the statement is true for every n. –  domotorp Mar 8 '11 at 17:23
    
Ok, then just ignore the answer :) –  Marc Gillé Mar 8 '11 at 17:53

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.