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

Let $X$ be a non-empty set. Consider $\mathcal{P}(X)$, the power-set of $X$. We say that $a,b \in \mathcal{P}(X)$ form an edge if and only if their symmetric difference is a singleton, i.e. $\textrm{card}((a\setminus b) \cup (b\setminus a)) = 1$.

It is clear that for a finite set $X$ the resulting graph has chromatic number 2: color those subsets of $X$ with an even number of members with color 1, and the rest with color 2.

For $X$ infinite, does the resulting graph still have chromatic number 2?

share|cite|improve this question
Such a colouring implies that $\mathbb{N}$ isn't ``Ramsey'': see Proposition 29. – Colin McQuillan Sep 19 '12 at 9:39
up vote 4 down vote accepted

Yes, for $X$ infinite the resulting graph also has chromatic number 2. To see this, just use the fact that a graph is bipartite if and only if it does not contain an odd cycle (this remains true for infinite graphs). An odd cycle in your graph quickly leads to a contradiction due to parity reasons.

share|cite|improve this answer

The affirmative answers by Tony Huynh and Gjergji Zaimi are correct, but it may be worth noting that both depend on the axiom of choice. For example, although each of the components (as described in Gjergji's answer) is 2-colorable, it has (exactly) two 2-colorings, and you need to choose one, in each component, in order to 2-color the whole graph. In some models of set theory without choice, for example Solovay's model where all sets of reals are Lebesgue measurable, there is no way to make these choices and your graph (even for $X=\mathbb N$) is not 2-colorable. Even in the presence of the axiom of choice, so that your graph is 2-colorable, there may not be a definable 2-coloring, even allowing arbitrary ordinal numbers and arbitrary real numbers as parameters in the definition.

share|cite|improve this answer
Indeed, any independent set will be meager in the product topology, and null with respect to say the product (1/2,1/2) measure, so with such a measurability constraint you can't even color this graph with countably many colors – Clinton Conley Sep 19 '12 at 14:40
(In the previous comment, I had intended for the "measurability constraint" to apply to the first part of the statement. Since that's not actually how English works, let me be more precise. Any independent set with the property of Baire will be meager, and any independent set which is $(1/2,1/2)^\mathbb{N}$-measurable will be null.) – Clinton Conley Sep 19 '12 at 15:16
Let me mention the following result of Shelah and Soifer ( Let $G$ be the graph whose vertices are the real numbers. Two vertices $s$ and $t$ are adjacent if $s-t-\sqrt{2}$ is a rational number. It is easy to see that all cycles of $G$ have even length. Assuming ZFC, $G$ has chromatic number 2. Assuming just ZF, the chromatic number of $G$ is uncountable. – Richard Stanley Sep 19 '12 at 16:30

Your graph is going to be disconnected. Every connected component is a graph with vertices having finite symmetric difference with respect to some base set. Once you observe this, you can still use the parity argument, and split the sets according to whether they differ from the base set on an even or odd number of places.

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.