The grid theorem of Robertson and Seymour can be equivalently stated using balanced separators, that are separators whose deletion leaves every component with no more than half of the vertices of the graph, as follows. Every graph that excludes some planar graph as a minor has a balanced separator of bounded size. Building on this formulation, Gartland and Lokshtanov conjectured an induced minor version of that theorem inspired by coarse graph theory. They conjectured that every graph that excludes some planar graph as an induced minor has a balanced separator which is dominated by a bounded number of vertices. We confirm this conjecture for excluding any fixed wheel, that is, a cycle together with a universal vertex, as an induced minor.
This talk is based on joint work with Maria Chudnovsky, Matjaž Krnc, and Martin Milanič.
Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. We therefore say that cycles satisfy the Erdős-Pósa property. However, while odd cycles do not satisfy the Erdős-Pósa property, Reed proved in 1999 an analogue by relaxing packing to half-integral packing, where each vertex is allowed to be contained in at most two such cycles. Moreover, he gave a structural characterisation for when the Erdős-Pósa property for odd cycles fails.
We prove a far-reaching generalisation of the theorem of Reed; if the edges of a graph are labelled by finitely many abelian groups, then the cycles whose values avoid a fixed finite set for each abelian group satisfy the half-integral Erdős-Pósa property, and we similarly give a structural characterisation for the failure of the Erdős-Pósa property.
A multitude of natural properties of cycles can be encoded in this setting. For example, we show that the cycles of length $\ell$ modulo $m$ satisfy the half-integral Erdős-Pósa property, and we characterise for which values of $\ell$ and $m$ these cycles satisfy the Erdős-Pósa property.
This is joint work with Kevin Hendrey, Ken-ichi Kawarabayashi, O-joung Kwon, Sang-il Oum, and Youngho Yoo.
Pascal Gollin from the IBS Discrete Mathematics Group has been appointed as the IBS Young Scientist Fellow as of August 1, 2021. The title of his research proposal was “Structural questions for infinite graphs, digraphs, and matroids“. Congratulations!
On May 18, 2021, Pascal Gollin from the IBS Discrete Mathematics Group gave a talk at the Discrete Math Seminar on the existence of a large flame extending a given vertex-flame in a countable digraph. The title of his talk was “Enlarging vertex-flames in countable digraphs“.
A rooted digraph is a vertex-flame if for every vertex v there is a set of internally disjoint directed paths from the root to v whose set of terminal edges covers all ingoing edges of v. It was shown by Lovász that every finite rooted digraph admits a spanning subdigraph which is a vertex-flame and large, where the latter means that it preserves the local connectivity to each vertex from the root. A structural generalisation of vertex-flames and largeness to infinite digraphs was given by Joó and the analogue of Lovász’ result for countable digraphs was shown.
In this talk, I present a strengthening of this result stating that in every countable rooted digraph each vertex-flame can be extended to a large vertex-flame.
On April 7, 2020, Pascal Gollin from the IBS Discrete Mathematics Group presented his work on the relation between the packing of edge sets intersecting all directed cuts in some class B and the maximum size of a minimal nonempty directed cut in B, motivated by Woodall’s conjecture. The title of his talk is “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.
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“.
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.
