Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.