most recent 30 from http://mathoverflow.net 2013-05-19T14:37:49Z http://mathoverflow.net/feeds/question/108711 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/108711/hypergraph-coloring Shahab 2012-10-03T15:04:11Z 2012-10-04T07:23:46Z

<p>I am investigating whether the following hypergraph is $2$-colorable.</p> <p>Let $0\le c &lt; d &lt; 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?</p> <p>I'll be grateful for any suggestions or comments.</p>

http://mathoverflow.net/questions/108711/hypergraph-coloring/108724#108724 Ilya Bogdanov 2012-10-03T17:16:21Z 2012-10-04T07:23:46Z

<p>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.</p> <p>Surely this works for any bound instead of $2e-1$.</p> <p><b>EDIT.</b> Even simpler: just erase $v+d$ from each edge $\{v+c,v+d,v+e\}$. The remaining graph is obviously bipartite.</p>