On trees and tree-like structures in infinite graphs

Abstract

In this dissertation we solve different problems in infinite graph theory that are concerned with trees and tree-like graphs.

In Chapter 2, we determine the number of topological types of trees of given cardinality. Two graphs are of the same topological type if they are topological minors of each other. We show that for any infinite cardinal κ there are exactly κ^+ distinct topological types of trees of size κ.

In Chapter 3, we investigate the Erdős-Pósa property for infinite graphs. A class G of graphs has the Erdős-Pósa property (EPP) if there is a function f : ℕ → ℕ such that for every graph Γ and every k ∈ ℕ there are either k disjoint graphs from G in Γ or there is a set X ⊆ V(Γ) of size at most f(k) such that Γ − X contains no graph from G. Moreover, G has the κ-EPP, where κ is an infinite cardinal, if for any graph Γ there are either κ disjoint graphs from G in Γ or there is a set X of vertices of Γ of size less than κ such that Γ − X contains no graph from G. We show that if G consists of a single infinite graph that does not contain a path of length n for some n ∈ ℕ, then G has the EPP and the κ-EPP for all infinite cardinals κ. Furthermore, we show that the class of all subdivisions of any tree T has the κ-EPP for every uncountable cardinal κ, and if T is rayless, also the ℵ_0-EPP and the EPP. On the other hand, we also find for every infinite cardinal κ a graph that does not have the κ-EPP.

In Chapters 4 and 5, we present first results on ubiquity in digraphs. We call a digraph H ubiquitous if every digraph D containing k disjoint copies of H for every k ∈ ℕ also contains infinitely many disjoint copies of H. A turn of an oriented (double) ray is a vertex of in-degree 2 or out-degree 2. We prove that an oriented ray is ubiquitous if and only if it has a finite number of turns, and that an oriented double ray with at least one turn is ubiquitous if and only if it has an odd number of turns.

In Chapter 6, we present a systematic study of how tree-decompositions of finite adhesion capture properties of the topological space |G| formed by a graph G together with its ends. The ends of a graph G interact in a natural way with a tree-decomposition (T, V) of G of finite adhesion. As every edge e of T induces a finite order separation {A_e, B_e} of G, each end of G has to choose one side of the separation and thus one component of T − e. By orienting the edges of T accordingly, we obtain an orientation of T for each end of G. Consider any set Ψ of ends of G. If for every end in Ψ the respective orientation of T points towards a (unique) end of T, and if this correspondence between Ψ and the ends of T is bijective, then we say that the tree-decomposition (T, V) displays Ψ. We find connections between sets of ends of G that can be displayed and their topological properties in the space |G|. In particular, we show that the following are equivalent: • There is a tree-decomposition of finite adhesion displaying Ψ. • The subspace of |G| consisting of Ψ together with all vertices and edges of G is completely metrizable. • Ψ is G_δ (i.e. a countable intersection of open sets) in |G|.