MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.