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

DOI10.14712/1213-7243.2023.028MaRDI QIDQ6178013zbMATH OpenFDO

Authors Amitayu Banerjee

Publication date 18 January 2024

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

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)

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$.

Cites work

• scientific article; zbMATH DE number 1201510 (Why is no real title available?)
• A New Proof of the Tychonoff Theorem
• A note on uncountable chordal graphs
• 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
• Coloring infinite graphs and the Boolean prime ideal theorem
• Dilworth's decomposition theorem for posets in ZF
• Graph colorings and the axiom of choice
• Graph theory
• Incidence matrices and interval graphs
• Non-constructive properties of the real numbers
• On Ramsey choice and partial choice for infinite families of \(n\)-element sets
• On Ramsey's theorem and the existence of infinite chains or infinite anti-chains in infinite posets
• On special partitions of Dedekind- and Russell-sets.
• 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
• On vector spaces over specific fields without choice
• Problems and theorems in classical set theory
• Some remarks and problems on the colouring of infinite graphs and the theorem of Kuratowski
• Spanning graphs and the axiom of choice
• The axiom of choice
• The chromatic number of the product of two \(\aleph _ 1\)-chromatic graphs can be countable
• The number of maximal independent sets in connected graphs
• Łoś's theorem and the axiom of choice

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)