Question

I am investigating whether the following hypergraph is $2$-colorable.

Let $0\le c < d < e$ be fixed natural numbers and consider a graph on $2e$ vertices, with the vertices labelled as $0,1,\cdots 2e-1$. For every vertex $u$, whenever $u+x-y$ and $u+z-y$ make sense as a vertex and $x,y,z$ are such that $\{x,y,z\}=\{c,d,e\}$, there is a hyperedge $\{u,u+x-y,u+z-y\}$. Is this graph $2$-colorable? If so, how can I construct a $2$-coloring?

I'll be grateful for any suggestions or comments.

Answer 1

As far as I understand, your hyperedges are of the form $\{v+c,v+d,v+e\}$ for all suitable $v$. Hence you can just color the vertices from the left to the right. Color the vertices $u\leq e-c-1$ as you wish; then, when you consider some further vertex $u\geq e-c$, there is exactly one edge with the maximal element $u$; so you can color $u$ so that this edge is multichromatic. Proceeding in this way, you will finish with no troubles; each edge was considered on some step, so it is not monochromatic.

Surely this works for any bound instead of $2e-1$.

EDIT. Even simpler: just erase $v+d$ from each edge $\{v+c,v+d,v+e\}$. The remaining graph is obviously bipartite.