2
$\begingroup$

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?

Improve this question
$\endgroup$
1

3 Answers 3

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – Clinton Conley
    Commented Sep 19, 2012 at 14:40
  • $\begingroup$ (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.) $\endgroup$
    – Clinton Conley
    Commented Sep 19, 2012 at 15:16
  • 2
    $\begingroup$ Let me mention the following result of Shelah and Soifer (shelah.logic.at/files/E33.pdf). 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. $\endgroup$
    – Richard Stanley
    Commented Sep 19, 2012 at 16:30
4
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .