\documentclass[11pt,reqno]{amsart} \usepackage{amssymb,mathtools} \usepackage{newtxtext,newtxmath} \usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue,pdfencoding=auto]{hyperref} \title[A finite-color partition relation for \texorpdfstring{$\omega_1^2$}{omega-one squared}] {A finite-color partition relation for \texorpdfstring{$\omega_1^2$}{omega-one squared}} \author{Will Howe} \email{\href{mailto:howew@purdue.edu}{\textcolor{black}{howew@purdue.edu}}} \author{Grant Huffman} \email{\href{mailto:huffma97@purdue.edu}{\textcolor{black}{huffma97@purdue.edu}}} \author{Jensen Kohlmeyer} \email{\href{mailto:jenwin@purdue.edu}{\textcolor{black}{jenwin@purdue.edu}}} \author{Liam Kruer} \email{\href{mailto:kruerl@purdue.edu}{\textcolor{black}{kruerl@purdue.edu}}} \date{November 11, 2026} \subjclass[2020]{Primary 03E02. Secondary 05D10.} \keywords{Ordinal partition relations, Ramsey theory, Cohen forcing, Baire category} \thanks{The authors acknowledge the assistance of OpenAI's Codex and AI research agents in developing and checking the argument and preparing the manuscript.} \emergencystretch=2em \setlength{\textwidth}{446.4bp} \setlength{\oddsidemargin}{\dimexpr82.8bp-1in\relax} \setlength{\evensidemargin}{\oddsidemargin} \addtolength{\topmargin}{-33.3bp} \addtolength{\textheight}{44.6bp} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \numberwithin{equation}{section} \DeclareMathOperator{\row}{row} \newcommand{\stock}{$B$-stock} \newcommand{\stocks}{$B$-stocks} \allowdisplaybreaks[1] \hypersetup{ pdftitle={A finite-color partition relation for omega-one squared}, pdfauthor={Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer}, pdfsubject={A ZFC proof of Erdos problem 1171} } \begin{document} \begin{abstract} We prove in ZFC that \[ \omega_1^2 \longrightarrow \bigl(\omega_1\cdot\omega,\underbracket[.45pt][1.7pt]{3,\ldots,3}_{k}\bigr)^2_{k+1} \qquad (k<\omega), \] answering Erd\H{o}s problem~1171. Under a Baire category hypothesis, a branch through a countable tree of reservoirs enables an induction on the positive colors. We then show that Cohen forcing supplies the category hypothesis and that a homogeneous set of order type \(\omega_1\cdot\omega\) in a ground-model coloring reflects to the ground model. \end{abstract} \maketitle \section{Introduction} The binary case of the partition relation below is due to Erd\H{o}s and Hajnal~\cite{EH71}, and the case of two positive colors is due to Baumgartner and Hajnal~\cite{BH87}. Under \(\mathrm{MA}(\aleph_1)\), Baumgartner proved \(\omega_1\cdot\omega\to(\omega_1\cdot\omega,3)^2\)~\cite{B89}. Applying that relation to each positive color in turn gives the finite-color conclusion under the same hypothesis. The question for arbitrary finite palettes in ZFC appears as problem~7.84 in the 1999 booklet \emph{Some of Paul's Favorite Problems}~\cite{Va99} and as problem~1171 in Bloom's catalogue~\cite{E1171}. See Komj\'ath \cite[pp.~442--443]{Komjath} for a discussion of the small palettes. \begin{theorem}\label{thm:main} For every \(k<\omega\), every coloring \(c:[\omega_1^2]^2\to\{0,1,\ldots,k\}\) has a color-\(0\) homogeneous set of inherited order type \(\omega_1\cdot\omega\), or a monochromatic triangle in one of the colors \(1,\ldots,k\). \end{theorem} The proof first reduces to colorings whose positive edges satisfy a condition on the row and column coordinates. A category argument then produces a color-\(0\) set in these colorings. The final step transfers this conclusion from a Cohen extension to the ground model. \section{Rows and the reduction to nested edges}\label{sec:rows} Put \(\Omega=\omega_1^2\) and \(B=\omega_1\cdot\omega\). Write \((a,\alpha)\) for the point \(\omega_1 a+\alpha\), where \(a,\alpha<\omega_1\). The row of this point is \(a\), and its column is \(\alpha\). Thus the ordinal order on \(\Omega\) is lexicographic, with the row compared first. A \emph{thick slice} is an uncountable subset of one row. A \emph{\stock} is a union of thick slices in a strictly increasing sequence of rows of length \(\omega\). For distinct points \(x,y\), write \(c(x,y)=c(\{x,y\})\). A set contains an inherited copy of \(B\) if and only if it has infinitely many thick rows. In that case its first \(\omega\) thick rows give a \stock, since every thick slice has order type \(\omega_1\). For the converse, suppose it has exactly \(m<\omega\) thick rows. All rows before or between those thick rows contribute countable order types, which are absorbed by the following thick slice. The remaining tail is an \(\omega_1\)-sum of countable order types, of order type at most \(\omega_1\). Thus the set has order type at most \(\omega_1(m+1)\gamma\).} \end{equation} A row set outside \(J\) is \(J\)-positive. On a substock whose row set \(S\) is \(J\)-positive, the restriction \(J\!\upharpoonright S=\{E\subseteq S:E\in J\}\) is proper. Restriction to such a substock preserves \eqref{eq:marks}, since thinning cannot enlarge any mark set on the retained rows. Data satisfying \eqref{eq:marks} cannot have \(L=K\). To see this, take a point \(y\in X\) above \(\gamma\) and outside the countable union of the exceptions from Lemma~\ref{lem:incidence} for the slices of \(A\). Every slice contains uncountably many positive neighbors of \(y\), so in every row some positive color has a thick fiber. Thus \(R(A)=\bigcup_{\ell\in K}M_\ell(A,y)\in J\), contradicting properness. We prove by induction on \(r\le k\) that every full \(Y\subseteq X\) contains a \stock{} with data satisfying \eqref{eq:marks} and \(|L|\ge r\). For \(r=0\), choose any \stock{} in \(Y\), take \(J\) to be the ideal of finite sets, and let \(L=\varnothing\). We give the induction step in three parts. \medskip \noindent\textit{A countable tree of reservoirs.} Assume the assertion for \(r\) and fix a full \(Y\subseteq X\). The root reservoir is \(Y\). At each node \(s\) choose, in its full reservoir \(Y_s\), a stock \(A_s\) and data \(J_s,L_s,\gamma_s\) given by the induction hypothesis. For each \(a\in R(A_s)\) set \begin{equation}\label{eq:child} C_{s,a}=\bigl\{y\in Y_s:\row(y)>\gamma_s,\ a\notin M_\ell(A_s,y)\ \text{for all }\ell\in L_s\bigr\}. \end{equation} If \(C_{s,a}\) is full, include a child indexed by \(a\) with that reservoir. The row index distinguishes children even when their reservoirs coincide. Each level is countable and there are only countably many levels. Along a branch, every stock lies above the preceding stock's cutoff. Choose \(\gamma_*<\omega_1\) bounding all the \(\gamma_s\). From the full tail of \(Y\) above \(\gamma_*\), exclude all nonfull classes \(C_{s,a}\) and all the exceptional sets in Lemma~\ref{lem:incidence} for the slices of all \(A_s\). These are countably many small sets. Fix a point \(h\) that remains. At a node \(s\) with \(h\in Y_s\), the rows on which every color in \(L_s\) is thin at \(h\) form a \(J_s\)-positive set. Its complement is a finite union of sets in \(J_s\). On each of these rows, some color in \(K\setminus L_s\) is thick at \(h\), because \(h\) has uncountably many positive neighbors in each slice and \(K\) is finite. Since \(J_s\) is closed under finite unions, there is some \(i_s\in K\setminus L_s\) for which the set \(D_s\) of rows having both properties is \(J_s\)-positive. For every \(a\in D_s\) we have \(h\in C_{s,a}\), and \(C_{s,a}\) is full by the choice of \(h\). Starting at the root, keep just these children. The resulting tree branches countably infinitely at every node, since the finite sets belong to \(J_s\). Enumerating the children at each node identifies its branch space, with the cylinder topology, with \(\omega^\omega\). \medskip \noindent\textit{A branch meeting all finite requirements.} A node \(s\) has type \((L_s,i_s)\). For any finite set \(F\subseteq X\) of points above \(\gamma_*\), at each node \(s\) one can choose a row in \(D_s\) on which all fibers at points of \(F\) in colors in \(L_s\) are thin. Indeed, the union of the mark sets \(M_\ell(A_s,y)\) for \(y\in F\), \(\ell\in L_s\), belongs to \(J_s\) by \eqref{eq:marks}, whereas \(D_s\) is \(J_s\)-positive. For each such \(F\), each type \(\tau\), and each \(n<\omega\), impose the following requirement on a branch. At a node of type \(\tau\) of depth at least \(n\), it chooses a row with all these fibers thin, or it has a prefix with no extension node of type \(\tau\) at depth at least \(n\). Here an extension may be the prefix itself. Both alternatives are witnessed by finite prefixes, so the requirement is open. It is dense because from any given prefix we can extend to a node of the specified type and depth and make the required choice, if such a node exists. If none exists, the prefix already witnesses the second alternative. There are at most \(\aleph_1\) requirements because \(X\) has cardinality \(\aleph_1\) and there are finitely many types. The category hypothesis gives a branch meeting all of them. For any type occurring infinitely often along this branch, the second alternative is impossible. Hence for every finite \(F\) as above, the branch makes the simultaneous thin choice at arbitrarily late occurrences of that type. \medskip \noindent\textit{Increasing the set of marked colors.} Choose a type \((L,i)\) that occurs infinitely often on this branch. At each occurrence take, in its chosen row, the thick \(i\)-fiber at \(h\). These slices form a \stock{} in \(Y\). Its vertices are all \(i\)-neighbors of \(h\), so it contains no \(i\)-edge. For a retained slice chosen at node \(s\) in row \(a\), every vertex of a later retained slice lies in \(C_{s,a}\). Thus \eqref{eq:child} gives countable backward degrees into the earlier slice for every color in \(L\). Nesting gives countable forward degrees into each later slice. Apply Lemma~\ref{lem:thinning} to remove all cross edges in colors from \(L\). Denote the resulting \stock{} by \(A\). Its positive internal colors lie in \(K\setminus(L\cup\{i\})\). For every finite \(F\subseteq X\) above \(\gamma_*\), there are infinitely many rows of \(A\) outside all \(M_\ell(A,y)\) with \(y\in F\) and \(\ell\in L\). These are rows at which the branch made the simultaneous thin choice, a property preserved by taking subsets of the slices. Let \(J\) be the ideal on \(R(A)\) generated by the finite sets and all \(M_\ell(A,y)\) for \(\ell\in L\) and \(\row(y)>\gamma_*\). Every finite union of generators has infinite complement, so \(J\) is proper. Among the substocks of \(A\) on \(J\)-positive row sets choose one, \(A'\), with the fewest positive internal colors. Write \(P\) for its positive palette and \(J'=J\!\upharpoonright R(A')\). Any substock of \(A'\) on a \(J'\)-positive row set uses every color of \(P\), by minimality. Also \(P\ne\varnothing\), since otherwise \(A'\) is color-\(0\) homogeneous. For \(p\in P\) and \(y\in X\) above \(\gamma_*\), suppose \(M_p(A',y)\notin J'\). The thick \(p\)-fibers at \(y\) in those rows form a substock on a \(J'\)-positive row set. It contains no \(p\)-edge, by triangle exclusion. This contradicts minimality, so \(M_p(A',y)\in J'\). The mark condition therefore holds on \(A'\) for \(L\cup P\) with cutoff \(\gamma_*\). Since \(P\) is nonempty and disjoint from \(L\), we have \(|L\cup P|\ge r+1\). This completes the induction. At \(r=k\) we obtain data with \(L=K\), which was shown to be impossible. \end{proof} \section{Cohen forcing and reflection}\label{sec:forcing} For an index set \(I\), let \(\mathbb P_I\) consist of finite partial functions \(I\times\omega\to\omega\), ordered by extension, with a larger function a stronger condition. By the finite \(\Delta\)-system lemma, every uncountable family of conditions contains an uncountable subfamily whose domains form a \(\Delta\)-system and whose conditions agree on its root. If one domain occurs uncountably often, restrict to that domain and then to a common assignment. Otherwise choose uncountably many distinct domains, form a \(\Delta\)-system, and restrict to a common assignment on its finite root. In either case, the subfamily is pairwise compatible. In particular, \(\mathbb P_I\) is ccc and preserves \(\omega_1\) and \(\omega_2\). \begin{lemma}[Reflection]\label{lem:reflection} If \(\mathbb P_I\) adds a color-\(0\) \stock{} for a ground-model coloring of \([\Omega]^2\), then that coloring already has a color-\(0\) \stock{} in the ground model. \end{lemma} \begin{proof} Work in the ground model. Let \(p\) force that \(\dot H\) is a color-\(0\) \stock. Set \(r_{-1}=p\). For each \(n<\omega\), choose \(q_n\) extending \(r_{n-1}\) that decides the \(n\)-th row of \(\dot H\), say as \(a_n\). There are uncountably many distinct ground vertices \(x\) in row \(a_n\) for which some \(p_{n,x}\) extending \(q_n\) forces \(x\in\dot H\). If there were only countably many possible members, \(q_n\) would force the slice into that countable ground set, contrary to thickness. Apply the \(\Delta\)-system argument to the domains of these witness conditions, retaining an uncountable family with a common root assignment \(r_n\). Each domain contains \(\operatorname{dom}(q_n)\), so \(r_n\) extends \(q_n\). The petals in this family are pairwise disjoint. The recursion yields increasing roots \(r_n\), and the decided rows \(a_n\) are strictly increasing because each \(q_n\) extends the earlier deciding conditions. Let \(D=\bigcup_{n<\omega}\operatorname{dom}(r_n)\), a countable set. In each row family discard the at most countably many witnesses whose petals meet \(D\). In a recursion of length \(\omega_1\), select uncountably many of the remaining witnesses in each row while keeping the petals pairwise disjoint across all the selections. At each step only countably many coordinates have been used, each of which excludes at most one witness in the current row family. Also exclude the countably many witnesses already selected. The resulting conditions are pairwise compatible. Their roots agree on overlaps, and all petals are disjoint from \(D\) and from each other. A common extension of any two witnesses forces both of their vertices into \(\dot H\). The ground color of their pair must therefore be \(0\). The selected vertices give a ground-model color-\(0\) \stock. \end{proof} This argument uses compatible witness conditions, as in Golshani's preservation analysis for a full-square target~\cite[Section~2]{Golshani}. Here the increasing root sequence handles the countably many thick rows required for the order type \(B\). \begin{lemma}\label{lem:baire} For \(I=\omega_2\), the forcing \(\mathbb P_I\) forces the category hypothesis of Section~\ref{sec:category}. \end{lemma} \begin{proof} In the extension, let a family of at most \(\aleph_1\) dense open sets be given. Index it by a sequence of length at most \(\omega_1\). Code each open set \(U\) by the set of finite strings \(s\in\omega^{<\omega}\) whose basic cylinder is contained in \(U\). The indexed codes have at most \(\aleph_1\) membership bits in total. Working with a name for the sequence of codes, take a maximal antichain deciding each membership bit. These antichains are countable by the ccc, and the conditions on them use only finitely many coordinates each. Thus there is \(S\subseteq I\) of size at most \(\aleph_1\) in the ground model such that all the codes belong to the intermediate extension by \(\mathbb P_S\). If an initial condition is used to force the specified indexing, include its coordinates in \(S\). Choose \(i\in I\setminus S\). The product factorization of \(\mathbb P_I\) makes the function at coordinate \(i\) Cohen-generic over the intermediate extension. The density test for a code is that every finite string has an extension in the code. This test is absolute between the intermediate and full extensions. The Cohen function at \(i\) extends a string in each code. Thus in the full extension it belongs to every open set in the family. \end{proof} \begin{proof}[Proof of Theorem~\ref{thm:main}] Suppose a ground-model coloring is a counterexample. Force with \(\mathbb P_{\omega_2}\). The ordinal square is unchanged, and a positive monochromatic triangle would already be present in the ground model, since it consists of three ground vertices with fixed edge colors. In the extension, Lemma~\ref{lem:baire} and Proposition~\ref{prop:category} give a color-\(0\) homogeneous set of order type \(B\), hence a color-\(0\) \stock. By Lemma~\ref{lem:reflection}, such a stock exists in the ground model. This is the desired contradiction. \end{proof} \begin{thebibliography}{9} \bibitem{B89} J. E. Baumgartner, \emph{Remarks on partition ordinals}, in \emph{Set Theory and its Applications}, Lecture Notes in Mathematics \textbf{1401}, Springer, 1989, pp.~5--17. \href{https://doi.org/10.1007/BFb0097328}{doi:10.1007/BFb0097328}. \bibitem{BH87} J. E. Baumgartner and A. Hajnal, \emph{A remark on partition relations for infinite ordinals with an application to finite combinatorics}, in \emph{Logic and Combinatorics}, Contemp. Math. \textbf{65}, Amer. Math. Soc., 1987, pp.~157--167. \href{https://doi.org/10.1090/conm/065/891246}{doi:10.1090/conm/065/891246}. \bibitem{E1171} T. F. Bloom, \emph{Erd\H{o}s Problems}, problem~1171. \url{https://www.erdosproblems.com/1171}, accessed November~11, 2026. \bibitem{EH71} P. Erd\H{o}s and A. Hajnal, \emph{Ordinary partition relations for ordinal numbers}, Period. Math. Hungar. \textbf{1} (1971), no.~3, 171--185. \href{https://www.renyi.hu/~p_erdos/1971-15.pdf}{Available from the R\'enyi Institute}. \bibitem{Golshani} M. Golshani, \emph{Martin's axiom and \(\omega_1^2\longrightarrow(\omega_1^2,3)^2\)}, \href{https://arxiv.org/abs/2608.13213}{arXiv:2608.13213}, 2026. \bibitem{Komjath} P. Komj\'ath, \emph{The Erd\H{o}s--Hajnal problem list}, Bull. Symbolic Logic \textbf{31} (2025), no.~3, 418--461. \href{https://doi.org/10.1017/bsl.2025.1}{doi:10.1017/bsl.2025.1}. \bibitem{Va99} \emph{Some of Paul's Favorite Problems}, booklet circulated at \emph{Paul Erd\H{o}s and His Mathematics}, Budapest, July~1999, problem~7.84, p.~13. \href{https://web.math.pmf.unizg.hr/~vjekovac/EP/Some_of_Pauls_favorite_problems.pdf}{Digitized copy}. \end{thebibliography} \end{document}