Pascal Gollin, Disjoint dijoins for classes of dibonds in finite and infinite digraphs

A dibond in a directed graph is a bond (i.e. a minimal non-empty cut) for which all of its edges are directed to a common side of the cut. A famous theorem of Lucchesi and Younger states that in every finite digraph the least size of an edge set meeting every dicut equals the maximum number of disjoint dibonds in that digraph. We call such sets dijoins.

Woodall conjectured a dual statement. He asked whether the maximum number of disjoint dijoins in a digraph equals the minimum size of a dibond.
We study a modification of this question where we restrict our attention to certain classes of dibonds, i.e. whether for a class $\mathfrak{B}$ of dibonds of a digraph the maximum number of disjoint edge sets meeting every dibond in $\mathfrak{B}$ equal the size a minimum dibond in $\mathfrak{B}$.

In particular, we verify this questions for nested classes of dibonds, for the class of dibonds of minimum size, and for classes of infinite dibonds.

Pascal Gollin gave a talk on the existence of a decomposition of an infinite graph into spanning trees at the discrete math seminar

On October 29, 2019, Pascal Gollin from IBS discrete mathematics group gave a talk on the existence of a decomposition of an infinite graph into spanning trees in terms of the existence of packing and covering of spanning trees at the discrete math seminar. The title of his talk was “A Cantor-Bernstein-type theorem for spanning trees in infinite graphs“.

Pascal Gollin, A Cantor-Bernstein-type theorem for spanning trees in infinite graphs

Given a cardinal $\lambda$, a $\lambda$-packing of a graph $G$ is a family of $\lambda$ many edge-disjoint spanning trees of $G$, and a $\lambda$-covering of $G$ is a family of spanning trees covering $E(G)$.

We show that if a graph admits a $\lambda$-packing and a $\lambda$-covering  then the graph also admits a decomposition into $\lambda$ many spanning trees. In this talk, we concentrate on the case of $\lambda$ being an infinite cardinal. Moreover, we will provide a new and simple proof for a theorem of Laviolette characterising the existence of a $\lambda$-packing, as well as for a theorem of Erdős and Hajnal characterising the existence of a $\lambda$-covering.

Joint work with Joshua Erde, Attila Joó, Paul Knappe and Max Pitz.