Maximal independent sets, variants of chain/antichain principle and cofinal subsets without AC

DOI10.14712/1213-7243.2023.028arXiv2009.05368MaRDI QIDQ6178013FDOQ6178013

Authors: Amitayu Banerjee 

Publication date: 18 January 2024

Published in: Commentationes Mathematicae Universitatis Carolinae (Search for Journal in Brave)

Abstract: In set theory without the Axiom of Choice (AC), we observe new relations of the following statements with weak choice principles. 1. Every locally finite connected graph has a maximal independent set. 2. Every locally countable connected graph has a maximal independent set. 3. If in a partially ordered set all antichains are finite and all chains have size $alep{h}_{alpha}$, then the set has size $alep{h}_{alpha}$ if $alep{h}_{alpha}$ is regular. 4. Every partially ordered set has a cofinal well-founded subset. 5. 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:w,vin{E}_G$ is a clique for each $vin{V}_G$.

Full work available at URL: https://arxiv.org/abs/2009.05368

zbMATH Keywords

graph homomorphismaxiom of choicemaximal independent setscofinal well-founded subsets of partially ordered setsFraenkel-Mostowski (FM) permutation models of ZFA + \(\neg\) ACvariants of chain/antichain principle

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorics of partially ordered sets (06A07) Consistency and independence results (03E35) Axiom of choice and related propositions (03E25)

Cites Work

• The axiom of choice
• Incidence matrices and interval graphs
• Problems and theorems in classical set theory
• Title not available (Why is that?)
• Graph theory
• The number of maximal independent sets in connected graphs
• A New Proof of the Tychonoff Theorem
• Non-constructive properties of the real numbers
• The chromatic number of the product of two \(\aleph _ 1\)-chromatic graphs can be countable
• On Ramsey's theorem and the existence of infinite chains or infinite anti-chains in infinite posets
• On Ramsey choice and partial choice for infinite families of \(n\)-element sets
• Graph colorings and the axiom of choice
• On the minimal cover property and certain notions of finite
• On the set-theoretic strength of the existence of disjoint cofinal sets in posets without maximal elements
• A note on uncountable chordal graphs
• Coloring infinite graphs and the Boolean prime ideal theorem
• Dilworth's decomposition theorem for posets in ZF
• On special partitions of Dedekind- and Russell-sets.
• Spanning graphs and the axiom of choice
• Some remarks and problems on the colouring of infinite graphs and the theorem of Kuratowski
• Łoś's theorem and the axiom of choice
• On vector spaces over specific fields without choice
• Axiom of Choice, Maximal Independent Sets, Argumentation and Dialogue Games
• Chromatic number of the product of graphs, graph homomorphisms, antichains and cofinal subsets of posets without AC

Cited In (2)

• Distinguishing colorings, proper colorings, and covering properties without \textsf{AC}
• On the deductive strength of the Erdős-Dushnik-Miller theorem and two order-theoretic principles

This page was built for publication: Maximal independent sets, variants of chain/antichain principle and cofinal subsets without AC

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