[web](https://www.assafrinot.com/paper/17) [file](<file:///home/ur/Dropbox/Papers/rinot/17 Rinot - Same graph different universe.pdf>) **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 Gödel’s constructible universe, for every uncountable cardinal $μ$ below the first fixed-point of the $ℵ$-function, there exists a graph $G_{\mu}$ satisfying the following: • $G_{\mu}$ has size and chromatic number $μ$; • for every infinite cardinal $κ < μ$, there exists a cofinality-preserving GCH- preserving forcing extension in which $\mathrm{Chr}(G_{\mu} ) = κ.$ # 1. Introduction ![[Coloring graphs#Definitions]] **Fact.** Let $\phi$ be the first such that $\phi=\aleph_{\phi}$.Then for every infinite cardinal $μ$: $\mu < \phi$ iff the interval of cardinals $[ℵ_{0} , μ)$ may be partitioned into finitely many progressive sets, that is, $\mathrm{Card}[ℵ_{0} , μ) = a_0 \cup. . .\cup a_m$, disjoint union, with $\mathrm{min}(a_i) > |a_i |$ for all $i ≤ m$. ## 2. Preliminaries **Proposition 2.1** [[Hajnal, Komjáth - Embedding graphs into colored graphs]] Suppose that $κ^{<κ} = κ$ is cardinal satisfying $2^κ = κ^+$ . Then there exists $E ⊆ [κ^+ ]^2$ and a notion of forcing $Q$ such that: • $\mathrm{Chr}(κ^+ , E) = κ^+$ ; • $\Vdash_Q \mathrm{Chr}(κ^+ , E) = κ$; • $Q$ is (lt; κ$)-[[Directed closed]] and $κ^+$-cc; • $Q$ has size $κ^+$ . **Corollary 2.2.** CH entails a subset $E_1 ⊆ [ω_1 ]^2$ and a poset $Q_1$ such that: • $Chr(ω_1 , E_1 ) = ω_1$ ; • $Q_1 \Vdash Chr(ω_1 , E_1 ) = ω$; • $Q_1$ is absolutely ccc; • $Q_1$ has size $ℵ_1$. ^41c9cc >[!remark] >These are buttons for ccc forcing ## Main theorem **Theorem 1**. ($V=L$) For every uncountable cardinal $μ$ below the first fixed-point of the $ℵ$-function, there exists a graph $G_{\mu}$ satisfying the following: • $G_{\mu}$ has size and chromatic number $μ$; • for every infinite cardinal $κ < μ$, there exists a cofinality-preserving GCH- preserving forcing extension in which $\mathrm{Chr}(G_{\mu} ) = κ.$ ### General idea For every cardinal $\lambda<\mu$ define (pg. 791) a graph $(G^{\lambda},E^{\lambda})$ such that - $\mathrm{Chr}(G^{\lambda},E^{\lambda})=\lambda ^{+}$ (Lemma 3.2) - There is a forcing $Q_{\lambda}$ (after lemma 3.4) which forces $\mathrm{Chr}(G^{\lambda},E^{\lambda})\leq\aleph_{0}$. Then take the graph $\mathcal{G}_{\mu}$ to be the disjoint sum of the above and the forcing to be appropriate products. **Lemma.** $Q_{\lambda}$ has the following properties (from lemma 3.7) - Size $\lambda^{+}$ - $\lambda$-distributive - preserves cofinalities - preserves the GCH If we take products, cofinalities and GCH are preserved, the size is as the largest, distributivity as the smallest. >[!note] Remark >The construction is very involved, using specific types of coherent sequences from [[Brodsky, Rinot - A Microscopic approach to Souslin-tree constructions. Part I]] and uses proofs from [[Rinot - Chromatic numbers of graphs - large gaps]] >[!note] Notation >Let $\phi$ denote the first fixed-point of the $\aleph$-function. > Let $\Phi: \mathrm{Card}\rightarrow \mathrm{Card}$ be the class function $\Phi(\mu):=\left|\operatorname{Card}[0, \mu)\right|^{+}$. > > Note that $\Phi \upharpoonright \operatorname{Card}\left(\aleph_1, \aleph_\phi\right)$ is a regressive map.