MONOCHROMATIC FORESTS OF FINITE SUBSETS OF N

Tom C. Brown

Department of Mathematics and Statistics, Simon Fraser University, Burnaby, BC Canada V5A 1S6

                                 tbrown@sfu.ca

Received: 2/3/00, Revised: 2/29/00, Accepted: 3/28/00, Published: 5/19/00

Abstract

It is known that if N is finitely colored, then some color class is piecewise syndetic. (See Definition 1.1 below for a definition of piecewise syndetic.) We generalize this result by considering finite colorings of the set of all finite subsets of N . The monochromatic objects obtained are “d-copies” of arbitrary finite forests and arbitrary infinite forests of finite height. Van der Waerden’s theorem on arithmetic progressions is generalized in a similar way. Ramsey’s theorem and van der Waerden’s theorem are used in some of the proofs.

1. Introduction

N denotes the set of positive integers, and [1, n] denotes the set {1, 2, ⋯, n}. P_{f}(N) denotes the set of all finite subsets of N, and P ([1, n]) denotes the set of all subsets of [1, n].

We first give several basic definitions and facts.

Definition 1.1 A subset X of N is piecewise syndetic if for some fixed d there are arbitrarily large (finite) sets A ⊂ X such that gs(A) ≤ d, where gs(A), the gap size of A = {a_{1} < a_{2} < ⋯ < a_{n}}, is defined by gs(A) = max{a_{j+1} − a_{j} : 1 ≤ j ≤ n − 1}. (If |A| = 1, we set gs(A) = 1.)

Definition 1.2 A subset X of N has property AP if there are arbitrarily large (finite) sets A ⊂ X such that A is an arithmetic progression.

Fact 1 If N = X_{1}∪X_{2}∪⋯∪X_{n}then some X_{i} is piecewise syndetic (and hence also has property AP, by van der Waerden’s theorem on arithmetic progressions). (The first proofs of Fact 1 appear in [2], [3], [7].) However, Fact 1 neither implies, nor is implied by, van der Waerden’s theorem.

Fact 2 If X ⊆ N and X has positive upper density, then has property AP (by Szemerédi’s theorem) but need not be piecewise syndetic. (For an example, see [1].)

The finite version of Fact 1 is:

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 0 (2000), #A04 2

Theorem 1.1 For all r ≥ 1 and f ∈ N^{N}, there exists (a smallest) n = n(f, r) such that whenever [1, n] is r-colored, there is a monochromatic set A such that |A| > f(gs(A)). Furthermore, n(f, 1) = f(1) + 1 and n(f, r + 1) ≤ (r + 1)f(n(f, r)) + 1.

Proof. We use induction on r. For r = 1, it’s clear that n(f, 1) = f(1) + 1, for then A = [1, f(1) + 1] is monochromatic, and |A| > f(1) = f(gs(A)).

Suppose that n(f, r) exists, and assume without loss of generality that f is non-decreasing. Let an (r + 1)-coloring of [1, n] be given, such that for every monochromatic set A ⊆ [1, n], |A| ≤ f(gs(A)). We’ll show that under these conditions n ≤ (r + 1)f(n(f, r)), from which it follows that n(f, r + 1) ≤ (r + 1)f(n(f, r)) + 1.

Now if B = [a, b] ⊆ [1, n] misses the color j, then by the induction hypothesis (applied to the interval [a, b] instead of the interval [1, b − a + 1])and our assumption about the given coloring, |B| = b − a + 1 ≤ n(f, r) − 1.

Hence if A(j) = {x ∈ [1, n] : x has color j}, then gs(A(j)) ≤ (b+1)−(a−1) ≤ n(f, r). Therefore (again by our assumption about the given coloring) |A(j)| ≤ f(gs(A(j))) ≤ f(n(f, r)).

Finally, n = ∑ |A(j)| ≤ (r + 1)f(n(f, r)). □

There are applications of this result to the theory of locally finite semigroups, and in particular to Burnside’s problem for semigroups of matrices (see [10]).

In [8] it is shown that there is a 2-coloring χ of N and a function f ∈ N^{N} such that if A = {a, a+d, a+2d, ⋯} is any χ-monochromatic arithmetic progression, then |A| < f(d). Hence one cannot require the monochromatic set A in Theorem 1.1 to be an arithmetic progression.

In this note we generalize Theorem 1.1 by considering finite colorings of P ([1, n]) and of P_{f}(N). We also generalize van der Waerden’s theorem on arithmetic progressions. (We use van der Waerden’s theorem in the proof, as well as Ramsey’s theorem.) We conclude with several open questions.

2. d-copies Of Finite Rooted Forests

Theorem 2.1 below is a generalization of Theorem 1.1. To state Theorem 2.1, we need some additional terminology.

Let F be any finite rooted forest, by which we mean a union of pairwise disjoint rooted trees. We regard F as a partially ordered set in the natural way. This means that the roots of the trees in F are the minimal elements of F, and for vertices x, y of F, x ≤ y means that in some tree T in F, x is an ancestor of y, that is, the unique path from the root of T to y contains x. For vertices x, y of F, we write x ∧ y for the greatest lower bound of x, y, if it exists. (Thus x ∧ y exists if and only if x, y are vertices of some tree T in F, and then x ∧ y is the common ancestor of x and y which has greatest height, that is, is furthest from the root of F.)

Definition 2.1 Let F be a rooted forest, and let d ≥ 1. (This definition applies to both finite and infinite rooted forests F.) A d-copy of F in P ([1, n]) (resp P_{f}(N)) is a subset S of P ([1, n]) (resp P_{f}(N)) for which there exists a bijection ϕ from the vertex set of F to S such that for all vertices x, y of F,

• 1. x ≤ y ⇔ ϕ(x) ⊆ ϕ(y)

• 2. If x ∧ y exists, then ϕ(x ∧ y) = ϕ(x) ∩ ϕ(y)

• 3. If x, y belong to different trees of F, then ϕ(x) ∩ ϕ(y) = ∅.

• 4. If y covers x then |ϕ(y)| − |ϕ(x)| ≤ d. (We say that y covers x iff x < y and there does not exist z with x < z < y.

Theorem 2.1 For all r ≥ 1 and f ∈ N^{N}, there exists (a smallest) n^{∗} = n^{∗}(f, r) such that whenever P ([1, n^{∗}]) is r-colored, there exist d ≥ 1 and monochromatic d-copies (all in the same color) of all rooted forests having f(d) vertices. Furthermore, n^{∗}(1) = f(1) and n^{∗}(f, r + 1) ≤ n^{∗}(f, r) · f(n^{∗}(f, r)).

Proof. We use induction on r. For r = 1, we can take d = 1, and then easily construct a 1-copy of any rooted forest with f(1) vertices, using subsets of [1, f(1)]. (For a forest with more than one component, we need to use all the elements of [1, f(1)].) Therefore n^{∗}(f, 1) = f(1).

Now let r ≥ 1, and assume that n^{∗}(f, r) = m exists. We show that n^{∗}(f, r + 1) ≤ mf(m).

Let an (r + 1)-coloring χ of P ([1, mf(m)]) be given. We show that either (Case 1) there is a d ≥ 1, a fixed color i, 1 ≤ i ≤ r, and a fixed t, 1 ≤ t ≤ f(m), such that every rooted forest with f(d) vertices has a χ-monochromatic d-copy in the color i, contained in P ([1, tm]), or else (Case 2) every rooted forest F with f(m) vertices has a χ-monochromatic m-copy in the color r + 1, contained in P ([1, mf(m)]).

Case 1. For some s, 0 ≤ s ≤ f(m) − 1, there is A ⊆ [1, sm] (for P ([sm + 1, (s + 1)m]) defined by χ′(B) = χ(A ∪ B), B ⊆ [sm + 1, (s + 1)m], does not use the color r + 1, and hence is an r-coloring. By the induction hypothesis and the definition of m (using the interval [sm + 1, (s + 1)m] instead of the interval [1, m]), there is a d ≥ 1 and a fixed color i, 1 ≤ i ≤ r, such that every rooted forest with f(d) vertices has a χ′-monochromatic d-copy in the color i, contained in [sm + 1, (s + 1)m]. By adjoining the set A to each set in this d-copy, we get a χ-monochromatic d-copy in the color i, contained in [1, (s + 1)m]. This finishes Case 1.

Case 2. Now we assume that Case 1 does not occur, and that F is an arbitrary rooted forest with f(m) vertices. We show how to construct an m-copy of F in P ([1, mf(m)]), which is χ-monochromatic in the color r + 1.

First, by assumption the color r + 1 occurs when χ is restricted to P ([1, m]). Assume χ(B_{1}) = r + 1, where B_{1} ⊆ [1, m]. We set ϕ(x_{1}) = B_{1}, where x_{1} is a root of F .

If F has another root, x_{2}, we set ϕ(x_{2}) = B_{2}, where B_{2} ⊆ [m + 1, 2m] and χ(B_{2}) = r + 1. Similarly, if x_{1}, x_{2}, ⋯ x_{t} are all the roots of F, we define ϕ(x_{i}) = B_{i}, where B_{i} ⊆ [(i−1)m+1, im] and χ(B_{i}) = r + 1, 1 ≤ i ≤ t.

The construction continues as follows. Suppose y_{1} covers x_{1} in F. Since ϕ(x_{1}) = B_{1} ⊆ [1, tm], we make up the coloring χ′ on P ([tm + 1, (t + 1)m]) by setting χ′(B) = χ(B_{1} ∪ B), B ⊆ [tm + 1, (t + 1)m]. Since Case 1 does not occur, χ′ takes on the value r + 1, say r + 1 = χ′(C_{1}) = χ(B_{1} ∪ C_{1}), where C_{1} ⊆ [tm + 1, (t + 1)m]. Then we set ϕ(y_{1}) = B_{1} ∪ C_{1} , and clearly |ϕ(y_{1})| − |ϕ(x_{1})| = |C_{1}| ≤ m .

The construction is continued in the same way. If y covers x in F, and ϕ(x) has already been defined but ϕ(y) has not, we set ϕ(y) = ϕ(x) ∪ C, where C is some subset of the next unused interval of length m, for which χ(ϕ(x) ∪ B) = r + 1. Since F has f(m) vertices, there are enough intervals of length m to finish the construction. □

It is straightforward to show that Theorem 1.1 implies Fact 1. In the same way, it is straightforward to show that Theorem 2.1 implies the following result.

Theorem 2.2 Let P_{f}(N) be finitely colored. Then there exists a fixed d ≥ 1 such that for every finite forest F, there is a monochromatic d-copy of F.

3. d-copies Of ω-forests

In this section, we show that a result considerably stronger than Theorem 2.2 can be proved by using Ramsey’s theorem together with Fact 1.

Theorem 3.1 Let P_{f}(N) be finitely colored. Then for some fixed d ≥ 1 there exist arbitrarily large (finite) sets A = {a_{0} < a_{1} < ⋯ < a_{n}} ⊂ N with a_{j+1} − a_{j} ≤ d, 0 ≤ j ≤ n − 1, and infinite sets Y ⫅ N (Y depends on A) such that [Y]^{a_{0}} ∪ [Y]^{a_{1}} ∪ ⋯ ∪ [Y]^{a_{n}} is monochromatic, where [Y]^{a_{i}} denotes the set of all a_{i}-element subsets of Y.

Proof. Let g be a given finite coloring of P_{f}(N). Using Ramsey’s theorem, let N = X_{0} ⫆ X_{1} ⫆ ⋯ ⫆ X_{m} ⫆ ⋯ be a sequence of infinite sets such that for each m ≥ 1, g is constant on the set [X_{m}]^{m} of all m-element subsets of X_{m}. Define the finite coloring h of N by setting h(m) = g(A), where A is any m-element subset of X_{m}.

By Fact 1 above, there is some i such that h^{−1}(i) is a piecewise syndetic set. This means that there is a fixed d ≥ 1 such that for arbitrarily large n, there are h-monochromatic sets {a_{0} < a_{1} < ⋯ < a_{n}} with a_{j+1} − a_{j} ≤ d, 0 ≤ j ≤ n − 1.

Let {a_{0} < a_{1} < ⋯ < a_{n}} be such an h-monochromatic set. By the definition of h, g is constant on [X_{a_{0}}]^{a_{0}} ∪ [X_{a_{1}}]^{a_{1}} ∪ [X_{a_{2}}]^{a_{2}} ∪ ⋯ ∪ [X_{a_{n}}]^{a_{n}}. Since X_{a_{0}} ⫆ X_{a_{1}} ⫆ X_{a_{2}} ⫆ ⋯ ⫆ X_{a_{n}}, we have that g is constant on [Y]^{a_{0}} ∪ [Y]^{a_{1}} ∪ [Y]^{a_{2}} ∪ ⋯ ∪ [Y]^{a_{n}}, where Y = X_{a_{n}}. □

Definition 3.1 An ω-tree of height n is a rooted tree in which every maximal chain has n + 1 vertices, and every non-maximal vertex has infinitely many immediate successors. An ω-forest of height n is a union of infinitely many pairwise disjoint ω-trees of height n.

Corollary 3.2 Let P_{f}(N) be finitely colored. Then there exists a fixed d ≥ 1 such that for every n ≥ 1, there is a monochromatic d-copy of an ω-forest of height n.

Proof. Let d be as in the conclusion of Theorem 3.1, and let n be given. From Theorem 3.1, let A = {a_{0} < a_{1} < ⋯ < a_{n}} ⊂ N satisfy a_{j+1} − a_{j} ≤ d, 0 ≤ j ≤ n − 1, and let Y be an infinite set such that [Y]^{a_{0}} ∪ [Y]^{a_{1}} ∪ ⋯ ∪ [Y]^{a_{n}} is monochromatic.

Now it is just a matter of constructing an ω-forest F of height n in which all the roots belong to [Y]^{a_{0}}, and for each j, 1 ≤ j ≤ n, all the vertices at height j belong to [Y]^{a_{j}}. For then, if vertex y covers vertex x in the forest F, then for some j, 0 ≤ j ≤ n − 1, x ∈ [Y]^{a_{j}}, y ∈ [Y]^{a_{j+1}},and x ⊂ y, so that |y| − |x| = a_{j+1} − a_{j} ≤ d.

One construction of F is the following. Assume without loss of generality that Y = N, and let p_{1}, p_{2}, ⋯, p_{k}, ⋯ be the sequence of primes. Let the roots of F be the sets S_{i}, 1 ≤ i, where S_{i} = {p_{i}, p_{i}^{2}, p_{i}^{3}, ⋯, p_{i}^{a_{0}}}. For each 1 ≤ i, let the vertices which cover the vertex S_{i} be the sets S_{i} ∪ S_{ij}, i < j, where S_{ij} = {p_{i}p_{j}, p_{i}p_{j}^{2}, p_{i}p_{j}^{3}, ⋯, p_{i}p_{j}^{a_{1}−a_{0}}}. For each 1 ≤ i < j, let the vertices which cover the vertex S_{i} ∪ S_{ij} be the sets S_{i} ∪ S_{ij} ∪ S_{ijk}, j < k, where S_{ijk} = {p_{i}p_{j}p_{k}, p_{i}p_{j}p_{k}^{2}, p_{i}p_{j}p_{k}^{3}, ⋯, p_{i}p_{j}p_{k}^{a_{2}−a_{1}}}. Continue in this way until an ω -forest of height n is obtained. □

4. Arithmetic Copies Of ω-forests

In this section, we use Ramsey’s theorem together with van der Waerden’s theorem on arithmetic progressions to obtain a result similar to Theorem 3.1, except that now the set A will be an arithmetic progression.

Theorem 4.1 Let P_{f}(N) be finitely colored. Then for every n ≥ 1 there exist an arithmetic progression {a, a + d, a + 2d, ⋯ a + (n − 1)d} and an infinite set Y such that [Y]^{a} ∪ [Y]^{a+d} ∪ [Y]^{a+2d} ∪ ⋯ ∪ [Y]^{a+(n−1)d} is monochromatic.

Proof. The proof is essentially the same as the proof of Theorem 3.1. Let g be a given finite coloring of P_{f}(N). Using Ramsey’s theorem, let N = X_{0} ⫆ X_{1} ⫆ ⋯ ⫆ X_{m} ⫆ ⋯ be a sequence of infinite sets such that for each m ≥ 1, g is constant on the set [X_{m}]^{m} of all m-element subsets of X_{m}. Define the finite coloring h of N by setting h(m) = g(A), where A is any m -element subset of X_{m}.

By van der Waerden’s theorem on arithmetic progressions, for every n ≥ 1 there is an hmonochromatic set {a, a + d, a + 2d, ⋯ a + (n − 1)d}. Hence, as in the proof of Theorem 3.1, g is constant on [Y]^{a} ∪ [Y]^{a+d} ∪ [Y]^{a+2d} ∪ ⋯ ∪ [Y]^{a+(n−1)d}, where Y = X_{a+(n−1)d}. □

Definition 4.1 Let F be a rooted forest. An arithmetic copy of F in P ([1, n]) (resp P_{f}(N)) is a subset S of P ([1, n]) (resp P_{f}(N)) for which there exist positive integers a, d and a bijection ϕ from the vertex set of F to S such that for all vertices x, y of F,

• 1. x ≤ y ⇔ ϕ(x) ⊆ ϕ(y)

• 2. If x ∧ y exists, then ϕ(x ∧ y) = ϕ(x) ∩ ϕ(y)

• 3. If x, y belong to different trees of F, then ϕ(x) ∩ ϕ(y) = ∅.

• 4. If x is any root of F, then |ϕ(x)| = a.

• 5. If y covers x then |ϕ(y)| − |ϕ(x)| = d.

Corollary 4.2 Let P_{f}(N) be finitely colored. Then for every n ≥ 1 there exists a monochromatic arithmetic copy of an ω-forest of height n.

Proof. Using Theorem 4.1,the monochromatic arithmetic copy of an ω-forest of height n can be constructed just as in the proof of Corollary 3.2. □

Corollary 4.3 For all r ≥ 1 and k ≥ 1 , there exists (a smallest) w^{∗} = w^{∗}(k, r) such that whenever P ([1, w^{∗}] is r-colored, there exist a ≥ 1 and d ≥ 1 and monochromatic arithmetic copies (all in the same color) of all rooted forests having k vertices. These monochromatic copies have the property that every vertex at height j = 0, 1, ⋯ has size a + jd.

Proof. This follows from Corollary 4.2 by a compactness argument. (It could also be proved directly, using the finite forms of Ramsey’s theorem and van der Waerden’s theorem.) □

5. Remarks And Open Questions

Piecewise syndetic sets are discussed at length in [5] and [6].

Howard Straubing [10] has used Theorem 1.1 to give new proofs (which are almost entirely combinatorial) of all of the key theorems dealing with the local finiteness of semigroups of matrices over an arbitrary field, and with the local finiteness of subsemigroups of rings satisfying a polynomial identity. Since trees give a natural way to describe n-ary operations, perhaps Theorem 2.1 may have some applications to algebra.

The proof of Theorem 4.1, although found independently from [9], combines van der Waerden’s theorem and Ramsey’s theorem in the same way these were combined in the proof of Theorem 2 in [9]. Some related results, and additional references, can be found in [11] and [12].

It was observed by J. Walker, as reported in [13], that if k ≥ 1 and ε > 0 are given, then for sufficiently large n, if S ⊆ P ([1, n]) and |S| > ε|P ([1, n])|, S must contain an arithmetic copy of a path of length k. Is it true that S must also contain arithmetic copies of all k-vertex rooted forests?

It would also be of interest to find ”canonical” versions of the results above, where the number of colors is arbitrary. (For the canonical version of van der Waerden’s theorem, see [4], p. 17.)

References

[1] V. Bergelson, N. Hindman, R. McCutcheon, Notions of size and combinatorial properties of quotient sets in semigroups, Topology Proc., to appear.

[2] T.C. Brown, On locally finite semigroups (in Russian), Ukraine Math. J. 20 (1968), 732-738.

[3] T.C. Brown, An interesting combinatorial method in the theory of locally finite semigroups, Pacific J. Math. 36 (1971), 285-289.

[4] Paul Erdös and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory, L’Enseignement Mathématique, Genève, 1980.

[5] H. Furstenberg, Recurrence in Ergodic Theory and Combinatorial Number Theory, Princeton University Press, Princeton, 1981.

[6] N. Hindman and D. Strauss, Algebra in the Stone -Čech Compactification, Walter de Gruyter, Berlin, New York, 1998.

[7] G. Jacob, La finitude des représentations linéaires des semi-groupes est décidable, J. Algebra 52 (1978), 437-459.

[8] J. Justin, Théorèm de van der Waerden, Lemme de Brown et demi-groups répétitifs, ”Journées sur la Théorie Algébrique des Demi-groups (1971),” Faculté de Sciences de Lyon.

[9] J. Nešetřil, V. Rödl, Combinatorial partitions of finite posets and lattices - Ramsey lattices, Algebra Universalis 19 (1984), 106-119.

[10] H. Straubing, The Burnside problem for semigroups of matrices, in Combinatorics on Words, Progress and Perspectives, Academic Press 1982, 279-295.

[11] C.J. Swanepoel, L.M. Pretorius, A van der Waerden theorem for trees, Bull. ICA 21 (1997), 108-111.

[12] C.J. Swanepoel, L.M. Pretorius, Upper Bounds for a Ramsey Theorem for Trees, Graphs and Combin. 10 (1994), 377-382.

[13] W.T. Trotter, P. Winkler, Arithmetic Progressions in Partially Ordered Sets, Order 4 (1987), 37-42.