\documentclass[10pt,letterpaper,leqno]{amsart} \usepackage[margin=1in]{geometry} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage{amsmath,amssymb,amsthm} \usepackage{enumitem} \usepackage{needspace} \usepackage{microtype} \usepackage[colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref} \hypersetup{ pdftitle={Erdos problem 597 and finite-target independence}, pdfauthor={Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer}, pdfsubject={Ordinal graph partition relations}, pdfkeywords={ordinal partition relations, infinite graphs, ordering property, Martin's axiom} } \setlength{\emergencystretch}{2em} \raggedbottom \clubpenalty=10000 \widowpenalty=10000 \displaywidowpenalty=10000 \numberwithin{equation}{section} \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} \newcommand{\Om}{\omega_1^2} \newcommand{\Bl}{\omega_1\cdot\omega} \newcommand{\MA}{\mathrm{MA}_{\aleph_1}} \newcommand{\CH}{\mathrm{CH}} \newcommand{\ZFC}{\mathrm{ZFC}} \newcommand{\otp}{\operatorname{otp}} \newcommand{\Gam}{\Gamma} \newcommand{\NN}{\mathbb N} \title[Erd\H{o}s problem 597 and finite-target independence]{Erd\H{o}s problem 597 and finite-target independence} \author[W. Howe, G. Huffman, J. Kohlmeyer, and L. Kruer]{Will Howe, Grant Huffman, Jensen Kohlmeyer, and Liam Kruer} \date{November 12, 2026} \subjclass[2020]{03E02, 05C55, 03E35} \keywords{Ordinal partition relations, infinite graphs, ordering property, Martin's axiom, continuum hypothesis} \thanks{Electronic correspondence may be addressed to \href{mailto:howew@purdue.edu}{\texttt{howew@purdue.edu}} (W.~Howe), \href{mailto:huffma97@purdue.edu}{\texttt{huffma97@purdue.edu}} (G.~Huffman), \href{mailto:jenwin@purdue.edu}{\texttt{jenwin@purdue.edu}} (J.~Kohlmeyer), and \href{mailto:kruerl@purdue.edu}{\texttt{kruerl@purdue.edu}} (L.~Kruer).} \begin{document} \begin{abstract} We study the graph-target partition relation $\omega_1^2\to(\omega_1\cdot\omega,H)^2$ from Erd\H{o}s problem~597. In $\ZFC$ we construct a connected bipartite graph of cardinality $\aleph_1$ and diameter at most three, containing no $K_{\omega,\omega}$, for which this relation fails. We also construct a fixed finite $K_4$-free graph $H_0$ for which the relation fails under the continuum hypothesis. Under Martin's axiom at $\aleph_1$, it holds for every finite graph. Consequently the universal finite-target assertion, and the assertion for $H_0$ itself, are independent of $\ZFC$, relative to the consistency of $\ZFC$. \end{abstract} \maketitle \section{Introduction and statements} All graphs are simple and undirected. A copy of a graph $H$ in a graph $G$ is an injective map $f\colon V(H)\to V(G)$ satisfying \[ uv\in E(H)\quad\Longrightarrow\quad f(u)f(v)\in E(G). \] Additional edges among the image vertices are permitted. An order on the host imposes no order requirement on this copy. For ordinals $\alpha,\beta$ and a graph $H$, the relation $\alpha\to(\beta,H)^2$ means that every red-blue coloring of $[\alpha]^2$ has a red homogeneous set of inherited order type $\beta$ or a blue copy of $H$. We write \[ \Omega=\Om,\qquad B=\Bl. \] We identify $\Omega$ with $\omega_1\times\omega_1$ in row-first lexicographic order, so $(a,b)$ has ordinal position $\omega_1a+b$. Equivalently, the blue pairs define a graph on $\Omega$, and a red homogeneous set is an independent set in this graph. Erd\H{o}s asked whether $\Omega\to(B,H)^2$ holds for every graph $H$ of cardinality at most $\aleph_1$ that contains neither $K_4$ nor $K_{\omega,\omega}$, and whether it holds when $H$ is finite \cite{Erdos}. Here $K_{\omega,\omega}$ denotes a complete bipartite graph with both vertex classes countably infinite. \begin{theorem}\label{thm:infinite} There is a graph $H_\infty$ of cardinality $\aleph_1$ such that \begin{enumerate}[label=\textup{(\roman*)},leftmargin=2.3em] \item $H_\infty$ is connected and bipartite, with diameter at most three. \item $H_\infty$ contains neither $K_4$ nor $K_{\omega,\omega}$. \item $\Omega\not\to(B,H_\infty)^2$. \end{enumerate} These conclusions hold in $\ZFC$. \end{theorem} \begin{theorem}\label{thm:finite} There is a fixed finite $K_4$-free graph $H_0$ such that $\CH$ implies \begin{equation}\label{eq:negative} \Omega\not\to(B,H_0)^2. \end{equation} Under $\MA$, for every finite graph $H$, \begin{equation}\label{eq:positive} \Omega\to(B,H)^2. \end{equation} \end{theorem} \begin{corollary}\label{cor:independence} Assume that $\ZFC$ is consistent. Then each of the following assertions is independent of $\ZFC$. \begin{enumerate}[label=\textup{(\roman*)},leftmargin=2.3em] \item $\Omega\to(B,H)^2$ for every finite $K_4$-free graph $H$. \item $\Omega\to(B,H_0)^2$ for the graph $H_0$ in Theorem~\ref{thm:finite}. \end{enumerate} \end{corollary} The negative construction uses the nested-interval method of Baumgartner--Hajnal \cite{BH} and Chen--Garti--Weinert \cite{CGW}. The finite passage from an ordered obstruction to an unordered target is an instance of the Ne\v{s}et\v{r}il--R\"odl ordering property \cite{NR}. We give its sparse-hypergraph proof in the form needed here. The positive partition theorem is due to Baumgartner \cite{Baumgartner}. Related nonuniversality methods occur in Shelah \cite{Shelah}, and Li \cite{Li} studies their application to the unrestricted graph-target question. \section{Uncountable rows in an ordinal block} For $S\subseteq\Omega$ and $a<\omega_1$, put \[ S_a=\{b<\omega_1:(a,b)\in S\}. \] We call $a$ an uncountable row of $S$ when $S_a$ is uncountable. Every uncountable subset of $\omega_1$ is unbounded and has order type $\omega_1$. \begin{lemma}\label{lem:rows} If $S\subseteq\Omega$ has only finitely many uncountable rows, then $\otp(S)r$, and then $b\in S_a$ with $b>s$. The vertices $(a,b),(r,s)$ are adjacent by \eqref{eq:nested}. Now let $S$ be any nonempty vertex set. Choose $(a,b)\in S$ in the least row occupied by $S$. Every neighbor $(r,s)$ of $(a,b)$ in $S$ satisfies $ar$, \begin{equation}\label{eq:selection-rank} e_t(r)>e_t(a), \qquad e_t(r)>e_t(u) \quad\text{for every previously selected row }ur$. Their union is a pattern $P_\nu\subseteq S$. The coordinates of $P_\nu$, together with $\nu$, are bounded below $\omega_1$. Since $S_a$ is unbounded, choose $b\in S_a$ strictly above all these ordinals. Then $P_\nu$ is eligible for $(a,b)$. Lemma~\ref{lem:construction} supplies a point of $\Gam(a,b)\cap P_\nu$, giving an edge of $G$ with both ends in $S$. \end{proof} \section{The ordered six-vertex obstruction} For $y\in\Gam(x)$, let $\tau_x(y)$ be its selection index in the construction of $\Gam(x)$. The uniqueness of its selected row makes this index well defined. \begin{lemma}[Selection reversal]\label{lem:reversal} Suppose $u,v\in\Gam(x)$, the row of $u$ is smaller than the row of $v$, and $uv\in E(G)$. Then $\tau_x(v)<\tau_x(u)$. \end{lemma} \begin{proof} Equation~\eqref{eq:orientation} gives $v\in\Gam(u)$. If $u$ had been selected before $v$ in $\Gam(x)$, rule~\eqref{eq:selection-avoid} would have excluded $v$. The two selection indices are distinct, so the stated inequality follows. \end{proof} \begin{lemma}[Triangle comparison]\label{lem:triangle} If $u,v,w$ form a triangle of $G$ in rows $r_u0$ such that, for all sufficiently large $n$, some outcome satisfies $X-Y-Z\ge c n^{5/4}$. From this outcome, delete one hyperedge from each originally counted bad pair or triple. Repeated deletions of the same hyperedge are counted once. The resulting hypergraph $\mathcal H$ has \begin{equation}\label{eq:many-hyperedges} m=|\mathcal H|\ge c n^{5/4}, \end{equation} distinct hyperedges intersect in at most one vertex, and no triple of hyperedges has three distinct intersection witnesses as above. Independently for each $E\in\mathcal H$, choose a uniformly random bijection from the six labels of $F$ onto $E$, and place the corresponding edges of $F$ on $E$. Let $H_0$ be the union of all these graph edges. Every graph edge has a unique supporting hyperedge, since two hyperedges meet in at most one vertex. Every triangle of $H_0$ lies in one supporting hyperedge. If two of its edges have the same support $E$, all three triangle vertices belong to $E$, and the support of its third edge must also be $E$. If the three supports are distinct, the three triangle vertices are distinct intersection witnesses, contrary to the construction of $\mathcal H$. If $H_0$ contained a $K_4$, two triangles sharing an edge would have the same supporting hyperedge. All four vertices would lie in that hyperedge, and uniqueness of support would place all six edges in its copy of $F$. This contradicts the fact that $F=K_{2,2,2}$ is $K_4$-free. Therefore every choice of the label bijections produces a $K_4$-free graph $H_0$. Fix a linear order on $[n]$. For any $E\in\mathcal H$, the probability that its labels occur in precisely the order \eqref{eq:order-F} is $1/6!$. These events are independent over the hyperedges, since their label bijections were chosen independently. The probability that at least one of the $n!$ linear orders has no successful hyperedge is at most \begin{equation}\label{eq:union-bound} n!\left(1-\frac1{6!}\right)^m \le \exp\left(n\log n-\frac{m}{720}\right)<1 \end{equation} for sufficiently large $n$, by \eqref{eq:many-hyperedges}. Some choice of the label bijections therefore works for every linear order on $[n]$. Fix that choice to obtain $H_0$. \end{proof} \begin{proposition}\label{prop:no-finite-copy} Under $\CH$, the graph $G$ from Section~4 contains no copy of $H_0$. \end{proposition} \begin{proof} Suppose $f\colon V(H_0)\to V(G)$ is an injective edge-preserving map. Order $V(H_0)$ by the rows of its images under $f$, breaking ties by any fixed linear order. Lemma~\ref{lem:ordering-property} gives an ordered copy of $F$ for this linear order. Its six image rows are nondecreasing in the order $x,y,p,q,z,w$. Each consecutive pair in this list is an edge of $F$. Since $G$ has no same-row edges, each consecutive pair of image rows is strictly increasing. Proposition~\ref{prop:ordered-obstruction} now gives a contradiction. \end{proof} Color the edges of $G$ blue and all other pairs red. Lemma~\ref{lem:no-red} and Proposition~\ref{prop:no-finite-copy} show that this coloring has neither a red set of order type $B$ nor a blue copy of $H_0$. The finite graph $H_0$ was fixed in Lemma~\ref{lem:ordering-property}, before the assumption of $\CH$. This proves \eqref{eq:negative}. \section{The positive relation and independence} Recall that $\MA$ states that for every nonempty partially ordered set satisfying the countable chain condition, every family of at most $\aleph_1$ dense subsets is met by a filter. We use the following partition theorem. \begin{theorem}[Baumgartner {\cite[Theorem~3.5(a)]{Baumgartner}}]\label{thm:Baumgartner} Assume $\MA$. Then \[ \Bl\to(\Bl,n)^2 \qquad\text{for every finite }n. \] \end{theorem} Here the second alternative is a blue complete graph on $n$ vertices. \begin{proof}[Proof of \eqref{eq:positive} and Theorem~\ref{thm:finite}] Let $H$ be a finite graph with $n$ vertices. For $n=0$, every host contains the empty copy, so the assertion is immediate. For $n>0$, restrict an arbitrary coloring of $[\Omega]^2$ to its initial segment of type $B$. Theorem~\ref{thm:Baumgartner} gives a red set of order type $B$ or a blue $K_n$. Every $n$-vertex graph has an edge-preserving copy in $K_n$, proving \eqref{eq:positive}. Together with the construction in Section~6, this proves Theorem~\ref{thm:finite}. \end{proof} \begin{proof}[Proof of Corollary~\ref{cor:independence}] Let $\mathsf A$ be the assertion that $\Omega\to(B,H)^2$ for every finite $K_4$-free graph $H$, and let $\mathsf A_0$ be $\Omega\to(B,H_0)^2$. Theorem~\ref{thm:finite} proves \[ \CH\ \Longrightarrow\ \neg\mathsf A\wedge\neg\mathsf A_0, \qquad \MA\ \Longrightarrow\ \mathsf A\wedge\mathsf A_0. \] G\"odel's relative consistency theorem gives a model of $\ZFC+\CH$ whenever $\ZFC$ is consistent \cite{Godel}. The relative consistency theorem of Solovay and Tennenbaum gives a model of $\ZFC+\MA$ under the same assumption \cite{ST}. Thus each of $\mathsf A$ and $\mathsf A_0$, as well as each of their negations, is consistent with $\ZFC$ relative to its consistency. \end{proof} \section*{Acknowledgments} The authors acknowledge assistance from OpenAI's ChatGPT in mathematical exploration, proof checking, and preparation of the exposition. \begin{thebibliography}{9} \raggedright \bibitem{Baumgartner} J.~E. Baumgartner, \emph{Remarks on partition ordinals}, in \emph{Set Theory and its Applications} (J.~Stepr\={a}ns and S.~Watson, eds.), Lecture Notes in Mathematics \textbf{1401}, Springer, Berlin, 1989, 5--17. \href{https://doi.org/10.1007/BFb0097328}{doi:10.1007/BFb0097328}. \bibitem{BH} 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} (S.~G. Simpson, ed.), Contemporary Mathematics \textbf{65}, American Mathematical Society, Providence, RI, 1987, 157--167. \href{https://doi.org/10.1090/conm/065/891246}{doi:10.1090/conm/065/891246}. \bibitem{CGW} W.~Chen, S.~Garti, and T.~Weinert, \emph{Cardinal characteristics of the continuum and partitions}, Israel Journal of Mathematics \textbf{235} (2020), 13--38. \href{https://doi.org/10.1007/s11856-019-1942-y}{doi:10.1007/s11856-019-1942-y}. \bibitem{Erdos} P.~Erd\H{o}s, \emph{Some problems on finite and infinite graphs}, in \emph{Logic and Combinatorics} (S.~G. Simpson, ed.), Contemporary Mathematics \textbf{65}, American Mathematical Society, Providence, RI, 1987, 223--228. \bibitem{Godel} K.~G\"odel, \emph{The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis with the Axioms of Set Theory}, Annals of Mathematics Studies \textbf{3}, Princeton University Press, Princeton, NJ, 1940. \bibitem{Li} A.~C. Li, \emph{A nonuniversality obstruction to an ordinal graph partition relation}, preprint, version~1.1, 2026. \href{https://doi.org/10.5281/zenodo.22671917}{doi:10.5281/zenodo.22671917}. \bibitem{NR} J.~Ne\v{s}et\v{r}il and V.~R\"odl, \emph{On a probabilistic graph-theoretical method}, Proceedings of the American Mathematical Society \textbf{72} (1978), 417--421. \href{https://doi.org/10.1090/S0002-9939-1978-0507350-7}{doi:10.1090/S0002-9939-1978-0507350-7}. \bibitem{Shelah} S.~Shelah, \emph{Universality among graphs omitting a complete bipartite graph}, Combinatorica \textbf{32} (2012), 325--362. \href{https://doi.org/10.1007/s00493-012-2033-4}{doi:10.1007/s00493-012-2033-4}. \bibitem{ST} R.~M. Solovay and S.~Tennenbaum, \emph{Iterated Cohen extensions and Souslin's problem}, Annals of Mathematics (2) \textbf{94} (1971), 201--245. \href{https://doi.org/10.2307/1970860}{doi:10.2307/1970860}. \end{thebibliography} \end{document}