CanaDAM 2015
University of Saskatchewan, June 1 - 4, 2015

Matroid theory
Organizer and Chair: Stefan van Zwam (Louisiana State University, USA)

JOSEPH BONIN, The George Washington University
Excluded Minors for (Strongly) Base-Orderable Matroids  [PDF]

The minor-closed classes of base-orderable matroids and strongly base-orderable matroids properly include transversal matroids and gammoids. In 1976, Ingleton sketched how one could, in theory, find the infinite set of excluded minors for base-orderable matroids; he gave examples, attractive conjectures, and results (without proofs). We approach Ingleton's ideas from the perspective of cyclic flats and make progress on his conjectures. Ingleton gave an example of a matroid that is base-orderable but not strongly base-orderable; building on that, we show that the class of strongly base-orderable matroids has infinitely many base-orderable excluded-minors.

This is joint work with Thomas Savitsky.

DILLON MAYHEW, Victoria University of Wellington
Fans and fragile matroids  [PDF]

Let $\mathcal{S}$ be a set of matroids. The matroid $M$ is $\mathcal{S}$-fragile if, for every element $e$ in the ground set of $M$, either $M\backslash e$ or $M/e$ has no minor isomorphic to a member of $\mathcal{S}$. Fragile classes are important in excluded-minor proofs.

When characterising fragile classes, it seems sometimes the only way we can build from a fragile matroid while remaining fragile is to grow fans. How can we know this is the case? We have proved a theorem that reduces this question to a finite-case analysis.

Joint work with Carolyn Chun, Deb Chun, and Stefan van Zwam.

PETER NELSON, University of Waterloo
Matroids denser than a projective geometry  [PDF]

The unique densest simple rank-$n$ matroid representable over a finite field GF$(q)$ is the projective geometry over GF$(q)$, which has $\frac{q^n-1}{q-1}$ elements. Moreover, a theorem of Kung shows that any denser matroid has a $U_{2,q+2}$-minor , which is a simple certificate of non-GF$(q)$-representability. I will discuss a theorem that shows that much richer minors can be found in every large-rank matroid denser than a projective geometry over GF$(q)$. I will also state many corollaries that bound the growth rate function of most classes obtained by excluding free spikes, free swirls and/or lines as minors.

IRENE PIVOTTO, The University of Western Australia
A first step in decomposing near-regular matroids  [PDF]

The prototypical example of a matroid decomposition theorem is Seymour's result that any regular matroid may be constructed from graphic and cographic matroids and copies of $R_{10}$ via 1-, 2- and 3-sums. Whittle conjectured that a similar decomposition theorem holds for the more general class of near-regular matroids. This conjecture, later amended by Mayhew, Whittle and van Zwam to include 4-sums, is still open. In this talk we present a first step toward resolving this conjecture, namely a decomposition theorem for single element extensions and coextensions of graphic matroids. This is joint work with D. Chun and D. Slilaty.

STEFAN VAN ZWAM, Louisiana State University
Minor-closed classes have no asymptotically good codes  [PDF]

A binary, linear, $[n,r]$ error-correcting code is an $r$-dimensional subspace of $\textrm{GF}(2)^n$. The distance between two codewords is the number of coordinates where they differ, and the minimum distance is denoted by $d_C$. A family of codes is asymptotically good if there exists an $\epsilon>0$ and codes in the family with $r_C/n_C\geq\epsilon$, $d_C/n_C\geq\epsilon$, and $n_C$ arbitrarily large.

We show that structured families are not asymptotically good. In this case, “structured” means that the corresponding matroids form a proper minor-closed class. Our proof is built on the Matroid Structure Theorem by Geelen, Gerards, and Whittle.

Joint work with P. Nelson

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society University of Saskatchewan