Erdős Problem #919 — Chromatic graphs on ordinal squares
Let be the set of pairs with , ordered lexicographically, so that its order type is the ordinal product . For a graph on and a subset , let denote the induced subgraph on , and let be the order type inherited from . Is there a graph on such that
The second question is whether such a graph exists with instead, retaining the same condition on every subset of smaller order type. Requiring the condition for induced subgraphs is equivalent to requiring it for all subgraphs on those vertex sets, since deleting edges cannot increase chromatic number. Erdős Problem #919 Erdős (1969)
Background
The question is motivated by a theorem for graphs on well-ordered vertex sets: if the chromatic number is at least countably infinite, there is a subgraph on a vertex set of order type whose chromatic number is . The issue is whether this kind of small-order-type witness persists at higher cardinalities, or whether high chromatic number can first appear only across a much longer well-order. Erdős Problem #919 Erdős (1969)
References
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.