Abstract. May the same graph admit two different chromatic numbers in two different universes? how about infinitely many different values? and can this be achieved without changing the cardinals structure?
In this paper, it is proved that in Godel’s constructible universe, for every uncountable cardinal $\lambda$ below the first fixed-point of the $\aleph$-function, there exists a graph $\mathcal G_\lambda$ satisfying the following:
- $\mathcal G_\lambda$ has size and chromatic number $\lambda$;
- for every infinite cardinal $\kappa<\lambda$, there exists a cofinality-preserving, GCH-preserving forcing extension in which $\text{chr}(\mathcal G_\lambda)=\kappa$.
Downloads:
![[No arXiv entry]](/design/002_arxiv_dis.png "No arXiv entry") |
Citation information:
A. Rinot, Same Graph, Different Universe, Arch. Math. Logic, 56(7-8): 783-796, 2017.
Same same, but different.
Exactly!
This reminds me of some theorems of Shelah and Soifer (in “Axiom of choice and chromatic number: examples on the plane.”) where they construct a graph that has different chromatic numbers depending on the truth of AC.
There are also some survey articles about this. Like this one by MS Payne.
http://arxiv.org/pdf/0707.1177.pdf
Thanks, Mike! How cool is that! I’ll incorporate this info to the paper (maybe tomorrow).
p.s.
The fact that chromatic numbers are sensitive to the axiom of choice is also witnessed by this curious theorem of Galvin and Komjath.
A new version that discusses work as of Shelah-Soifer has been uploaded. Thanks again, Mike!
Submitted to the special issue in memory of Jim Baumgartner, November 2014.
Accepted, September 2015.
I notice that neither your paper nor the blog is aware of the graph $G_0$ of Kechris-Solecki-Todorcevic (1999). This graph is acyclic but it has uncountable Baire-chromatic number.
The study of Borel chromatic numbers in general, and the minimal graph $G_0$ are very interesting, but this particular paper does not concentrate on this line of study. I only gave one quick-and-simple example in this vein to demonstrate the role of the axiom of choice in the study of chromatic numbers, and to stress that I will only be interested in ZFC extensions of L.
Since you already happened to glance over the paper, let me mention that it is open whether the fixed point limitation in the statement of the main theorem may be waived.
The graph $G_0$ is put forward to your blog because you got excited by the result of Shelah and Soifer which studies the effect of the axiom of choice on the value of a given graph. The earlier paper KST1999 gives the right mathematical explanation of this phenomenon and moreover gives also two universes in which the same graph has different chromatic numbers, the universes that could be built on the basis of the consistency of ZFC rather than ZFC plus an inaccessible.