On Andreaes Ubiquity Conjecture Johannes Carmesin University of Birmingham

2025-05-02 0 0 231.18KB 3 页 10玖币

侵权投诉

On Andreae’s Ubiquity Conjecture

Johannes Carmesin∗

University of Birmingham

October 11, 2022

Abstract

A graph His ubiquitous if for every graph Gthat for every natural

number ncontains nvertex-disjoint H-minors contains inﬁnitely many

vertex-disjoint H-minors. Andreae conjectured that every locally ﬁnite

graph is ubiquitous. We give a disconnected counterexample to this

conjecture. It remains open whether every connected locally ﬁnite

graph is ubiquitous.

Introduction. Thomas conjectured that the class of countable graphs

is well-quasi ordered by the minor relation [7]. Related to this, in 2002

Andreae conjectured that every locally ﬁnite1graph is ubiquitous; here

a graph His ubiquitous (with respect to the minor relation) if for ev-

ery graph Gthat for every natural number ncontains nvertex-disjoint

H-minors contains inﬁnitely many vertex-disjoint H-minors [1]. Finite

graphs are clearly ubiquitous, and by Halin’s theorem [6] the ray is

ubiquitous. Andreae proved quite a few cases of his conjecture, par-

ticularly that connected graphs of ﬁnite tree-width such that all their

maximal 2-connected subgraphs are ﬁnite are ubiquitous [2]. Recently

Bowler, Elbracht, Erde, Gollin, Heuer, Pitz and Teegen put forward

a series of papers [5, 4, 3] in which they prove that a large class of

locally ﬁnite graphs are ubiquitous, including the 2-dimensional grid!

Here we note that the condition of ‘connectedness’ needs to be added

to Andreae’s conjecture. In other words, we construct a disconnected

locally ﬁnite graph that is not ubiquitous.

The construction. The graph Gis indicated in Figure 1 and deﬁned

in its caption. Let Ibe the 1-sum2of K5and K3,3. Let Hbe the

disjoint union of Iwith a ray.

∗Funded by EPSRC, grant number EP/T016221/1

1Andreae constructed an uncountable graph that is not ubiquitous.

2The 1-sum of K5and K3,3is obtained from their disjoint by identifying two vertices,

one from each.

arXiv:2210.02711v2 [math.CO] 10 Oct 2022

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

OnAndreae'sUbiquityConjectureJohannesCarmesin*UniversityofBirminghamOctober11,2022AbstractAgraphHisubiquitousifforeverygraphGthatforeverynaturalnumberncontainsnvertex-disjointH-minorscontainsinnitelymanyvertex-disjointH-minors.Andreaeconjecturedthateverylocallynitegraphisubiquitous.Wegiveadisconne...

展开>> 收起<<

On Andreaes Ubiquity Conjecture Johannes Carmesin University of Birmingham.pdf

共3页,预览1页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

On Andreaes Ubiquity Conjecture Johannes Carmesin University of Birmingham

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: