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:



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!

  • 2
    $\begingroup$ Property B is more commonly called 2-colourability. $\endgroup$ Nov 12 '10 at 9:05
  • 1
    $\begingroup$ @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 $\endgroup$ Nov 12 '10 at 16:53
  • 2
    $\begingroup$ I stand corrected. I have deleted my wrong answer as well. $\endgroup$ Nov 12 '10 at 21:30

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.

  • 3
    $\begingroup$ Very nicely put, the asker likes your proof. Thanks for writing it down! $\endgroup$
    – 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$.

  • 2
    $\begingroup$ 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. $\endgroup$
    – domotorp
    Mar 8 '11 at 17:23
  • $\begingroup$ Ok, then just ignore the answer :) $\endgroup$
    – Marc Bury
    Mar 8 '11 at 17:53

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.