Topological ubiquity of trees

Nathan Bowler, Christian Elbracht, Joshua Erde, J. Pascal Gollin, Karl Heuer, Max Pitz, Maximilian Teegen

Research output: Contribution to journalArticlepeer-review


Let ⊲ be a relation between graphs. We say a graph G is ⊲-ubiquitous if whenever Γ is a graph with nG⊲Γ for all n∈N, then one also has ℵ0G⊲Γ, 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 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.

Original languageEnglish
Pages (from-to)70-95
Number of pages26
JournalJournal of Combinatorial Theory, Series B
Publication statusPublished - Nov 2022


  • Ends of infinite graphs
  • G-tribes
  • Linkages of rays
  • Self-minors
  • Shelah singular compactness
  • Ubiquity conjecture
  • Well-quasi-order

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Cite this