CanaDAM 2019
SFU Harbour Centre, 29 - 31 mai 2019

Matroid theory I
Org: Peter Nelson (University of Waterloo)

JOSEPH BONIN, George Washington University
New connections between polymatroids and graph coloring  [PDF]

A polymatroid is \emph{$k$-decomposable} if, for some matroids $M_1,M_2,\ldots,M_k$ on $E$, $$\rho(X) = r_{M_1}(X)+ r_{M_2}(X)+\cdots+ r_{M_k}(X)$$ for each subset $X$ of $E$. We show how to construct polymatroids from a hypergraph so that the $k$-decompositions of each polymatroid correspond bijectively to the $k$-colorings of the line graph of the hypergraph. We show that for each $2$-polymatroid $\rho$, there is a graph $G$ and a rational number $s$ so that for each positive integer $k$, the number of $k$-tuples of matroids $(M_1,M_2,\ldots,M_k)$ for which the equality above holds is $s\cdot \chi(G;k)$ where $\chi(G;x)$ is the chromatic polynomial of $G$.

NATHAN BOWLER, University of Hamburg
Flowers in infinite matroids  [PDF]

After a quick introduction to infinite matroids, I’ll introduce the concept of flowers. I’ll talk about how this concept has been used to uncover tree-like structures underlying finite matroids, and how we might hope to use it to find similar tree-like structures in infinite matroids. In particular, these structures seem well-suited for generalising Seymour’s decomposition theorem for regular matroids to the infinite context.

RUTGER CAMPBELL, University of Waterloo
Complexity of Matroid Representability  [PDF]

We will see that proving or disproving the representability of a matroid requires, in the worst case, an exponential number of rank-function queries.

TARA FIFE, Louisiana State University
Matroids with a Cyclic Arrangement of Circuits and Cocircuits  [PDF]

Wheels and whirls have a cyclic ordering on their elements such that every two consecutive elements lie in both a $3$-element circuit and a $3$-element cocircuit. Spikes and swirls have a cyclic ordering on their elements such that every three consecutive elements lie in both a $4$-element circuit and a $4$-element cocircuit. We describe matroids that have a cyclic ordering of $E(M)$ such that every $t-1$ consecutive elements lie in a $t$-element circuit and a $t$-element cocircuit. This is joint work with Nick Brettell, Deborah Chun, and Charles Semple and was initiated at the Tutte Centenary Retreat.

DILLON MAYHEW, Victoria University of Wellington
Axiomatising bicircular matroids  [PDF]

We conjecture that the class of frame matroids can be axiomatised in monadic second-order logic. We have succeeded in axiomatising the class of bicircular matroids. This implies that bicircularity can be tested in polynomial time when the input is restricted to finite-field representable matroids of bounded branch-width. Furthermore, a class of bicircular matroids with bounded branch-width has a decidable theory, so there is a finite procedure to test whether or not any given monadic second-order sentence is a theorem for the class.

This is joint work with Daryl Funk and Mike Newman.