Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

My apologies for asking so many questions recently.

Let $0\le c<d<e$ be fixed natural numbers and consider any graph on $2e$ vertices, with the vertices labelled as $0,1,\cdots 2e-1$. I want to color the vertices red and blue so that the following property holds:

For any vertex $u$, if $u$ is colored red then for any $x,y,z$ such that $\{x,y,z\}=\{c,d,e\}$ at least one amongst $u+x-y$ or $u+z-y$ (assuming it makes sense as a vertex) is colored blue. Likewise if $u$ is colored blue then for any $x,y,z$ such that $\{x,y,z\}=\{c,d,e\}$ at least one amongst $u+x-y$ or $u+z-y$ is colored red. Basically I want that the set $\{u,u+x-y,u+z-y\}$ should not be monochromatic.

How can I get such a vertex coloring? Is it impossible to get such a coloring? (I don't know.)

I'll be grateful for any suggestions or comments.

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

I asked the question on mathoverflow and got the answer: The given problem is equivalent to $2$-coloring a hypergraph on $2e$ vertices where each hyperedge is given by $\{c+v,d+v,e+v\}$, where $0\le v\le e-1$. Considering the bipartite graph obtained by removing $d+v$ from each hyperedge we immediately see that the hypergraph is $2$-colorable.

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.