A ZFC counterexample to Taylor's conjecture on finite subgraphs
Version 1 / Nov 20, 2026 / CC BY 4.0
Abstract
We construct, in ZFC, a graph of chromatic number such that every graph whose finite ordinary subgraphs embed into has chromatic number at most . Taking the target chromatic number to be 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 .
Provenance statement
References
- 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.
- 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
- 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
- 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
- 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
- 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