Geodesic
Chromatic number of the product of graphs, graph homomorphisms, antichains and cofinal subsets of posets without AC
Commentationes Mathematicae Universitatis Carolinae, Tome 62 (2021) no. 3, pp. 361-382.

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

In set theory without the axiom of choice (AC), we observe new relations of the following statements with weak choice principles. $\circ$ If in a partially ordered set, all chains are finite and all antichains are countable, then the set is countable. $\circ$ If in a partially ordered set, all chains are finite and all antichains have size $\aleph_{\alpha}$, then the set has size $\aleph_{\alpha}$ for any regular $\aleph_{\alpha}$. $\circ$ Every partially ordered set without a maximal element has two disjoint cofinal sub sets -- CS. $\circ$ Every partially ordered set has a cofinal well-founded subset -- CWF. $\circ$ Dilworth's decomposition theorem for infinite partially ordered sets of finite width -- DT. We also study a graph homomorphism problem and a problem due to A. Hajnal without AC. Further, we study a few statements restricted to linearly-ordered structures without AC.
DOI : 10.14712/1213-7243.2021.028
Classification : 03E25, 03E35, 05C15
Keywords: chromatic number of product of graphs; ultrafilter lemma; permutation model; Dilworth's theorem; chain; antichain; Loeb's theorem; application of Loeb's theorem 
@article{10_14712_1213_7243_2021_028,
     author = {Banerjee, Amitayu and Gyenis, Zal\'an},
     title = {Chromatic number of the product of graphs, graph homomorphisms, antichains and cofinal subsets of posets without {AC}},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     pages = {361--382},
     publisher = {mathdoc},
     volume = {62},
     number = {3},
     year = {2021},
     doi = {10.14712/1213-7243.2021.028},
     mrnumber = {4331288},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14712/1213-7243.2021.028/}
}
TY  - JOUR
AU  - Banerjee, Amitayu
AU  - Gyenis, Zalán
TI  - Chromatic number of the product of graphs, graph homomorphisms, antichains and cofinal subsets of posets without AC
JO  - Commentationes Mathematicae Universitatis Carolinae
PY  - 2021
SP  - 361
EP  - 382
VL  - 62
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.14712/1213-7243.2021.028/
DO  - 10.14712/1213-7243.2021.028
LA  - en
ID  - 10_14712_1213_7243_2021_028
ER  - 
%0 Journal Article
%A Banerjee, Amitayu
%A Gyenis, Zalán
%T Chromatic number of the product of graphs, graph homomorphisms, antichains and cofinal subsets of posets without AC
%J Commentationes Mathematicae Universitatis Carolinae
%D 2021
%P 361-382
%V 62
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.14712/1213-7243.2021.028/
%R 10.14712/1213-7243.2021.028
%G en
%F 10_14712_1213_7243_2021_028
Banerjee, Amitayu; Gyenis, Zalán. Chromatic number of the product of graphs, graph homomorphisms, antichains and cofinal subsets of posets without AC. Commentationes Mathematicae Universitatis Carolinae, Tome 62 (2021) no. 3, pp. 361-382. doi : 10.14712/1213-7243.2021.028. http://geodesic.mathdoc.fr/articles/10.14712/1213-7243.2021.028/

Cité par Sources :