Connectivity and tree structure in graphs and matroids

图和拟阵中的连通性和树结构

• 批准号: 248688805
• 负责人: Professor Dr. Reinhard Diestel
• 金额: --
• 依托单位: Fachbereich Mathematik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2014
• 资助国家: 德国
• 起止时间: 2013-12-31 至 2019-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/248688805?language=en
• 关键词: Connectivity; tree; structure; graphs; matroids

It has been a long-standing quest in graph theory, finite or infinite, to find a way to decompose a given graph into highly connected pieces in such a way that some coarse structure can be identified that organizes those pieces into the given graph. More specifically, given an integer k, can we in any (k-1)-connected graph identify a coarse tree-structure whose tree is built from something like its `k-connected blocks'?For k=2, this is a well-known elementary fact: every connected graph decomposes into its maximal 2-connected subgraphs and `bridges', which together form its block-cutvertex tree. For k=3 there is a similar, though more complicated, result of Tutte from the 1960s. For larger k, two approaches have each been partly successful. Robertson and Seymour proved in 1991 that every graph has a tree-decomposition into parts that distinguishes its tangles of order k so that these tangles live in different decomposition parts. This result has recently been extended to matroids by Geelen, Gerards, Robertson and Whittle. Independently, Dunwoody and Krön have recently proposed an axiomatic theory of `vertex cuts' which decompose a (k-1)-connected graph in a tree-like way that distinguishes its maximal (k-1)-inseparable vertex sets. These sets, the `k-blocks' of the graph, were first studied by Mader in 1971, but Mader did not investigate how they are positioned relative to each other in the whole graph.In our own previous work, we re-proved the results of Dunwoody and Krön for finite graphs in a non-axiomatic way using standard terms (such as tree-decompositions), extended them to graphs that are not (k-1)-connected, and showed how the various tree-structures for different values of k can be unified into one overall tree-structure.The aims of this project are as follows:  - understand the internal structure of the parts of such tree-decompositions with respect to the k-block they contain;  - unify the notions of k-blocks and tangles, so as to obtain a decomposition theorem that encompasses and strengthens all the above results;  - extend such a unified notion of `k-connected pieces', and the corresponding decomposition, from graphs to matroids;  - extend the theory to infinite graphs and matroids.

在有限或无限的图论中，找到一种方法将给定的图分解成高度连接的片段，从而可以识别出一些粗略的结构，将这些片段组织到给定的图中，这是一个长期的探索。更具体地说，给定一个整数k，我们能否在任何（k-1）连通图中识别一个粗糙的树结构，其树是由类似于“k连通块”的东西构成的？对于k=2，这是一个众所周知的基本事实：每个连通图都分解成它的最大2连通子图和“桥”，它们一起形成了它的块切顶点树。对于k=3, 20世纪60年代的Tutte得出了一个类似的结果，尽管更为复杂。对于较大的k，有两种方法都部分成功。Robertson和Seymour在1991年证明了每个图都有一个分成若干部分的树分解，这些部分区分了k阶的缠结，使得这些缠结存在于不同的分解部分。这个结果最近被Geelen， Gerards， Robertson和Whittle推广到拟阵。Dunwoody和Krön最近独立地提出了一个“顶点切割”的公理理论，该理论将（k-1）连通图以树状方式分解，以区分其最大（k-1）不可分割顶点集。这些集合，即图中的“k块”，最早是由Mader在1971年研究的，但Mader并没有研究它们在整个图中的相对位置。在我们自己之前的工作中，我们使用标准术语（如树分解）以非公理的方式重新证明了Dunwoody和Krön对于有限图的结果，并将其扩展到非（k-1）连接的图，并展示了不同k值的各种树结构如何统一为一个整体的树结构。这个项目的目的如下：-理解这些树分解的部分的内部结构，相对于它们所包含的k块；-统一k块和缠结的概念，得到一个包含并强化上述所有结果的分解定理；-将这种“k连通块”的统一概念，以及相应的分解，从图推广到拟阵；-将理论扩展到无限图和拟阵。