Timeline for Chromatic number of the power set
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 7, 2013 at 13:41 | vote | accept | Dominic van der Zypen | ||
| Nov 7, 2013 at 13:41 | |||||
| Sep 19, 2012 at 16:30 | comment | added | Richard Stanley | 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. | |
| Sep 19, 2012 at 15:16 | comment | added | Clinton Conley | (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.) | |
| Sep 19, 2012 at 14:40 | comment | added | Clinton Conley | 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 | |
| Sep 19, 2012 at 13:22 | history | answered | Andreas Blass | CC BY-SA 3.0 |