| Title:
|
Maximal independent sets, variants of chain/antichain principle and cofinal subsets without AC (English) |
| Author:
|
Banerjee, Amitayu |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
64 |
| Issue:
|
2 |
| Year:
|
2023 |
| Pages:
|
137-159 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
In set theory without the axiom of choice (AC), we observe new relations of the following statements with weak choice principles. $\circ$ $\mathcal{P}_{\rm lf,c}$ (Every locally finite connected graph has a maximal independent set). $\circ$ $\mathcal{P}_{\rm lc,c}$ (Every locally countable connected graph has a maximal independent set). $\circ$ CAC$^{\aleph_{\alpha}}_{1}$ (If in a partially ordered set all antichains are finite and all chains have size $\aleph_{\alpha}$, then the set has size $\aleph_{\alpha}$) if $\aleph_{\alpha}$ is regular. $\circ$ CWF (Every partially ordered set has a cofinal well-founded subset). $\circ$ $\mathcal{P}_{G,H_{2}} $ (For any infinite graph $ G=(V_{G}, E_{G}) $ and any finite graph $ H=(V_{H}, E_{H})$ on 2 vertices, if every finite subgraph of $G$ has a homomorphism into $H$, then so has $G$). $\circ$ If $ G=(V_{G},E_{G}) $ is a connected locally finite chordal graph, then there is an ordering ``$<$" of $V_{G}$ such that $\{w < v \colon \{w,v\} \in E_{G}\}$ is a clique for each $v\in V_{G}$. (English) |
| Keyword:
|
variants of chain/antichain principle |
| Keyword:
|
graph homomorphism |
| Keyword:
|
maximal independent sets |
| Keyword:
|
cofinal well-founded subsets of partially ordered sets |
| Keyword:
|
axiom of choice |
| Keyword:
|
Fraenkel--Mostowski (FM) permutation models of ZFA + $\neg$ AC |
| MSC:
|
03E25 |
| MSC:
|
03E35 |
| MSC:
|
05C69 |
| MSC:
|
06A07 |
| idZBL:
|
Zbl 07790588 |
| idMR:
|
MR4658996 |
| DOI:
|
10.14712/1213-7243.2023.028 |
| . |
| Date available:
|
2023-12-13T13:31:57Z |
| Last updated:
|
2025-07-07 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/151857 |
| . |
| Reference:
|
[1] Banerjee A., Gyenis Z.: Chromatic number of the product of graphs, graph homomorphisms, antichains and cofinal subsets of posets without AC.Comment. Math. Univ. Carolin. 62 (2021), no. 3, 361–382. MR 4331288 |
| Reference:
|
[2] Delhommé C., Morillon M.: Spanning graphs and the axiom of choice.Rep. Math. Logic 40 (2006), 165–180. MR 2207308 |
| Reference:
|
[3] Diestel R.: Graph Theory.Grad. Texts in Math., 173, Springer, Berlin, 2017. Zbl 1218.05001, MR 3644391 |
| Reference:
|
[4] Friedman H. M.: Invariant maximalilty and incompleteness.Foundations and Methods from Mathematics to Neuroscience, CSLI Lecture Notes, 213, CSLI Publications, Stanford, 2014, pages 25–51. MR 3617852 |
| Reference:
|
[5] Fulkerson D. R., Gross O. A.: Incidence matrices and interval graphs.Pacific J. Math. 15 (1965), 835–855. MR 0186421, 10.2140/pjm.1965.15.835 |
| Reference:
|
[6] Füredi Z.: The number of maximal independent sets in connected graphs.J. Graph Theory 11 (1987), no. 4, 463–470. MR 0917193, 10.1002/jgt.3190110403 |
| Reference:
|
[7] Galvin F., Komjáth P.: Graph colorings and the axiom of choice.Period. Math. Hungar. 22 (1991), no. 1, 71–75. MR 1145937, 10.1007/BF02309111 |
| Reference:
|
[8] Hajnal A.: The chromatic number of the product of two $\aleph_{1}$-chromatic graphs can be countable.Combinatorica 5 (1985), no. 2, 137–139. MR 0815579, 10.1007/BF02579376 |
| Reference:
|
[9] Halbeisen L., Tachtsis E.: On Ramsey choice and partial choice for infinite families of $n$-element sets.Arch. Math. Logic 59 (2020), no. 5–6, 583–606. MR 4123294, 10.1007/s00153-019-00705-7 |
| Reference:
|
[10] Herrlich H., Howard P., Tachtsis E.: On special partitions of Dedekind- and Russell-sets.Comment. Math. Univ. Carolin. 53 (2012), no. 1, 105–122. MR 2880914 |
| Reference:
|
[11] Howard P., Keremedis K., Rubin J. E., Stanley A., Tachtsis E.: Non-constructive properties of the real numbers.MLQ Math. Log. Q. 47 (2001), no. 3, 423–431. MR 1847458, 10.1002/1521-3870(200108)47:3<423::AID-MALQ423>3.0.CO;2-0 |
| Reference:
|
[12] Howard P., Rubin J. E.: Consequences of the Axiom of Choice.Mathematical Surveys and Monographs, 59, American Mathematical Society, Providence, 1998. Zbl 0947.03001, MR 1637107, 10.1090/surv/059 |
| Reference:
|
[13] Howard P., Saveliev D. I., Tachtsis E.: On the set-theoretic strength of the existence of disjoint cofinal sets in posets without maximal elements.MLQ Math. Log. Q. 62 (2016), no. 3, 155–176. MR 3509700, 10.1002/malq.201400089 |
| Reference:
|
[14] Howard P., Tachtsis E.: On vector spaces over specific fields without choice.MLQ Math. Log. Q. 59 (2013), no. 3, 128–146. Zbl 1278.03082, MR 3066735, 10.1002/malq.201200049 |
| Reference:
|
[15] Jech T. J.: The Axiom of Choice.Stud. Logic Found. Math., 75, North-Holland Publishing Co., Amsterdam, American Elsevier Publishing, New York, 1973. Zbl 0259.02052, MR 0396271 |
| Reference:
|
[16] Komjáth P.: A note on uncountable chordal graphs.Discrete Math. 338 (2015), 1565–1566. MR 3345591, 10.1016/j.disc.2015.03.022 |
| Reference:
|
[17] Komjáth P., Totik V.: Problems and Theorems in Classical Set Theory.Probl. Books in Math., Springer, New York, 2006. MR 2220838 |
| Reference:
|
[18] Läuchli H.: Coloring infinite graphs and the Boolean prime ideal theorem.Israel J. Math. 9 (1971), 422–429. MR 0288051, 10.1007/BF02771458 |
| Reference:
|
[19] Loeb P. A.: A new proof of the Tychonoff theorem.Amer. Math. Monthly 72 (1965), no. 7, 711–717. MR 0190896, 10.1080/00029890.1965.11970596 |
| Reference:
|
[20] Mycielski J.: Some remarks and problems on the coloring of infinite graphs and the theorem of Kuratowski.Acta Math. Acad. Sci. Hungar. 12 (1961), 125–129. MR 0130686, 10.1007/BF02066677 |
| Reference:
|
[21] Spanring C.: Axiom of choice, maximal independent sets, argumentation and dialogue games.Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2014, pages 91–98. |
| Reference:
|
[22] Tachtsis E.: On Ramsey's theorem and the existence of infinite chains or infinite anti-chains in infinite posets.J. Symb. Log. 81 (2016), no. 1, 384–394. MR 3480974, 10.1017/jsl.2015.47 |
| Reference:
|
[23] Tachtsis E.: On the minimal cover property and certain notions of finite.Arch. Math. Logic 57 (2018), no. 5–6, 665–686. MR 3828886, 10.1007/s00153-017-0595-y |
| Reference:
|
[24] Tachtsis E.: Dilworth's decomposition theorem for posets in ZF.Acta Math. Hungar. 159 (2019), no. 2, 603–617. MR 4022152, 10.1007/s10474-019-00967-w |
| Reference:
|
[25] Tachtsis E.: Łoś's theorem and the axiom of choice.MLQ Math. Log. Q. 65 (2019), no. 3, 280–292. MR 4030955, 10.1002/malq.201700074 |
| . |
