Chromatic number of the product of graphs, graph homomorphisms, Antichains and cofinal subsets of posets without AC

DOI10.14712/1213-7243.2021.028arXiv1911.00434MaRDI QIDQ6328369

Author name not available (Why is that?)

Publication date: 1 November 2019

Abstract: We have observations concerning the set theoretic strength of the following combinatorial statements without the axiom of choice. 1. If in a partially ordered set, all chains are finite and all antichains are countable, then the set is countable. 2. If in a partially ordered set, all chains are finite and all antichains have size $alep{h}_{alpha}$, then the set has size $alep{h}_{alpha}$ for any regular $alep{h}_{alpha}$. 3. CS (Every partially ordered set without a maximal element has two disjoint cofinal subsets). 4. CWF (Every partially ordered set has a cofinal well-founded subset). 5. DT (Dilworth's decomposition theorem for infinite p.o.sets of finite width). 6. If the chromatic number of a graph $G_1$ is finite (say $k<omega$), and the chromatic number of another graph $G_2$ is infinite, then the chromatic number of $G_{1}imes{G}_2$ is $k$. 7. For an infinite graph $G=(V_G,E_G)$ and a finite graph $H=(V_H,E_H)$, if every finite subgraph of $G$ has a homomorphism into $H$, then so has $G$. Further we study a few statements restricted to linearly-ordered structures without the axiom of choice.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Chromatic number of the product of graphs, graph homomorphisms, Antichains and cofinal subsets of posets without AC

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6328369)