\documentclass[11pt,reqno]{amsart} \usepackage{amssymb,mathtools} \usepackage{newtxtext,newtxmath} \usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue,pdfencoding=auto]{hyperref} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \numberwithin{equation}{section} \newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\R}{\mathbb R} \newcommand{\C}{\mathbb C} \newcommand{\Prb}{\mathbb P} \newcommand{\E}{\mathbb E} \newcommand{\NS}{\mathrm{NS}_{\omega_1}} \newcommand{\ZFC}{\mathrm{ZFC}} \newcommand{\Con}{\operatorname{Con}} \newcommand{\dd}{\,\mathrm d} \author{Will Howe} \email{howew@purdue.edu} \author{Grant Huffman} \email{huffma97@purdue.edu} \author{Jensen Kohlmeyer} \email{jenwin@purdue.edu} \author{Liam Kruer} \email{kruerl@purdue.edu} \date{November 17, 2026} \thanks{AI tools assisted with developing and checking arguments and with drafting this manuscript.} \emergencystretch=2em \setlength{\textwidth}{446.4bp} \setlength{\oddsidemargin}{\dimexpr82.8bp-1in\relax} \setlength{\evensidemargin}{\oddsidemargin} \addtolength{\topmargin}{-33.3bp} \addtolength{\textheight}{44.6bp} \hypersetup{pdfauthor={Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer},pdftitle={Relative Independence of the Simultaneous Chromatic Number at Aleph-1}} \title[Edge colorings and stationary sets]{Relative independence of the simultaneous chromatic number at \texorpdfstring{\(\aleph_1\)}{aleph-1}} \subjclass[2020]{Primary 03E35, 03E55. Secondary 03E05, 05C15.} \keywords{Erd\H{o}s problem, simultaneous chromatic number, stationary sets, saturated ideals} \begin{document} \begin{abstract} Let \(Q\) assert that every graph of chromatic number \(\aleph_1\) admits an edge coloring with palette \(\omega_1\) such that every countable partition of its vertices has a part whose induced edges realize the whole palette. Hajnal and Komj\'ath proved the relative consistency of \(Q\) by adding a Cohen real. We prove the relative consistency of \(\neg Q\) from one Woodin cardinal. In the negative model a single graph of chromatic number \(\aleph_1\) has the stronger property that every binary edge coloring admits a countable partition into parts with monochromatic induced edges. \end{abstract} \maketitle \section{Statement of the result} Write \(Q\) for the assertion in the abstract, with graphs allowed on arbitrary vertex sets. This is Erd\H{o}s Problem~1176 \cite{Bloom}. A set of vertices is called homogeneous for an edge coloring if its induced edges all have one color. An edgeless set is homogeneous for either binary color. \begin{theorem}\label{thm:independence} The relative consistency implications are \begin{align*} \Con(\ZFC)&\ \Longrightarrow\ \Con(\ZFC+Q),\\ \Con(\ZFC+\text{there is a Woodin cardinal}) &\ \Longrightarrow\ \Con(\ZFC+\neg Q). \end{align*} In the model of \(\neg Q\), there is a graph on a stationary subset of \(\omega_1\) of chromatic number \(\aleph_1\) such that every binary edge coloring permits a countable partition into homogeneous sets. \end{theorem} The positive implication is Theorem~1 of Hajnal and Komj\'ath \cite{HK}, applied with \(\kappa=\omega\). Its hypothesis \(\kappa^{<\kappa}=\kappa\) holds, and the theorem applies to graphs of chromatic number \(\kappa^+\) on arbitrary vertex sets in the Cohen extension. To prove the negative implication, we use Hoffelner's model \(W_0\) \cite[Sections~3.1--3.2.2 and Theorem~45]{Hof}. Starting with a Woodin cardinal, that construction supplies a model of \(\ZFC\) in which \(\NS\) is \(\aleph_2\)-saturated and remains saturated after ccc forcing. We give the ccc forcing and then extract the counterexample in its extension. \section{Finite conditions for a graph on \(\omega_1\)} We seek a graph \(G\) on \(\omega_1\) satisfying the following properties. \begin{enumerate} \item Every stationary \(X\subseteq\omega_1\) contains an edge of \(G\). \item For each map \(\rho:\omega_1\to\omega_1\) with \(\rho(\xi)<\xi\) at nonzero \(\xi\), the graph \(G_\rho\) consisting of the edges \(xy\) of \(G\) with \(\rho(x)\ne\rho(y)\) is countably chromatic. \item Every binary edge coloring of \(G\) has a stationary homogeneous set. \end{enumerate} The finite graph and homogeneous-set steps adapt the construction in \cite[Theorem~5]{HK}. A block family \(T\) in the ground model consists of finite sets \(A^T_\xi\) for \(\xi\in D_T\subseteq\omega_1\), with \(\min A^T_\xi=\xi\) and \(\max A^T_\xi<\eta\) whenever \(\xi<\eta\) are in \(D_T\). Put \[ D_T^{\mathrm{extra}}=\bigcup_{\xi\in D_T}(A^T_\xi\setminus\{\xi\}). \] This set is nonstationary. If \(D_T\) is unbounded, no extra point is a limit point of \(D_T\), whose limit points form a club. If \(D_T\) is bounded, it has only countably many finite blocks and their union is bounded. For any graph on \(\omega_1\) define \(H_T\) on \(D_T\) by placing an edge \(\xi\eta\) whenever there is a \(G\)-edge between the two blocks other than the possible edge between their minima. Such an edge of \(G\) has at least one endpoint in \(D_T^{\mathrm{extra}}\). In the initial forcing a condition is a triple \((s,g,a)\), where \(s\subseteq\omega_1\) is finite, \(g\) is a graph on \(s\), and \(a\) has finite domain of ground-model block families. For each \(T\) in that domain, \(a(T)\) is a finite partial map \(D_T\to\omega\). All blocks indexed in its domain lie in \(s\), and \(a(T)\) properly colors the extra-cross-edge graph on these blocks computed in \(g\). Strengthening extends \(g\) as an induced subgraph and extends all the partial maps. Adding new vertices isolated from the existing vertex set always gives an extension. Any desired block can be added in this way and assigned a fresh color. Hence the generic union gives a graph \(G\) on \(\omega_1\) and a total proper coloring \(a_T:D_T\to\omega\) of \(H_T\) for each ground-model family \(T\). Over the initial forcing take a finite-support iteration of length \(\lambda=(2^{\aleph_1})^V\). A stage treating a name for a regressive map \(\rho\) uses finite partial proper colorings of \(G_\rho\) into \(\omega\). A stage treating a name for a binary edge coloring \(F\) uses the trivial forcing if a stationary \(0\)-homogeneous set already exists. In the other case the stage is called active and uses finite \(1\)-homogeneous sets ordered by reverse inclusion. An unused stage is trivial. In a determined condition the preceding condition decides every finite coordinate value in use, including the active alternative at a homogeneous-set coordinate. At a regressive coordinate it also decides the regressive values at the finitely many vertices used. Every such vertex belongs to the initial vertex set \(s\). Determined conditions are dense, by induction on prefixes. At a successor, first decide the finite value, the applicable alternative, and any finitely many regressive values. Refine the preceding condition to a determined one. Add all vertices of the decided value to its initial graph as isolated new vertices. This strengthens the preceding condition and preserves its decisions. At a limit the finite support is bounded in an earlier prefix. We omit empty values from supports. \begin{lemma}\label{lem:ccc} Every prefix of this iteration, including the full forcing, satisfies the countable chain condition. \end{lemma} \begin{proof} In an uncountable family of determined conditions, thin the finite vertex sets, block-family supports and tail supports to delta systems. Let \(s_0\) be the vertex root. Thin further so the graph on \(s_0\) agrees throughout. For each shared block-family coordinate, require agreement on membership and color of every block meeting \(s_0\). There are only finitely many such blocks. At each shared tail coordinate require agreement on membership of each root vertex and its assigned natural color when the coordinate is a proper coloring. All these comparisons have only countably many patterns. For any two surviving conditions, use the union of their graphs, with no edge between the two vertex petals. A block included on only one side at a shared initial coordinate is disjoint from the vertex root. A pair of blocks newly brought together has no edge between them. The union of the two finite proper colorings is therefore valid there. At a shared tail coordinate the values agree on root vertices and their union only introduces comparisons across the petals. Those pairs are nonedges. At a coordinate present on one side use its original value. Induction through the finite union of the supports verifies that each assembled prefix strengthens both old prefixes and forces the corresponding constraints. The pair is compatible. \end{proof} \subsection{Bookkeeping and stationary witnesses} Block families and finite determined records admit codes from a universe of cardinality \(\lambda\). The ccc gives nice names for subsets of \(\omega_1\) with at most \(\aleph_1\) determined conditions in each name. Their supports are bounded below \(\lambda\), since \(\operatorname{cf}(2^{\aleph_1})>\aleph_1\) by K\"onig's theorem. There are at most \(\lambda^{\aleph_1}=\lambda\) such codes. Partition \(\lambda\) into \(\lambda\) pairwise disjoint cofinal sets and assign one to each code and stage kind. At a scheduled stage interpret the code if it is available in that prefix. Its final-model interpretation is available at all sufficiently late stages of its schedule. Both kinds of functions can be coded by subsets of \(\omega_1\), extending edge labelings arbitrarily to the nonedges for the purpose of coding. Invalid interpretations may be replaced by the constant-zero function. Consequently every final-model map or labeling is handled. At a proper-coloring stage any new vertex can receive a fresh natural color. At an active homogeneous stage and for any ground club \(C\), put a fresh vertex of \(C\) into a determined initial graph without incident edges to its old vertices. Extend the finite homogeneous set by that vertex. Thus the generic homogeneous set meets every ground club. Every club in a ccc extension contains a ground club, so the set is stationary. In the trivial alternative the existing stationary \(0\)-homogeneous set serves instead. The subsequent quotients are ccc, since the prefixes are complete suborders of the full ccc iteration. They preserve the stationarity of these witnesses. This proves properties 2 and 3. \section{Every stationary set contains an edge} Let \(p\) force that \(\dot X\) is stationary. There is a stationary ground set of \(\xi\) for which some determined \(p_\xi\le p\) forces \(\xi\in\dot X\) and has \(\xi\) in its initial vertex set. Otherwise a ground club avoiding all possible members would contradict the forced stationarity. On nonzero limit indices, press down a bound for the finite part of the initial vertex set below \(\xi\), then thin stationarily to make this part a fixed \(s_0\). Take a club closed under the maxima of the finite vertex sets. The remaining vertex sets have the form \(s_0\cup A_\xi\), where the \(A_\xi\) form a block family with minima \(\xi\). The corresponding stationary delta-system thinning for supports follows by injecting the union of those finite supports into \(\omega_1\), pressing down their coded initial parts, and using the same club closure. Make the agreements from Lemma~\ref{lem:ccc} on a stationary subset. At each common tail coordinate, thin further so that either every distinguished vertex \(\xi\) occurs in its finite value or none does. At a common regressive coordinate containing \(\xi\), press down the decided value \(\rho(\xi)\). On the resulting stationary index set \(I\) these values are constant at each such coordinate. Delete also the finitely many sets of extra points of the common block-family coordinates. The family \(T_*=(A_\xi:\xi\in I)\) is a ground block family, so the initial forcing already supplies \(a_{T_*}\). Suppose first that no common homogeneous coordinate contains both distinguished vertices of a pair from \(I\). Amalgamate two conditions as in Lemma~\ref{lem:ccc}, adding the single edge between their distinguished vertices. At a common block coordinate it cannot be an extra edge, since both endpoints avoided the extra points. At a common regressive coordinate containing both endpoints, the regressive values agree. A noncommon coordinate only uses old vertices from its own side. These facts, together with the assumption on homogeneous coordinates, prove that the new edge is permitted. Otherwise let \(\beta\) be the largest common homogeneous coordinate that contains the distinguished vertices. Consider the prefix before \(\beta\), with generic filter \(\mathcal G_\beta\), and set \[ U=\{\xi\in I : p_\xi\!\upharpoonright\!\beta\in\mathcal G_\beta\}. \] Some condition in that prefix forces \(U\) stationary. If the prefix forced \(U\) nonstationary, it would force a club disjoint from \(U\). By the ccc there would be a ground club forced contained in that club. For any \(\xi\) in its intersection with \(I\), the condition \(p_\xi\!\upharpoonright\!\beta\) forces \(\xi\in U\), a contradiction. In a prefix extension where \(U\) is stationary, take a stationary subset \(U'\subseteq U\) on which \(a_{T_*}\) is constant. There are no cross edges between the blocks of two members of \(U'\) except possibly the edge between their minima. The restrictions in the filter force that \(\beta\) is active. Hence \(U'\) has an edge \(\xi\eta\) with label \(1\) at that stage. Take a determined prefix condition in the filter extending both restrictions and deciding this edge, its label, and all the other cross pairs between the two finite petals as nonedges. Keep its entire prefix, and at \(\beta\) and later use the unions of the two original tail values. The designated edge is allowed at \(\beta\). Above \(\beta\), maximality protects every shared homogeneous coordinate. The equal regressive values protect the shared proper-coloring coordinates. Every other newly compared pair is a nonedge. Induction through the remaining finite support gives a joint extension, forcing \(\xi,\eta\in\dot X\) and \(\xi\eta\in E(G)\). This proves property 1. \section{Extracting a counterexample from saturation} Work in the final extension, where \(\NS\) remains saturated by \cite[Theorem~45]{Hof}. Since the forcing is ccc, its induced ground ideal is the actual nonstationary ideal. Any club witnessing nonstationarity in the extension contains a ground club. Property 1 implies that an induced graph on a stationary set has chromatic number \(\aleph_1\), since some part of any countable partition of that set is stationary. On the other hand, a nonstationary set has a countably chromatic induced graph. Choose a disjoint club containing \(0\), treating \(0\) separately if necessary. On the countable intervals between its consecutive points, the map to the left endpoint is regressive and separates distinct intervals. Property 2 colors the crossing edges countably. Separately inject each interval into \(\omega\) and pair the two colors. Let \(\mathcal I\) consist of the nonstationary sets and the stationary \(S\subseteq\omega_1\) admitting a binary edge coloring on \(G[S]\) with both colors occurring on every stationary subset of \(S\). Downward closure follows by restriction. For a countable union, disjointify in order and use the constituent witnessing colorings on the resulting pieces. Every stationary subset of the union meets some piece stationarily. For a diagonal union of \(\langle S_\xi:\xi<\omega_1\rangle\), index each point \(v\) by the least \(\xi