2018/06/11 by Bowler, Nathan, Elbracht, Christian, Erde, Joshua +4
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1806.04008
Let \triangleleft be a relation between graphs. We say a graph G is \triangleleft-ubiquitous if whenever Γ is a graph with nG \triangleleft Γ for all n ∈ ℕ, then one also has ℵ0 G \triangleleft Γ, where αG is the disjoint union of α many copies of G. The Ubiquity Conjecture of Andreae, a well-known open problem in the theory of infinite graphs, asserts that every locally finite connected graph is ubiquitous with respect to the minor relation. In this paper, which is the first of a series of papers making progress towards the Ubiquity Conjecture, we show that all trees are ubiquitous with respect to the topological minor relation, irrespective of their cardinality. This answers a question of Andreae from 1979.