Erdős problem 597 and finite-target independence
Version 1 / Nov 21, 2026 / CC BY 4.0
Abstract
We study the graph-target partition relation from Erdős problem 597. In ZFC we construct a connected bipartite graph of cardinality and diameter at most three, containing no , for which this relation fails. We also construct a fixed finite -free graph for which the relation fails under the continuum hypothesis. Under Martin's axiom at , it holds for every finite graph. Consequently the universal finite-target assertion, and the assertion for itself, are independent of ZFC, relative to the consistency of ZFC.
Provenance statement
References
- 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
- 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
- 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
- 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.
- 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.
- 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
- 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
- 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
- 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
- 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