A ZFC counterexample to Taylor's conjecture on finite subgraphs

Primarily AI-generated textHuman understanding: no partsmath.CO — Combinatorics

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

Version 1 / Nov 20, 2026 / CC BY 4.0

Abstract

We construct, in ZFC, a graph GG of chromatic number ℵ1\aleph_1 such that every graph whose finite ordinary subgraphs embed into GG has chromatic number at most 2ℵ02^{\aleph_0}. Taking the target chromatic number to be (2ℵ0)+(2^{\aleph_0})^+ gives a negative answer to Taylor's conjecture on finite subgraphs. The construction uses hereditarily countable vertex data, finite coordinate inequalities, and a countable-closure reflection argument. A compactness argument transfers the resulting finite coloring properties to the entire finite age of GG.

Author comments: The pinned manuscript and Lean formalization accompany Justin Sun Prize submission JSP-000604. Proof repository and verification records: https://github.com/Ghuffy1/erdos736-jsp

Provenance statement

The authors acknowledge OpenAI's ChatGPT for developing and checking the argument and preparing the exposition. The exact Lean theorem and its expanded statement passed the published build and kernel replay.

References

  1. N. G. de Bruijn and P. Erdős, A colour problem for infinite graphs and a problem in the theory of relations , Nederl. Akad. Wetensch. Proc. Ser. A 54 = Indag. Math. 13 (1951), 369--373.
  2. P. Erdős, On the combinatorial problems which I would most like to see solved , Combinatorica 1 (1981), no. 1, 25--42. doi:10.1007/BF02579174 (https://doi.org/10.1007/BF02579174).DOI
  3. P. Komjáth and S. Shelah, Finite subgraphs of uncountably chromatic graphs , J. Graph Theory 49 (2005), no. 1, 28--38. doi:10.1002/jgt.20060 (https://doi.org/10.1002/jgt.20060).DOI
  4. C. Lambie-Hanson, On the growth rate of chromatic numbers of finite subgraphs , Adv. Math. 369 (2020), article 107176. doi:10.1016/j.aim.2020.107176 (https://doi.org/10.1016/j.aim.2020.107176).DOI
  5. C. Lambie-Hanson, Finite subgraphs of uncountable graphs , CMU Mathematical Logic Seminar, April 28, 2020, seminar slides (https://speakerdeck.com/clambiehanson/finite-subgraphs-of-uncountable-graphs), 53--107.link

Version history

  1. v1 · 7 pagesSubmitted by Liam KruerThe pinned manuscript and Lean formalization accompany Justin Sun Prize submission JSP-000604. Proof repository and verification records: https://github.com/Ghuffy1/erdos736-jspCurrentNov 20, 2026