Connectivity and tree structure in graphs and 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.