A note on the Engelking-Karłowicz theorem (Q2390149): Difference between revisions

For ordinals \(\alpha<\beta\) let typ\((\alpha,\beta)\) be the collection of all bounded subsets of \(\beta\) of order-type \(\alpha\). And for a limit ordinal \(\alpha\) let typ\((\alpha,\{\beta\})\) be the collection of all unbounded subsets of \(\beta\) of order-type \(\alpha\). Two subset \(X\), \(Y\) of a linearly ordered set \(A\) are called consistent iff there is an order isomorphism \(f:X\to Y\) with \(f(x)=x\) for \(x\in X\cap Y\), otherwise inconsistent. For ordinals \(\alpha\leq \beta\) let \(G(\alpha,\beta)\) be the graph \(G(V,E)\), where the vertex set \(V\) is typ\((\alpha,\beta)\), and where the edge set \(E\) consists of all pairs \((a,b)\in V\times V\) where \(a\) and \(b\) are inconsistent. Similarly \(G(\alpha,\{\beta\})\) is the graph with vertex set typ\((\alpha,\{\beta\})\) and where the edge set is the set of all pairs \((a,b)\) that are inconsistent sets of type \(\alpha\) (unbounded in \(\beta\)). The chromatic number is \(\chi\). Then it is proved: Theorem 2.2. \(\chi(G(\omega,\{\beth_\omega\}))>\beth_\omega\). More generally, if \(\lambda\) is a strong limit singular cardinal and cf\((\lambda)=\kappa\), then \(\chi(G(\kappa,\{\lambda\}))>\lambda\). A graph \(G\) is said to have \(\kappa\)-chromatic number \(\mu\) iff \(\mu\) is the least cardinal such that there is a function \(\tau\) from its vertex set into \(\mu\) such that \(\tau^{-1}\{\alpha\}\) does not contain a clique of cardinality \(\kappa\). Then there follows: Theorem 2.5. \(\chi_{\aleph_0}(G(\omega,\{\beth_\omega\}))>\beth_\omega\). Theorem 4.1. Let \(G=G(\omega,(2^\kappa)^+)\), \(\chi_{\aleph_0}(G)>\kappa\). If \(\kappa^{\aleph_0}=\kappa\) then any subgraph of \(G\) of smaller cardinality has chromatic number \(\leq 2^\kappa\). Theorem 4.2. Assume that \(\kappa^{\aleph_0}=\kappa\). Then \(\chi_{\aleph_1}(G(\omega,(2^\kappa)^+))\leq\kappa\). Also ``ladder graphs'' are treated: For an ordinal \(\lambda\) let \(S^\lambda_\omega\subset \lambda\) be the subset of \(\lambda\) of limit ordinals with countable cofinality. A ladder system \(X=\langle X_\alpha\mid \alpha \in S^\lambda_\omega\rangle\) is given when the \(X_\alpha\subset \alpha\) are unbounded in \(\alpha\) and of order-type \(\omega\). A ladder graph induced by \(X\) is a subgroup of \(G(\omega,\lambda)\) having the \(X_\alpha\)s as vertices, and as edges all inconsistent pairs. Then some results on chromatic numbers of ladder graphs are established.