2-colouring shift-chains

Source abstract

A shift-chain is an $r$-uniform hypergraph $\mathcal{H}$ on vertex set $[n]$ with the property that, for any two edges $\{ e_1, \ldots, e_r \}$ and $\{ f_1, \ldots, f_r \}$ with $e_1 < \cdots < e_r$ and $f_1 < \cdots < f_r$, either $e_i \le f_i$ for all $i \in [r]$ or $f_i \le e_i$ for all $i \in [r]$. It is known that all shift-chains are properly vertex-colourable with three colours (that is, such that no edge is monochromatic), which is optimal for $r \in \{ 2, 3 \}$. It was asked by Pálvölgyi in 2010 whether all shift-chains of sufficiently large uniformity are properly $2$-colourable. We answer this question in a strong form, proving that in fact all shift-chains of uniformity at least $4$ are properly $2$-colourable. The colouring is obtained via a natural algorithm with linear running time.