NEW BOUNDS ON THE RAMSEY NUMBER r(I_{m}, L_{n})

FERDINAND IHRINGER, DEEPAK RAJENDRAPRASAD, AND THILO V. WEINERT

Abstract. We investigate the Ramsey numbers r(I_{m}, L_{n}) which is the minimal natural number k such that every oriented graph on k vertices contains either an independent set of size m or a transitive tournament on n vertices. Apart from the finitary combinatorial interest, these Ramsey numbers are of interest to set theorists since it is known that r(ωm, n) = ωr(I_{m}, L_{n}), where ω is the lowest transfinite ordinal number, and r(κm, n) = κr(I_{m}, L_{n}) for all initial ordinals κ. Continuing the research by Bermond from 1974 who did show r(I_{3}, L_{3}) = 9, we prove r(I_{4}, L_{3}) = 15 and r(I_{5}, L_{3}) = 23. The upper bounds for both the estimates above are obtained by improving the upper bound of m^{2} on r(I_{m}, L_{3}) due to Larson and Mitchell (1997) to m^{2} − m + 3. Additionally, we provide asymptotic upper bounds on r(I_{m}, L_{n}) for all n ≥ 3. In particular, we show that r(I_{m}, L_{3}) ∈ Θ(m^{2}/ log m).

Mathematical Subject Classification of the AMS: 05D10 (Primary), 03E02, 05C20, 05C55 (Secondary) .

1. Introduction

Ramsey Theory, sometimes described as the collection of mathematics conforming to the slogan that total disorder is impossible, can be traced back to [930Rams]. In this paper Ramsey proved the theorem now named after him. Shortly thereafter, Paul Erdős and George Szekeres, in [935ES], answered a question of Esther Klein affirmatively. She had previously shown that among any five points in the plane one can find four forming a convex quadrilateral and asked whether this result could be generalised. After a few more years, Erdős and Rado proved a cornucopia of theorems in their seminal paper [956ER]. This paper also saw the introduction of the partition symbol whose definition we restate here. We also use [X]^{n} to denote the family of all n-element subsets of X while ω denotes the order-type of the natural numbers.

Definition 1.1. α ⟶ (β_{0}, …, β_{k})^{n} means that for any set X of size α and any function (which may be called colouring) χ : [X]^{n} ⟶ k + 1 there is an i ⩽ k and a Y ⊂ X of size β_{i} which is homogeneous for χ, i.e. the colouring χ is constant on [Y]^{n}. We call α the source and β_{0}, …, β_{k} the targets of the relation.

The first author acknowledges support from a PIMS Postdoctoral Fellowship. Research supported by the Israel Science Foundation grant number 1365/14.

The notion of size in this definition is usually interpreted to mean cardinality but one can in principle employ any notion of size for the formulation of a corresponding partition relation. The main alternative is to consider the notion of linear ordertype. This is particularly attractive since there is exactly one linear order-type for every finite cardinal (also known as natural number) n. Also, assuming the Axiom of Choice, every set can be well-ordered, so replacing every cardinal in the relation above by its corresponding initial ordinal (the smallest ordinal of that cardinality), yields an equivalent statement. Therefore replacing cardinality by linear order-type amounts to a proper extension of the scope of Definition 1.1. Now Ramsey’s Theorem for two colours may be stated as follows:

Theorem 1.2. ω ⟶ (ω, ω)^{n} for all natural numbers n.

There exists an alternative notation which is more common in papers on finitary combinatorics:

Definition 1.3. r_{n}(β_{0}, …, β_{k}) is the smallest α such that α ⟶ (β_{0}, …, β_{k})^{n} but γ−̸→(β_{0}, …, β_{k})^{n} for all γ smaller than α. The number r(β_{0}, …, β_{k}) is understood to be r_{2}(β_{0}, …, β_{k}).

As the finite linear orders are themselves well-ordered by proper inclusion, for finite α the relation α ⟶ (β_{0}, …, β_{k})^{n} is equivalent to r_{n}(β_{0}, …, β_{k}) ⩾ α.

In this paper we denote a set of m pairwise independent vertices by I_{m}, the undirected complete graph on n vertices by K_{n} and the transitive tournament on n vertices by L_{n}. By an oriented graph we mean a graph without loops or double edges all edges of which have an orientation.

If an oriented graph D does not contain an oriented graph S as an induced subgraph, then we say that D is S-free. If S_{0}, S_{1} are oriented graphs and D contains neither as an induced subgraph, we say that D is (S_{0}, S_{1})-free. For natural numbers m and n let r(I_{m}, L_{n}) denote the minimal natural number k such that no oriented graph on k vertices is (I_{m}, L_{n})-free. In this spirit, the classical undirected Ramsey numbers r(m, n), which is the minimal natural number k such that no undirected graph on k vertices is (I_{m}, K_{n})-free will be denoted here as r(I_{m}, K_{n}).^{1}

Then [956ER, Theorem 25] amounts to the following:

Theorem 1.4 (Erdős and Rado [956ER]). r(ωm, n) = ωr(I_{m}, L_{n}).

In [967ER] Erdős and Rado showed that for any infinite initial ordinal κ and any natural numbers m and n there is a natural number ℓ such that r(κm, n) ⩽ κℓ. They conjectured that ℓ never depends on κ. In [974Baum] Baumgartner proved this. In fact, we have the following:

1 Notice that some authors use r(H_{1}, H_{2}) to denote the minimal natural number k such that for every graph G on k vertices, either G contains H_{1} or the complement of G contains H_{2}. But we do not follow that notation in this paper.

Theorem 1.5 (Baumgartner [974Baum]). r(κm, n) = κr(I_{m}, L_{n}) for all infinite initial ordinals κ.

The case m = 2 received a decent amount of attention, c.f. [994SF], also the third author published results along the lines of [974Baum] involving products of more than one infinite initial ordinal in [014Wein]. Yet the last paper published on the numbers r(I_{m}, L_{n}) which is known to the authors was published two decades ago by Larson and Mitchell, c.f. [997LM]. In this paper they proved r(I_{m}, L_{3}) ⩽ m^{2} using a degree argument and provided a counterexample showing r(I_{4}, L_{3}) > 13. This left open three possibilities for the number r(I_{4}, L_{3}), the arguably easiest case among the hitherto open ones. It is known that r(I_{2}, L_{3}) = 4, c.f. [956ER], that r(I_{2}, L_{4}) = 8, c.f. [964EM] and that r(I_{2}, L_{5}) = 14 and r(I_{2}, L_{6}) = 28, c.f. [970RP]. It is also known that r(I_{3}, L_{3}) = 9,

c.f. [974Berm].

This research is motivated by the wide gap between the knowledge of the undirected Ramsey numbers r(I_{m}, K_{n}) and that of the oriented Ramsey numbers r(I_{m}, L_{n}). The numbers r(I_{m}, K_{3}) are known for n < 10, they are 3, 6, 9, 14, 18, 23, 28, 36 the last of these values was established in 1982 by Grinstead and Roberts in [982GR0]. It is known that r(I_{4}, K_{4}) = 18[955GG] and r(I_{5}, K_{4}) = 25[995MR]. Moreover good asymptotic estimates are available for undirected Ramsey numbers. Ajtai, Komlós, and Szemeredi proved in [980AKS] that r(I_{m}, K_{3}) ∈ O(m^{2}/ log m) and that for each n ≥ 3, r(I_{m}, K_{n}) ≤ c_{n}m^{n−1}/(log m)^{n−2}. Kim showed in [995Kim] that r(m, 3) ∈ Θ(m^{2}/ log m).

In this paper, we determine the values r(I_{4}, L_{3}) and r(I_{5}, L_{3}). For each n ≥ 3, we give asymptotic upper bounds on r(I_{m}, L_{n}) which are of the same order as the best known upper bounds for r(I_{m}, K_{n}).

In Section 3, we improve Larson’s and Mitchell’s upper bound of m^{2} for the numbers r(I_{m}, L_{3}) to m^{2} − m + 3. In Section 4, we construct oriented graphs witnessing r(I_{4}, L_{3}) > 14 and r(I_{5}, L_{3}) > 22. Thereby we prove

Theorem 1.6. r(I_{4}, L_{3}) = 15 and r(I_{5}, L_{3}) = 23.

In Section 5 we use results of Alon and Kim to show

Theorem 1.7. r(I_{m}, L_{3}) ∈ Θ(m^{2}/ log m).

Then we follow an argument of Ajtai, Komlós, and Szemeredi to extend the above result to

Theorem 1.8. For each n ≥ 3, r(I_{m}, L_{n}) ≤ C_{n}m^{n−1}/(log m)^{n−2}, where C_{n} is constant for each n.

Notice that, though the upper bound in Theorem 1.7 is asymptotically better to m^{2} − m + 3, the latter is much smaller for small values of m. In particular, the former fails to allow for an exact determination of any of r(I_{4}, L_{3}) and r(I_{5}, L_{3}). Finally— in an appendix—we provide a formula which gives the best known upper bounds for small values of m and n.

2. Preliminaries

Let v be a vertex of D = (V, A). We denote the in-neighbourhood of v in by N^{−}(v) and the out-neighbourhood of v by N^{+}(v). Formally, we have N^{−}(v) = {w ∈ V : (v, w) ∈ A} and N^{+}(v) = {w ∈ V : (w, v) ∈ A}. We denote the vertices non-adjacent to v by I(v), formally we have I(v) = V \ ({v} ∪ N^{−}(v) ∪ N^{+}(v)). We denote |N^{−}(v)| by d^{−}(v) and |N^{+}(v)| by d^{+}(v).

For the remaining section we assume that D = (V, A) is a (I_{m}, L_{n})-free graph.

Lemma 2.1. Let v ∈ V. Then the following holds:

(1) The induced subgraphs on N^{−}(v) and N^{+}(v) are (I_{m}, L_{n−1})-free.

(2) The induced subgraph on I(v) is (I_{m−1}, L_{n})-free.

Proof. To show the first assertion suppose towards a contradiction that N^{−}(v) contains a set of vertices T such that the induced subgraph on T is a tournament of size n − 1. Then {v} ∪ T is a tournament of size n. This contradicts that D is L_{n}-free.

To show the second assertion suppose towards a contradiction that I(v) contains an independent set I of size m − 1. Then {v} ∪ I is an indepedent set of size m. This contradicts that D is I_{m}-free. ■

This has the following consequences for the case n = 3.

Corollary 2.2. Let v ∈ V. Suppose that D is L_{3}-free. Then N^{−}(v) and, respectively, N^{+}(v) are independent sets. Particularly, d^{−}(v), d^{+}(v) ⩽ m − 1.

We now provide a recursive upper bound for r(I_{m}, L_{n}).

Lemma 2.3. We have r(I_{m+1}, L_{n+1}) ⩽ 2r(I_{m+1}, L_{n}) + r(I_{m}, L_{n+1}) − 1 for all natural numbers m and n. Furthermore, if an (I_{m+1}, I_{n+1})-free graph D = (V, A) has size 2r(I_{m+1}, L_{n}) + r(I_{m}, L_{n+1}) − 2, then all v ∈ V satisfy

(1) d^{−}(v) = d^{+}(v) = r(I_{m+1}, L_{n}) − 1 and

(2) |I(v)| = r(I_{m}, L_{n+1}) − 1.

Proof. Let D be a (I_{m+1}, L_{n+1})-free graph. Let v ∈ D. By Lemma 2.1, N^{−}(v) and N^{+}(v) have at most size r(I_{m+1}, L_{n})−1 each, and I(v) has at most size r(I_{m}, L_{n+1})−1.

Hence,

|V | ⩽ |{v}| + |N^{−}(v)| + |N^{+}(v)| + |I(v)|
⩽ 1 + 2(r(I_{m+1}, L_{n}) − 1) + r(I_{m}, L_{n+1}) − 1
= 2r(I_{m+1}, L_{n}) + r(I_{m}, L_{n+1}) − 2.

This implies the assertion. ■

The following Lemma is proved in [997LM] and follows from Corollary 2.2 and Lemma 2.3. Proposition 3.4 is an improvement of it.

Lemma 2.4. r(I_{m}, L_{3}) ⩽ m^{2}.

A proof of the following Lemma can be found in [959Stea] but we reprove it here.

Lemma 2.5. r(I_{2}, L_{n}) ⩽ 2^{n−1}.

Proof. Suppose that the statement of the Lemma would fail. Then there is a smallest natural number n for which it does so. Let T be a tournament on 2^{n−1} vertices witnessing this. Pick any vertex v ∈ T. Clearly, one of N^{−}(v) and N^{+}(v) must have at least 2^{n−2} elements. Without loss of generality suppose that N^{−}(v) does. By minimality of n, there is an X ∈ [N^{−}(v)]^{n−1} inducing a transitive subtournament, a contradiction. ■

Remark 2.6. Lemma 2.5 implies

r(m, n) ⩽ r(I_{m}, L_{n}) ⩽ r(m, 2^{n−1}).

In Section 5 we will provide some evidence that r(I_{m}, L_{n}) behaves similarly to the lower bound, at least asymptotically.

3. Improving the Larson-Mitchell Upper Bound

In this section we improve Lemma 2.4 and show that r(I_{m}, L_{3}) ⩽ m^{2} − (m − 3) for all m ⩾ 3. This upper bound turns out to be tight for m ∈ {3, 4, 5}.

If D = (V, A) is a oriented graph and B, C ⊂ V, let E(B, C) denote the set of edges between vertices in B and vertices in C, irrespective of their direction. Formally we have E(B, C) = A ∩ ((B × C) ∪ (C × B)).

Lemma 3.1. Every (I_{3}, L_{3})-free oriented graph D on eight vertices has the following properties:

(1) D is 4-regular,

(2) every triple of vertices of D contains at least one edge,

(3) the non-neighbourhood of any vertex of D induces a triangle, and

(4) any set of 5 vertices in D either contains a triangle or the induced underlying unoriented graph is isomorphic to C_{5}.

(5) any set of 6 vertices in D contains a triangle,

(6) D is unique up to isomorphism.

Proof. As r(I_{2}, L_{3}) = 4 and r(I_{3}, L_{2}) = 3, the bound in Lemma 2.3 is tight. Hence, the graph is 4-regular. The second and third assertion follow from D being I_{3}-free.

Let M be a set of five vertices of D. We assume that M does not contain a triangle. We can ignore the orientation of the edges. Let x ∈ M. By part 3, |I(x) ∩ M| ⩽ 2. If |I(x) ∩ M| ⩽ 1, then |M ∩ (N^{+}(x) ∪ N^{−}(x)| ⩾ 3, so part 2 implies the assertion. Hence, |I(x)∩M| = 2 for all x ∈ M. Hence, the induced subgraph on M is isomorphic to a cycle of length 5. This implies the fourth assertion. The fifth assertion follows similarly.

Now we show the uniqueness of D. W.l.o.g. the vertex set of D is {0, 1, 2, 3, 4, 5, 6, 7}, where N^{+}(0) = {1, 2}, N^{−}(0) = {3, 4}, and I(0) = {5, 6, 7}. As I(0) is I_{2}-free, w.l.o.g. we have the edges

(5, 6), (6, 7), and (7, 5)

in D. By definition, we have

(0, 1), (0, 2), (3, 0), and (4, 0)

in D. As every vertex in D has degree 4,

|E(N^{+}(0) ∪ N^{−}(0), I(0))| = 4|I(0)| − 2|E(I(0), I(0))| = 12 − 6 = 6.

Hence,

2|E(N^{+}(0), N^{−}(0))| = 4 · 3 − |E(N^{+}(0) ∪ N^{−}(0), I(0))| = 6.

As D is L_{3}-free, the three edges in E(N^{+}(0), N^{−}(0)) go from N^{+}(0) to N^{−}(0), so w.l.o.g. we can assume that the edges

(1, 3), (2, 3), and (2, 4)

are in D. As 2 has in-degree 2, there is one edge from I(0) to 2, w.l.o.g. that is (5, 2). As I(2) is (I_{2}, L_{3})-free, the edges (1, 6) and (7, 1) are in D. Similarly, I(1) is (I_{2}, L_{3})-free, so (4, 5) is an edge of D. As the out- and in-degrees of all vertices are 2, the edges (3, 7) and (6, 4) are in D. Now we have given all 16 oriented edges of D without loss of generality. ■

The unique oriented (I_{3}, L_{3})-free graph may be defined on ℤ_{8} by setting both x ↦ x + 1 and x ↦ x − 2, see Figure 1.

Lemma 3.2. An (I_{4}, L_{3})-free oriented graph on fourteen vertices contains at least 38 edges.

0 1 2 3 4 5 6 7

Figure 1. The unique (I_{3}, L_{3})-free graph on 8 vertices.

Proof. Suppose towards a contradiction that D = (V, A) was a 14-vertex (I_{4}, L_{3})- free oriented graph with at most 37 edges. Recall r(I_{3}, L_{3}) = 9. By Lemma 2.1, d^{−}(v) + d^{+}(v) ⩾ 14 − r(I_{3}, L_{3}) = 5. By Corollary 2.2, d^{−}(v) + d^{+}(v) ⩽ 6. Let x be the number of vertices v such that d^{−}(v) + d^{+}(v) = 5. As we have at most 37 edges and 14 vertices, we obtain

5x + 6(14 − x) ⩽ 37 · 2.

This implies that there are at least ten vertices v ∈ V such that d^{−}(v) + d^{+}(v) = 5. Pick one of them with d^{−}(v) = 2. Clearly, d^{+}(v) = 3. Since N^{+}(v) is already an independent set of size 3, and D is I_{4}-free, all the 8 vertices in I(v) are adjacent to at least one vertex of N^{+}(v). Hence |E(N^{+}(v), I(v))| ⩾ 8. Similarly, since any four vertices of I(v) contain two independent vertices, we get |E(N^{−}(v), I(v))| ⩾ 5 lest there be an independent quadruple. By Lemma 3.1, |E(I(v), I(v))| = 16. Let y be the number of vertices u in I(v) such that d^{+}(u) + d^{−}(u) = 6. Then

45 ⩽ |E(N^{+}(v), I(v))| + |E(N^{−}(v), I(v))| + 2 · |E(I(v), I(v))| = 6y + 5(8 − y).

Hence, y ⩾ 5. This contradicts that we have at least ten vertices u with d^{−}(u)+d^{+}(u) = 5. ■

Lemma 3.3. Let D = (V, A) be an (I_{m}, L_{3})-free oriented graph. Let v ∈ V with d^{−}(v) = d^{+}(v) = m − 1. Then

|E(N^{−}(v) ∪ N^{+}(v), I(v))| ⩾ 4(|I(v)| − m + 1).

Proof. By Corollary 2.2, N^{−}(v) and N^{+}(v) are independent sets of size m − 1. Notice that x ∈ I(v) is adjacent to at least one vertex of N^{−}(v) as otherwise N^{−}(v) ∪ {x} is an independent set of size m. We call x ∈ I(v) a private neighbour (with respect to N^{−}(v)) if x has exactly one neighbour in N^{−}(v). We claim that a vertex u ∈ N^{−}(v) is adjacent to at most two private neighbours.

Suppose that u is adjacent to three private neighbours, call them x, y and z. If x, y and z are all connected, then the induced subgraph on {u, x, y, z} is a (I_{2}, L_{3})-free graph. This contradicts r(I_{2}, L_{3}) = 4. If without loss of generality x and y are not connected, then {x, y} ∪ N^{−}(v) \ {u} is an independent set of size m. This contradicts thats D is I_{m}-free. This shows our claim.

Hence, each u ∈ N^{−}(v) is adjacent to at most two private neighbours in I(v). Hence, at most 2d^{−}(v) vertices of I(v) have one neighbour in N^{−}(v), while at least |I(v)| − 2d^{−}(v) vertices in I(v) have at least two neighbours in N^{−}(v). Hence,

|E(N^{−}(v), I(v))| ⩾ 2d^{−}(v) + 2(|I(v)| − 2d^{−}(v)) = 2(|I(v)| − m + 1).

An analogous argument shows

|E(N^{+}(v), I(v))| ⩾ 2(|I(v)| − m + 1).

The assertion follows. ■

Proposition 3.4. If m is a natural number, where m ⩾ 3, then r(I_{m}, L_{3}) ⩽ m^{2}−m+3 and every (I_{m}, L_{3})-free oriented graph on m^{2} − m + 2 vertices has at least (m^{2} − m + 2)(2m − 3)/2 edges.

Proof. We prove this by induction on m. The truth of the proposition for m = 3 follows from Lemmas 2.4 and 3.1. Assume that r(I_{m}, L_{3}) ⩽ m^{2} − m + 3 and every (I_{m}, L_{3})-free oriented graph on m^{2} −m+2 vertices has at least (m^{2} −m+2)(2m−3)/2 edges.

Assume towards a contradiction that D is an (I_{m+1}, L_{3})-free oriented graph D = (V, A) on (m + 1)^{2} − (m + 1) + 3 = m^{2} + m + 3 vertices. As r(I_{m+1}, L_{2}) = m + 1 and, by induction hypothesis, r(I_{m}, L_{3}) ⩽ m^{2} − m + 3, we have equality in Lemma 2.3. By Lemma 2.3, d^{−}(v) = d^{+}(v) = m and I(v) = m^{2} − m + 2 for all v ∈ V.

Let us fix v. As d^{−}(v) + d^{+}(v) = 2m, we can apply Lemma 3.3 and obtain

|E(N^{−}(v) ∪ N^{+}(v), I(v))| ⩾ 4(|I(v)| − m) = 4(m^{2} − 2m + 2). (1)

As d^{−}(w) + d^{+}(w) = 2m for w ∈ I(v), we have that

|E(N^{−}(v) ∪ N^{+}(v), I(v))| + 2|E(I(v), I(v)| = 2m · |I(v)| = 2m(m^{2} − m + 2). (2)

Now we will employ our knowledge about the degrees and the induction hypothesis for the number of edges in a (I_{m}, L_{3})-free oriented graph on m^{2} − m + 2 vertices. We distinguish three cases:

• If m = 3, then, by Lemma 3.1, |E(I(v), I(v))| ⩾ 16. By Equation (2),

|E(N^{−}(v) ∪ N^{+}(v), I(v))| ⩽ 16.

By Equation (1),

|E(N^{−}(v) ∪ N^{+}(v), I(v))| ⩾ 20.

This is clearly a contradiction.

• If m = 4, then by Lemma 3.2, |E(I(v), I(v))| ⩾ 38. By Equation (2),

|E(N^{−}(v) ∪ N^{+}(v), I(v))| ⩽ 36.

By Equation (1),

|E(N^{−}(v) ∪ N^{+}(v), I(v))| ⩾ 40.

Again, this is a contradiction.

• If m > 4, then we have |E(I(v), I(v))| ⩾ (2m − 3)(m^{2} − m + 2)/2 by the induction hypothesis. By Equation (2),

|E(N^{−}(v) ∪ N^{+}(v), I(v))| ⩽ 3m^{2} − 3m + 6.

As m > 4, this contradicts Equation (1). It remains to show the claim on the minimum number of edges. By Lemma 3.2, we only have to consider the case m > 3. Let D = (V, A) a (I_{m}, L_{3})-free graph with m^{2} − m + 2 vertices. Following the arguments in Lemma 2.3, we have equality in our bound if and only if each vertex v ∈ V satisfies d^{−}(v) + d^{+}(v) ⩾ 2m − 3. Hence, we have at least

|V | · (2m − 1)/2 = (m^{2} − m + 2)(2m − 3)/2

edges in D. ■

4. Constructive Lower Bounds

Observation 4.1. r(I_{4}, L_{3}) = 15.

Proof. By Proposition 3.4, r(I_{4}, L_{3}) ⩽ 15. The oriented (I_{4}, L_{3})-free graph on page 10 may be defined on ℤ_{14} by setting both x ↦ x + 1 and x ↦ x − 2 for all x ∈ ℤ_{14} and moreover x ↦ x + 4 if x is even and x ↦ x − 6 if x is odd. ■

We want to remark that there is no oriented (I_{4}, L_{3})-free Cayley graph on 14 vertices.

Observation 4.2. r(I_{5}, L_{3}) = 23.

Proof. By Proposition 3.4, r(I_{5}, L_{3}) ⩽ 23. The oriented (I_{5}, L_{3})-free graph on page 11 may be defined on ℤ_{22} by setting both x ↦ x+1, x ↦ x+4, x ↦ x−5 and x ↦ x+10 for all x ∈ ℤ_{22}. ■

Both obersvations together imply Theorem 1.6.

Figure 2. An oriented graph showing r(I_{4}, L_{3}) > 14.

5. Probabilistic Upper Bounds

In this section, we use a result of Alon to show that r(I_{m}, L_{3}) is in O(m^{2}/ log m). This bound is better than the one in Proposition 3.4 for large enough m. Moreover, this is tight upto multiplicative constants since r(I_{m}, L_{3}) ⩾ r(I_{m}, K_{3}). Then we follow an upper bound argument of Ajtai, Komlós and Szemeredi for r(I_{m}, K_{n}) to obtain upper bounds of commensurate order for r(I_{m}, L_{n}).

Proposition 5.1 ([996Alon, Prop. 2.1]). Let G = (V, E) be a graph on v vertices with maximum degree d ⩾ 1, in which the neighbourhood of any vertex is r-colourable. Then

α(G) ⩾ \frac{v ld d}{160d ld(r + 1)}.

Corollary 5.2.

r(I_{m}, L_{3}) ⩽ \frac{2^{9}m^{2}}{ld m} .

Proof. Assume towards a contradiction that there is a natural number m and a oriented graph D on v := 2^{9}m^{2}/ ld m vertices with no transitive triangle and no independent set of size m. Let G be the undirected graph attained from D by forgetting the directions of the edges. Let d denote the maximal degree of a vertex in G. Note that the neighbourhood of any vertex x is 2-colourable since it consists of the in- and

NEW BOUNDS ON THE RAMSEY NUMBER r(I_{m}, L_{n}) 11

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 Figure 3. An oriented graph showing r(I_{5}, L_{3}) > 22.

out-neighbourhoods of x, both of which are independent sets. Since

\frac{v ld d}{160d ld 3}

is decreasing in d and, by Corollary 2.2, d < 2m, by Proposition 5.1, we may conclude that

m > α(G) ⩾ \frac{2^{9}m^{2}}{ld m} · \frac{ld(2m)}{160 · 2m ld 3} = \frac{2^{9}m(ld 2 + ld m)}{320 ld 3 ld m} = \frac{2^{9}m}{320 ld 3}(1 + \frac{1}{ld m}).

It follows that 2^{9} < 320 ld 3 which is a contradiction. ■

Due to Kim [995Kim], r(I_{m}, K_{3}) ⩾ Θ(m^{2}/ log m). Since r(I_{m}, L_{3}) ⩾ r(I_{m}, K_{3}), the bound in Corollary 5.2 is asymptotically tight up to a multiplicative constant.

We follow an argument by Ajtai, Komlós, and Szemeredi for (I_{m}, K_{n})-free graphs [980AKS] to obtain another upper bound for (I_{m}, L_{n})-free graphs.

Following the proof of in [980AKS, Lemma 4], we obtain the following lemma.

Lemma 5.3. Let D be an oriented graph with v vertices, e edges, h transitive triangles, and average degree d. Let 0 < p < 1. Then there exists an induced subgraph D′ of D with v′ vertices, e′ edges, h′ transitive triangles, and average degree d′ satisfying

v′ ⩾ vp/2,  e′ ⩽ 3ep^{2}  h′ ⩽ 3hp^{3},  d′ ⩽ 6dp.

We also need the average version of Alon’s bound. The constant in the bound can be easily verified from the proof there.

Theorem 5.4 ([996Alon, Theorem 1.1]). Let G = (V, E) be a graph on v vertices with average degree d ⩾ 1, in which the neighbourhood of any vertex is r-colourable. Then

α(G) ⩾ \frac{v ld 2d}{640d ld(r + 1)}.

Lemma 5.5. Let ε > 0. Let D be a graph with v vertices, average degree d, and h ⩽ vd^{2−ε} transitive triangles. If d is sufficienty large, then

α(D) ⩾ 2^{−16}ε\frac{v}{d} ld d.

Proof. By Lemma 5.3, we obtain a graph D′ with v′ ⩾ vp/2 vertices, average degree d′ ⩽ 6dp, and h′ ⩽ 3hp^{3} transitive triangles. If we choose p = \sqrt{d^{ε−2}/12}, then we get h′ ⩽ \frac{1}{4}vp ⩽ \frac{1}{2}v′. Deleting one vertex from each of the transitive triangles gives us an oriented L_{3}-free graph D′′ on v′′ ⩾ \frac{1}{4}vp vertices. By Corollary 5.1,

α(D) ⩾ α(D′′)

⩾ \frac{v′′ ld d′}{160d′ ld 3}

⩾ \frac{vp ld 6dp}{4 · 640 · 6dp ld 3}

⩾ 2^{−16}ε · \frac{v ld d}{d}.

■

Theorem 5.6. For every m, n ⩾ 2,

r(I_{m}, L_{n}) ⩽ 2^{19n} · \frac{m^{n−1}}{(ld m)^{n−2}} .

Proof. We proof the bound by induction on n. We already know that r(I_{m}, L_{2}) ⩽ m and, by Corollary 5.2, r(I_{m}, L_{3}) ⩽ 2^{9} · \frac{m^{2}}{ld m}. Fix n ⩾ 4 and assume that the claim is true for n − 1 and n − 2.

Suppose that D is an oriented L_{n}-free graph on

v ⩾ 2^{19n} · \frac{m^{n−1}}{(ld m)^{n−2}}

vertices. We will argue that α(D) ⩾ m. Let ε = 1/n. Case 1. The number of transitive triangles in D is less than v · d^{2−ε}. By Lemma 2.3, the maximum degree d in D is less than

2r(I_{m}, L_{n−1}) ⩽ 2^{19n−18} · \frac{m^{n−2}}{(ld m)^{n−3}} .

By Lemma 5.5,

α(D) ⩾ 2^{−16}ε · v · \frac{ld d}{d} ⩾ m.

Case 2. The number of transitive triangles in D is at least v·d^{2−ε}. The graph D contains at most vd/2 edges. By double counting there exists an oriented edge e = (x, y) in D such that (a, b) lies in at least

\frac{vd^{2−ε}}{vd/2}

transitive triangles of the form {(a, b), (b, v), (a, v)}. Let V_{e} denote the set of vertices v such that {(a, b), (b, v), (a, v)} is a transitive triangle of D. Then |V_{e}| ⩾ 2d^{1−ε}.

If there is an oriented subgraph H isomorphic to L_{n−2} in the subgraph D′ induced on V_{e}, then the induced subgraph on {a, b} ∪ H is isomorphic to L_{n}. Hence, D′ is (I_{m}, L_{n−2})-free. Hence,

2d^{1−ε} ⩽ |V_{e}| < r(I_{m}, L_{n−2}).

Hence,

d < r(I_{m}, L_{n−2})^{1/(1−ε)} < 2^{19(n−1)} · \frac{m^{n−2}}{(ld m)^{n−3}} .

By Turan’s bound,

α(D) ⩾ \frac{v}{d + 1} ⩾ m.

■

This implies Theorem 1.7.

6. Coda

There are more open problems in finite combinatorics stemming from set theory. Determining r(I_{3}, L_{4}) would continue our work and seems feasible given the size of the candidates for examples of (I_{3}, L_{4})-free graphs.

In [014Wein] the Ramsey numbers of the form r(ω^{2}m, n) were characterised by finite Ramsey numbers concerned with edge-coloured oriented graphs. We have r(ω^{2}m, n) = ω^{2}r(I_{m}, A_{n}) where A_{n} is a class of n-vertex edge-coloured transitive tournaments satisfying some additional restrictions. It would be nice to improve the following asymptotic bounds on r(I_{m}, A_{3}) established there.

r(I_{m}, A_{3}) ∈ O(m^{3}) ∩ Ω(\frac{m^{2}}{ld m}).

Finally, for the Ramsey numbers r(ω^{m}, n) formulae have been found for all natural numbers m ≠ 4 and all natural numbers n by Nosal in [975Nosa, 979Nosa]. The determination of the numbers r(ω^{4}, n) by a formula, however, has still to be accomplished.

Appendix A. A Formula for Small m and n

We provide the following—admittedly slightly baroque—formula. It gives asymptotically suboptimal upper bounds for r(I_{m}, L_{n}) but provides the state of the art for small m and n.

Theorem A.1. r(I_{m}, L_{n}) ⩽ v(m, n) for all m ∈ ω \ 2 and n ∈ ω \ 3 where

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

Proof. We are going to prove the Theorem using a two-dimensional induction. To this end, we have to check three things:

(1) First we show that (3) agrees with Lemma 2.5.

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

= ∑_{i=0}^{n−2} 2^{i} + 1
=(2^{n−1} − 1) + 1 = 2^{n−1}.

(2) Now we prove that (3) agrees with Proposition 3.4 for m ∈ ω \ 3. As \binom{m−3}{m−4} = m − 3 for m ⩾ 3,

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

(3) Finally we prove that v(m + 1, n + 1) = 2v(m + 1, n) + v(m, n + 1) − 1:

2v(m + 1, n) + v(m, n + 1) − 1

= ∑_{i=0}^{n−2} \binom{i + m}{i + 1}2^{i+1} − \binom{m + n − 5}{m − 3}2^{n−2} + 2

+ ∑_{i=0}^{n−1} \binom{i + m − 1}{i + 1}2^{i} − \binom{m + n − 5}{m − 4}2^{n−2} + 1 − 1

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

+ ∑_{i=0}^{n−1} \binom{i + m − 1}{i + 1}2^{i}

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

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

References

[014Wein] T.  V.  Weinert.  Idiosynchromatic  poetry.  Combinator-
ica,  34(6):707–742,  2014,  doi:10.1007/s00493-011-2980-1,

https://www.math.bgu.ac.il/~weinert/Poetry_colour0.pdf.

[013Jone] A. L. Jones. Even more on partitioning triples of countable ordinals. Preprint, 2013.

[997LM] J. A. Larson and W. J. Mitchell. On a problem of Erdős and Rado. Ann. Comb., 1(3):245–

252, 1997, doi:10.1007/BF02558478, http://dx.doi.org/10.1007/BF02558478.

[996Alon] N. Alon. Independence numbers of locally sparse graphs and a Ramsey type problem. Random Structures Algorithms, 9(3):271–278, 1996, doi:10.1002/(SICI)1098-2418(199610)9:3<271::AID-RSA1>3.0.CO;2-U,

http://dx.doi.org/10.1002/(SICI)1098-2418(199610)9:3<271::AID-RSA1>3.0.CO;2-U.

[995Kim] J. H. Kim. The Ramsey number R(3, t) has order of magnitude t^{2}/ log t. Random Structures Algorithms, 7(3):173–207, 1995, doi:10.1002/rsa.3240070302,

http://dx.doi.org/10.1002/rsa.3240070302.

[995MR] B. D. McKay and S. P. Radziszowski. R(4, 5) = 25. J. Graph Theory, 19(3):309–322, 1995,

doi:10.1002/jgt.3190190304, http://dx.doi.org/10.1002/jgt.3190190304.

[994Radz] S. P. Radziszowski. Small Ramsey numbers. Electron. J. Combin., 1:Dynamic Survey 1,

30 pp. (electronic), 1994, http://www.combinatorics.org/Surveys/index.html.

[994SF] A. Sánchez-Flores. On tournaments and their largest transitive subtournaments. Graphs Combin., 10(4):367–376, 1994, doi:10.1007/BF02986687,

http://dx.doi.org/10.1007/BF02986687.

[991MR0] B.D. McKay and S.P. Radziszowski. The First Classical Ramsey Number for Hypergraphs is Computed. Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA91, San Francisco, (1991) 304–308.

[982GR0] C. Grinstead and S. Roberts. On the Ramsey Numbers R (3,8) and R (3,9). Journal of Combinatorial Theory, Ser. B, 33 (1982) 27–51, doi:10.1016/0095-8956(82)90055-7,

http://dx.doi.org/10.1016/0095-8956(82)90055-7.

[980AKS] M. Ajtai, J. Komlós and E. Szemerédi. A note on Ramsey numbers. J. Combin. Theory Ser. A, 29(3):354–360, 1980, doi:10.1016/0097-3165(80)90030-8,

http://dx.doi.org/10.1016/0097-3165(80)90030-8.

[979Nosa] E. Nosal. Partition relations for denumerable ordinals. J. Combin.

Theory Ser. B, 27(2):190–197,  1979,  doi:10.1016/0095-8956(79)90080-7,

http://dx.doi.org/10.1016/0095-8956(79)90080-7.

[975Nosa] E. Nosal. On arrow relations w(k,w) 2(2) (m,n,k less than w): A study in the partition calculus. ProQuest LLC, Ann Arbor, MI, 1975,

http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&res_dat=xri:pqdiss&rft_dat=xri:pqdiss:NK25043.

Thesis (Ph.D.)–University of Calgary (Canada).

[974Baum] J. E. Baumgartner. Improvement of a partition theorem of Erdös and Rado. J. Combinatorial Theory Ser. A, 17:134–137, 1974.

[974Berm] J.-C. Bermond. Some Ramsey numbers for directed graphs. Discrete Math., 9:313–321, 1974.

[970RP] K. B. Reid, Jr. and E. T. Parker. Disproof of a conjecture of Erdős and Moser on tournaments. J. Combinatorial Theory, 9:225–238, 1970.

[967ER] P. Erdős and R. Rado. Partition relations and transitivity domains of binary relations. J. London Math. Soc., 42:624–633, 1967.

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

http://www.renyi.hu/~p_erdos/1964-22.pdf.

[961Shoe] J. R. Shoenfield. The problem of predicativity. In Essays on the foundations of mathematics, pages 132–139. Magnes Press, Hebrew Univ., Jerusalem, 1961.

[959Stea] R. Stearns. The voting problem. Amer. Math. Monthly, 66:761–763, 1959.

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

http://www.ams.org/journals/bull/1956-62-05/S0002-9904-1956-10036-0/S0002-9904-1956-10036-0.pdf.

[955GG] R. E. Greenwood, Jr. and A. M. Gleason. Combinatorial relations and chromatic graphs.

Canad. J. Math., 7:1–7, 1955, http://cms.math.ca/cjm/v7/cjm1955v07.0001-0007.pdf.

[935ES] P. Erdős and G. Szekeres. A combinatorial problem in geometry. Compositio Math., 2:463–

470, 1935, http://www.numdam.org/item?id=CM_1935__2__463_0.

[930Rams] F. P. Ramsey. On a problem of formal logic. Proc. London Math. Soc., 30:264–286, 1930,

http://plms.oxfordjournals.org/content/s2-30/1/264.full.pdf.

The Hebrew University of Jerusalem

E-mail address: ferdinand.ihringer@gmail.com

Indian Institute of Technology Palakkad

E-mail address: deepak@iitpkd.ac.in

Ben-Gurion-University of the Negev

E-mail address: aleph omega@posteo.net