Connectivity and tree structure in graphs and matroids

无论是有限的还是无限的，找到一种方法将给定的图分解成高度相连的部分，以便可以识别出一些将这些部分组织到给定的图中的粗略结构，这是图论中长期存在的探索。更具体地说，给定一个整数k，我们能在任何(k-1)连通图中识别出一个非常粗略的树结构吗？对于k=2，这是一个众所周知的基本事实：每个连通图都分解成它的最大2-连通子图和‘桥’，这两个子图一起形成了它的块割顶点树。对于k=3，上世纪60年代的图特也有类似的结果，尽管要复杂得多。对于较大的k，两种方法都取得了部分成功。1991年，Robertson和Seymour证明了每个图都有一个树分解成几个部分，以区分它的k阶缠绕，使得这些缠绕存在于不同的分解部分。这一结果最近被推广到Geelen，Gerards，Robertson和Whitell等人的拟阵上。独立地，Dunwoody和Krön最近提出了一个公理的‘顶点割’理论，它以树形的方式分解一个(k-1)-连通图，以区分它的最大的(k-1)-不可分顶点集。这些集合，即图的k块，是由Mader在1971年首次研究的，但Mader没有研究它们在整个图中是如何相对于彼此定位的.在我们之前的工作中，我们用标准项(如树分解)用非公理的方法重新证明了Dunwoody和Krön关于有限图的结果，并将它们推广到不是(k-1)连通的图.并展示了如何将不同k值的各种树结构统一为一个整体的树结构。本项目的目标是：了解这种树的各部分相对于它们所包含的k块的内部结构；--统一k-块和缠结的概念，从而得到一个包含并加强了所有上述结果的分解定理；--将这种统一的“k-连通片”概念及其相应的分解，从图推广到拟阵；--将该理论推广到无限的图和拟阵。

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.