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

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

Speaker: Cameron Crenshaw, Louisiana State University
Title: Ordering circuits of matroids

Abstract: The cycles of a graph give a natural cyclic ordering to their edge-sets, and these orderings are consistent in that two edges are adjacent in one cycle if and only if they are adjacent in every cycle in which they appear together. An orderable matroid is one whose set of circuits admits such a consistent ordering. In this talk, we consider the question of determining which matroids are orderable. Although we are able to answer this question for non-binary matroids, it remains open for binary matroids. We give examples to provide insight into the potential difficulty of this question in general. We also discuss that, by requiring that the ordering preserves the three arcs in every theta-graph restriction of a binary matroid $M$, we guarantee that $M$ is orderable if and only if $M$ is graphic. This is joint work with James Oxley.

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

Time: Thursday, May 11, 3pm ET
Zoom: https://uwaterloo.zoom.us/j/8674047206?pwd=RjVGV1duUHJPbEpZTWdRR3BLSld4Zz09
ID: 867 404 7206
Passcode: knauer1

Speaker: Kolja Knauer, Universitat de Barcelona
Title: Complexes of oriented matroids and their tope graphs

Abstract: Complexes of oriented matroids (COMs) arise from the combinatorics of a real hyperplane arrangement intersected with an open convex set. They generalize (affine) oriented matroids and capture various other classes such as convex geometries, antimatroids, CAT(0)-cube and Coxeter complexes, lopsided and ample set systems. I will give a gentle introduction and then focus on the tope graph of a COM – an object that determines the COM up to isomorphism. I will present a purely graph theoretic polynomial time verifiable characterization that specializes to oriented matroids.

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.