{"id":"palomar/PALOMAR-2026-11-01-000003","url":"https://github.com/mnn31/erdos-919-palomar/tree/b1aababb75cd555fab236a2217ec8ada6ce047cf","json":"https://data.palomar-registry.org/entries/PALOMAR-2026-11-01-000003-v1.json","repo":"https://github.com/mnn31/erdos-919-palomar","tags":["math.CO","math.LO","msc:05C15","msc:03E05"],"score":0,"title":"Reductions for Erdős Problem 919","trust":"high","domain":"math.CO","source":"palomar","authors":["Manan Gupta"],"reviews":0,"subject":"math.CO","summary":"Erdős Problem 919 asks for a graph on the ordinal omega_2 squared with chromatic number aleph_2, or aleph_1, such that every subgraph on a vertex set of smaller order type has chromatic number at most aleph_0. This formalization proves in ZFC that the aleph_2 question is equivalent to the first question of Erdős Problem 918, that the aleph_1 question is equivalent to the existence of a graph on aleph_2 vertices that is not countably chromatic although all its subgraphs on aleph_1 vertices are, that the aleph_2 question implies the aleph_1 question, and that the aleph_1 question has a…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"verified":true,"discussed":0,"published":"2026-11-01","reactions":{},"formalized":true}