Dominating Functions and Graphs

Reinhard Diestel  Saharon Shelah^{∗} Juris Steprāns

June 7, 2000

Abstract

A graph is called dominating if its vertices can be labelled with integers in such a way that for every function f: ω → ω the graph contains a ray whose sequence of labels eventually exceeds f. We obtain a characterization of these graphs by producing a small family of dominating graphs with the property that every dominating graph must contain some member of the family.

1 Introduction

If f and g are functions from ω to ω, we write f ≥^{∗} g and say that f dominates g if the set {n ∈ ω : f(n) < g(n)} is finite. A family F of functions from ω to ω is called a dominating family if every function g: ω → ω is dominated by some f ∈ F. The least cardinality of a dominating family is denoted by 𝔡.

Similarly, a family F of functions from ω to ω is called bounded if there exists a function g: ω → ω which dominates every f ∈ F; if no such function exists, F is unbounded. The least cardinality of an unbounded family is denoted by 𝔟.

It is well known and easy to show that ω < 𝔟 ≤ 𝔡 ≤ 2^{ω}. Depending on the axioms of set theory assumed, 𝔟 and 𝔡 may or may not coincide, and it is consistent that both are less than 2^{ω}. Properties of these and related cardinals have been studied widely in the literature; see the article by Vaughan in [3].

Taking a different approach to considering merely the cardinalities of bounded families of functions, Halin (see [2]) introduced the notion of a bounded graph: a graph is called bounded if for every labelling of its vertices with integers the labellings along its rays—its one-way infinite paths—form a bounded family. Thus, the family of functions considered is constrained not by cardinality but by imposing an intersection pattern on its members. A long-standing conjecture of Halin, known as the ‘bounded graph conjecture’, said that the bounded graphs are characterized by the exclusion of four simple types of unbounded graph; this conjecture was recently proved in [1].

∗The second author’s research is supported by the Israel Research Fund while the third author is supported by NSERC. This is publication 443 in the second author’s catalogue of publications

In this paper we prove an analogous result for dominating graphs; a graph is called dominating if its vertices can be labelled with integers in such a way that the labellings along its rays form a dominating family of functions. We show that a graph is dominating if and only if it contains one of three specified prototypes of a dominating graph.

As usual, a graph will be thought of as a symmetrical binary relation on some underlying set, its set of vertices. Thus, a graph on a set X is a subset of the set [X]^{2} of unordered pairs of X, called its edges. Two graphs will be called disjoint if and only if their vertex sets are disjoint. If G is a graph on X, then G′ is a subgraph of G if G′ is a subset of G ∩ [X′]^{2} for some X′ ⊆ X.

The degree of a vertex is the number of edges containing it. If m ∈ ω + 1, a path of length m in a graph G on X is a one-to-one function P: m → X such that {P (n − 1), P (n)} ∈ G whenever 0 < n < m. Often, the image of a path will be confused with the path itself; for example, a vertex x will be said to be ‘on’ P when what is really meant is that P (n) = x for some n ∈ m. With some abuse of notation we shall say that {P_{i} : i ∈ I} is a family of disjoint paths from (or: starting at) x if P_{i}(0) = x for every i and no vertex other than x is on both P_{i} and P_{j} if i ≠ j. Similarly we may speak of a family of ‘disjoint’ paths ending at x, or of a family of ‘disjoint’ paths from x to y when x and y are two fixed vertices.

A path of infinite length will be called a ray. Thus, more formally, a graph on X is dominating if and only if there exists a labelling L: X → ω such that for every f: ω → ω there is a ray R: ω → X with f ≤^{∗} L ∘ R.

A graph in which any two vertices can be connected by a unique path is a tree. The tree in which every vertex has countably infinite degree is denoted by T_{ω}. A tree T is called a subdivision of T_{ω} if each vertex of T has either degree 2 or countably infinite degree, and every ray in T contains a vertex that has infinite degree in T. The vertices of infinite degree in T are its branch vertices, the vertices of degree 2 its subdividing vertices.

If T is a subdivision of T_{ω}, there is a natural bijection ϕ from the vertices of T_{ω} to the branch vertices of T such that if x, y form an edge of T_{ω} then the unique path in T joining ϕ(x) to ϕ(y) contains no other branch vertex of T; identifying the vertices of T_{ω} with their images under ϕ, we may call such a path in T a subdivided edge (of T_{ω}) at ϕ(x).

A subdivision T of T_{ω} will be called uniform if it has a branch vertex r, called its root, such that whenever x is a branch vertex, all the subdivided edges at x that are not contained in the unique path from x to r have the same length.

It is not difficult to see [1, §4] that the edges of a T_{ω} may be enumerated in such a way that, for every edge other than the first edge, one of its two vertices also belongs to an edge preceding it in the enumeration. Such an enumeration will be called a standard construction of T_{ω}. As a typical (if trivial) application of this tool, consider the task of constructing a T_{ω} subgraph in some given graph every vertex of which has infinite degree: at each step, we will have specified only a finite portion of our T_{ω}, so we will always be able to add the next edge as required.

2 Examples of dominating graphs

In this section we look at some typical dominating graphs, including those needed to state our characterization theorem.

Since supergraphs of dominating graphs are again dominating, our aim will be to find dominating graphs which are minimal, in the sense that any subgraph that does not itself contain a copy of the original graph is no longer dominating. A trivial example of such a minimal dominating graph is given by any graph that is the union of 𝔡 disjoint rays:

Proposition 2.1 If a graph is the union of 𝔡 disjoint rays then it is dominating.

Proof: Label each ray by a different member of some dominating family of functions. ■

So how about countable graphs? Clearly, a complete graph (one in which every pair of vertices is an edge) on a countably infinite set is dominating: just label its vertices injectively. In the same way we see that a T_{ω} (which is ‘smaller’ than a complete infinite graph) is dominating.

An arbitrary subdivision of T_{ω} is not necessarily dominating. Indeed, consider any enumeration e: ω → T_{ω} of the edges of T_{ω}. For each n ∈ ω subdivide e(n) exactly n times, so that the resulting subdivided edge is a path of length n + 2. Call this tree T. To see that T is not dominating, let L be any labelling of its vertices. Let H: ω → ω be any increasing function satisfying H(n) > max {L(x) : x ∈ e(n)} for all n ∈ ω. We show that, for any ray R in T and any i ∈ ω, there exists a k > i such that H(k) > L(R(k)) (so H is not dominated by L∘R). Given such R and i, choose j, k ∈ ω with i < j < k so that {R(j), R(k)} = e(n) for some n, and so that U = {R(ℓ) : j ≤ ℓ ≤ k} contains no other branch vertex of T. Then R traces out the subdivided edge e(n), and in particular we have k ≥ |U | = n + 2. Since H is increasing and H(n) > L(R(k)) by definition of H, this gives H(k) ≥ H(n) > L(R(k)) as desired.

Uniform subdivisions of T_{ω}, on the other hand, are easily seen to be dominating:

Proposition 2.2 Uniform subdivisions of T_{ω} are dominating.

Proof: Let T be a uniform subdivision of T_{ω}, with vertex set X and root r. Let L: X → ω be any injective labelling; we show that for every function f: ω → ω there is a ray R: ω → X such that f ≤^{∗} L ∘ R.

We define R inductively, choosing its subdivided edges one at a time. (Recall that any ray in a subdivision of T_{ω} contains infinitely many branch vertices, and is thus a concatenation of paths that are subdivided edges of the T_{ω}.) Let R(0) = r. Suppose now that R(n) has been defined for every n ≤ m, and that R(m) is a branch vertex. Then all the (infinitely many) subdivided edges at R(m) that are not contained in the portion of R defined so far have the same length ℓ, and so we can find one of them, P say, such that L(P (i)) ≥ f(m + i) whenever 0 < i < ℓ. Setting R(m + i) = P (i) for these i, we see that L(R(m + i)) ≥ f(m + i); moreover, R(m + ℓ − 1) is again a branch vertex of T. This completes the induction step, and hence the construction of R. Since L(R(n)) ≥ f(n) for every n > 0, we have f ≤^{∗} L ∘ R as required. ■

How many disjoint copies of arbitrary subdivisions of T_{ω} are needed to make a dominating graph? By Proposition 2.1, 𝔡 copies will certainly do, since each of them contains a ray. Our next proposition says that, in fact, 𝔟 copies suffice.

Proposition 2.3 If a graph is the union of 𝔟 disjoint subdivisions of T_{ω}, then it is dominating.

Proof: Let {f_{ξ} : ξ ∈ 𝔟} be an unbounded family of increasing functions from ω to ω. Let {G_{ξ} : ξ ∈ 𝔟} be a family of 𝔟 disjoint subdivisions of T_{ω}, and let G_{ξ} have vertex set X_{ξ} and root r_{ξ}. We show that G = ⋃{G_{ξ} : ξ ∈ 𝔟} is dominating.

For each branch vertex x of G_{ξ}, let N(x) be the set of all branch vertices y that are not contained in the unique path from r_{ξ} to x and which are joined to x by a subdivided edge (i.e. by a path not containing any other branch vertices). Let S(x) denote the union of these x–y paths; thus, S(x) consists of all the paths from x to a vertex in N(x). For y ∈ N(x) we denote the length of the path from r_{ξ} to y by K(y).

Let us define a labelling L on G to witness that G is dominating. For each ξ, we fix L(r_{ξ}) arbitrarily, and then define L separately on each set S(x) \ {x} for all the other branch vertices x of G_{ξ}. There are two cases to consider. If infinitely many y ∈ N(x) have the same value of K(y), we let L ↾ (S(x) \ {x}) be an arbitrary one-to-one mapping. Otherwise, we choose for each y ∈ N(x) some y^{+} ∈ N(x) such that K(y) < K(y^{+}); then, for each z ≠ x on the path from x to y, we set L(z) = f_{ξ}(K(y^{+}).

To show that G is dominating, let f: ω → ω be given, without loss of generality increasing. As in the proof of Proposition 2.2 we inductively define a ray R: ω → X_{ξ} starting at r_{ξ}, so that f ≤^{∗} L ∘ R; here ξ is chosen so that f_{ξ} ≰^{∗} f. Since f is increasing, it suffices to show that for every branch vertex x of G_{ξ} there is some y ∈ N(x) such that L(z) ≥ f(K(y)) for each z ≠ x on the path from x to y; we may then choose the path from x to y as the next segment for R.

If infinitely many y ∈ N(x) have the same value of K(y), say k, then L is injective on S(x) \ {x}; since f takes only finitely many values on the first k + 1 integers, we can easily find y as desired. If not, then each y ∈ N(x) has been assigned some y^{+} ∈ N(x). Pick y′ ∈ N(x), find an i ≥ K(y′) such that f_{ξ}(i) > f(i), and choose y ∈ N(x) with maximal K(y) ≤ i. Then K(y) ≤ i < K(y^{+}). For each z ≠ x on the path from x to y we have

L(z) = f_{ξ}(K(y^{+})) ≥ f_{ξ}(i) ≥ f(i) ≥ f(K(y))

as desired. ■

3 A characterization of dominating graphs

We now come to prove our main result, the following characterization of dominating graphs.

Theorem 3.1 A graph G is dominating if and only if it satisfies one of the following three conditions:

1. G contains a uniform subdivision of T_{ω};

2. G contains 𝔟 disjoint subdivisions of T_{ω};

3. G contains 𝔡 disjoint rays.

Note that if 𝔟 = 𝔡 then (2) above is redundant, since 𝔡 disjoint subdivisions of T_{ω} contain 𝔡 disjoint rays.

The bulk of the proof of Theorem 3.1 is divided up into several lemmas. We shall consider these lemmas in turn, and then complete the formal proof of the theorem.

Our first lemma is an easy consequence of the fact that there is no infinite decreasing sequence of ordinals; its proof is left to the reader.

Lemma 3.1 If ρ is an ordinal-valued function on ω, then there exists some n_{0} ∈ ω such that for every n ≥ n_{0} there is an m > n with ρ(m) ≥ ρ(n). ■

The next three lemmas make up most of the proof of Theorem 3.1.

Lemma 3.2 If |X | < 𝔟, then any dominating graph on X contains a uniform subdivision of T_{ω}.

Proof: Let G be a graph on X, where |X | < 𝔟. The basic idea of the proof is recursively to define a rank function ρ on some or all of the vertices of G, with the following property. If any vertex remains unranked, i.e. if the recursion ends before ρ is defined on all of X, then G contains a uniform subdivision of T_{ω}; if ρ gets defined for every vertex, then G is not dominating.

For the definition of ρ, we first define subsets Σ_{ξ} of X, as follows. Let Σ_{0} be the set of vertices x ∈ X that have finite degree in G. For ξ > 0, let Σ_{ξ} be the set of vertices x ∈ X such that, for every m ∈ ω, any family of disjoint paths of length m starting at x and ending at vertices not in ⋃_{ζ∈ξ} Σ_{ζ}, is finite. Note that if ζ < ξ, then Σ_{ζ} ⊆ Σ_{ξ}. Finally, for each x ∈ X, define ρ(x) to be the least ξ such that x ∈ Σ_{ξ}; if no such ξ exists, let ρ(x) remain undefined.

It is not difficult to see that if there is some x ∈ X such that ρ(x) is not defined then G contains a uniform subdivision of T_{ω}. Indeed, if ρ(x) has remained undefined then, by definition of ρ, there exists an infinite set of disjoint paths from x in G, all of the same length, and ending in vertices for which ρ is also undefined. Following the standard construction of T_{ω}, it is easy to build a uniform subdivision of T_{ω} from all these paths: at each point of the construction, only finitely many vertices have been used, but there is an infinite set of disjoint paths from which the next subdivided edge can be chosen.

Let us assume from now on that ρ(x) is defined for all x ∈ X, and show that G is not dominating. Let L: X → ω be any labelling. Assuming the Claim below (which will be proved later), we shall find a function H: ω → ω which is not dominated by L ∘ R for any ray R in G.

Let a path P from x to y in G be called upward if ρ(y) = max {ρ(z) : z ∈ P }.

Claim. For each x ∈ X and m ∈ ω, there are only finitely many vertices y ∈ X such that G contains an upward path of length m + 1 from x to y.

From the claim it follows that we may define, for each x ∈ X, a function Q_{x}: ω → ω such that Q_{x}(m) > L(y) for any m ∈ ω and any vertex y to which x can be linked by an upward path of length m + 1. By our hypothesis that | X | < 𝔟, there exists a function H: ω → ω which dominates each of the functions Q_{x}. Redefining H(n) as max {H(k) : k ≤ n} if necessary, we may assume that H is increasing.

Now let R be any ray in G; it suffices to show that H ≰^{∗} L ∘ R. By Lemma 3.1, we may find an infinite increasing sequence {k_{i} : i ∈ ω} such that ρ(R(k_{i})) ≤ ρ(R(k_{i+1})) for each i, and ρ(R(j)) < ρ(R(k_{i})) whenever k_{i} < j < k_{i+1}. Note in particular that, for each i, the part of R that connects R(k_{0}) with R(k_{i}) is an upward path of length k_{i} − k_{0} + 1.

Since H dominates Q_{R(k_{0})}, there is some K ∈ ω such that Q_{R(k_{0})}(k) ≤ H(k) for all k ≥ K. But then

L(R(k_{i})) < Q_{R(k_{0})}(k_{i} − k_{0}) ≤ H(k_{i} − k_{0}) ≤ H(k_{i})

for all i with k_{i}−k_{0} ≥ K, by definition of Q_{R(k_{0})}. Thus L∘R fails to dominate H, as required.

Hence all that remains to be proved is the Claim. Suppose the contrary, and consider a vertex x, an integer m, and an infinite set {y_{n} : n ∈ ω} such that for each n there is an upward path P_{n} of length m + 1 from x to y_{n}. Choose k ≤ m maximal so that there exist a vertex z and an infinite set P ⊆ {P_{n} : n ∈ ω} such that P (k) = z for every P ∈ P. (Note that k exists, because every P_{n} starts in x.) We now select an infinite sequence {P_{n_{i}} : i ∈ ω} of paths in P so that any two of these are disjoint after z; since each P_{n} is an upward path, and hence ρ(z) ≤ ρ(y_{n}) for every n, this will contradict the definition of ρ.

Let P_{n_{0}} be any path from P. Now suppose P_{n_{0}}, …, P_{n_{i}} have been chosen, and let U be the union of their vertex sets. By the maximality of k, there are at most finitely many paths in P that contain a vertex from U after z; let P_{n_{i+1}} be any other path from P. It is then clear that the full sequence {P_{n_{i}} : i ∈ ω} has the required disjointness property. ■

Lemma 3.3 If | X | < 𝔡, then any dominating graph on X contains a subdivision of T_{ω}.

Proof: Let G be a graph on X, where |X | < 𝔡. As in the proof of Lemma 3.2, the key lies in defining an appropriate rank function ρ on X. Let Σ_{0} be the set of vertices x ∈ X that have finite degree in G. For ξ > 0, let Σ_{ξ} be the set of vertices x ∈ X such that any family of disjoint paths starting at x and ending at vertices not in ⋃_{ζ∈ξ} Σ_{ζ} is finite. Again, we have Σ_{ζ} ⊆ Σ_{ξ} for ζ < ξ. Finally, for each x ∈ X, define ρ(x) to be the least ξ such that x ∈ Σ_{ξ}; if no such ξ exists, let ρ(x) remain undefined.

As in the proof of Lemma 3.2, we may imitate the standard construction of T_{ω} to show that if there exists an x ∈ X such that ρ(x) has remained undefined, then G contains a subdivision of T_{ω}.

We shall therefore assume that ρ(x) is defined for all x ∈ X, and show that G is not dominating. Let L: X → ω be any labelling. We shall find a function H: ω → ω which is not dominated by L ∘ R for any ray R in G.

Consider a vertex x ∈ X, and let Y = {y : ρ(y) ≥ ρ(x), y ≠ x}. Let P be a maximal set of disjoint paths starting at x and ending in Y. Then, by the definition of ρ, the set Y_{x} = ⋃ P \ {x} is a finite subset of X \ {x} separating x from Y (i.e. every x–Y path meets Y_{x}).

For each x ∈ X, let {x} = T_{x}^{0} ⊆ T_{x}^{1} ⊆ T_{x}^{2} ⊆ … be an infinite sequence of finite subsets of X, chosen so that for every i and z ∈ T_{x}^{i} we have Y_{z} ⊆ T_{x}^{i+1}. It is then possible to define a function Q_{x}: ω → ω such that Q_{x}(m) ≥ L(y) for every m ∈ ω and every y ∈ T_{x}^{m}. From our hypothesis that | X | < 𝔡 it follows that there exists a function H: ω → ω which is not dominated by any of the functions Q_{x}; clearly, we may choose H to be increasing.

Now let R be any ray in G; we prove that H is not dominated by L ∘ R. By Lemma 3.1, there is some K ∈ ω such that for each i ≥ K there is a k > i with ρ(R(i)) ≤ ρ(R(k)). Let

M = {m ∈ ω : H(m) > Q_{R(K)}(m)}.

M is infinite, since H ≰^{∗} Q_{R(K)}. We show that for each m ∈ M with m ≥ K there is some j ≥ m such that Q_{R(K)}(m) ≥ L(R(j)). Since H is increasing, this will imply that

H(j) ≥ H(m) > Q_{R(K)}(m) ≥ L(R(j))

for all these infinitely many j, giving H ≰^{∗} L ∘ R as desired.

It suffices to prove that for each m ≥ K there is some j ≥ m such that R(j) ∈ T_{R(K)}^{m−K} (⊆ T_{R(K)}^{m}), because then Q_{R(K)}(m) ≥ L(R(j)) by definition. This fact can be proved by induction on m. If m = K, let j = K; then {R(j)} = {R(K)} = T_{R(K)}^{0} = T_{R(K)}^{m−K} as desired. If m > K, use the induction hypothesis to find an i ≥ m − 1 such that R(i) ∈ T_{R(K)}^{m−1−K}, and choose k > i so that ρ(R(i)) ≤ ρ(R(k)). (Such k exists by m − 1 ≥ K and the choice of K.) Then Y_{R(i)} separates R(i) from R(k), so there is a j with i < j ≤ k such that R(j) ∈ Y_{R(i)}. Then R(j) ∈ Y_{R(i)} ⊆ T_{R(K)}^{m−K} (by R(i) ∈ T_{R(K)}^{m−1−K} and the definition of T_{R(K)}^{m−K}) and j ≥ i + 1 ≥ m, so j is as desired. ■

Let us say that a function f: ω → ω tends to infinity if f^{−1}(n) is finite for every n ∈ ω.

Lemma 3.4 If G is a graph on X, and if Y ⊆ X and L: X → ω, then there is a set Z with Y ⊆ Z ⊆ X and | Y | = | Z | which has the following property: for any ray R in G with infinitely many vertices in Z and L ∘ R tending to infinity, there is a ray R′ with all its vertices in Z such that L ∘ R′ = L ∘ R.

Proof: The lemma is trivial when Y is finite, so we assume that Y is infinite. Beginning with Z_{0} = Y, let us define an infinite increasing sequence Z_{0} ⊆ Z_{1} ⊆ Z_{2} ⊆ … of subsets of X, as follows. Suppose Z_{n} has already been defined. To obtain Z_{n+1} from Z_{n}, consider first every vertex y ∈ Z_{n}. Let P be a maximal set of (finite) paths in G ending in y and having no other vertices in Z_{n} such that L ∘ P ≠ L ∘ P′ for distinct P, P′ ∈ P. (This implies that P is countable.) For each P ∈ P, check whether G ∩ [Z_{n}]^{2} contains an infinite set of disjoint paths ending in y such that every path P′ in this set satisfies L ∘ P′ = L ∘ P; if there is no such set then add the vertices of P to Z_{n}. Similarly, consider every pair {x, y} ∈ [Z_{n}]^{2}. Now let P be a maximal set of x–y paths in G that have no other vertices in Z_{n}, and such that L ∘ P ≠ L ∘ P′ for distinct P, P′ ∈ P. For each P ∈ P, check whether G ∩ [Z_{n}]^{2} contains an infinite set of disjoint paths from x to y such that every path P′ in this set satisfies L ∘ P′ = L ∘ P; if there is no such set then add the vertices of P to Z_{n}.

Note that, since Y = Z_{0} was assumed to be infinite, we have |Z_{n} | = |Z_{n+1} | for each n. Therefore Z = ⋃_{n∈ω} Z_{n} satisfies |Y | = |Z | as required. Moreover, Z has the following two properties. Whenever y ∈ Z and P is a path of length > 1 in G that ends in y but has no other vertices in Z, there is an infinite set of disjoint paths ending in y such that every path P′ in this set has all its vertices in Z and satisfies L ∘ P′ = L ∘ P. Similarly, whenever x, y ∈ Z are joined in G by a path P of length > 2 whose only vertices in Z are x and y, there are infinitely many disjoint paths P′ from x to y whose vertices are all in Z and which satisfy L ∘ P′ = L ∘ P.

Now let R be any ray in G with infinitely many vertices in Z and L ∘ R tending to infinity. If all the vertices of R are in Z, we set R′ = R. Otherwise there is a (finite or infinite) sequence m_{0} ≤ n_{1} < m_{1} ≤ n_{2} < m_{2} ≤ … of integers such that the vertices of R outside Z are precisely the vertices of the form R(k) with k < m_{0} or n_{i} < k < m_{i} for some i. We shall obtain R′ from R by replacing its initial segment P_{0} = R ↾ m_{0} and, for i > 0, its subpaths P_{i} from x_{i} = R(n_{i}) to y_{i} = R(m_{i}) with paths on Z that carry the same labelling.

For each i = 0, 1, … in turn, let us find a path Q_{i} in G ∩ [Z]^{2} from x_{i} to y_{i} (or, in the case of i = 0, just ending in y_{0} = R(m_{0})) so that L ∘ Q_{i} = L ∘ P_{i}. If P_{i} has no vertices outside Z, we let Q_{i} = P_{i}. Otherwise, by the construction of Z, there is an infinite set Q_{i} of disjoint paths that qualify for selection as Q_{i}. Now Q_{i} has an infinite subset Q′_{i} of paths all avoiding the paths Q_{j} chosen earlier (except that we might have x_{i} = y_{j} if i = j + 1). Since the paths in Q′_{i} all carry the same labelling, they only use finitely many labels. Since, by assumption, L ∘ R tends to infinity, R has only finitely many vertices carrying any of these labels. Since Q′_{i} is an infinite set of disjoint paths from x_{i} to y_{i} (or ending at y_{0}, respectively), we may therefore choose Q_{i} from Q′_{i} so that Q_{i} has no other vertices on R.

Let R′ be obtained from R by replacing each P_{i} with the corresponding Q_{i} as defined above. Then R′ is a ray in G ∩ [Z]^{2}, and L ∘ R′ = L ∘ R as required.

■

Proof of Theorem 3.1: The sufficiency of the three conditions has been established in Propositions 2.2, 2.3 and 2.1, respectively. To prove the necessity, let G be a dominating graph on a set X and suppose that this is witnessed by the function L: X → ω. Let R be a maximal collection of disjoint rays in G. If | R | ≥ 𝔡 then there is nothing to do. If not, it follows from Lemma 3.4 that there is some Y ⊆ X such that

• |Y | = |R| < 𝔡;

• if R ∈ R then R ⊆ Y;

• for any ray R in G with infinitely many vertices in Y and L ∘ R tending to infinity, there is a ray R′ in G ∩ [Y]^{2} such that L ∘ R′ = L ∘ R.

G∩[Y]^{2} is a dominating graph on Y, and this is witnessed by the labelling L ↾ Y. Indeed, let f: ω → ω be given, without loss of generality increasing. Since G is dominating, it contains a ray R such that f ≤^{∗} L ∘ R. Since f is increasing, L ∘ R tends to infinity. Moreover, R has infinitely many vertices in Y, by the maximality of R. Therefore, G ∩ [Y]^{2} has a ray R′ such that L ∘ R′ = L ∘ R and hence f ≤^{∗} L ∘ R′.

Let T be a maximal collection of disjoint subdivisions of T_{ω} contained in G ∩ [Y]^{2}. If | T | ≥ 𝔟 then there is nothing to do. If not, it follows from Lemma 3.4 that there is some Z ⊆ Y such that

• |Z | = |T | < 𝔟;

• if T ∈ T then the vertices of T are all in Z;

• for any ray R on Y with infinitely many vertices in Z and L ∘ R tending to infinity, there is a ray R′ in G ∩ [Z]^{2} such that L ∘ R′ = L ∘ R.

If G ∩ [Z]^{2} contains a uniform subdivision of T_{ω}, we are done; we therefore assume that it does not. Then, by Lemma 3.2, G ∩ [Z]^{2} is not dominating. We show that now G ∩ [Y \ Z]^{2} must be a dominating graph on Y \ Z. Since |Y \ Z | < 𝔡 and G ∩ [Y \ Z]^{2} contains no subdivision of T_{ω} (by the maximality of T ), this will contradict Lemma 3.3.

Let H: ω → ω be a function witnessing (with respect to L) that G ∩ [Z]^{2} is not dominating. In order to show that G ∩ [Y \ Z]^{2} is dominating, let I: ω → ω be given; we shall find a ray on Y \ Z whose sequence of labels dominates I. Let J: ω → ω be increasing and such that J(n) ≥ max{H(n), I(n)} for every n. Recall that G ∩ [Y]^{2} with L was found to be dominating; choose a ray R on Y so that J ≤^{∗} L ∘ R. As J is increasing, L ∘ R tends to infinity. Since H, and hence also J, witnesses that G ∩ [Z]^{2} is not dominating, the definition of Z implies that R meets Z in only finitely many vertices. Let R′ be a subray of R whose vertices are all in Y \ Z; since J ≤^{∗} L ∘ R and J is increasing, we have I ≤^{∗} J ≤^{∗} L ∘ R′ as desired. ■

ACKNOWLEDGEMENT

During their work on this paper, the authors benefited from the continual interest of Paul Erdős and Alan Mekler.

REFERENCES

[1] R. Diestel and I. Leader, A proof of the bounded graph conjecture, Inventiones Math. 108 (1992), 131–162.

[2] R. Halin, Some problems and results in infinite graphs, Annals of Discrete Math. 41 (1989), 195–210.

[3] J. van Mill and G.M. Reed (editors), Open Problems in Topology, North-Holland, Amsterdam, 1991.

[4] F. Rothberger, Sur les Familles Indénombrables des Suites de Nombres Naturels et les Problèmes Concernants la Propriété C, Proceedings of the Cambridge Philosophical Society 27 (1941), 8–26.

[5] F. Rothberger, Une Remarque Concernante l’Hypothèse du Continu, Fundamenta Mathematicae 31 (1938), 224-226.

Reinhard Diestel, Faculty of Mathematics (SFB 343), University of Bielefeld, D-4800 Bielefeld 1, Germany

Saharon Shelah, Institute of Mathematics, Hebrew University, Jerusalem, Givat Ram, Israel

Juris Steprāns, Department of Mathematics, York University, 4700 Keele Street, North York, Ontario, Canada M3J 1P3