Topological ubiquity of trees

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

doi:10.1016/j.jctb.2022.05.011

Topological ubiquity of trees

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

Institute of Discrete Mathematics (5050)

Research output: Contribution to journal › Article › peer-review

Abstract

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 ℵ₀G⊲Γ, 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 language	English
Pages (from-to)	70-95
Number of pages	26
Journal	Journal of Combinatorial Theory, Series B
Volume	157
DOIs	https://doi.org/10.1016/j.jctb.2022.05.011
Publication status	Published - Nov 2022

Keywords

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

Access to Document

10.1016/j.jctb.2022.05.011Licence: CC BY 4.0

Cite this

@article{40eb4746877744f3869c27300869a337,

title = "Topological ubiquity of trees",

abstract = "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.",

keywords = "Ends of infinite graphs, G-tribes, Linkages of rays, Self-minors, Shelah singular compactness, Ubiquity conjecture, Well-quasi-order",

author = "Nathan Bowler and Christian Elbracht and Joshua Erde and Gollin, {J. Pascal} and Karl Heuer and Max Pitz and Maximilian Teegen",

note = "Publisher Copyright: {\textcopyright} 2022 The Authors",

year = "2022",

month = nov,

doi = "10.1016/j.jctb.2022.05.011",

language = "English",

volume = "157",

pages = "70--95",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Topological ubiquity of trees

AU - Bowler, Nathan

AU - Elbracht, Christian

AU - Erde, Joshua

AU - Gollin, J. Pascal

AU - Heuer, Karl

AU - Pitz, Max

AU - Teegen, Maximilian

PY - 2022/11

Y1 - 2022/11

N2 - 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.

AB - 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.

KW - Ends of infinite graphs

KW - G-tribes

KW - Linkages of rays

KW - Self-minors

KW - Shelah singular compactness

KW - Ubiquity conjecture

KW - Well-quasi-order

UR - http://www.scopus.com/inward/record.url?scp=85132220710&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2022.05.011

DO - 10.1016/j.jctb.2022.05.011

M3 - Article

AN - SCOPUS:85132220710

SN - 0095-8956

VL - 157

SP - 70

EP - 95

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

ER -

Topological ubiquity of trees

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this