Consistency results on infinite graphs
type: Item
instance of: scholarly article
title: Consistency results on infinite graphs
zbMATH Open document ID: 0668.05031
DOI: 10.1007/BF02772573
author: Péter Komjáth
published in: Israel Journal of Mathematics
publication date: 1988-01-01T00:00:00Z
review text: In this paper it is shown that it is consistent (with \(2^{\aleph_ 0}=\aleph_ 3)\) that there is an \(\aleph_ 2\)-chromatic graph of size \(\aleph_ 2\) which does not have an exactly \(\aleph_ 1\)-chromatic subgraph, by extending \textit{F. Galvin}'s result [Period. Math. Hung. 4, 117-119 (1973; Zbl 0278.05105)]. Another extension is the following one: it is consistent that \(2^{\aleph_ 0}=\aleph_ 2\) and there exists a graph X on \(\omega_ 2\) such that every subgraph of size \(\leq \aleph_ 1\) is countably chromatic, while there is no independent set of size \(\aleph_ 2\), therefore every subgraph of size \(\aleph_ 2\) is \(\aleph_ 2\)-chromatic. An old question of P. Erdős and A. Hajnal is whether it is true that every uncountably chromatic graph contains an uncountably chromatic \(\omega\)-connected subgraph. In the second part of this paper it is proved that it is consistent that there exists an \(\aleph_ 1\)-chromatic graph of size \(\aleph_ 1\) with no \(\omega\)- connected \(\aleph_ 1\)-chromatic subgraph and it is consistent that \(2^{\aleph_ 0}=\aleph_ 2\) and every \(\aleph_ 1\)-size, \(\aleph_ 1\)-chromatic graph contains an \(\omega\)-connected, \(\aleph_ 1\)- chromatic subgraph. Finally, using the method of the first part, it is proved that Singular Cardinal Compactness is consistently false for uncountable chromatic graphs: it is consistent that there exists a graph X of size \(\aleph_{\omega}\), with chromatic number equal to \(\aleph_ 1\) such that every subgraph of smaller cardinality is countably chromatic, thus solving a problem raised by \textit{S. Shelah} [Isr. J. Math. 21, 319-349 (1975; Zbl 0369.05034)].
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 4093486
zbMATH Keywords: infinite graph
zbMATH Keywords: Ramsey ultrafilter
zbMATH Keywords: proper forcing axiom
zbMATH Keywords: \(\omega\)- connected subgraph
zbMATH Keywords: countably chromatic
Wikidata QID: Q60680298
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
cites work: Generic graph construction
cites work: Q3949653
cites work: Problems and results on finite and infinite combinatorial analysis. II
cites work: On the combinatorial problems which I would most like to see solved
cites work: Q3691755
cites work: On chromatic number of graphs and set-systems
cites work: Chromatic number of finite and infinite graphs and hypergraphs
cites work: Potent Axioms
cites work: Some downwards transfer properties for \(\aleph _ 2\)
cites work: Chromatic numbers of subgraphs
cites work: Connectivity and chromatic number of infinite graphs
cites work: Forcing constructions for uncountably chromatic graphs
cites work: Q4142328
cites work: A compactness theorem for singular cardinals, free algebras, Whitehead problem and transversals
cites work: Proper forcing
full work available at URL: https://doi.org/10.1007/bf02772573
OpenAlex ID: W2069003332
Recommended article: A note on chromatic number and connectivity of infinite graphs
Recommended article: Q3348927
Recommended article: Forcing constructions for uncountably chromatic graphs
Recommended article: Chromatic numbers of graphs -- large gaps
Recommended article: Identities on cardinals less than ℵω
Recommended article: Finite subgraphs of uncountably chromatic graphs
Recommended article: Generic graph construction
Recommended article: A Note on Conjectures of F. Galvin and R. Rado
Recommended article: Q3356318
Recommended article: Connectivity and chromatic number of infinite graphs
description: scientific article; zbMATH DE number 4093486