YouTube recording: https://www.youtube.com/watch?v=3KYEAEiHkb0

Time: Thursday, Apr 27, 3pm ET
Zoom: https://gatech.zoom.us/j/8802082683

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.

YouTube recording: https://www.youtube.com/watch?v=OaRpqCco8ko

Time: Thursday, Apr 13, 3pm ET
Zoom: https://gatech.zoom.us/j/8802082683

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 integer
programming is, in general, NP-hard, and a long line of research has been
devoted to identifying instances of IP that can be solved efficiently. In the
talk, we will explain how structural properties of matroids can be applied in
the context of integer programming. Our main focus is on matroid depth
parameters, namely contraction*-depth and deletion-depth. In particular, we
will discuss how these parameters can be used to design algorithms that
efficiently transform the constraint matrix of an instance of integer
programming into an equivalent sparse (and so computationally tractable)
form.

YouTube recording: https://www.youtube.com/watch?v=iIcl15EgNe4

Time: Thursday, Mar 30, 3pm ET
Zoom: https://gatech.zoom.us/j/8802082683

Speaker: Ruth Luo, University of South Carolina
Title: A hypergraph analog of Dirac’s Theorem for 2-connected graphs

Abstract: Every graph with minimum degree $k \geq 2$ contains a cycle of length at least $k+1.$ Dirac proved that if the graph is also 2-connected then in fact we can find a cycle of length at least $min\{2k, n\}$. We prove a hypergraph version of this theorem: a minimum degree condition that forces the existence of long Berge cycles in 2-connected, uniform hypergraphs. This is joint work with Alexandr Kostochka and Grace McCourt.

YouTube recording: https://www.youtube.com/watch?v=2ga1XlPid9c

Time: Thursday, Mar 16, 3pm ET (beware of U.S./Canada time change on Mar 12!)
Zoom: https://uwaterloo.zoom.us/j/94977150195
pwd=LzRHN3NVcWtGbWlOVGNmakJQenF1Zz09
Passcode: kroeker1

Speaker: Matthew Kroeker, University of Waterloo
Title: Unavoidable Flats in Matroids Representable over a Prime Field

Abstract: The Sylvester-Gallai Theorem says that every rank-3 real-representable matroid contains a two-point line. A high-dimensional generalization of this result, due to Hansen, implies that every simple real-representable matroid of sufficiently high rank contains a rank-k independent flat. One only needs to look as far as the binary projective plane to see that such a result cannot hold for the class of matroids representable over a finite field. In light of this, we ask whether it is possible to determine a small list of “unavoidable” rank-k flats guaranteed to exist in a simple GF(q)-representable matroid of sufficiently high rank. We will answer this question for the case of prime fields: in particular, we show that, for any prime p and positive integer k, any simple GF(p)-representable matroid of sufficiently high rank contains a rank-k flat which is either independent, or is a projective or affine geometry. This is joint work with Jim Geelen.