← All problems

Erdős Problem #919 — Chromatic graphs on ordinal squares

57 years old · traced to

Let LL be the set of pairs (α,β)(\alpha,\beta) with 1≤α,β<ω21\leq\alpha,\beta<\omega_2, ordered lexicographically, so that its order type is the ordinal product ω22\omega_2^2. For a graph GG on LL and a subset X⊆LX\subseteq L, let G[X]G[X] denote the induced subgraph on XX, and let otp⁡(X)\operatorname{otp}(X) be the order type inherited from LL. Is there a graph GG on LL such that

χ(G)=ℵ2andχ(G[X])≤ℵ0 for every X⊆L with otp⁡(X)<ω22?\chi(G)=\aleph_2 \quad\text{and}\quad \chi(G[X])\leq\aleph_0\ \text{for every }X\subseteq L\text{ with }\operatorname{otp}(X)<\omega_2^2?

The second question is whether such a graph exists with χ(G)=ℵ1\chi(G)=\aleph_1 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 ω\omega whose chromatic number is ℵ0\aleph_0. 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

Progress summary

Never refreshed

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.