Ubiquity in graphs I: Topological ubiquity of trees
Ubiquity in graphs I: Topological ubiquity of trees
复制标题
图中的普遍性 I：树的拓扑普遍性
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Maximilian Teegen
中科院分区：
文献类型：
--
作者：
N. Bowler;C. Elbracht;Joshua Erde;Pascal Gollin;K. Heuer;Max Pitz;Maximilian Teegen
设$riangleleft$是图之间的一种关系。我们说一个图$G$是空的如果当$Gamma$是一个图，其中$n在Mathbb{N}$中都有$Ng riangleleft Gamma$，则还有$Aleph_0 G riangleleft Gamma$，其中$αG$是$α$的许多副本的不相交的并。
作为无限图论中一个著名的公开问题，Andreae的Emh{ubiquity猜想}断言每个局部有限连通图关于次关系是泛在的。
本文是向泛在猜想发展的一系列论文中的第一篇，我们证明了所有树都是关于拓扑子关系的泛在树，而与它们的基数无关。这回答了Andreae自1979年提出的一个问题。
Let $ riangleleft$ be a relation between graphs. We say a graph $G$ is emph{$ riangleleft$-ubiquitous} if whenever $Gamma$ is a graph with $nG riangleleft Gamma$ for all $n in mathbb{N}$, then one also has $aleph_0 G riangleleft Gamma$, where $alpha G$ is the disjoint union of $alpha$ many copies of $G$.
The emph{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.