Idiosynchromatic Poetry

Thilo V. Weinert

weinert@math.uni-bonn.de

Hausdorff Center for Mathematics

Rheinische Friedrich-Wilhelms-Universität Bonn

Endenicher Allee 62

53115 Bonn

Germany

June 14, 2014

Abstract

We prove equivalences of asymmetric partition relations involving natural numbers and products of weakly compact cardinals κ, infinite cardinals λ < κ and natural numbers to certain classes of finitary problems in the theory of edge-coloured digraphs. We are able to determine three classes of Ramsey numbers exactly, typical examples in these classes are r(ω^{2}2, 3), r(κλ2, 3) and r(κλ3, 3). We moreover provide general upper bounds for r(ω^{2}m, 3) and r(κλm, n).

Keywords: partition, digraph, ordinal, weakly compact, Ramsey, edge-coloured. Mathematical Subject Classification of the AMS: 03E02, 05C20, 05C63,

05D10.

1 Introduction

The partition calculus as introduced by Erdős and Rado in [56ER] is of interest both to set theorists and combinatorialists. While the former are usually more interested in statements with consistency strength which are hence independent over ZFC the latter are normally interested in finitary problems. In between falls a class of problems the æsthetic appeal of which is in the author’s opinion usually underestimated—partition relations between countable ordinals.

0This title is a tribute both to my PhD advisor who regarded this work at an early stage as poetry—the author concedes but hopes it to be good poetry—and to David Schrittesser who came up with the word “idiosynchromatic”.

Notation 1.1. In this paper we use the terminology which is nowadays pretty common. Ordinals are von-Neumann-ordinals so in particular an ordinal is identical to the set of its ordinal predecessors. Therefore α\β denotes the half-open interval from β to α containing the former but not the latter. Ω denotes the class of all ordinals. [α]^{β} denotes the set of subsets of α with order type β. c^{“}X for X ⊂ dom(c) is defined to be {y ∈ ran(c)|∃x ∈ X : c(x) = y} i.e. the pointwise image of X under the function c. Recall that the asymmetric partition relation α → (β, n) means ∀c : [α]^{2} ⟶ 2∃X ∈ [α]^{β} : c^{“}X = {0} ∨ ∃X ∈ [α]^{n} : c^{“}X = {1}, i.e. for every colouring of the unordered pairs of ordinals less than α with two colours we find a subset of α of order type β homogeneous in colour 0 or a subset of α of order type n homogeneous in colour 1.

Moreover we employ the common notation for Ramsey numbers also in this more general case. So r(β, n) = α means that α is the least ordinal such that α → (β, n) holds true.

When v, w are vertices of a directed graph v ↦_{b}w means that there is a solid black arrow from v to w while v ↦_{g}w says that there is a solid grey arrow from v to w, v ↦_{d}w claims the existence of a dashed black arrow from v to w and finally v ↦ w means that there is an arrow of some kind from v to w. Sometimes we want to talk about there being an arrow of a certain colour between v and w without claiming anything about its direction. For this we write v −_{b}w—there is a solid black arrow between v and w, v −_{g}w—there is a solid grey arrow between v and w or v −_{d}w—there is a dashed black arrow between v and w. The solid black in-neighborhoods of a vertex v will be denoted by N_{B}^{−}(v), the solid black out-neighborhoods by N_{B}^{+}(v) and N_{G}^{−}(v), N_{G}^{+}(v), N_{D}^{−}(v) and N_{D}^{+}(v) have their expected denotations. The set of vertices independent from v will be denoted by I(v).

In this paper, a digraph has at most one arrow between any two vertices and never any from a vertex to itself.

For the graph-theoretic terminology we follow [09BG]. Some of the notation was inspired by [09GS].

People working in this area seem to have been mainly interested in evaluating partition relations of the form α → (α, n) for countable α and natural n. There are three cases in which partition relations of the form α → (β, n) for β < α both countable and n natural have been analysed in some generality. This was the case for α, β finite powers of ω, for α, β finite multiples of ω and for α, β natural—the last case of course being by far the most popular. In this last case people went to great lengths to calculate the r(m, n)’s, see for example [95MR]! There are a few results which do not fall into one of these categories, for example in [69Mi], [69HSc], [69HSa] and [69HSb].

Definition 1.2. A coloured digraph is a triple ⟨V, A, c⟩ such that V is a set( of vertices), A is a binary irreflexive asymmetric relation on V —a set of arcs—and c : A ⟶ ran(c) is a colouring of A.

We are in the following going to be concerned with arc-coloured digraphs, i.e. directed graphs with coloured arcs. We will be especially interested in three-coloured digraphs, i.e. in the case where ran(c) = 3. Remember that a complete digraph is called a tournament.

For brevity in the following we will speak of triples instead of three-person-three-coloured-tournaments.

In [56ER] Erdős and Rado prove the following theorem^{1}

Theorem 1.3. Let m, n ∈ ω \ 2 and denote by l_{0} = l_{0}(m, n) the least finite number l possessing the following property.

Property P_{mn}. Whenever ρ(λ, μ) < 2 for {λ, μ} ∈ [l]^{2}, then there is either {λ_{0}, …, λ_{m−1}} ∈ [l]^{m} such that ρ(λ_{α}, λ_{β}) = 0 for α < β < m or there is {λ_{0}, …, λ_{n−1}} ∈ [l]^{n} such that ρ(λ_{α}, λ_{β}) = 1 for {α, β} ∈ [n]^{2}. Then ωl_{0} → (m, ωn)^{2} but γ ↛ (m, ωn)^{2} for γ < ωl. Moreover, if l_{1} → (m, m, n)^{2}, then l_{0} ⩽ l_{1}.

Note, however, that a possible alternative formulation of all but the last sentence of this theorem would nowadays be the following.

Theorem 1.4. The partition relation ωl → (ωm, n) holds true if and only if for every digraph C on l vertices contains an independent set of size m or there is a subtournament S of C induced by a set of n vertices such that all triples in S are transitive.

These two theorems are equivalent by a well-known fact.

Fact 1.5. If a tournament has a cycle then it has one of length 3.

Later theorem 1.3 was generalized by Baumgartner, see [74Ba], in the following way:

Theorem 1.6. Let κ be any infinite cardinal. The partition relation κl → (κm, n) holds true if and only if for every digraph C on l vertices contains an independent set of size m or there is a subtournament S of C induced by a set of n vertices such that all triples in S are transitive.

1.1 Added in Proof

The author believed for quite some time that the discovery that r(ω^{2}2, 3) = ω^{2}10 was due to him. Only later he discovered that it already appeared in [69HSb]. No proof was given though and there was also neither a formulation of a finitary problem equivalent to the calculation of the r(I_{m}, A_{n})’s nor an upper bound for the r(I_{m}, A_{3})’s given.

2 Determining a Ramsey number

In this section we mainly build on work of Pál Erdős and Richard Rado in the aforementioned [56ER] and Ernst Specker in [57Sp]. The following eclectic definition is justified by theorem 2.6 the proof of which explains the background of it.

1The author changed the notation partially to his own. This Theorem was first published as Theorem 25 in “A Partition Calculus in Set Theory” in the Bulletin of the American Mathematical Society in No. 62, pp. 427–489, published by the American Mathematical Society, \begin{matrix}c \\ ◯ \end{matrix}Pál Erdős and Richard Rado, 1956.

Definition 2.1. We identify 0 with solid black, 1 with solid grey and 2 with dashed black arrows.^{2} A triple is called agreeable if and only if it is one of the following.

If a triple is not agreeable we call it disagreeable. Note that all agreeable triples are transitive rather than cyclic, i.e. there is both a vertex emitting two arrows and a vertex absorbing two arrows. Fact 2.2. A triple is disagreeable if and only if it is either…

♢ … a cyclic triple, regardless of the colouring, i.e. ♢ … or one of the following:

We remind the reader of the definition of weakly compacts. Definition 2.3. κ ∈ Ω \ 3 is called weakly compact iff κ → (κ)_{ω}^{2}. Fact 2.4. For all κ ∈ Ω we have κ → (κ)_{2}^{2} iff κ ∈ {0, 1, 2, ω} or κ is weakly compact. Fact 2.5. κ → (κ)_{2}^{2} iff ∀n < ω, α < κ : κ → (κ)_{α}^{n}

Both facts are corollaries of theorem 7.6 of [03Ka] which can be found on page 76.

2It is planned to make a coloured postprint version of this paper available on the web.

Theorem 2.6. Let κ ∈ Ω \ 3 satisfy κ → (κ)_{2}^{2}.

The partition relation κ^{2}l → (κ^{2}m, n) holds true if and only if every coloured digraph C = ⟨l, A, c⟩ with ran(c) = 3 contains an independent set of size m or there is a subtournament S of C induced by a set of n vertices such that all triples in S are agreeable.

Proof.

♢ Let us first assume that the finite combinatorial characterization above holds true. Given any colouring χ : [κ^{2}l]^{2} ⟶ 2 we define a new colouring χ′ as follows:

χ′ : [κ]^{4} ⟶ 2^{4l^{2}}
{h, j, i, k}_{<} ⟼ ∑_{f,g<l} (χ({κ^{2}f + κh + j, κ^{2}g + κi + k})2^{4(lf+g)}
+χ({κ^{2}f + κh + i, κ^{2}g + κj + k})2^{4(lf+g)+1}
+χ({κ^{2}f + κh + k, κ^{2}g + κj + i})2^{4(lf+g)+2}
+χ({κ^{2}f + κh + j, κ^{2}g + κh + i})2^{4(lf+g)+3})

Now we use fact 2.5 in the form κ → (κ)_{2^{4l^{2}}}^{4} thereby finding an X ∈ [κ]^{κ} homogeneous for χ′.

Now fix a surjection b : X → ⟶ {⟨ν, γ⟩|ν < l ∧ γ < κ + 1} and monotonic enumeration functions e_{ν} : κ ⟷ b^{−1}^{“}({⟨ν, κ⟩}) such that

• ∀ν < l∀γ < κ + 1 : \overline{\overline{b^{−1}^{“}(\{⟨ν, γ⟩\})}} = κ.

• ∀ν < l∀γ < κ∀δ ∈ b^{−1}^{“}({⟨ν, γ⟩}) : e_{ν}(γ) < δ.

Now let Y := {κ^{2}f + κh + j|f < l ∧ h ∈ b^{−1}(⟨f, κ⟩) ∧ j ∈ b^{−1}(⟨f, e_{f}^{−1}(h)⟩)}.

In prose what’s happening is this. We distribute the elements of X to signify multiples of 1 or κ in the l blocks of size κ^{2}. No two ordinals may appear in two roles and within one κ^{2}-block the 1-coordinate is always larger than the κ-coordinate. Note that Y ∈ [κ^{2}l]^{κ^{2}l}.

Now observe that the colour of an element {κ^{2}f + κh + j, κ^{2}g + κi + k} ∈ [Y]^{2}—where we suppose that h < i—is completely determined by f, g and whether h < j < i < k, h < i < j < k, h < i < k < j or h = i < j < k.

Now we define a coloured digraph C = ⟨l, A, c⟩ as follows. If for {f, g} ∈ [l]^{2} we have

• ∀{κ^{2}f + κh + j, κ^{2}g + κi + k} ∈ [Y]^{2} : χ({κ^{2}f + κh + j, κ^{2}g + κi + k}) = 0 then there is no arc between f and g in C.

• ∃{κ^{2}f + κh + j, κ^{2}g + κi + k} ∈ [Y]^{2} : χ({κ^{2}f + κh + j, κ^{2}g + κi + k}) = 1 where we again assume that h < i and

⋄ h < i < k < j then we let f ↦_{b}g. ⋄ h < i < j < k then we let f ↦_{g}g.

⋄ h < j < i < k then we let f ↦_{d}g.

In this case there may very well be more than one way to put an arc between f and g and to colour it—clearly there could be six possible ways to do this yet it suffices just to do it in one way.

Our remark above shows us that this is well-defined. Since l is natural we do not even have to use the axiom of choice.

Now we may use our combinatorial statement. If I ∈ [l]^{m} is independent in C then obviously Z := {{κ^{2}f + κh + j, κ^{2}g + κi + k} ∈ [Y]^{2}|{f, g} ⊂ I ∧ h, i, j, k < κ} is a homogeneous set of size κ^{2}m in colour 0. So let us assume that there is a subtournament S of C of size n such that all triples in S are agreeable.

Let ⟨m_{0}, m_{2}, …, m_{n−1}⟩ be the sequence of natural numbers defined by the following backwards recursion:

• m_{n} := 0,

• m_{i−1} := 3m_{i} + 2.

We have m_{i} := 3^{n−i} − 1. Furthermore let ⟨v_{0}, v_{1}, …, v_{n−1}⟩ be a sequence of vertices such that S := {v_{i}|i < n}.

Now we are going to inductively construct the 1-homogeneous set {κa_{i} + b_{i}|i < n} where a_{i} and b_{i} are ordinals less than κ for i < n.

First we are going to inductively define a sequence ⟨s_{i}|i < m_{0}⟩ of ordinals less than κ. Let s_{0} := 0. Given ⟨s_{j}|j ⩽ i⟩ choose α_{i} < κ such that e_{v_{j}}(α_{i}) ⩾ s_{i} for all j < n and then choose s_{i+1} < ω such that ∀j < n, k ⩽ i : b^{−1}^{“}({⟨v_{j}, α_{k}⟩}) ∩ s_{i+1} \ s_{i} ⊋ ∅.

In step i < n suppose we have already defined a 1-homogeneous set of size i.

The following will be our induction hypothesis.

1. min{j ∈ ω \ 1|∃k < ω : {a_{h}, b_{h}|h < i} ∩ s_{j+k+1} \ s_{j+k} ⊋ ∅ ∧ {a_{h}, b_{h}|h < i} ∩ s_{k+1} \ s_{k} ⊋ ∅} > m_{i+1},

2. ∀j, k < i : v_{j} ↦_{b}v_{k} ↔ a_{j} < a_{k} < b_{k} < b_{j},

3. ∀j, k < i : v_{j} ↦_{g}v_{k} ↔ a_{j} < a_{k} < b_{j} < b_{k},

4. ∀j, k < i : v_{j} ↦_{d}v_{k} ↔ a_{j} < b_{j} < a_{k} < b_{k}.

This we do as follows, let L_{κ} := max({a_{h}|h < i ∧ v_{h} ↦ v_{i}} ∪ {b_{h}|h < i ∧ v_{h} ↦_{d}v_{i}}) and U_{κ} := min({a_{h}|h < i ∧ v_{i} ↦ v_{h}} ∪ {b_{h}|h < i ∧ v_{h} ↦_{b}v_{i}} ∪ {b_{h}|h < i ∧ v_{h} ↦_{g}v_{i}}).

Claim 2.7. L_{κ} < U_{κ}.

Proof of Claim:

Suppose not. The claim could fail in the following ways:

• max{a_{h}|h < i ∧ v_{h} ↦ v_{i}} ⩾ min{a_{j}|j < i ∧ v_{i} ↦ v_{j}}. Fix h and j witnessing this. The induction hypothesis implies that v_{j} ↦ v_{h}. But then v_{h}, v_{i} and v_{j} form a cyclic and hence disagreeable triple. Contradiction!

• max{a_{h}|h < i ∧ v_{h} ↦ v_{i}} ⩾ min{b_{j}|j < i ∧ v_{j} ↦_{b}v_{i}}. As before fix witnesses h and j. By induction hypothesis we have v_{j} ↦_{d}v_{h} and fact 2.2 implies that {v_{h}, v_{i}, v_{j}} is disagreeable. Contradiction!

• max{a_{h}|h < i ∧ v_{h} ↦ v_{i}} ⩾ min{b_{j}|j < i ∧ v_{j} ↦_{g}v_{i}}. Fix h and j witnessing this. The induction hypothesis implies that v_{j} ↦_{d}v_{h}. A look at fact 2.2 shows that {v_{h}, v_{i}, v_{j}} is disagreeable. Contradiction!

• max{b_{h}|h < i ∧ v_{h} ↦_{b}v_{i}} ⩾ min{a_{j}|j < i ∧ v_{i} ↦ v_{j}}. Fix h, j witnessing this. By induction hypothesis we now either have v_{j} ↦ v_{h}, v_{h} ↦_{b}v_{j} or v_{h} ↦_{g}v_{j}. In every case {v_{h}, v_{i}, v_{j}} is disagreeable. Contradiction!

• max{b_{h}|h < i ∧ v_{h} ↦_{d}v_{i}} ⩾ min{b_{j}|h < i ∧ v_{j} ↦_{b}v_{i}}. Let h, j witness this. As before the induction hypothesis implies that either v_{h} ↦_{b}v_{j}, v_{j} ↦_{g}v_{h} or v_{j} ↦_{d}v_{h}. Again by fact 2.2 {v_{h}, v_{i}, v_{j}} is disagreeable. Contradiction!

• max{b_{h}|h < i ∧ v_{h} ↦_{d}v_{i}} ⩾ min{b_{j}|h < i ∧ v_{j} ↦_{g}v_{i}}. Fix witnesses h and j to this fact. By induction hypothesis we now either have v_{h} ↦_{b}v_{j}, v_{j} ↦_{g}v_{h} or v_{j} ↦_{d}v_{h}. Fact 2.2 again shows {v_{h}, v_{i}, v_{j}} to be disagreeable. Contradiction!

■(Claim)

Let h < m_{0} be minimal such that L_{κ} < s_{h}. Then take

a_{i} ∈ e_{v_{i}}^{“}(κ) ∩ s_{h+m_{i}+1} \ s_{h+m_{i}}.

Now we are going to define b_{i}. Similarly, let L_{1} := max({a_{i}}∪{a_{h}|h < i∧v_{i} ↦_{g}v_{h}}∪{b_{h}|h < i ∧ v_{i} ↦_{b}v_{h}} ∪ {b_{h}|h < i ∧ v_{h} ↦_{g}v_{i}}) and U_{1} := min({a_{h}|h < i ∧ v_{i} ↦_{d}v_{h}} ∪ {b_{h}|h < i ∧ v_{h} ↦_{b}v_{i}} ∪ {b_{h}|h < i ∧ v_{i} ↦_{g}v_{h}}).

Claim 2.8. L_{1} < U_{1}.

Proof of Claim: As above we distinguish cases and reach contradictions.

• Suppose a_{i} ⩾ min{a_{h}|h < i ∧ v_{i} ↦_{d}v_{h}}. Since {a_{h}|h < i ∧ v_{i} ↦_{d}v_{h}} ⊂ {a_{h}|h < i ∧ v_{i} ↦ v_{h}} we have min{a_{h}|h < i∧v_{i} ↦_{d}v_{h}} ⩾ min{a_{h}|h < i∧v_{i} ↦ v_{h}} and since min{a_{h}|h < i∧v_{i} ↦ v_{h}} ⩾ U_{κ} it follows that a_{i} ⩾ U_{κ}. Contradiction!

• If a_{i} ⩾ min{b_{h}|h < i ∧ v_{h} ↦_{b}v_{i}} then analogously we get min{b_{i}|h < i ∧ v_{h} ↦_{b}v_{i}} ⩾ U_{κ} implying a_{i} ⩾ U_{κ}. Contradiction!

• Suppose a_{i} ⩾ min{b_{h}|h < i ∧ v_{i} ↦_{g}v_{h}}. Similarly we have min{b_{h}|h < i ∧ v_{h} ↦_{g}v_{i}} ⩾ U_{κ} and thus a_{i} ⩾ U_{κ}. Contradiction!

• Suppose max{a_{h}|h < i ∧ v_{i} ↦_{g}v_{h}} ⩾ min{a_{j}|j < i ∧ v_{i} ↦_{d}v_{j}}. Fix witnesses h and j to this fact. The induction hypothesis implies v_{j} ↦ v_{h}. Fact 2.2 shows that in all three cases {v_{h}, v_{i}, v_{j}} is disagreeable.

• Suppose max{a_{h}|h < i ∧ v_{i} ↦_{g}v_{h}} ⩾ min{b_{j}|j < i ∧ v_{j} ↦_{b}v_{i}}. Once more fix witnesses h, j. Again the induction hypothesis implies that v_{j} ↦_{d}v_{h}. Fact 2.2 implies that {v_{h}, v_{i}, v_{j}} is a disagreeable triple. Contradiction!

• In case max{a_{h}|h < i ∧ v_{i} ↦_{g}v_{h}} ⩾ min{b_{j}|j < i ∧ v_{i} ↦_{g}v_{j}} we can again fix h and j witnessing this and use the induction hypothesis to see that v_{j} ↦_{d}v_{h}. A backcheck with fact 2.2 assures us of the disagreeability of {v_{h}, v_{i}, v_{j}}. Contradiction!

• In case max{b_{h}|h < i ∧ v_{i} ↦_{b}v_{h}} ⩾ min{a_{j}|j < i ∧ v_{i} ↦_{d}v_{j}} let us once more fix witnesses h and j to this fact and use the induction hypothesis. We must either have v_{j} ↦ v_{h} or v_{h} ↦_{b}v_{j} or v_{h} ↦_{g}v_{j}. Fact 2.2 shows that in all five cases {v_{h}, v_{i}, v_{j}} is disagreeable. Contradiction!

• Suppose that max{b_{h}|h < i ∧ v_{i} ↦_{b}v_{h}} ⩾ min{b_{j}|j < i ∧ v_{j} ↦_{b}v_{i}}. Fix witnesses h and j and use the induction hypothesis in order to see that we either have v_{h} ↦_{b}v_{j} and hence a cyclic triple {v_{h}, v_{i}, v_{j}} or we have either v_{j} ↦_{g}v_{h} or v_{j} ↦_{d}v_{h}. In both of the last two cases {v_{h}, v_{i}, v_{j}} is disagreeable by fact 2.2. Contradiction!

• If max{b_{h}|h < i ∧ v_{i} ↦_{b}v_{h}} ⩾ min{b_{j}|j < i ∧ v_{i} ↦_{g}v_{j}} we again fix witnesses h and j. By induction hypothesis we have v_{h} ↦_{b}v_{j} or v_{j} ↦_{g}v_{h} or v_{j} ↦_{d}v_{h}. Fact 2.2 assures us once again of {v_{h}, v_{i}, v_{j}}’s disagreeability in any case. Contradiction!

• Suppose max{b_{h}|h < i ∧ v_{h} ↦_{g}v_{i}} ⩾ min{b_{j}|j < i ∧ v_{j} ↦_{b}v_{i}}. Let h and j be witnesses to this fact. The induction hypothesis implies that either v_{h} ↦_{b}v_{j} or v_{j} ↦_{g}v_{h} or v_{j} ↦_{d}v_{h}. By fact 2.2 in any case {v_{h}, v_{i}, v_{j}} is disagreeable. Contradiction!

• If max{b_{h}|h < i ∧ v_{h} ↦_{g}v_{i}} ⩾ min{b_{j}|j < i ∧ v_{i} ↦_{g}v_{j}} we fix witnesses h and j. By induction hypothesis we either have v_{h} ↦_{b}v_{j} or v_{j} ↦_{g}v_{h} or v_{j} ↦_{d}v_{h}. In each case by fact 2.2 {v_{h}, v_{i}, v_{j}} would be disagreeable. Contradiction!

• If max{b_{h}|h < i ∧ v_{h} ↦_{g}v_{i}} ⩾ min{a_{j}|j < i ∧ v_{i} ↦_{d}v_{j}} we can again fix witnesses h, j to this fact. By induction hypothesis we can conclude that either v_{j} ↦ v_{h} in which case {v_{h}, v_{i}, v_{j}} is cyclic and in particular disagreeable or that either v_{h} ↦_{b}v_{j} or v_{h} ↦_{g}v_{j}. But fact 2.2 tells us that in these cases {v_{h}, v_{i}, v_{j}} is disagreeable too. Contradiction!

■(Claim)

Now let h < m_{0} be minimal such that L_{1} < s_{h}. Take

b_{i} ∈ b^{−1}^{“}({⟨v_{i}, e^{−1}(a_{i})⟩}) ∩ s_{h+2m_{i}+1} \ s_{h+2m_{i}}^{3}.

By claims 2.7 and 2.8 and condition 1. of the inductive hypothesis we have chosen a_{i} and b_{i} such that a_{i} < U_{κ} and b_{i} < U_{1}. So by definition of the bounds L_{κ}, U_{κ}, L_{1} and U_{1} conditions 2. to 4. of our inductive hypothesis are fulfilled. We also made sure that 1. holds true for the next step.

But then, after n steps, by the definition of our coloured digraph C, we see that {κa_{i}+b_{i}|i < n} is homogeneous of colour 1.

♢ Now suppose towards a contradiction that there is a a 3-coloured digraph D = ⟨l, A, c⟩ of size l such that both all its independent sets have size less than m and every subtournament S of D of size n contains a disagreeable triple.

Now we define a colouring χ as follows.

χ : [ω^{2}l]^{2} ⟶ 2

\{ω^{2}e + ωg + i, ω^{2}f + ωh + j\} ⟼ \begin{cases}1 if g < h < j < i and e ↦_{b}f, \\ 1 if g < h < i < j and e ↦_{g}f, \\ 1 if g < i < h < j and e ↦_{d}f, \\ 0 if e and f are unconnected, \\ 0 if \overline{\overline{\{g, h, i, j\}}} < 4, \\ 0 if e = f or i < g or j < h. \end{cases}

In the naming of the pair of ordinals we can of course assume without loss of generality that g ⩽ h.

Now if there were a set H ∈ [κ^{2}l]^{κ^{2}m} which is 0-homogeneous for χ there would be a set S ∈ [l]^{m} such that for all s ∈ S we have otyp({κ^{2}s + α ∈ H|α < κ^{2}}) = κ^{2}. Since all independent sets in D have size less than m it follows that we have e ↦ f for e, f ∈ S. Now if e ↦_{d}f, choose first g ∈ \{k|k < κ ∧ \overline{\overline{\{k′|k′ < κ ∧ κ^{2}e + κk + k′ ∈ H\}}} = κ\}, then i ∈ \{k|k ∈ κ\(g+1)∧κ^{2}e+κg+k ∈ H\}, then h ∈ \{k|k ∈ κ\(i+1)∧\overline{\overline{\{k′|k′ < κ ∧ κ^{2}f + κk + k′ ∈ H\}}} = κ} and finally j ∈ {k|k ∈ κ \ (h + 1) ∧ κ^{2}f + κh + k ∈ H}. But now we have found κ^{2}e + κg + i, κ^{2}f + κh + j ∈ H such that χ({κ^{2}e + κg + i, κ^{2}f + κh + j}) = 1 which contradicts our assumption that H was 0-homogeneous. If instead of e ↦_{d}f we have e ↦_{g}f or e ↦_{b}f we can argue similarly, we only have to change the sequence of choices.

So assume that there is a set H ∈ [ω^{2}l]^{n} which is 1-homogeneous for χ. Considering the last clause in the definition of χ we conclude that no κ^{2}-block can contain more than one element of H, i.e. we have \overline{\overline{H ∩ κ^{2}(k + 1) \ κ^{2}k}} < 2 for every k < l. So S := \{s|s < l∧H∩κ^{2}(s+1)\κ^{2}s ⊋ ∅} has size n. Moreover the fourth clause in the definition of χ implies that every two elements of S are connected by an arrow. So S spans a subtournament of D. Hence S has to contain a disagreeable triple T = {t_{0}, t_{1}, t_{2}} ∈ [S]^{3}. Take κ^{2}t_{0} + κu_{0} + v_{0}, κ^{2}t_{1} + κu_{1} + v_{1}, κ^{2}t_{2} + κu_{2} + v_{2} ∈ H. Now we distinguish four cases

3There are basically two ideas behind this abundance of case distinctions. First one can conceive of a completeness theorem for linear orders. Unless one cannot derive a contradiction there has to be a model.

The other is the fact that if a tournament has a cycle it has one of length 3. Here it only gets a little bit more involved since one has to simultaneously consider the ω-coordinates and the 1-coordinates.

• T is cyclic. Suppose we have t_{0} ↦ t_{1} ↦ t_{2} ↦ t_{0}. Considering the first three clauses of the definition of χ we may conclude that for the elements chosen above we have u_{0} < u_{1} < u_{2} < u_{0}. Contradiction!

• Suppose t_{0} ↦_{g}t_{1} or t_{0} ↦_{d}t_{1}, that t_{2} ↦_{b}t_{1} or t_{1} ↦_{g}t_{2} or t_{1} ↦_{d}t_{2} and that t_{0} ↦_{b}t_{2}. Then using again the definition of χ we arrive at v_{0} < v_{1} < v_{2} < v_{0}. Contradiction!

• Suppose that t_{0} ↦_{d}t_{1}, that t_{1} ↦ t_{2}. and that t_{0} ↦_{b}t_{2} or t_{0} ↦_{g}t_{2}. Then v_{0} < u_{1} < u_{2} < v_{0} follows. Contradiction!

• Suppose that t_{0} ↦_{d}t_{1}, that t_{2} ↦_{b}t_{1} or t_{2} ↦_{g}t_{1} and that either t_{0} ↦_{b}t_{2} or t_{2} ↦_{g}t_{0} or t_{2} ↦_{d}t_{0}. Then v_{0} < u_{1} < v_{2} < v_{0}. Contradiction!

Note that modulo a renaming of t_{0}, t_{1} and t_{2} the above clauses cover all disagreeable triples. So this finishes the second part of the proof.

■

The author wants to point out that if you believe in enough reflection you might believe something like (There are stationarily many weakly compact cardinals in the universe.) so theorem 2.6 really says something about a lot of ordinals.

So we now can also state—not in complete earnest—a joint generalization of the theorems 1.4 and 2.6. In this artificial sense being agreeable is a generalization of being transitive.

Theorem 2.9. For i ∈ 3 \ 1 and κ ∈ Ω \ 3 such that κ → (κ)_{2}^{2} the partition relation κ^{i}l → (κ^{i}m, n) holds true if and only if every coloured digraph C = ⟨l, A, c⟩ with ran(c) = 2i − 1 contains an independent set of size m or there is a subtournament S of C induced by a set of n vertices such that all triples in S are agreeable.

The special case the author was actually most interested in however is this one:

Corollary 2.10. The partition relation ω^{2}l → (ω^{2}m, n) holds true if and only if every coloured digraph C = ⟨l, A, c⟩ with ran(c) = 3 contains an independent set of size m or there is a subtournament S of C induced by a set of n vertices such that all triples in S are agreeable.

Henceforth A_{n} is a graph on n vertices such that all its induced subgraphs on three vertices are agreeable. This allows us to define the Ramsey number r(I_{m}, A_{n}) to be the smallest natural number such that any digraph on r(I_{m}, A_{n}) vertices either contains an independent set of size m or an induced subgraph on n vertices all triples of which are agreeable. Since A_{n} does not denote a single graph but a class of graphs this might be seen as a slight abuse of notation, or at least a shorthand. So the equivalence between the infinitary partition problems and finite digraph combinatorics above can be also condensed into the following formula:

r(κ^{2}m, n) = κ^{2}r(I_{m}, A_{n}) for κ = ω or κ weakly compact.

Theorem 2.11. r(I_{2}, A_{3}) > 9.

Proof. The statement above holds because there is the following tricoloured nine-person tournament:

Algebraically this can be seen as the tournament on ℤ_{9} where from every i ∈ ℤ_{9} there is a dashed black arrow pointing at i + 1, solid grey arrows pointing both at i + 2 and i + 3 and a solid black arrow pointing at i + 4.

A close observation reveals that every triple in this tournament is disagreeable thereby showing ω^{2}9 ↛ (ω^{2}2, 3).

There is even an easier counterexample which is this one:

This is algebraically interpretable as the tournament on ℤ_{3} × ℤ_{3} where from every ⟨i, j⟩ there is a dashed black arrow pointing at ⟨i+1, j⟩ and solid grey arrows pointing at ⟨i, j +1⟩ and ⟨i + 1, j + 1⟩ and ⟨i + 2, j + 1⟩.

Also this should be easily checkable. Either a triple is one of three completely coloured in dashed black—these are disagreeable—or it shares exactly one point with each of these triples—then it forms a disagreeable triple completely coloured in solid grey—or it shares two points with one and one with another—then it is either one of two dashed black/solid greycoloured disagreeable triples. These counterexamples were not found in a very systematic way, so there might be others or there might not be others. ■

Now some easy observations quickly yield upper bounds for r(I_{2}, A_{3}). For example by ordering the vertices and then colour a pair of them in one of six colours depending on both whether the direction of the arc agrees with the ordering or not and the original colour of the arc. Since all monochromatic transitive triples are agreeable this yields r(I_{2}, A_{3}) ⩽ r(3, 3, 3, 3, 3, 3). Using r(3, 3, 3) = 17 from [55GG] together with the recursive formula we get r(I_{2}, A_{3}) ⩽ 1898.

A much better bound is found by observing that every four-person-tournament contains a transitive triple. So clearly r(I_{2}, A_{3}) ⩽ r(4, 4, 4). The recursive formula together with the result that r(3, 3, 4) ⩽ 31 from [98PR] yields r(4, 4, 4) ⩽ 236 so r(I_{2}, A_{3}) ⩽ 236 follows. Finally by observing that every six-person-tournament coloured in either solid black or solid grey contains an agreeable triple we get r(I_{2}, A_{3}) ⩽ r(4, 6). In

[97MR] it is shown that r(4, 6) ⩽ 41 so we have r(I_{2}, A_{3}) ⩽ 41.

But far better results are possible.

Fact 2.12. In a tournament on ten vertices containing no agreeable triple there can be at most ten dashed black arrows, thirty solid grey arrows and ten solid black arrows. So there are at least five dashed black, twenty-five solid grey and five solid black arrows.

Proof. Take any tournament on ten vertices not containing any agreeable triple.

Suppose that there are eleven dashed black arrows. By the pigeonhole principle there has to be a vertex where two dashed black arrows leave. But then this vertex together with the targets of the two dashed black arrows forms an agreeable triple.

Suppose that there are eleven solid black arrows. Again by the pigeonhole principle there has to be a vertex where two solid black arrows leave. Analogously this vertex together with the targets of the two solid black arrows forms an agreeable triple.

Suppose that there are thirty-one solid grey arrows. By the pigeonhole principle there has to be a vertex where four solid grey arrows leave. Then all of the targets of these arrows have to be connected by dashed black arrows to one another. Fix one of these target-vertices v. Since it is adjacent to at least three dashed black arrows at least two dashed black arrows are leaving from there or two dashed black arrows are arriving there. Suppose two dashed black arrows are leaving. Then v together with the targets of these arrows forms an agreeable triple. If on the other hand two dashed black arrows are arriving then again v together with the sources of these arrows forms an agreeable triple.

The second statement follows immediately after one observes that a tournament on ten vertices has \binom{10}{2}, i.e. 45 arrows. ■

Lemma 2.13. Any tournament T on ten vertices containing no agreeable triple contains three dashed black triples, i.e. we have v_{0}, …, v_{9} ∈ V_{T} with v_{1} ↦_{d}v_{2} ↦_{d}v_{3} ↦_{d}v_{1} and v_{4} ↦_{d}v_{5} ↦_{d}v_{6} ↦_{d}v_{4} and v_{7} ↦_{d}v_{8} ↦_{d}v_{9} ↦_{d}v_{7}.

Proof. First observe that any such tournament has to contain two such dashed black triples. This is because by fact 2.12 there have to be at least twenty-five solid grey arrows and hence five vertices where three solid grey arrows leave. Since the targets of the three solid grey arrows leaving such a vertex have to form a dashed black triple and since any vertex in such a dashed black triple may be the target of at most three solid grey arrows the pigeonhole principle implies that there have to be at least two dashed black triples.

Now suppose towards a contradiction that there are exactly two such dashed black triples {v_{0}, v_{1}, v_{2}} and {v_{3}, v_{4}, v_{5}} and that there are six vertices where three solid grey arrows leave.

Again the targets of these solid grey arrows have to form dashed black triples. Since two dashed black triples cannot overlap without producing an agreeable triple we can apply the pigeonhole principle and conclude that each vertex in each of both triples has to receive three solid grey arrows. Now since three solid grey arrows each are hitting v_{0}, v_{1} and v_{2} the sources of them again form a dashed black triple. Since there are only two of them and v_{0}, v_{1} and v_{2} are connected to each other by dashed black arrows we know that the sources of them can only be v_{3}, v_{4} and v_{5}. So we have v_{i} ↦_{g}v_{j} for every i ∈ 6 \ 3 and j ∈ 3. But since v_{3} is also hit by three solid grey arrows and is already connected in the opposite direction with v_{0}, v_{1} and v_{2} there has to be a third dashed black triple.

An analogous argument works for the case that there are six vertices where three solid grey arrows leave.

So there are at most five vertices where three solid grey arrows leave and at most five vertices where three solid grey arrows arrive. So there are at most twenty-five solid grey arrows. By fact 2.12 we may restrict our attention to the case of ten dashed black, twentyfive solid grey and ten solid black arrows. Since no vertex is the target of more than one dashed black arrow and no vertex is the source of more than one dashed black arrow the remaining four dashed black arrows have to form a cycle. So without loss of generality we have v_{6} ↦_{d}v_{7} ↦_{d}v_{8} ↦_{d}v_{9} ↦_{d}v_{6}.

Now we argue as before. Consider now again the five vertices where three solid grey arrows are leaving. The targets of the three solid grey arrows leaving such a vertex must form a dashed black triple. By the pigeonhole principle every vertex in one of the two dashed black triples has to receive three solid grey arrows each. But then their sources again form a dashed black triple. This shows that without loss of generality we have v_{i} ↦_{g}v_{j} for every i ∈ 6 \ 3 and j ∈ 3.

In total there are five vertices with three solid grey arrows leaving and there are five vertices with three solid grey arrows arriving. Both the targets of the former and the sources of the latter have to form dashed black triples. Since every vertex may emit or absorb at most three solid grey arrows it follows that there are two-element-sets {w_{0}, w_{1}} and {w_{2}, w_{3}} with w_{0} ↦_{d}w_{1} and w_{2} ↦_{d}w_{3} such that v_{i} ↦_{g}w_{j} for every i ∈ 3 and j ∈ 2 and w_{i} ↦_{g}v_{j} for every i ∈ 4 \ 2 and j ∈ 6 \ 3.

Now we are going to distinguish some—not altogether different—cases. Note that since there are ten solid black arrows and a vertex can emit at most one, every vertex has to emit exactly one.

♢ \overline{\overline{\{w_{0}, w_{1}, w_{2}, w_{3}\}}} = 2. Since there are only two possible targets—the elements of the set {v_{6}, …, v_{9}} \ {w_{0}, w_{1}}—for the solid black arrows emitted by the vertices v_{0}, …, v_{5}, w_{0}, w_{1} one of them has to be target of at least four solid black arrows which contradicts fact 2.12.

♢ \overline{\overline{\{w_{0}, w_{1}, w_{2}, w_{3}\}}} = 3. Let X := \{w_{0}, w_{1}\} ∩ \{w_{2}, w_{3}\}. Obviously \overline{\overline{X}} = 1. Let w := ⋃ X. The only possible target for the solid black arrow leaving w is v := ⋃({v_{6}, …, v_{9}} \ {w_{0}, w_{1}, w_{2}, w_{3}}) since for each i ∈ 4 we either have w = w_{i} or w ↦_{d}w_{i} or w_{i} ↦_{d}w and for all i ∈ 6 we either have w ↦_{g}v_{i} or v_{i} ↦_{g}w. Now since the vertices v_{0}, …, v_{5} all also have to emit a solid black arrow and the sources of solid black arrows pointing at the same vertex have to be connected by dashed black arrows, lest there be an agreeable triple, we know that none of these solid black arrows can point at v. None can point at w either since w was already shown to be connected differently to every other vertex. So let x := ⋃({w_{0}, w_{1}} \ {v, w}) and y := ⋃({w_{2}, w_{3}} \ {v, w}). Since v_{i} ↦_{g}x for any i ∈ 3 it follows that v_{i} ↦_{b}y for any i ∈ 3 Similarly y ↦_{g}v_{i} for any i ∈ 6 \ 3 implies v_{i} ↦_{b}x for any i ∈ 6 \ 3. But now we see that not both x and y can emit a solid black arrow hence we have a contradiction.

♢ \overline{\overline{\{w_{0}, w_{1}, w_{2}, w_{3}\}}} = 4. Remember that v_{6}, …, v_{9} form a dashed black four-cycle. Since {v_{6}, …, v_{9}} = {w_{0}, …, w_{3}} and w_{0} ↦_{b}w_{1} and w_{2} ↦_{d}w_{3} we can conclude w_{0} ↦_{d}w_{1} ↦_{d}w_{2} ↦_{d}w_{3} ↦_{d}w_{0}. Now recall that we focused on the case where there are five vertices emitting three solid grey arrows. Since in total there are twenty-five solid grey arrows every arrow has to emit at least two solid grey arrows. Now consider the vertex w_{0}. Since it can only send one solid grey arrow to w_{2} and none to v_{0}, v_{1}, v_{2}, w_{1} or w_{3} it has to send one to v_{3}, v_{4} or v_{5}. But then w_{0} and w_{2} would have to be connected by a dashed black arrow making either {w_{0}, w_{1}, w_{2}} or {w_{2}, w_{3}, w_{0}} an agreeable triple. Again we have a contradiction.

■

Theorem 2.14. r(I_{2}, A_{3}) ⩽ 10.

Proof. Suppose towards a contradiction that there is a tricoloured tournament on ten vertices v_{0}, …, v_{9} not containing any agreeable triple. By lemma 2.13 we know that there are three dashed black triples {v_{1}, v_{2}, v_{3}}, {v_{4}, v_{5}, v_{6}} and {v_{7}, v_{8}, v_{9}}. Since no vertex can emit more than one dashed black arrow and no vertex can absorb more than one dashed black arrow either, we know that v_{0} has to be connected to v_{1}, …, v_{9} purely by solid black and solid grey arrows. In the situation in which all triples are agreeable we know that the targets of three solid grey arrows starting at v_{0} have to form a dashed black triple. The same holds for the sources of three solid grey arrows ending at v_{0} and the sources of three solid black arrows ending at v_{0}. Moreover we know that v_{0} may emit at most one solid black arrow. So we may distinguish three cases up to isomorphism:

♢ v_{1}, v_{2}, v_{3} ↦_{b}v_{0}, v_{4}, v_{5}, v_{6} ↦_{g}v_{0} v_{0} ↦_{g}v_{7}, v_{8} and v_{0} ↦_{b}v_{9}. In this case {v_{0}, v_{7}, v_{9}} is agreeable.

♢ v_{1}, v_{2}, v_{3} ↦_{b}v_{0}, v_{0} ↦_{g}v_{4}, v_{5}, v_{6} v_{7}, v_{8} ↦_{g}v_{0} and v_{0} ↦_{b}v_{9}. Here {v_{0}, v_{8}, v_{9}} is agreeable.

♢ v_{1}, v_{2}, v_{3} ↦_{g}v_{0}, v_{0} ↦_{g}v_{4}, v_{5}, v_{6}, v_{7}, v_{8} ↦_{b}v_{0}( and either v_{9} ↦_{b}v_{0} or v_{0} ↦_{b}v_{9}).

Now we prove two claims:

Claim 2.15. The dashed black triple {v_{7}, v_{8}, v_{9}} is connected purely by solid grey arrows to one of the other two dashed black triples.

Proof of Claim: First note that no solid grey arrow can point from a v_{i} with i ∈ 4 \ 1 to a v_{j} with j ∈ 10 \ 7, otherwise {v_{0}, v_{i}, v_{j}} would be agreeable. Similarly no solid grey arrow may point from a v_{i} with i ∈ 10 \ 7 to a v_{j} with j ∈ 7 \ 4, otherwise {v_{0}, v_{i}, v_{j}} would be agreeable. Since at least two solid black arrows are leaving the set {v_{7}, v_{8}, v_{9}} heading towards v_{0} and there can be at most one solid black arrow leaving a vertex we conclude that there can be at most one solid black arrow leaving {v_{7}, v_{8}, v_{9}} in the direction of any vertex v_{i} with i ∈ 10 \ 1. So we have either that all arrows between {v_{7}, v_{8}, v_{9}} and {v_{4}, v_{5}, v_{6}} are either incoming solid grey or incoming solid black or that all arrows between {v_{7}, v_{8}, v_{9}} and {v_{1}, v_{2}, v_{3}} are either outgoing solid grey or incoming solid black. Suppose the latter happens. Assume towards a contradiction that v_{i} ↦_{b}v_{j} for i ∈ 4 \ 1 and j ∈ 10 \ 7. Since at most one solid black arrow may leave a vertex we know that v_{k} ↦_{g}v_{i} for both k ∈ 10 \ (7 ∪ {j}). Now choose k ∈ 10 \ (7 ∪ {j}) such that v_{k} ↦_{d}v_{j}. Then {v_{i}, v_{j}, v_{k}} is agreeable, contradiction! So now assume that the former happens, i.e. that all arrows between {v_{7}, v_{8}, v_{9}} and {v_{4}, v_{5}, v_{6}} are either incoming solid grey or incoming solid black. Assume towards a contradiction that for some i ∈ 7 \ 4 and some j ∈ 10 \ 7 we have v_{i} ↦_{b}v_{j}. Since at most one solid black arrow may leave any vertex it follows that v_{i} ↦_{g}v_{k} for k ∈ 10 \ (7 ∪ {j}). Choose k ∈ 10 \ (7 ∪ {j}) such that v_{j} ↦_{d}v_{k}. Then {v_{i}, v_{j}, v_{k}} is agreeable, contradiction! ■(Claim)

Claim 2.16. At both the dashed black triples {v_{1}, v_{2}, v_{3}} and {v_{4}, v_{5}, v_{6}} there are at least two vertices connected by a solid grey arrow to a vertex in the other dashed black triple.

Proof of Claim: Suppose this would fail for {v_{1}, v_{2}, v_{3}}. Then two vertices, v_{i} and v_{j} with {i, j} ∈ [4 \ 1]^{2} would be connected to {v_{4}, v_{5}, v_{6}} purely by solid black arrows. But there are six such connections to be made and since at most one solid black arrow may leave a vertex only the usage of five solid black arrows is allowed here—contradiction. The proof for the other case works totally analogously. ■(Claim)

Now we are moving ever closer to a contradiction. By claim 2.15 we know that the dashed black triple {v_{7}, v_{8}, v_{9}} is connected purely by solid grey arrows to one of the other two dashed black triples. Suppose {v_{1}, v_{2}, v_{3}} is this triple. Since at most one solid black arrow may leave the dashed black triple {v_{7}, v_{8}, v_{9}} in the direction of any vertex v_{i} with i ∈ 10\1 and at most one solid black arrow can leave each vertex v_{i} with i ∈ 7 \ 4 we know that five arrows between {v_{4}, v_{5}, v_{6}} and {v_{7}, v_{8}, v_{9}} have to be solid grey. So in particular at least two vertices in {v_{4}, v_{5}, v_{6}} have to have solid grey connections to vertices in the dashed black triple {v_{7}, v_{8}, v_{9}}. Using claim 2.16 and a variant of the pigeonhole principle we may choose a vertex v_{i} with i ∈ 7 \ 4 which has a solid grey connection both to a vertex v_{j} with j ∈ 4 \ 1 and to a vertex v_{k} with k ∈ 10 \ 7. Since we supposed the truth of claim 2.15 to be witnessed by {v_{1}, v_{2}, v_{3}} we know that also v_{j} and v_{k} are connected by solid grey arrows. If we now remember that all solid grey arrows between {v_{1}, v_{2}, v_{3}} and {v_{7}, v_{8}, v_{9}} have to point from the latter to the former we know that in order for {v_{i}, v_{j}, v_{k}} to be disagreeable the only possibility left is v_{i} ↦_{g}v_{k} ↦_{g}v_{j} ↦_{g}v_{i}. But then we have v_{j} ↦_{g}v_{0} ↦_{g}v_{i} and v_{j} ↦_{g}v_{i} hence {v_{0}, v_{i}, v_{j}} is agreeable. Contradiction. If the truth of claim 2.15 is witnessed by {v_{4}, v_{5}, v_{6}} instead the proof works totally analogously. So this proves the theorem.

■

3 Strong agreeability

Definition 3.1. A triple is called strongly agreeable if and only if it is agreeable and does not contain any dashed black arrow. So it is strongly agreeable precisely if it is one of these:

The proof of the following theorem is heavily inspired by [74Ba].

Theorem 3.2. Let κ be weakly compact and λ ∈ κ \ ω be a cardinal. The partition relation κλl → (κλm, n) holds true if and only if every edge-coloured digraph C = ⟨l, A, c⟩ with ran(c) = 2 contains an independent set of size m or there is a subtournament S of C induced by a set of n vertices such that all triples in S are strongly agreeable.

Proof.

♢ Towards a contradiction let us assume that the finite combinatorial characterization above holds true yet there is neither a 0-homogeneous set of size κλm nor a 1-homogeneous ntuple. Let furthermore χ : [κλl]^{2} ⟶ 2 be any colouring. W.l.o.g. we may assume that χ^{“}(κ(λk + α + 1) \ κ(λk + α)) = 1 for any α < λ and k < l. We define a new colouring ξ as follows:

ξ : [κ]^{2} ⟶^{[λl]^{2}} 4
{α, β}_{<} ⟼ ⟨{γ, δ}_{<}, 2χ({κγ + α, κδ + β}) + χ({κγ + β, κδ + α})⟩

Now we use fact 2.5 in the form κ → (κ)_{2^{λ}}^{2} thereby finding an X ∈ [κ]^{κ} homogeneous for ξ. Set ψ := ⋃ ξ^{“}X. We have ψ : [λl]^{2} ⟶ 4.

Let ⟨⟨b_{j}, c_{j}⟩|j < 2l(l − 1)⟩ be an enumeration of l^{2} \ Δ.

We are going to inductively construct for every i < l a sequence of sets ⟨Y_{i}^{j}|j ⩽ 2l(l − 1)⟩ by letting Y_{i}^{0} := λ(i + 1) \ λi and for any j < l(l − 1) letting Y_{b_{j}}^{2j+1} := B and Y_{c_{j}}^{2j+1} := C if there are sets B ∈ [Y_{b_{j}}^{2j}]^{λ}, C ∈ [Y_{c_{j}}^{2j}]^{λ} with \overline{\overline{\{y ∈ C|ψ(\{x, y\}) ≡ 1(2)\}}} < λ for all x ∈ B. If there are no such sets let Y_{b_{j}}^{2j+1} := Y_{b_{j}}^{2j} and Y_{c_{j}}^{2j+1} := Y_{c_{j}}^{2j}. Similarly let Y_{b_{j}}^{2j+2} := B and Y_{c_{j}}^{2j+2} := C if there are sets B ∈ [Y_{b_{j}}^{2j+1}]^{λ}, C ∈ [Y_{c_{j}}^{2j+1}]^{λ} with \overline{\overline{\{y ∈ C|ψ(\{x, y\}) ∈ 4 \ 2\}}} < λ for all x ∈ B. If there are no such sets let Y_{b_{j}}^{2j+2} := Y_{b_{j}}^{2j+1} and Y_{c_{j}}^{2j+2} := Y_{c_{j}}^{2j+1}. Generally

let Y_{i}^{2j+2} := Y_{i}^{2j} for j < l(l −1) and i ∈ l \{b_{j}, c_{j}}. Finally we let Z_{i} := Y_{i}^{2l(l−1)} for all i < l.

Now we define a digraph D = ⟨l, A, c⟩ by setting for i, j < l:

i ↦_{b}j ⟹∃α ∈ Z_{i} : \overline{\overline{\{β ∈ Z_{j}|ψ(\{α, β\}) ≡ 1(2)\}}} = λ  (1)
⟺∀C ∈ [Z_{j}]^{λ} : \overline{\overline{\{η ∈ Z_{i}|\overline{\overline{\{ν ∈ C|ψ(\{η, ν\}) ≡ 1(2)\}}} < λ\}}} < λ  (2)
i ↦_{g}j ⟹∃α ∈ Z_{i} : \overline{\overline{\{β ∈ Z_{j}|ψ(\{α, β\}) ∈ 4 \ 2\}}} = λ  (3)
⟺∀C ∈ [Z_{j}]^{λ}\overline{\overline{\{η ∈ Z_{i}|\overline{\overline{\{ν ∈ C|ψ(\{η, ν\}) ∈ 4 \ 2\}}} < λ\}}} < λ  (4)

We have ⇒ instead of ⇔ here for a reason. This definition neither necessarily tells us the direction of an arrow—since i and j could change roles—nor does it determine its colour uniquely—since we have 3 ∈ {x ∈ 4 \ 2|n ≡ 1(2)}. We only have to follow the principle that whenever these conditions allow us to set an arrow we do so. The equivalences hold because of the definition of the Z_{i}’s. We will use the negations of (1) and (3) in the case where we define the 0-homogeneous set and (2) and (4) in the case in which we define the 1-homogeneous set.

After having so defined the digraph we may employ our finitary hypothesis and distinguish two cases:

• There is N ∈ [l]^{n} such that all elements of [N]^{3} are strongly agreeable. We are going to inductively construct a 1-homogeneous set H. Since no strongly agreeable triple is cyclic we may choose an enumeration e : n ⟷ N in such a way that i < j if and only if e(i) ↦ e(j). Now we proceed by induction. We may, using (2) and (4), choose an α_{i} ∈ Z_{e(i)} such that ⋄ ∀j < i(e(i) ↦_{b}e(j) → ψ({α_{j}, α_{i}) ≡ 1(2)). ⋄ ∀j < i(e(i) ↦_{g}e(j) → ψ({α_{j}, α_{i}) ∈ 4 \ 2). ⋄ ∀j ∈ n \ (i + 1)(e(i) ↦_{b}e(j) → \overline{\overline{\{β ∈ Z_{e(j)}|ψ(\{α_{0}, β\}) ≡ 1(2)\}}} = λ) ⋄ ∀j ∈ n \ (i + 1)(e(i) ↦_{g}e(j) → \overline{\overline{\{β ∈ Z_{e(j)}|ψ(\{α_{0}, β\}) ∈ 4 \ 2\}}} = λ) Now choose this end let S ∈ [κ]^{2^{n}} be such that ∀η ∈ S∀ν ∈ η ∩ S∃ζ ∈ X ∩ η \ ν. Let ⟨s_{η}|η < 2^{n}⟩ be the increasing enumeration of S and let e : n ⟷ N. Now let k_{−2} := 0, k_{−1} := 2^{n} and k_{0} := 2^{n−1}. By induction we choose γ_{i} ∈ X ∩ s_{k_{i}} \ s_{k_{i}−1} and k_{i+1} such that the following conditions are met. ⋄ If e(j) ↦_{b}e(i + 1) then k_{i+1} < k_{j}. ⋄ If e(j) ↦_{g}e(i + 1) then k_{i+1} > k_{j}. ⋄ |k_{i+1} − k_{j}| ⩾ 2^{n−i−1} for every j ⩽ i. This we do for every i < n. Note that we are always able to choose the parameters in this way because all elements of [N]^{3} are strongly agreeable. Finally we may define H := {κα_{i} + γ_{i}|i < n}. H is 1-homogeneous.

• There is an independent M ∈ [l]^{m}. Again we have to distinguish two cases: ⋄ λ is regular. This case is easy. Let Y_{0} := ∅ and for limit ordinals ν let Y_{ν} := ⋃_{η<ν} X_{η}.

For any η < λ, i ∈ M and an enumeration f : m ⟷ M let

Y_{mη+i+1} := Y_{mη+i} ∪ {min({ν ∈ Z_{f(i)}|∀ζ ∈ Y_{mη+i} : ψ({ν, ζ}) = 0})}  (5)

At the end let Y := Y_{λ}. M is independent so the formulas on the right of (1) and (3) are jointly negated. The regularity of λ now ensures that the minimum referred to in (5) always exists.

⋄ λ is singular. Here we have to be a bit more careful. We have to make sure that we do not spoil our chances of defining a homogeneous set before our inductive construction is finished. So we thin out the Z_{i}’s further as follows: For each i ∈ M let η_{i} ∈ λ cf(λ) + 1 \ λ be the least ordinal such that there exists an enumeration e_{i} : η_{i} ⟷ Z_{i} such that

ν ⟼ max(\{\overline{\overline{\{ζ ∈ Z_{j}|ψ(\{e_{i}(ν), ζ\}) > 0\}}}|j ∈ M \ \{i\}\})

is nondecreasing. Fix such η_{i} and e_{i}. Similar to the case before we set Y_{0} := ∅, for limit ordinals ν we let Y_{ν} := ⋃_{ζ<ν} X_{ζ} and for ν < λ, i ∈ M and an enumeration f : m ⟷ M we define

Y_{mν+i+1} := Y_{mν+i} ∪ {e_{f(i)}(min({ζ < λ|∀ρ ∈ Y_{mν+i} : ψ({e_{f(i)}(ζ), ρ}) = 0}))}. (6)

Once more set Y := Y_{λ}. Again the independence of M implies that the right sides of (1) and (3) are jointly negated. By rearranging the Z_{i}’s using the e_{i}’s we ensured that the minimum in (6) always exists.

Let ⟨X_{η}|η < λl⟩ be a partition of X into λ sets of size κ. We set H := {κα+γ|α ∈ Y ∧γ ∈ X_{α}}. A little contemplation shows that H is 0-homogeneous for χ.

♢ Suppose that the finite combinatorial characterization above fails, i.e. there is an edge-2-coloured digraph D = ⟨l, A, c⟩ neither containing an independent set of size m nor a set of size n only inducing strongly agreeable triples. We define a colouring χ : [κλl]^{2} ⟶ 2 as follows.

χ : [κλl]^{2} ⟶ 2

\{κ(λj + α) + γ, κ(λk + β) + δ\}_{<} ⟼ \begin{cases}1 if j ↦_{b}k ∧ α < β ∧ δ < γ \\ 1 if k ↦_{b}j ∧ β < α ∧ γ < δ \\ 1 if j ↦_{g}k ∧ α < β ∧ γ < δ \\ 1 if k ↦_{g}j ∧ β < α ∧ δ < γ \\ 0 else. \end{cases}

• Suppose that χ would admit a 0-homogeneous set X ∈ [κλl]^{κλm}. Then there would have to be a set Y ∈ [l]^{m} such that otyp(X ∩ κλ(k + 1) \ κλk) = κλ for any k ∈ Y. Since D contains no independent set of size m we may choose {j, k} ∈ [Y]^{2} with j ↦ k. Let α := min{η < λ| otyp(X ∩ κ(λj + η + 1) \ κ(λj + η)) = κ} and let β := min{η ∈ λ \ (α + 1)| otyp(X ∩ κ(λk + η + 1) \ κ(λk + η) = κ}. We distinguish two cases:

⋄ c({j, k}) = 0. Let γ := min{η < κ|κ(λk + β) + η ∈ X} and let δ := min{η ∈ κ \ (γ + 1)|κ(λj + α) + η ∈ X}. Obviously χ({κ(λj + α) + δ, κ(λk + β) + γ}) = 1 contradicting the 0-homogeneity of X.

⋄ c({j, k}) = 1. Let γ := min{η < κ|κ(λj + α) + η ∈ X} and let δ := min{η ∈ κ \ (γ + 1)|κ(λk + β) + η ∈ X}. Obviously χ({κ(λj + α) + γ, κ(λk + β) + δ}) = 1 contradicting the 0-homogeneity of X.

• Now suppose that χ would admit a 1-homogeneous n-tuple X ∈ [κλl]^{n}. Per definitionem of χ we have that {κ(λj + α) + γ, κ(λk + β) + δ} ∈ [X]^{2} for j, k < l; α, β < λ and γ, δ < κ implies j ≠ k; α ≠ β and γ ≠ δ. Consider Y := {k < l|∃η < κλ : κλ + η ∈ X}. We have Y ∈ [l]^{n} and in fact Y induces a subdigraph S of D. W.l.o.g. we may assume that S is a tournament because if {j, k} ∈ [Y]^{2} is independent we have that X ∩ ((κλ(j + 1) \ κλj) ∪ (κλ(k + 1) \ κλk) ⊂ X is 0-homogeneous. So Y is a tournament and contains a triple {i, j, k} ∈ [Y]^{3} which is not strongly agreeable. Per definitionem of Y we may conclude that there are α, β, γ < λ and δ, η, ζ < κ such that κ(λi + α) + δ, κ(λj + β) + η, κ(λk + γ) + ζ ∈ X. We may distinguish three cases:

⋄ It is a 3-cycle. Assume i ↦ j ↦ k ↦ i. Since X is 1-homogeneous we may, per definitionem of χ, conclude that α < β, β < γ and γ < α. Contradiction!

⋄ We have i ↦_{b}j, j ↦_{b}k and i ↦_{g}k. By 1-homogeneity of X and per definitionem of χ we

may conclude that δ > η, η > ζ and δ < ζ. Contradiction! ⋄ We have i ↦_{g}j, j ↦_{g}k and i ↦_{b}k. Again we may use the 1-homogeneity of X and the

definition of χ to conclude that δ < η, η < ζ and δ > ζ. Contradiction!

Note that modulo a renaming of i, j and k these three cases exhaust all possibilities.

This finishes the second part of the proof.

■

Similar to before we denote by S_{n} the class of graphs G on n vertices such that all triples in G are strongly agreeable and by r(I_{m}, S_{n}) the smallest natural number l such that all digraphs on l vertices either contain an independent set of size m or an induced subgraph on n vertices all triples of which are strongly agreeable. As before we may use this notation to condense the equivalences proved above into a single formula:

r(κλm, n) = κλr(I_{m}, S_{n}) for κ weakly compact and any cardinal λ ∈ κ \ ω.

Analogous to [89Ba] we can prove another nice theorem.

Theorem 3.3. If MA_{ℵ_{1}} holds true then r(ω_{1}ωm, n) = ω_{1}ωr(I_{m}, S_{n}).

Let χ : [ω_{1}ωl]^{2} ⟶ 2 be any colouring. We define E := {P ∈ [ω_{1}ωl]^{2}|χ(P) = 1}.

Let Z := ⋃_{α<Ω}[ω_{1}(α + 1) \ ω_{1}α]^{ℵ_{1}}

For X ∈ Z let α_{X} < Ω be such that X ∈ [ω_{1}(α_{X} + 1) \ ω_{1}α_{X}]^{ℵ_{1}}. Let A_{X} := {ξ < ω_{1}|ω_{1}α_{X} + ξ ∈ X}. We say that the pair ⟨X, Y ⟩ is

♢ in constellation black iff X, Y ∈ Z and

∀B ∈ [X]^{ℵ_{1}}, C ∈ [Y]^{ℵ_{1}}∃γ ∈ A_{C}, β ∈ A_{B} \ (γ + 1) : {ω_{1}α_{X} + β, ω_{1}α_{Y} + γ} ∈ E.

♢ in constellation grey iff X, Y ∈ Z and

∀B ∈ [X]^{ℵ_{1}}, C ∈ [Y]^{ℵ_{1}}∃β ∈ A_{B}, γ ∈ A_{C} \ (β + 1) : {ω_{1}α_{X} + β, ω_{1}α_{Y} + γ} ∈ E.

♢ free iff ∀B ∈ [X]^{ℵ_{1}}, C ∈ [Y]^{ℵ_{1}}∃D ∈ [B]^{ℵ_{1}}, F ∈ [C]^{ℵ_{1}}∀δ ∈ D, η ∈ F : {δ, η} ∉ E.

Let us call a set S ⊂ Ω weakly independent if for all α, β < Ω with X = S∩ω_{1}(α+1)\ω_{1}α and Y = S ∩ ω_{1}(β + 1) \ ω_{1}β and \overline{\overline{X}} = \overline{\overline{Y}} = ℵ_{1} we have that ⟨X, Y ⟩ is free.

For the proof we are going to use theorem 3.1 from [89Ba]. By limiting its scope to the case α = ω we get the following theorem.

Theorem 3.4. Assume MA_{ℵ_{1}}. Let E ⊂ [ω_{1}ω]^{2} be a graph and let W ∈ [ω_{1}ω]^{ω_{1}ω} be weakly independent. Then there exists H ∈ [W]^{ω_{1}ω} which is independent such that ∀n < ω : \overline{\overline{H ∩ ω_{1}(n + 1) \ ω_{1}n}} ∈ \{0, ℵ_{1}\} and H ∩ω_{1}(n+1)\ω_{1}n ⊋ ∅ implies \overline{\overline{W ∩ ω_{1}(n + 1) \ ω_{1}n}} ⩽ ℵ_{0} for all natural n.

Now we prove theorem 3.3.

Proof. Even without MA_{ℵ_{1}} it is easy to see that r(ω_{1}ωm, n) ⩾ ω_{1}ωr(I_{m}, S_{n}). Let D be a 2-coloured digraph showing l < r(I_{m}, S_{n}). Now consider the following colouring:

χ : [ω_{1}ωl]^{2} ⟶ 2

\{ω_{1}ωh + ω_{1}j + α, ω_{1}ωi + ω_{1}k + β\}_{<} ⟼ \begin{cases}1 if h ↦_{b}i ∧ j < k ∧ β < α \\ 1 if i ↦_{b}h ∧ k < j ∧ α < β \\ 1 if h ↦_{g}i ∧ j < k ∧ α < β \\ 1 if i ↦_{g}h ∧ k < j ∧ β < α \\ 0 else. \end{cases}

Analogously to the proof of theorem 3.2 this now shows ω_{1}ωl ↛ (ω_{1}ωm, n).

Now assume MA_{ℵ_{1}}. Let l := r(I_{m}, S_{n}). We are going to show ω_{1}ωl → (ω_{1}ωm, n) by adapting the method of [89Ba] for our purposes.

Note that if a pair ⟨X, Y ⟩ is not free there are X′ ∈ [X]^{ℵ_{1}} and Y′ ∈ [Y]^{ℵ_{1}} such that ⟨X′, Y′⟩ is in one of the two other constellations. If at least one of these three properties applies to a pair then we call it decided.

We are choosing l-tuples ⟨X_{0}^{F} , …, X_{l−1}^{F}⟩ with F ∈ [ω]^{<ω} by recursion on max(F).

♢ If \overline{\overline{F}} = 1 and i < l let X_{i}^{F} ∈ [ω_{1}(ωi+⋃ F +1)\ω_{1}(ωi+⋃ F)]^{ℵ_{1}} such that for all G ∈ [⋃ F]^{<ω} and j ∈ l \ {i} either ⟨X_{j}^{G}, X_{i}^{F} ⟩ is free or there is an X ∈ [X_{j}^{G}]^{ℵ_{1}} such that ⟨X, X_{i}^{F} ⟩ is in one of the other two constellations above. This can be achieved by thinning out repeatedly.

♢ If \overline{\overline{F}} ∈ ω \ 2 let μ := max(F) and G := F \ \{μ\}. Now by again thinning out repeatedly for all i < l choose X_{i}^{F} ⊂ X_{i}^{G} such for all j ∈ l \ {i} we have that ⟨X_{i}^{F} , X_{j}^{{μ}}⟩ is decided.

Claim 3.5. For every natural f there is an F ∈ [ω]^{f} and an H ∈ [ω]^{ω} such that for all g, h < l the facts both whether or not for x, y ∈ [H]^{i} with i ∈ F and max(x) < min(y) we have that ⟨X_{g}^{x}, X_{h}^{y}⟩ is free or not free and what the constellation of a pair ⟨X_{g}^{x}, X_{h}^{y}⟩ with min(y) ∈ x and x, y ∈ [H]^{i} is only depends on g and h.

Proof of Claim: We repeatedly use Ramsey’s theorem to arrive at F and H.

Using Ramsey’s theorem we thin ω to some H_{0} ∈ [ω]^{ω} on which the freeness of some such ⟨X_{g}^{x}, Y_{h}^{y}⟩ for x, y ∈ [H_{0}]^{1} only depends on {g, h} and whether max(x) < min(y) or max(y) < min(x).

Because of the nature of our recursive construction the constellation of a pair ⟨X_{g}^{x}, X_{h}^{y}⟩ with min(y) ∈ x is determined by the constellation of the pair ⟨X_{g}^{x∩(min(y)+1)}, X_{h}^{{min(y)}}⟩. The constellation of this pair however can be made canonical as well using Ramsey’s theorem. So inductively do this for x ∩ min(y) = i to arrive at some H′_{i} for i < ω and after that find an H_{i+1} ∈ [H′_{i}]^{ω} on which the freeness/non-freeness for x, y ∈ [H_{i+1}]^{i+1} with max(x) < min(y) is canonical, i.e. only depends on g and h. This yields a sequence H_{0} ⊃ H′_{0} ⊃ H_{1} ⊃ H′_{1} ⊃ . . ..

Since there are only finitely many possible patterns of both freeness/non-freeness and constellations we may find an F ∈ [ω]^{f} and an H in the sequence which is sufficiently thin such that these patterns are the same for all i ∈ F. ■(Claim)

Use the claim to find F of a sufficiently( for what folllows) large finite size 2L, say 2^{n+1}−2. Now we define a digraph by letting there be arrows as follows:

g ↦_{b}h implies ⟨X_{g}^{x}, X_{h}^{{max(x)}}⟩ generally is in constellation black,
g ↦_{g}h implies ⟨X_{g}^{x}, X_{h}^{{max(x)}}⟩ generally is in constellation grey.

Moreover whenever one of these conditions applies an arrow is set.

Now first suppose there were an independent set I ∈ [l]^{m}. Let ⟨h_{i}|i < ω⟩ be the ascending enumeration of H and pick some f ∈ F. Let Z := {{h_{fi}, …, h_{f(i+1)−1}}|i < ω}. Then the union of all the X_{g}^{x}’s for g ∈ I and x ∈ Z is a weakly independent set of size ω_{1}ωm. This is because by our recursive construction and by definition of our digraph ⟨X_{g}^{x\{max(x)}}, X_{h}^{y}⟩ is free whenever max(x) ∈ y and there is no arrow between g and h . We now may use theorem 3.4 to thin this out to some truly independent set of the same order-type, i.e. some set of order-type ω_{1}ωm which is homogeneous for χ in colour 0.

Now suppose that our digraph contains no independent set of size m. Since we chose l to be r(I_{m}, S_{n}) we know that there is a strongly agreeable set S ∈ [l]^{n}.

Let ⟨f_{i}|i < L⟩ be an ascending enumeration of F. Define a_{i} := {h_{f_{i}}, …, h_{f_{L}}⟩ and let A_{g}^{i} := X_{g}^{a_{i}}.

Claim 3.6. Let g, h ∈ S, {i, j} ∈ [L]^{2} and i < j. Now if g ↦_{b}h then ⟨A_{g}^{i}, A_{h}^{j}⟩ is in constellation black and if g ↦_{g}h then it is in constellation grey.

Proof of Claim: Consider x := {h_{f_{i}}, …, h_{f_{j−1}}} and y := {h_{f_{j}}, …, h_{f_{2j−i−1}}}.

We know that ⟨X_{g}^{x}, X_{h}^{y}⟩ is not free. Because of X_{g}^{y} ⊂ X_{h}^{{h_{f_{j}} }} we have that ⟨X_{g}^{x}, X^{{h_{f_{j}} }}⟩ is

not free. By our recursive construction we get that ⟨X_{g}^{x∪{h_{f_{j}} }}, X_{h}^{{h_{f_{j}} }}⟩ is decided. The colour

of the arrow between g and h in S tells us how. Since A_{h}^{i} ⊂ X_{h}^{x∪{h_{f_{j}} }} and A_{g}^{j} ⊂ X_{g}^{{h_{f_{j}} }} the claim follows. ■(Claim)

Now we are going to construct the complete graph G ∈ [ω_{1}ωl]^{n} with [G]^{2} ⊂ E. To this end let ⟨s_{i}|i < n⟩ be an enumeration of S such that s_{i} ↦_{g}s_{j} or s_{j} ↦_{b}s_{i} for all i < j < n. This is possible since all triples in S are strongly agreeable. To start the construction now, i.e. in step 0 choose the middle element j_{0} of L. This divides L into two intervals of size, say, 2^{n−1} − 1. Let us call {−1, L} the border.

Now inductively in step i < n we haven chosen j_{k}’s with k < i such that the minimal distance between either of them and between one of them and the border is 2^{n−i} − 1. Now we choose an j_{i+1} such that the minimal distance between two of the j_{k+1}’s for k ⩽ i and between of them and the border is 2^{n−i−1} −1 and such that j_{i+1} > j_{k} iff s_{k} ↦ s_{i} for all k ⩽ i. Again strong agreeability allows us to do this.

Finally we choose in step 0 an ordinal α_{0} ∈ A_{s_{0}}^{j_{0}} such that for all i ∈ n \ 1 we have \overline{\overline{\{α ∈ A_{s_{i}}^{j_{i}}|\{α_{0}, α\} ∈ E\}}} = ℵ_{1}. Such an ordinal exists for otherwise there would be an i < n and uncountably many α ∈ A_{s_{0}}^{j_{0}} which are only connected to countably many things in A_{s_{i}}^{j_{i}} by E. Because of the way in which we sorted the elements of S this would contradict the constellation of ⟨A_{s_{0}}^{j_{0}}, A_{s_{i}}^{j_{i}}⟩. Now thin out the A_{s_{i}}^{j_{i}} for i ∈ n \ 1 to those uncountable subsets of ordinals the unordered pairs with α_{0} of which are in E. Now generally in step i < n choose an ordinal α_{i} ∈ A_{s_{i}}^{j_{i}} such that {α_{k}, α_{i}} ∈ E for all k < i and thin out the A_{s_{k}}^{j_{k}}’s for k ∈ n \ (i + 1). In this way we may construct our complete graph of size n, i.e. our set homogeneous for χ in colour 1. ■

Now we may take a look at the easiest examples.

Theorem 3.7. r(I_{2}, S_{3}) = 6.

Proof.

The lower bound is provided by the counterexample on the right, for the upper bound one can argue as follows: Consider any vertex v in a six-element tournament—if the digraph is not a tournament we are finished immediately. Now N_{B}^{−}(v) + N_{B}^{+}(v) + N_{G}^{−}(v) + N_{G}^{+}(v) ⩾ 5 so we may conclude using the pigeonhole principle that one of these four neighborhoods contains at least two elements. But then v together with this neighborhood is strongly agreeable.

■

Theorem 3.8. r(I_{3}, S_{3}) = 15.

Proof. The lower bound is given by the counterexample above. It can be viewed as a digraph

on ℤ_{14} where v ↦_{b}v + 1, v ↦_{g}v + 2, v ↦_{g}v − 3 and v ↦_{b}v − 4 for all v ∈ ℤ_{14}.

■

The upper bound is established by theorem 4.4 below.

Corollary 3.9. Let κ be the least weakly compact cardinal. Then r(κℵ_{ε_{ω7+9}}3, 3) = κℵ_{ε_{ω7+9}}15.

4 Upper bounds

4.1 Upper bounds for independent versus strongly agreeable sets.

We now are going to provide several general upper bounds for various Ramsey numbers. We start with something easy—an upper bound for the Ramsey numbers r(I_{m}, S_{3}).

Lemma 4.1. r(I_{m+1}, S_{3}) ⩽ r(I_{m}, S_{3}) + 4m + 1 for all m ∈ ω \ 2.

Proof. Let D be any edge-bicoloured digraph on r(I_{m}, S_{3}) + 4m + 1 vertices. Fix any vertex v. Since \overline{\overline{N_{B}^{+}(v)}} + \overline{\overline{N_{B}^{−}(v)}} + \overline{\overline{N_{G}^{+}(v)}} + \overline{\overline{N_{G}^{−}(v)}} + \overline{\overline{I(v)}} = r(I_{m}, S_{3}) + 4m it follows that one of the following cases has to obtain:

♢ \overline{\overline{N_{B}^{+}(v)}} ⩾ m + 1.

♢ \overline{\overline{N_{B}^{−}(v)}} ⩾ m + 1.

♢ \overline{\overline{N_{G}^{+}(v)}} ⩾ m + 1.

♢ \overline{\overline{N_{G}^{−}(v)}} ⩾ m + 1.

♢ \overline{\overline{I(v)}} ⩾ r(I_{m}, S_{3}).

In the first four cases either the respective neighbourhood is independent or two vertices in it are connected by an arrow in which case they form an S_{3} together with v. In the last case the neighbourhood either contains an S_{3} or an independent set of size m which together with v would form an independent set of size m + 1. ■

Theorem 4.2. For all m ∈ ω \ 2 we have r(I_{m}, S_{3}) ⩽ m(2m − 1).

Proof. The base case is established by theorem 3.7. For the inductive step by lemma 4.1 we only have to check that

(m + 1)(2(m + 1) − 1) = m(2m − 1) + 4m + 1

which is true. ■

We continue now by providing an upper bound for r(I_{2}, S_{n}).

Lemma 4.3. For all n ∈ ω \ 3 we have r(I_{2}, S_{n+1}) ⩽ 4r(I_{2}, S_{n}) − 2.

Proof. Let T = ⟨V, A, c⟩ be a bicoloured tournament on 4r(I_{2}, S_{n}) − 2 vertices. Fix any vertex v ∈ V. Since \overline{\overline{N_{B}^{−}(v) + N_{B}^{+}(v) + N_{G}^{−}(v) + N_{G}^{+}(v)}} = 4r(I_{2}, S_{n}) − 3 by the pigeonhole principle one of these neighbourhoods N has cardinality at least r(I_{2}, S_{n}). Hence there is an S ∈ [N]^{n} in which all triples are strongly agreeable. So if we set X := S ∪ {v} we have X ∈ [V]^{n+1} and all triples in X are strongly agreeable. ■

Theorem 4.4. For any n ∈ ω \ 3 we have

r(I_{2}, S_{n}) ⩽ \frac{4^{n−1} + 2}{3}.

Proof. By induction. The base case is given by theorem 3.7. The induction step also works:

4 · \frac{4^{n−1} + 2}{3} − 2 = \frac{4^{n−1+1} + 4 · 2 − 2 · 3}{3} = \frac{4^{n+1−1} + 2(4 − 3)}{3}

■

Again, note that for any integer n also \frac{4^{n−1}+2}{3} is an integer. It is easy to see by induction that 4^{n−1} ≡ 1(3) for any n ∈ ω \ 1. Hence 4^{n−1} + 2 ≡ 0(3) for any n ∈ ω \ 1.

Now we want to give a general upper bound for r(I_{m}, S_{n}).

Lemma 4.5. r(I_{m+1}, S_{n+1}) ⩽ r(I_{m}, S_{n+1}) + 4r(I_{m+1}, S_{n}) − 3 for all m ∈ ω \ 2 and all n ∈ ω \ 3.

Proof. Immediate. ■

Theorem 4.6. For all m ∈ ω \ 2 and all n ∈ ω \ 3 we have r(I_{m}, S_{n}) ⩽ u(m, n) where

u(m, n) :=\frac{1}{4}(3 + ∑_{i=0}^{n−1} \binom{i + m − 2}{i}4^{i}).  (7)

Proof. By induction. First we verify that u(2, 3) = 6. Recall that we have r(I_{2}, S_{3}) = 6 by theorem 3.7. Next we check that for u(2, n) agrees with the formula from theorem 4.4. We have

u(2, n) = \frac{1}{4}(3 + ∑_{i=0}^{n−1} 4^{i}).

Consider v(n) := u(2, n + 1) − u(2, n). It is easy to see that v(n) = 4^{n−1}. But it is also easy to see that

\frac{4^{n} + 2}{3} − \frac{4^{n−1} + 2}{3} = 4^{n−1}.

Induction on n provides what was demanded. It is even easier to see, using well-known properties of the binomial coefficients that

u(m, 3) = m(2m − 1).

Now we can check that in fact

u(m + 1, n + 1) = u(m, n + 1) + 4u(m + 1, n) − 3.  (8)

Then with lemma 4.5 the theorem will follow. The following calculation proves (8).

u(m, n + 1) + 4u(m + 1, n) − 3
= \frac{1}{4}(3 + ∑_{i=0}^{n} \binom{i + m − 2}{i}4^{i} + 4 ∑_{i=0}^{n−1} \binom{i + m − 1}{i}4^{i})

= \frac{1}{4}(3 + ∑_{i=0}^{n} \binom{i + m − 2}{i}4^{i} + ∑_{i=1}^{n} \binom{i + m − 2}{i − 1}4^{i})

= \frac{1}{4}(4 + ∑_{i=1}^{n} (\binom{i + m − 2}{i} + \binom{i + m − 2}{i − 1})4^{i})

= \frac{1}{4}(4 + ∑_{i=1}^{n} \binom{i + m − 1}{i}4^{i})

= \frac{1}{4}(3 + ∑_{i=0}^{n} \binom{i + m − 1}{i}4^{i})
= u(m + 1, n + 1).
■

4.2 Upper bounds for independent versus agreeable sets.

We are now going to provide an upper bound for the Ramsey numbers r(I_{n}, A_{3}).

Lemma 4.7. r(I_{n+1}, A_{3}) ⩽ r(I_{n}, A_{3}) + 2r(I_{n+1}, L_{3}) + 4n − 1 for all n ∈ ω \ 2.

Proof. Let there be an edge-tricoloured digraph ⟨V, A⟩ with r(I_{n}, A_{3}) + 2r(I_{n+1}, L_{3}) + 4n − 1 vertices. Pick any vertex v such that N_{B}^{+}(v) is maximal. Note that \overline{\overline{V \ \{v\}}} = r(I_{n}, A_{3}) + 2r(I_{n+1}, L_{3}) + 4n − 2! Now we may distinguish several cases. Note that necessarily at least one of them must hold!

♢ \overline{\overline{N_{B}^{−}(v)}} ⩾ n + 1. Since we chose v to have maximum solid black out-degree we might immediately hand over to the next case.

♢ \overline{\overline{N_{B}^{+}(v)}} ⩾ n + 1. In this case either there are two vertices w, x ∈ N_{B}^{+}(v) which are connected by an arrow—in which case {v, w, x} is an agreeable triple—or N_{B}^{+}(v) forms an independent set of size n + 1. In both cases we found a set homogeneous in the sought-after-sense.

♢ \overline{\overline{N_{G}^{−}(v)}} ⩾ r(I_{n+1}, L_{3}). If there are w, x ∈ N_{G}^{−}(v) which are connected by either a solid black or a solid grey arrow then {v, w, x} is an agreeable triple. So let us assume that all pairs of vertices in N_{G}^{−}(v) are either connected by dashed black arrows or not connected at all. But now our case condition implies that we either have an independent set of size n + 1 or a transitive dashed black triple—which is agreeable.

♢ \overline{\overline{N_{G}^{+}(v)}} ⩾ r(I_{n+1}, L_{3}). Works exactly like the case before.

♢ \overline{\overline{N_{D}^{−}(v)}} ⩾ n + 1. This and the next case work like the second. Either there are two vertices w, x ∈ N_{D}^{−}(v) which are connected by an arrow—then {v, w, x} is agreeable—or N_{D}^{−}(v) is an independent set of size n + 1.

♢ \overline{\overline{N_{D}^{+}(v)}} ⩾ n + 1. Again either there are two vertices which are connected which then form an agreeable triple together with v or N_{D}^{+}(v) is independent.

♢ \overline{\overline{I(v)}} ⩾ r(I_{n}, A_{3}). Now in the last case I(v) either contains an agreeable triple or is itself independent of size n. In the first case we are finished immediately and in the second I(v) ∪ {v} is an independent set of size n + 1.

■

Corollary 4.8. r(ω^{2}(n + 1), 3) ⩽ r(ω^{2}n, 3) + ω2r(ω(n + 1), 3) + ω^{2}(4n − 1) for all n ∈ ω \ 2.

Theorem 4.9. For all n ∈ ω \ 2 we have

r(I_{n}, A_{3}) ⩽ \frac{(2n + 1)(n^{2} + 4n − 6)}{3}.  (9)

Proof. By induction. The basis case is n = 2, formula 9 is verified by theorem 2.14 in it. So let us assume that the formula holds up to some n ∈ ω \ 2. Using lemma 4.7 we get

r(I_{n+1}, A_{3}) ⩽ r(I_{n}, A_{3}) + 2r(I_{n+1}, L_{3}) + 4n − 1.

Larson and Mitchell—see Lemma 4.1 of [97LM]—showed that r(I_{n}, L_{3}) ⩽ n^{2}, so we may bound this from above as follows:

⩽\frac{(2n + 1)(n^{2} + 4n − 6)}{3} + 2(n + 1)^{2} + 4n − 1
=\frac{(2(n + 1) + 1)((n + 1)^{2} + 4(n + 1) − 6)}{3}
■

Note that the fraction in theorem 4.9 is an integer if n is one. If n ≡ 1(3) then 2n+1 ≡ 0(3) and we are fine. If, however, n ≡ 0(3) then n^{2} + 4n − 6 ≡ 0(3) and if n ≡ 2(3) then n^{2} + 4n − 6 ≡ 0(3) too.

5 A semiconstructive lower bound

Theorem 5.1. r(I_{mn+1}, A_{3}) > (r(I_{m+1}, L_{3}) − 1)(r(I_{n+1}, L_{3}) − 1).

Proof. Let D_{0} = ⟨V_{0}, A_{0}⟩ be a digraph on r(I_{m}, L_{3}) − 1 vertices neither containing a transitive triple nor an independent set of size m + 1 and let D_{1} = ⟨V_{1}, A_{1}⟩ be a digraph on r(I_{n}, L_{3}) − 1 vertices neither containing a transitive triple nor an independent set of size n + 1. Then consider the coloured digraph D_{0} ∗ D_{1} := ⟨V_{0} × V_{1}, A_{2}, c⟩ where A_{3} = {⟨⟨v_{0}, v_{1}⟩, ⟨v_{2}, v_{1}⟩⟩|v_{0}, v_{2} ∈ V_{0} ∧ v_{1} ∈ V_{1} ∧ ⟨v_{0}, v_{2}⟩ ∈ A_{0}}, A_{4} = {⟨⟨v_{0}, v_{1}⟩, ⟨v_{2}, v_{3}⟩|v_{0}, v_{2} ∈ V_{0} ∧ v_{1}, v_{3} ∈ V_{1} ∧ ⟨v_{1}, v_{3}⟩ ∈ A_{1}}, A_{2} = A_{3} ∪ A_{4}, c^{“}A_{3} = {1} and c^{“}A_{4} = {2}. Clearly the independent sets in D_{0} ∗ D_{1} have size at most mn and the only transitive triples in D_{0} ∗ D_{1} contain two solid grey arrows which either originate from the same vertex or point at the same. Both types of triples are disagreeable. ■

6 Some tables

At the end we take the liberty of supplying a table of some Ramsey numbers r(α, n) known today for countable ordinals α and natural numbers n. Following the example of Radziszowski in [94Ra] we also supply a complementary table containing references. If a reference is given above another, then the upper one gives the upper bound and the lower one gives the lower bound.

3  4  5  6  7  8  9  m
3  6  9  14  18  23  28  36
4  9  18  25
ω  ω  ω  ω  ω  ω  ω  ω  ω
ω + 1  ω2 + 1  ω3 + 1  ω4 + 1 ω5 + 1 ω6 + 1 ω7 + 1 ω8 + 1  ω(m − 1) + 1
ω + 2  ω2 + 4  ω3 + 7  ω4 + 11 ω5 + 16 ω6 + 22 ω7 + 29 ω8 + 37 ω(m − 1) + \frac{m(m−1)}{2} + 1
ω + 3  ω2 + 8  ω3 + 16
ω + n ω2 + r(n, 3) + n − 1
λ2 λ4 λ8 λ14 λ28
λ3  λ9
ω^{2}  ω^{2}  ω^{2}  ω^{2}  ω^{2}  ω^{2}  ω^{2}  ω^{2}  ω^{2}
ω^{2} + 1  ω^{2}2 + 1  ω^{2}3 + 1  ω^{2}4 + 1 ω^{2}5 + 1 ω^{2}6 + 1 ω^{2}7 + 1 ω^{2}8 + 1  ω^{2}(m − 1) + 1
ω^{2} + 2  ω^{2}2 + 4  ω^{2}3 + 7  ω^{2}4 + 11 ω^{2}5 + 16 ω^{2}6 + 22 ω^{2}7 + 29 ω^{2}8 + 37 ω^{2}(m − 1) + \frac{m(m−1)}{2} + 1
ω^{2} + 3  ω^{2}2 + 8  ω^{2}3 + 16
ω^{2} + n ω^{2}2 + r(n, 3) + n − 1
ω^{2} + ω  ω^{2}4 + ω
ω^{2}2  ω^{2}10
ω^{3}  ω^{4}  ω^{4}  ω^{5}  ω^{5}  ω^{5}  ω^{5}  ω^{6}  ω^{2+⌈ld(m)⌉}
ω^{3} + n  ω^{4} + r(n, 3)  ω^{4} + ω^{3} + r(n, 4) + n − 1
ω^{4}  ω^{7}  ω^{7}  ω^{10}  ω^{10}  ω^{10}  ω^{10}
ω^{5+n}  ω^{9+2n}  ω^{9+2n}  ω^{13+3n} ω^{13+3n} ω^{13+3n} ω^{13+3n} ω^{17+4n}  ω^{1+(4+n)⌈ld(m)⌉}
ω^{ω}  ω^{ω}  ω^{ω}  ω^{ω}  ω^{ω}  ω^{ω}  ω^{ω}  ω^{ω}  ω^{ω}
ω^{ω^{2}}  ω^{ω^{2}}  ω^{ω^{2}}
κλ2  κλ6
κλ3  κλ15

3  4  5  6  7  8  9  10+m

                                                         [68GY] [92MM] [82GR]
 3  [55GG]  [55GG]  [64Ké]  [66Ka] [82GR] [66Ka]

                                  [95MR]

 4  [55GG]  [55GG]  [65Ka]
ω  [30Ra]  [30Ra]  [30Ra]  [30Ra]  [30Ra] [30Ra] [30Ra] [30Ra]
ω + 1  [69HSc]  [69HSc]  [69HSc]  [69HSc]  [69HSc] [69HSc] [69HSc] [69HSc]
ω + 2  [69HSc]  [69HSc]  [69HSc]  [69HSc]  [69HSc] [69HSc] [69HSc] [69HSc]
ω + 3  [69HSc]  [69HSc]
ω + n  [69HSc]
λ2  [56ER]/[74Ba] [64EM]/[74Ba] [70RP]/[74Ba] [70RP]/[74Ba]
λ3  [74Be]/[74Ba]
ω^{2}  [57Sp]  [57Sp]  [57Sp]  [57Sp]  [57Sp] [57Sp] [57Sp] [57Sp]
ω^{2} + 1  [69HSc]  [69HSc]  [69HSc]  [69HSc]  [69HSc] [69HSc] [69HSc] [69HSc]
ω^{2} + 2  [69HSc]  [69HSc]  [69HSc]  [69HSc]  [69HSc] [69HSc] [69HSc] [69HSc]
ω^{2} + 3  [69HSc]  [69HSc]

ω^{2} + n  [69HSc]
ω^{2} + ω  [69HSb]

ω^{2}2  [69HSa]
ω^{3}  [57Sp]  [69HSb]  [74No]  [74No]  [74No] [74No] [74No] [74No]
ω^{3} + n  [69Mi]  [69HSb]
ω^{4}  [75No]  [75No]  [10HL]  [10HL]  [10HL] [10HL]
ω^{5+n}  [79No]  [79No]  [79No]  [79No]  [79No] [79No] [79No] [79No]
ω^{ω}  [74La]  [74La]  [74La]  [74La]  [74La] [74La] [74La] [74La]
ω^{ω^{2}}  [upDL]  [upDL]

κλ2  This paper!
κλ3  This paper!

Combinations of the methods used to find the numbers above would probably generalize some results.

7 Problems, Questions & Conjectures

To the author the most interesting open question now is the following: Question 7.1. What is the order of growth of the function n ↦ r(I_{n}, A_{3})?

The author conjectures that he not being able to present a better upper bound is at most partly due to his personal incompetence. So he states the following conjecture—which to his mind seems very modest indeed. Conjecture 7.2. There exists an ε > 0 such that εn^{2+ε} < r(I_{n}, A_{3}) for all natural n.

The author was considerably surprised by the second counterexample showing r(I_{2}, A_{3}) > 9 since there was no solid black arrow in it. Hence the following seems to be a natural question to the author: Question 7.3. Are sharp lower bounds for r(I_{m}, A_{n}) for m and n natural numbers always attainable by counterexamples using only solid grey and dashed black arrows?

The author conjectures the answer to this question to be “No.”.

The author was not able to come up with a formula for the upper bounds given by the recurrence relations for r(I_{m}, A_{n}). Perhaps an expert on recurrence relations can find one. Problem 7.4. Find a nice formula for a general upper bound for r(I_{m}, A_{n})!

It is fairly obvious that the methods of this paper could be extended to determine Ramsey numbers for even more decomposable ordinals. The related finite combinatorics might turn out to be extremely difficult though. We mention just one example as an open problem. Problem 7.5. Determine r(κλω2, 3) for κ > λ both weakly compact!

The motivation behind this research was mainly an interest in countable ordinals. So although we have not discussed Ramsey numbers involving ordinals in ω_{1} \ ω^{3} here at all there are many open problems there. As a teaser we mention the following: Problem 7.6. Determine r(ω^{ω2}, 3)!

The author in vain tried to strengthen theorem 3.3 by replacing MA_{ℵ_{1}} by “ω_{1}ω is a partition ordinal.”. So he has to leave this as an open question. Question 7.7. Does r(ω_{1}ωm, n) = ω_{1}ωr(I_{m}, S_{n}) whenever ω_{1}ω is a partition ordinal?

A variant of this problem is the following:

Question 7.8. Does r(ω_{1}ωm, n) = ω_{1}ωr(I_{m}, S_{n}) whenever ω_{1}ω^{2} is a partition ordinal?

At the end we want to mention that there are problems in Ramsey theory which to the author’s mind could have been attacked algorithmically but were not. The author conjectures that r(I_{4}, L_{3}) and r(I_{3}, L_{4}) could easily be algorithmically determined. The same should hold true for r(I_{2}, S_{4}). Meanwhile the author is rather sceptical about the possibilities to determine r(I_{3}, A_{3}) or r(I_{2}, A_{4}) without considerable further mathematical insight.

The author wishes to thank at this point Rene Schipperus for getting him interested in this subject, his PhD advisor Stefan Geschke for allowing him to venture into the realms of it, Benjamin Seyfferth for his help in reading parts of the french articles [69HSc], [69HSa] and [69HSb], Andrés Caicedo, Peter Komjath, Lionel Ngyuen Van The, Philipp Schlicht, Stevo Todorčević, Wolfgang Wohofsky and in particular Jean Larson for discussing this work with them. Moreover [98CG] was a great source of inspiration for the author. At last I would also like to thank the referee her/his input.^{4}

References

[upDL] Carl Darby and Jean Ann Larson. A positive partition relation for a critical countable ordinal. In preparation.

[10HL] Andras Hajnal and Jean Ann Larson. Handbook of set theory. Vol. 1, chapter Partition relations, pages Vol. 1: xiv+736 pp. up. Springer, Dordrecht, 2010.

[09BG] Jørgen Bang-Jensen and Gregory Gutin. Digraphs. Springer Monographs in Mathematics. Springer-Verlag London Ltd., London, second edition, 2009. Theory, algorithms and applications.

[09GS] Agelos Georgakopoulos and Philipp Sprüssel. On 3-coloured tournaments. Preprint, April 2009, http://www.arxiv.org/pdf/0904.1967.pdf.

[03Ka] Akihiro Kanamori. The higher infinite. Springer Monographs in Mathematics. Springer-Verlag, Berlin, second edition, 2003. Large cardinals in set theory from their beginnings.

[98CG] Fan Rong K Chung Graham and Ronald Lewis Graham. Erdős on graphs. up. A K Peters Ltd., Wellesley, MA, 1998. His legacy of unsolved problems.

[98PR] Konrad Piwakowski and Stanisław P. Radziszowski. 30 ≤ R(3, 3, 4) ≤ 31. J. Combin. Math. Combin. Comput., 27:135–141, 1998.

[97LM] Jean A. Larson and William J. Mitchell. On a problem of Erdős and Rado. Ann. Comb., 1(3):245–252, 1997. http://dx.doi.org/10.1007/BF02558478.

[97MR] Brendan Damien McKay and Stanisław P. Radziszowski. Subgraph counting identities and Ramsey numbers. J. Combin. Theory Ser. B, 69(2):193–209, 1997. http://dx.doi.org/10.1006/jctb.1996.1741.

4The research presented in this article was supported by the DFG project “Continuous Ramsey theory in higher dimension”.

[95MR] Brendan Damien McKay and Stanisław P. Radziszowski. R(4, 5) = 25. J. Graph Theory, 19(3):309–322, 1995. http://dx.doi.org/10.1002/jgt.3190190304.

[94Ra] Stanisław P. Radziszowski. Small Ramsey numbers. Electron. J. Combin., 1:Dynamic Survey 1, 30 pp. (electronic), 1994. http://www.combinatorics.org/Surveys/index.html.

[92MM] Brendan Damien McKay and Zhang Ke Min. The value of the Ramsey number R(3, 8). J. Graph Theory, 16(1):99–105, 1992. http://dx.doi.org/10.1002/jgt.3190160111.

[89Ba] James Earl Baumgartner. Remarks on partition ordinals. In Set theory and its applications (Toronto, ON, 1987), volume 1401 of Lecture Notes in Math., pages 5–17. Springer, Berlin, 1989.

[82GR] Charles Miller Grinstead and Sam M. Roberts. On the Ramsey numbers R(3, 8) and R(3, 9). J. Combin. Theory Ser. B, 33(1):27–51, 1982. http://dx.doi.org/10.1016/0095-8956(82)90055-7.

[79No] Eva Nosal. Partition relations for denumerable ordinals. J. Combin. Theory Ser. B, 27(2):190–197, 1979. http://dx.doi.org/10.1016/0095-8956(79)90080-7.

[75No] Eva Nosal. On arrow relations w(k,w) 2(2) (m,n,k less than w): A study in the partition calculus. up. ProQuest LLC, Ann Arbor, MI, 1975. Thesis (Ph.D.)–University of Calgary (Canada).

[74Ba] James Earl Baumgartner. Improvement of a partition theorem of Erdös and Rado. J. Combinatorial Theory Ser. A, 17:134–137, 1974.

[74Be] Jean-Claude Bermond. Some Ramsey numbers for directed graphs. Discrete Math., 9:313– 321, 1974.

[74No] Eva Nosal. On a partition relation for ordinal numbers. J. London Math. Soc. (2), 8:306– 310, 1974.

[74La] Jean Ann Larson. A short proof of a partition theorem for the ordinal ω^{ω}. Ann. Math. Logic, 6:129–145, 1973/74.

[70RP] Kenneth Brooks Reid, Jr. and Ernest Tilden Parker. Disproof of a conjecture of Erdős and Moser on tournaments. J. Combinatorial Theory, 9:225–238, 1970.

[69HSa] Labib Haddad and Gabriel Sabbagh. Calcul de certains nombres de Ramsey généralisés. C. R. Acad. Sci. Paris Sér. A-B, 268:A1233–A1234, 1969.

[69HSb] Labib Haddad and Gabriel Sabbagh. Nouveaux résultats sur les nombres de Ramsey généralisés. C. R. Acad. Sci. Paris Sér. A-B, 268:A1516–A1518, 1969.

[69HSc] Labib Haddad and Gabriel Sabbagh. Sur une extension des nombres de Ramsey aux ordinaux. C. R. Acad. Sci. Paris Sér. A-B, 268:A1165–A1167, 1969.

[69Mi] E. C. Milner. Partition relations for ordinal numbers. Canad. J. Math., 21:317–334, 1969.

[68GY] Jack Edward Graver and James Yackel. Some graph theoretic results associated with Ramsey’s theorem. J. Combinatorial Theory, 4:125–175, 1968.

[66Ka] J. G. Kalbfleisch. Chromatic Graphs and Ramsey’s theorem. PhD thesis, University of Waterloo, January 1966.

[65Ka] J. G. Kalbfleisch. Construction of special edge-chromatic graphs. Canad. Math. Bull., 8:575–584, 1965.

[64EM] Pál Erdős and Leo Moser. On the representation of directed graphs as unions of orderings. Magyar Tud. Akad. Mat. Kutató Int. Közl., 9:125–132, 1964.

[64Ké] Gerzson Kéry. On a theorem of Ramsey. Mat. Lapok, 15:204–224, 1964.

[57Sp] Ernst Specker. Teilmengen von Mengen mit Relationen. Comment. Math. Helv., 31:302– 314, 1957.

[56ER] Pál Erdős and Richard Rado. A partition calculus in set theory. Bull. Amer. Math. Soc., 62:427–489, 1956.

[55GG] Robert Ewing Greenwood, Jr. and Andrew Mattei Gleason. Combinatorial relations and chromatic graphs. Canad. J. Math., 7:1–7, 1955.

[30Ra] Frank Plumpton Ramsey. On a problem in formal logic. Proc. London Math. Soc., 30:264– 286, 1930.