Johannes Carmesin

Canonical trees of tree-decompositions

We prove that every graph has a canonical tree of tree-decompositions that distinguishes all principal tangles (these include the ends and various kinds of large finite dense structures) efficiently. Here `trees of tree-decompositions' are a slightly weaker notion than `tree-decompositions' but much more well-behaved than `tree-like metric spaces'. This theorem is best possible in the sense that we give an example that `trees of tree-decompositions' cannot be strengthened to `tree-decompositions' in the above theorem. This implies results of Dunwoody and Krön as well as of Carmesin, Diestel, Hundertmark and Stein. Beyond that for locally finite graphs our result gives for each $k\in\mathbb N$ canonical tree-decompositions that distinguish all $k$ -distinguishable ends efficiently.

Characterising graphs with no subdivision of a wheel of bounded diameter

We prove that a graph has an r-bounded subdivision of a wheel if and only if it does not have a graph-decomposition of locality r and width at most two.

Every planar graph with the Liouville property is amenable

We introduce a strengthening of the notion of transience for planar maps in order to relax the standard condition of bounded degree appearing in various results, in particular, the existence of Dirichlet harmonic functions proved by Benjamini and Schramm. As a corollary we obtain that every planar non-amenable graph admits Dirichlet harmonic functions.

Large highly connected subgraphs in graphs with linear average degree

In 1972 Mader proved that every graph with average degree at least $4k$ has a $(k+1)$ -connected subgraph with more than $2k$ vertices. We improve this bound by showing that the constant $4$ can be replaced by $3+\frac{1}{3}$ ; this bound is sharp.

New Constructions related to the Polynomial Sphere Recognition Problem

We construct a simply connected $2-$ complex $C$ embeddable in $3-$ space such that for any embedding of $C$ in $\mathbb S^3$ , any edge contraction forms a minor of the $2-$ complex not embeddable in $3-$ space. We achieve this by proving that every edge of $C$ forms a nontrivial knot in any of the embeddings of $C$ in $\mathbb S^3$ .

preprint2016arXiv

A Liouville hyperbolic souvlaki

We construct a transient bounded-degree graph no transient subgraph of which embeds in any surface of finite genus. Moreover, we construct a transient, Liouville, bounded-degree, Gromov--hyperbolic graph with trivial hyperbolic boundary that has no transient subtree. This answers a question of Benjamini. This graph also yields a (further) counterexample to a conjecture of Benjamini and Schramm.

preprint2016arXiv

A short proof that every finite graph has a tree-decomposition displaying its tangles

We give a short proof that every finite graph (or matroid) has a tree-decomposition that displays all maximal tangles. This theorem for graphs is a central result of the graph minors project of Robertson and Seymour and the extension to matroids is due to Geelen, Gerards and Whittle.

preprint2016arXiv

Reconstruction of infinite matroids from their 3-connected minors

We show that any infinite matroid can be reconstructed from the torsos of a tree-decomposition over its 2-separations, together with local information at the ends of the tree. We show that if the matroid is tame then this local information is simply a choice of whether circuits are permitted to use that end. The same is true if each torso is planar, with all gluing elements on a common face.

preprint2015arXiv

$k$ -Blocks: a connectivity invariant for graphs

A $k$ -block in a graph $G$ is a maximal set of at least $k$ vertices no two of which can be separated in $G$ by fewer than $k$ other vertices. The block number $β(G)$ of $G$ is the largest integer $k$ such that $G$ has a $k$ -block. We investigate how $β$ interacts with density invariants of graphs, such as their minimum or average degree. We further present algorithms that decide whether a graph has a $k$ -block, or which find all its $k$ -blocks. The connectivity invariant $β(G)$ has a dual width invariant, the block-width ${\rm bw}(G)$ of $G$ . Our algorithms imply the duality theorem $β= {\rm bw}$ : a graph has a block-decomposition of width and adhesion $< k$ if and only if it contains no $k$ -block.

preprint2015arXiv

Canonical tree-decompositions of a graph that display its $k$ -blocks

A $k$ -block in a graph $G$ is a maximal set of at least $k$ vertices no two of which can be separated in $G$ by removing less than $k$ vertices. It is separable if there exists a tree-decomposition of adhesion less than $k$ of $G$ in which this $k$ -block appears as a part. Carmesin, Diestel, Hamann, Hundertmark and Stein proved that every finite graph has a canonical tree-decomposition of adhesion less than $k$ that distinguishes all its $k$ -blocks and tangles of order $k$ . We construct such tree-decompositions with the additional property that every separable $k$ -block is equal to the unique part in which it is contained. This proves a conjecture of Diestel.

Canonical tree-decompositions of finite graphs I. Existence and algorithms

We construct tree-decompositions of graphs that distinguish all their k-blocks and tangles of order k, for any fixed integer k. We describe a family of algorithms to construct such decompositions, seeking to maximize their diversity subject to the requirement that they commute with graph isomorphisms. In particular, all the decompositions constructed are invariant under the automorphisms of the graph.

Canonical tree-decompositions of finite graphs II. Essential parts

In Part I of this series we described three algorithms that construct canonical tree-decompositions of graphs which distinguish all their k-blocks and tangles of order k. We now establish bounds on the number of parts in these decompositions that contain no such block or tangle, and determine conditions under which such parts contain nothing but a k-block.

Connectivity and tree structure in finite graphs

Considering systems of separations in a graph that separate every pair of a given set of vertex sets that are themselves not separated by these separations, we determine conditions under which such a separation system contains a nested subsystem that still separates those sets and is invariant under the automorphisms of the graph. As an application, we show that the $k$ -blocks -- the maximal vertex sets that cannot be separated by at most $k$ vertices -- of a graph $G$ live in distinct parts of a suitable tree-decomposition of $G$ of adhesion at most $k$ , whose decomposition tree is invariant under the automorphisms of $G$ . This extends recent work of Dunwoody and Krön and, like theirs, generalizes a similar theorem of Tutte for $k=2$ . Under mild additional assumptions, which are necessary, our decompositions can be combined into one overall tree-decomposition that distinguishes, for all $k$ simultaneously, all the $k$ -blocks of a finite graph.

Edge-disjoint double rays in infinite graphs: a Halin type result

We show that any graph that contains k edge-disjoint double rays for any k>0 contains also infinitely many edge-disjoint double rays. This was conjectured by Andreae in 1981.

Even an infinite bureaucracy eventually makes a decision

We show that the fact that a political decision filtered through a finite tree of committees gives a determined answer generalises in some sense to infinite trees. This implies a new special case of the Matroid Intersection Conjecture.

Infinite trees of matroids

We generalise the construction of infinite matroids from trees of matroids to allow the matroids at the nodes, as well as the field over which they are represented, to be infinite.

On the intersection conjecture for infinite trees of matroids

Using a new technique, we prove a rich family of special cases of the matroid intersection conjecture. Roughly, we prove the conjecture for pairs of tame matroids which have a common decomposition by 2-separations into finite parts.

Topological cycle matroids of infinite graphs

We prove that the topological cycles of an arbitrary infinite graph induce a matroid. This matroid in general is neither finitary nor cofinitary.

Topological infinite gammoids, and a new Menger-type theorem for infinite graphs

Answering a question of Diestel, we develop a topological notion of gammoids in infinite graphs which, unlike traditional infinite gammoids, always define a matroid. As our main tool, we prove for any infinite graph $G$ with vertex sets $A$ and $B$ that if every finite subset of $A$ is linked to $B$ by disjoint paths, then the whole of $A$ can be linked to the closure of $B$ by disjoint paths or rays in a natural topology on $G$ and its ends. This latter theorem re-proves and strengthens the infinite Menger theorem of Aharoni and Berger for `well-separated' sets $A$ and $B$ . It also implies the topological Menger theorem of Diestel for locally finite graphs.

preprint2013arXiv

Infinite graphic matroids Part I

An infinite matroid is graphic if all of its finite minors are graphic and the intersection of any circuit with any cocircuit is finite. We show that a matroid is graphic if and only if it can be represented by a graph-like topological space: that is, a graph-like space in the sense of Thomassen and Vella. This extends Tutte's characterization of finite graphic matroids. The representation we construct has many pleasant topological properties. Working in the representing space, we prove that any circuit in a 3-connected graphic matroid is countable.

preprint2013arXiv

Infinite Matroids and Determinacy of Games

Solving a problem of Diestel and Pott, we construct a large class of infinite matroids. These can be used to provide counterexamples against the natural extension of the Well-quasi-ordering-Conjecture to infinite matroids and to show that the class of planar infinite matroids does not have a universal matroid. The existence of these matroids has a connection to Set Theory in that it corresponds to the Determinacy of certain games. To show that our construction gives matroids, we introduce a new very simple axiomatization of the class of countable tame matroids.

preprint2013arXiv

The ubiquity of Psi-matroids

Solving (for tame matroids) a problem of Aigner-Horev, Diestel and Postle, we prove that every tame matroid M can be reconstructed from its canonical tree decomposition into 3-connected pieces, circuits and cocircuits together with information about which ends of the decomposition tree are used by M . For every locally finite graph G, we show that every tame matroid whose circuits are topological circles of G and whose cocircuits are bonds of G is determined by the set Psi of ends it uses, that is, it is a Psi-matroid.

An excluded minors method for infinite matroids

The notion of thin sums matroids was invented to extend the notion of representability to non-finitary matroids. A matroid is tame if every circuit-cocircuit intersection is finite. We prove that a tame matroid is a thin sums matroid over a finite field k if and only if all its finite minors are representable over k. We expect that the method we use to prove this will make it possible to lift many theorems about finite matroids representable over a finite field to theorems about tame thin sums matroids over these fields. We give three examples of this: various characterisations of binary tame matroids and of regular tame matroids, and unique representability of ternary tame matroids.

Infinite matroid union

We consider the problem of determining whether the union of two infinite matroids is a matroid. We introduce a superclass of the finitary matroids, the nearly finitary matroids, and prove that the union of two nearly finitary matroids is a nearly finitary matroid. On the other hand, we prove that the union of two arbitrary infinite matroids is not necessarily a matroid. Indeed, we show (under a weak additional assumption) that the nearly finitary matroids are essentially the largest class of matroids for which one can have a union theorem. We then extend the base packing theorem for finite matroids to finite families of co-finitary matroids. This, in turn, yields a matroidal proof for the tree-packing results for infinite graphs due to Diestel and Tutte.

Matroid intersection, base packing and base covering for infinite matroids

As part of the recent developments in infinite matroid theory, there have been a number of conjectures about how standard theorems of finite matroid theory might extend to the infinite setting. These include base packing, base covering, and matroid intersection and union. We show that several of these conjectures are equivalent, so that each gives a perspective on the same central problem of infinite matroid theory. For finite matroids, these equivalences give new and simpler proofs for the finite theorems corresponding to these conjectures. This new point of view also allows us to extend, and simplify the proofs of, some cases where these conjectures were known to be true.

Matroids with an infinite circuit-cocircuit intersection

We construct some matroids that have a circuit and a cocircuit with infinite intersection. This answers a question of Bruhn, Diestel, Kriesell, Pendavingh and Wollan. It further shows that the axiom system for matroids proposed by Dress does not axiomatize all infinite matroids. We show that one of the matroids we define is a thin sums matroid whose dual isn't a thin sums matroid.