zbMATH — the first resource for mathematics

Generic graph construction. (English) Zbl 0573.03021
P. Erdős and A. Hajnal [Theory of Graphs, Proc. Colloquium Tihany, Hungary 1966, 83-98 (1968; Zbl 0164.248)], assuming GCH, constructed an example of a graph G on \(\aleph_ 2\) vertices having chromatic number \(\aleph_ 1\) with the property that every subgraph of G on at most \(\aleph_ 1\) vertices has chromatic number at most \(\aleph_ 0\). They asked whether there is a graph G on \(\aleph_ 2\) vertices but having chromatic number \(\aleph_ 2\) with the same subgraph property. No progress was made on this question until the paper under review. The paper is devoted to showing that the existence of such a graph is relatively consistent with ZF. (The author remarks that Foreman and Laver have shown the consistency of the non-existence of such a graph, using a huge cardinal.) The relative consistency is shown by constructing a forcing model; the forcing conditions are quite complicated. However, the author spends some time indicating why simpler conditions are unlikely to work; this aids considerably in absorbing the details.
Reviewer: N.H.Williams

03E35 Consistency and independence results
03E05 Other combinatorial set theory
05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Infinite and finite sets I pp 403– (1975)
[2] Combinatorial set theory (1977) · Zbl 0362.04008
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.