Hypothesis holds then the plane can be colored with countably many colors such that no right angled triangle is monocolored. The proof given there is incomplete: at a point the authors describe some conditions and state that "These requirements can be met by an inductive selection of colors." Unfortunately, this is not true. With an essential modification of the argument, with Balzs Bursics, we are going to publish a full argument (see

Abstract We prove consistent, assuming there is a supercompact cardinal, that there is a singular strong limit cardinalμ, of cofinalityω, such that everyμ+-chromatic graphXonμ+has an edge colouringcofXintoμcolours for which every vertex colouringgofXinto at mostμmany colours has ag-colour class on whichctakes every value. The paper also contains some generalisations of the above statement in whichμ+is replaced by other cardinals >μ.

Abstract It is consistent that there is a set mapping from the four-tuples of ωninto the finite subsets with no free subsets of sizetnfor some natural numbertn. For anyn< ω it is consistent that there is a set mapping from the pairs of ωninto the finite subsets with no infinite free sets. For anyn< ω it is consistent that there is a set mapping from the pairs of ωninto ωnwith no uncountable free sets.

One of the early partition relation theorems which include ordinals was the observation of Erdös and Rado [7] that if κ = cf(κ) > ω then the Dushnik–Miller theorem can be sharpened to κ→(κ, ω + 1)2. The question on the possible further extension of this result was answered by Hajnal who in [8] proved that the continuum hypothesis implies ω1 ↛ (ω1, ω + 2)2. He actually proved the stronger result ω1 ↛ (ω: 2))2. The consistency of the relation κ↛(κ, (ω: 2))2 was later extensively studied. Baumgartner [1] proved it for every κ which is the successor of a regular cardinal. Laver [9] showed that if κ is Mahlo there is a forcing notion which adds a witness for κ↛ (κ, (ω: 2))2 and preserves Mahloness, ω-Mahloness of κ, etc. We notice in connection with these results that λ→(λ, (ω: 2))2 holds if λ is singular, in fact λ→(λ, (μ: n))2 for n < ω, μ < λ (Theorem 4). In [11] Todorčević proved that if cf(λ) > ω then a ccc forcing can add a counter-example to λ→(λ, ω + 2)2. We give an alternative proof of this (Theorem 5) and extend it to larger cardinals: if GCH holds, cf (λ) > κ = cf (κ) then < κ-closed, κ+-c.c. forcing adds a counter-example to λ→(λ, κ + 2)2 (Theorem 6). Erdös and Hajnal remarked in their problem paper [5] that Galvin had proved ω2→(ω1, ω + 2)2 and he had also asked if ω2→(ω1, ω + 3)2 is true. We show in Theorem 1 that the negative relation is consistent.

Abstract It is consistent that there exists a set mapping F: [ω2]2 → [ω2]<ω such that F(α,β) ⊆ α for α < β < ω2 and there is no infinite free subset for F. This solves a problem of A. Hajnal and A. Máté.

In this paper we solve some of Pál Erdős's favorite problems on uncountably chromatic graphs. Generalizing a finite graph theory result of Tutte, Erdős and R. Rado showed that for every infinite cardinal κ there exists a triangle-free, κ-chromatic graph of size κ. For κ = ℵ0, Erdős established the existence of ℵ0-chromatic graphs excluding even C4, C5,…, Cn, i.e. circuits up to a given length. For κ < ℵ0 the situation is different. As shown by Erdős and A. Hajnal, a graph is necessarily countably chromatic if it omits any finite bipartite graph. We can, however, exclude any finite list of nonbipartite graphs (this obviously reduces to excluding finitely many odd circuits). They posed an even stronger conjecture, namely, that similar examples must occur in every uncountably chromatic graph. To be specific, they conjectured that for every infinite κ, every κ-chromatic graph contains a κ-chromatic triangle-free subgraph. Here we show that this may not be true for κ = ℵ1 i.e. we exhibit a model where it is false. We must emphasize that the conjecture is probably false already in ZFC, but we have been unable to show this.

For several old problems in combinatorial set theory A. Hajnal and the present author [2] showed that on collapsing a sufficiently Mahlo cardinal to ω1 by the Lévy-collapse one gets a model where these problems are solved in the “counter-example” direction. The authors of [2] have speculated that the theorems of that paper should hold in L, and this, in fact, was shown for some of the results by Todorčević and Velleman [7,8]. The observation that collapsing a large cardinal to ω1 may give rise to L-like constructions is not new. As it was shown long ago by Silver and Rowbottom, there is a Kurepa-tree if a strongly inaccessible cardinal is Lévy-collapsed to ω1. In [5] it is proved that even Silver's W holds in that model. Here we show that even a quagmire exists there, but not necessarily a morass. To be more exact, we show that if κ < λ are the first two strongly inaccessible cardinals, first λ is Lévy-collapsed to κ+, and then κ is Lévy-collapsed to then there is no ω1-morass with built-in diamond in the resulting model (GCH is assumed). If λ is Mahlo, there is not even a morass. Our notations are standard. For excellent survey papers on morass-like principles and their uses in combinatorial set theory see [4,5,6].

It was J. E. Baumgartner who in [1] proved that when a weakly compact cardinal is Lévy-collapsed to ω2 the new ω2 inherits some of the large cardinal properties; e.g. if S is a stationary set of ω-limits in ω2 then for some α < ω2, S ∩ α is stationary in α. Later S. Shelah extended this to the following theorem: if a supercompact cardinal κ is Lévy-collapsed to ω2, then in the resulting model the following holds: if S ⊆ λ is a stationary set of ω-limits and cf(λ) ≥ ω2 then there is an α. < λ such that S ∩ α is stationary in α, i.e. stationary reflection holds for countable cofinality (see [1] and [3]). These theorems are important prototypes of small cardinal compactness theorems; many applications and generalizations can be found in the literature. One might think that these results are true for sets with an uncountable cofinality μ as well, i.e. when an appropriate large cardinal is collapsed to μ++. Though this is true for Baumgartner's theorem, there remains a problem with Shelah's result. The point is that the lemma stating that a stationary set of ω-limits remains stationary after forcing with an ω2-closed partial order may be false in the case of μ-limits in a cardinal of the form λ+ with cf(λ) < μ, as was shown in [8] by Shelah. The problem has recently been solved by Baumgartner, who observed that if a universal box-sequence on the class of those ordinals with cofinality ≤ μ exists, the lemma still holds, and a universal box-sequence of the above type can be added without destroying supercompact cardinals beyond μ.