Online Talk: Sebastian Mies

YouTube recording:

Time: Thursday, Apr 27, 3pm ET

Speaker: Sebastian Mies, Johannes Gutenberg University Mainz
Title: The Strong Nine Dragon Tree Conjecture for $d \le k+1$

Abstract: The arboricity $\Gamma(G)$ of an undirected graph $G = (V,E)$ is the minimal number such that $E$ can be partitioned into $\Gamma(G)$ forests. Nash-Williams’ formula states that $\Gamma(G) = \lceil \gamma(G) \rceil$, where $\gamma(G)$ is the maximum of $|E_H|/(|V_H|-1)$ over all subgraphs $(V_H, E_H)$ of $G$ with $|V_H| \ge 2$.The Strong Nine Dragon Tree Conjecture states that if $\gamma(G) \le k + d / (d+k+1)$ for natural numbers k, d, then there is a partition of the edge set of G into k+1 forests such that one forest has at most d edges in each connected component.We settle the conjecture for $d \le k + 1$. For $d \le 2(k+1)$, we cannot prove the conjecture, however we show that there exists a partition in which the connected components in one forest have at most $d + \lceil kd/(k+1) \rceil – k$ edges.As an application of this theorem, we show that every 5-edge-connected planar graph G has a 5/6-thin spanning tree, a spanning tree whose edges fill up at most 5/6 of every cut. This theorem is best possible, in the sense that we cannot replace 5-edge-connected with 4-edge-connected, even if we replace 5/6 with any positive real number less than 1. This strengthens a result of Merker and Postle which showed 6-edge-connected planar graphs have a 18/19-thin spanning tree.This is joint work with Benjamin Moore.

Online Talk: Kristyna Pekárková

YouTube recording:

Time: Thursday, Apr 13, 3pm ET

Speaker: Kristyna Pekárková, Masaryk University
Title: Matroid-based approach to matrix sparsification

Abstract: Integer programming (IP) is a fundamental problem of discrete optimization;its notable applications can be found, for example, in scheduling and planning,string algorithms, or computational social choice. Solving instances of integerprogramming is, in general, NP-hard, and a long line of research has beendevoted to identifying instances of IP that can be solved efficiently. In thetalk, we will explain how structural properties of matroids can be applied inthe context of integer programming. Our main focus is on matroid depthparameters, namely contraction*-depth and deletion-depth. In particular, wewill discuss how these parameters can be used to design algorithms thatefficiently transform the constraint matrix of an instance of integerprogramming into an equivalent sparse (and so computationally tractable)form.