<p>This is not an answer.  What follows is a simple proof that the construction for <i>k</i>=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 <i>k</i>.</p>

<p>It is easy to verify that it is a shift-chain.  Let’s show that it does not have Property B.</p>

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

<ul>
<li><i>c</i><sub>3</sub>≠<i>c</i><sub>4</sub> by comparing the three hyperedges (345), (346), (347) and noticing a hyperedge (567).</li>
<li><i>c</i><sub>6</sub>≠<i>c</i><sub>7</sub> by comparing the three hyperedges (367), (467), (567) and noticing a hyperedge (345).</li>
<li><i>c</i><sub>5</sub>≠<i>c</i><sub>6</sub> by comparing the three hyperedges (567), (568), (569) and noticing a hyperedge (789).</li>
</ul>

<p>Therefore, we have <i>c</i><sub>3</sub>≠<i>c</i><sub>4</sub>≠<i>c</i><sub>5</sub>≠<i>c</i><sub>6</sub>≠<i>c</i><sub>7</sub>.  But this implies <i>c</i><sub>3</sub>=<i>c</i><sub>5</sub>=<i>c</i><sub>7</sub>, making the hyperedge (357) monochromatic.  This contradicts the assumption of the 2-coloring.</p>

CC BY-SA 2.5
2010-11-13T08:52:06.000Z
Very nicely put, the asker likes your proof. Thanks for writing it down!
domotorp
CC BY-SA 2.5
2010-11-13T02:17:22.137Z
2010-11-13T02:17:22.137Z
Tsuyoshi Ito
<p>Perhaps I'm missing something but I think there is a good lower bound with the probabilistic method:</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma" rel="nofollow">Lovasz local lemma</a> 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).</p>

<p>There is a <a href="http://onlinelibrary.wiley.com/doi/10.1002/%28SICI%291098-2418%28200001%2916:1%3C4%3a%3aAID-RSA2%3E3.0.CO;2-2/abstract;jsessionid=92159B653F14ABD058BA1095562D614F.d01t02" rel="nofollow">better bound</a> 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$. </p>

CC BY-SA 2.5
2011-03-08T17:23:20.520Z
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
CC BY-SA 2.5
2011-03-08T17:53:29.937Z
Ok, then just ignore the answer :)
Marc Bury
CC BY-SA 2.5
2011-03-08T09:14:49.037Z
2011-03-08T09:14:49.037Z
Marc Bury
<p>For <span class="math-container">$A\subset [n]$</span> denote by <span class="math-container">$a_i$</span> the <span class="math-container">$i^{th}$</span> smallest element of <span class="math-container">$A$</span>.</p>

<p>For two <span class="math-container">$k$</span>-element sets, <span class="math-container">$A,B\subset [n]$</span>, we say that <span class="math-container">$A\le B$</span> if <span class="math-container">$a_i\le b_i$</span> for every <span class="math-container">$i$</span>.</p>

<p>A <span class="math-container">$k$</span>-uniform hypergraph <span class="math-container">${\mathcal H}\subset [n]$</span> is called a <em>shift-chain</em> if for any hyperedges, <span class="math-container">$A, B \in {\mathcal H}$</span>, we have <span class="math-container">$A\le B$</span> or <span class="math-container">$B\le A$</span>. (So a shift-chain has at most <span class="math-container">$k(n-k)+1$</span> hyperedges.)</p>

<p>We say that a hypergraph  <span class="math-container">${\mathcal H}$</span> is two-colorable (or that it has Property B) if we can color its vertices with two colors such that no hyperedge is monochromatic.</p>

<p>Is it true that shift-chains are two-colorable if <span class="math-container">$k$</span> is large enough?</p>

<p><strong>Remarks.</strong> I first posted this problem on <a href="https://mathoverflow.net/questions/44312/do-shift-chain-have-property-b">mathoverflow</a>, but nobody commented on it.</p>

<p>The problem was investigated on the 1st Emlektabla Workshop for some partial results, see the <a href="http://www.renyi.hu/~emlektab/index_booklet.html" rel="nofollow noreferrer">booklet</a>.</p>

<p>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 <a href="http://www.cs.elte.hu/~dom/cikkek/thesis.pdf" rel="nofollow noreferrer">PhD thesis</a>.)</p>

<p>For <span class="math-container">$k=2$</span> there is a trivial counterexample: (12),(13),(23).</p>

<p>A very magical counterexample was given for <span class="math-container">$k=3$</span> by Radoslav Fulek with a computer program:</p>

<p>(123),(124),(125),(135),(145),(245),(345),(346),(347),(357),</p>

<p>(367),(467),(567),(568),(569),(579),(589),(689),(789).</p>

<p>If we allow the hypergraph to be the union of two shift-chains (with the same order), then there is a counterexample for any <span class="math-container">$k$</span>.</p>

<p><strong>Update.</strong> I have recently managed to show that more restricted version of shift-chains are two-colorable in <a href="http://arxiv.org/abs/1310.6900v1" rel="nofollow noreferrer">this preprint</a>.  </p>

<p><strong>Permanent bounty!</strong> I'm happy to award a 500 bounty for a solution anytime!</p>

CC BY-SA 2.5
2010-11-12T09:05:16.667Z
Property B is more commonly called 2-colourability.
Colin McQuillan
CC BY-SA 2.5
2010-11-12T16:53:50.813Z
@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.  http://en.wikipedia.org/wiki/Property_B
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-12T21:30:46.053Z
I stand corrected. I have deleted my wrong answer as well.
Colin McQuillan
<co.combinatorics><graph-colouring><hypergraphs>
Are shift-chains two-colorable?
domotorp
# Are shift-chains two-colorable?

(Asked by: username_0 on 2010-11-12)

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](https://mathoverflow.net/questions/44312/do-shift-chain-have-property-b), but nobody commented on it.

The problem was investigated on the 1st Emlektabla Workshop for some partial results, see the [booklet](http://www.renyi.hu/~emlektab/index_booklet.html).

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](http://www.cs.elte.hu/~dom/cikkek/thesis.pdf).)

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](http://arxiv.org/abs/1310.6900v1).

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

**Tags:** co.combinatorics, graph-colouring, hypergraphs
> **Comments:**
> **username_1**: Property B is more commonly called 2-colourability.  
> **username_2**: @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.  http://en.wikipedia.org/wiki/Property_B  
> **username_1**: I stand corrected. I have deleted my wrong answer as well.  

---

## 2 answers

### Answer by username_2 on 2010-11-13. Score: 13

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*4=*c*5, then all of 1, 2 and 3 must be the opposite color to *c*4, but this would give a monochromatic hyperedge (123). Therefore, it must be the case that *c*4≠*c*5. Similarly,

* *c*3≠*c*4 by comparing the three hyperedges (345), (346), (347) and noticing a hyperedge (567).
* *c*6≠*c*7 by comparing the three hyperedges (367), (467), (567) and noticing a hyperedge (345).
* *c*5≠*c*6 by comparing the three hyperedges (567), (568), (569) and noticing a hyperedge (789).

Therefore, we have *c*3≠*c*4≠*c*5≠*c*6≠*c*7. But this implies *c*3=*c*5=*c*7, making the hyperedge (357) monochromatic. This contradicts the assumption of the 2-coloring.

> **Comments:**
> **username_0**: Very nicely put, the asker likes your proof. Thanks for writing it down!  

---

### Answer by username_3 on 2011-03-08. Score: 1

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](http://en.wikipedia.org/wiki/Lov%C3%A1sz_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](http://onlinelibrary.wiley.com/doi/10.1002/%28SICI%291098-2418%28200001%2916:1%3C4%3a%3aAID-RSA2%3E3.0.CO;2-2/abstract;jsessionid=92159B653F14ABD058BA1095562D614F.d01t02) 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$.

> **Comments:**
> **username_0**: 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.  
> **username_3**: Ok, then just ignore the answer :)  

---

