A note on the Engelking-Karłowicz theorem
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.
- A Construction of Graphs without Triangles having Pre-Assigned Order and Chromatic Number
- scientific article; zbMATH DE number 1548943 (Why is no real title available?)
- On chromatic number of graphs and set-systems
- On decomposition of graphs
- Remarks on Boolean algebras
- Some theorems of set theory and their topological consequences
- The consistency with CH of some consequences of Martin's axiom plus \(2^{\aleph_0}>\aleph_1\)
This page was built for publication: A note on the Engelking-Karłowicz theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2390149)
