Erdős problem 597 and finite-target independence

Primarily AI-generated textHuman understanding: no partsmath.LO — Logic

Contributed by Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer ↗

Version 1 / Nov 21, 2026 / CC BY 4.0

Abstract

We study the graph-target partition relation ω12→(ω1⋅ω,H)2\omega_1^2\to(\omega_1\cdot\omega,H)^2 from Erdős problem 597. In ZFC we construct a connected bipartite graph of cardinality ℵ1\aleph_1 and diameter at most three, containing no Kω,ωK_{\omega,\omega}, for which this relation fails. We also construct a fixed finite K4K_4-free graph H0H_0 for which the relation fails under the continuum hypothesis. Under Martin's axiom at ℵ1\aleph_1, it holds for every finite graph. Consequently the universal finite-target assertion, and the assertion for H0H_0 itself, are independent of ZFC, relative to the consistency of ZFC.

Author comments: Manuscript accompanying Justin Sun Prize submission JSP-000484. Pinned source and Lean verification materials: https://github.com/Ghuffy1/erdos-597/tree/279825a39739918a2553880a32ec9ab1dee1f780

Provenance statement

AI assistance is disclosed in the manuscript. Its written proof establishes the fixed finite-target result. The Lean first-order independence endpoint concerns the universal finite-target sentence.

References

  1. J. E. Baumgartner, Remarks on partition ordinals , in Set Theory and its Applications (J. Steprāns and S. Watson, eds.), Lecture Notes in Mathematics 1401 , Springer, Berlin, 1989, 5--17. doi:10.1007/BFb0097328 (https://doi.org/10.1007/BFb0097328).DOI
  2. J. E. Baumgartner and A. Hajnal, A remark on partition relations for infinite ordinals with an application to finite combinatorics , in Logic and Combinatorics (S. G. Simpson, ed.), Contemporary Mathematics 65 , American Mathematical Society, Providence, RI, 1987, 157--167. doi:10.1090/conm/065/891246 (https://doi.org/10.1090/conm/065/891246).DOI
  3. W. Chen, S. Garti, and T. Weinert, Cardinal characteristics of the continuum and partitions , Israel Journal of Mathematics 235 (2020), 13--38. doi:10.1007/s11856-019-1942-y (https://doi.org/10.1007/s11856-019-1942-y).DOI
  4. P. Erdős, Some problems on finite and infinite graphs , in Logic and Combinatorics (S. G. Simpson, ed.), Contemporary Mathematics 65 , American Mathematical Society, Providence, RI, 1987, 223--228.
  5. K. Gödel, The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis with the Axioms of Set Theory , Annals of Mathematics Studies 3 , Princeton University Press, Princeton, NJ, 1940.
  6. A. C. Li, A nonuniversality obstruction to an ordinal graph partition relation , preprint, version 1.1, 2026. doi:10.5281/zenodo.22671917 (https://doi.org/10.5281/zenodo.22671917).DOI
  7. J. Nešetřil and V. Rödl, On a probabilistic graph-theoretical method , Proceedings of the American Mathematical Society 72 (1978), 417--421. doi:10.1090/S0002-9939-1978-0507350-7 (https://doi.org/10.1090/S0002-9939-1978-0507350-7).DOI
  8. S. Shelah, Universality among graphs omitting a complete bipartite graph , Combinatorica 32 (2012), 325--362. doi:10.1007/s00493-012-2033-4 (https://doi.org/10.1007/s00493-012-2033-4).DOI
  9. R. M. Solovay and S. Tennenbaum, Iterated Cohen extensions and Souslin's problem , Annals of Mathematics (2) 94 (1971), 201--245. doi:10.2307/1970860 (https://doi.org/10.2307/1970860).DOI

Version history

  1. v1 · 6 pagesSubmitted by Liam KruerManuscript accompanying Justin Sun Prize submission JSP-000484. Pinned source and Lean verification materials: https://github.com/Ghuffy1/erdos-597/tree/279825a39739918a2553880a32ec9ab1dee1f780CurrentNov 21, 2026