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

Amitayu Banerjee; Zalán Gyenis

Commentationes Mathematicae Universitatis Carolinae (2021)

  • Volume: 62, Issue: 3, page 361-382
  • ISSN: 0010-2628

Abstract

top
In set theory without the axiom of choice (AC), we observe new relations of the following statements with weak choice principles. ∘ If in a partially ordered set, all chains are finite and all antichains are countable, then the set is countable. ∘ If in a partially ordered set, all chains are finite and all antichains have size ℵ α , then the set has size ℵ α for any regular ℵ α . ∘ Every partially ordered set without a maximal element has two disjoint cofinal sub sets – CS. ∘ Every partially ordered set has a cofinal well-founded subset – CWF. ∘ 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.

How to cite

top

Banerjee, Amitayu, and Gyenis, Zalán. "Chromatic number of the product of graphs, graph homomorphisms, antichains and cofinal subsets of posets without AC." Commentationes Mathematicae Universitatis Carolinae 62.3 (2021): 361-382. <http://eudml.org/doc/297877>.

@article{Banerjee2021,
abstract = {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.},
author = {Banerjee, Amitayu, Gyenis, Zalán},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {chromatic number of product of graphs; ultrafilter lemma; permutation model; Dilworth's theorem; chain; antichain; Loeb's theorem; application of Loeb's theorem},
language = {eng},
number = {3},
pages = {361-382},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Chromatic number of the product of graphs, graph homomorphisms, antichains and cofinal subsets of posets without AC},
url = {http://eudml.org/doc/297877},
volume = {62},
year = {2021},
}

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
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 62
IS - 3
SP - 361
EP - 382
AB - 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.
LA - eng
KW - chromatic number of product of graphs; ultrafilter lemma; permutation model; Dilworth's theorem; chain; antichain; Loeb's theorem; application of Loeb's theorem
UR - http://eudml.org/doc/297877
ER -

References

top
  1. Banaschewski B., 10.1002/malq.19920380136, Z. Math. Logik Grundlag. Math. 38 (1992), no. 4, 383–385. DOI10.1002/malq.19920380136
  2. Cowen R. H., 10.1305/ndjfl/1093887927, Notre Dame J. Formal Logic 18 (1977), no. 2, 243–247. DOI10.1305/ndjfl/1093887927
  3. Dilworth R. P., 10.2307/1969503, Ann. of Math. (2) 51 (1950), 161–166. DOI10.2307/1969503
  4. Hajnal A., 10.1007/BF02579376, Combinatorica 5 (1985), no. 2, 137–139. DOI10.1007/BF02579376
  5. Halbeisen L., Tachtsis E., 10.1007/s00153-019-00705-7, Arch. Math. Logic 59 (2020), no. 5–6, 583–606. DOI10.1007/s00153-019-00705-7
  6. Hall M. Jr., 10.1090/S0002-9904-1948-09098-X, Bull. Amer. Math. Soc. 54 (1948), 922–926. DOI10.1090/S0002-9904-1948-09098-X
  7. Howard P. E., 10.4064/fm-121-1-17-23, Fund. Math. 121 (1984), no. 1, 17–23. DOI10.4064/fm-121-1-17-23
  8. Howard P., Rubin J. E., 10.1090/surv/059, Mathematical Surveys and Monographs, 59, American Mathematical Society, Providence, 1998. Zbl0947.03001DOI10.1090/surv/059
  9. Howard P., Saveliev D. I., Tachtsis E., 10.1002/malq.201400089, MLQ Math. Log. Q. 62 (2016), no. 3, 155–176. DOI10.1002/malq.201400089
  10. Howard P., Tachtsis E., 10.1002/malq.201200049, MLQ Math. Log. Q. 59 (2013), no. 3, 128–146. Zbl1278.03082DOI10.1002/malq.201200049
  11. Jech T. J., The Axiom of Choice, Studies in Logic and the Foundations of Mathematics, 75, North-Holland Publishing Co., Amsterdam, American Elsevier Publishing Co., New York, 1973. Zbl0259.02052
  12. Keremedis K., 10.1002/1521-3870(200010)46:4<569::AID-MALQ569>3.0.CO;2-J, MLQ Math. Log. Q. 46 (2000), no. 4, 569–571. DOI10.1002/1521-3870(200010)46:4<569::AID-MALQ569>3.0.CO;2-J
  13. Komjáth P., Totik V., Problems and Theorems in Classical Set Theory, Problem Books in Mathematics, Springer, New York, 2006. 
  14. Loeb P. A., 10.1080/00029890.1965.11970596, Amer. Math. Monthly 72 (1965), no. 7, 711–717. DOI10.1080/00029890.1965.11970596
  15. Łoś J., Ryll-Nardzewski C., 10.4064/fm-38-1-233-237, Fund. Math. 38 (1951), no. 1, 233–237. DOI10.4064/fm-38-1-233-237
  16. Tachtsis E., 10.1002/malq.201400115, MLQ Math. Log. Q. 62 (2016), no. 3, 190–203. DOI10.1002/malq.201400115
  17. Tachtsis E., 10.1017/jsl.2015.47, J. Symb. Log. 81 (2016), no. 1, 384–394. DOI10.1017/jsl.2015.47
  18. Tachtsis E., 10.1007/s00153-017-0595-y, Arch. Math. Logic. 57 (2018), no. 5–6, 665–686. DOI10.1007/s00153-017-0595-y
  19. Tachtsis E., 10.1007/s10474-019-00967-w, Acta Math. Hungar. 159 (2019), no. 2, 603–617. DOI10.1007/s10474-019-00967-w
  20. Tachtsis E., 10.1002/malq.201700074, MLQ Math. Log. Q. 65 (2019), no. 3, 280–292. DOI10.1002/malq.201700074

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.