2-colouring shift-chains

Zak Smith

In the authors' words

A shift-chain is an $r$ -uniform hypergraph $H$ on vertex set $[n]$ with the property that, for any two edges ${e_{1}, \dots, e_{r}}$ and ${f_{1}, \dots, f_{r}}$ with $e_{1} < \dots < e_{r}$ and $f_{1} < \dots < f_{r}$ , either $e_{i} \leq f_{i}$ for all $i \in [r]$ or $f_{i} \leq 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\'alv\"olgyi 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.

Main resultThe abstract does not state a limitation.

2-colouring shift-chains

In the authors' words

More on Combinatorics & discrete math that day

Breaking the Infinite Barrier in the 31​--32​ Conjecture

Proof of the Kahn Saks Conjecture

The Kelly--Trotter conjecture and dimension of poset products

Greedy queens and the golden ratio

Discounted Hitting Domination on Graphs with Submodularity, Complexity and Exact Algorithms

Breaking the Infinite Barrier in the $\frac{1}{3}$ -- $\frac{2}{3}$ Conjecture