CanaDAM 2017
Université Ryerson, 12 - 16 juin 2017

Matroids, Minors and Immersions

RUTGER CAMPBELL, University of Waterloo
On excluded minors for real representability  [PDF]

We show that any real representable matroid is the minor of an excluded-minor (for real-representability) that is complex-representable.

STEFAN HANNIE, Simon Fraser University
Immersion of 2-regular digraphs  [PDF]

This talk revolves around 2-regular digraphs (digraphs where every vertex has in-degree and out-degree 2). We will show that, for the class of 2-regular digraphs, immersion acts as a natural minor-like containment relation, and that a natural surface embedding is one where the edges incident with each vertex alternate in-out-in-out. It is thought that for a fixed surface the embeddable 2-regular digraphs are characterized by a finite list of immersion minimal obstructions. Johnson characterized the immersion minimal obstructions for the plane and we do the same for the projective plane. Using the projective plane obstructions, we are able to prove an analogue of a conjecture by Negami stating that a 2-regular digraph has a finite planar cover if and only if it is projective planar. Partial work towards classifying the obstructions for the torus and Klein bottle will also be presented.

ANNA LUBIW, University of Waterloo
Reconfiguring Ordered Bases of a Matroid  [PDF]

For a matroid with an ordered (or ``labelled'') basis, a basis exchange step removes one element with label $l$ and replaces it by a new element that results in a new basis, and with the new element assigned label $l$. We prove that one labelled basis can be reconfigured to another if and only if for every label, the initial and final elements with that label lie in the same connected component of the matroid. Furthermore, we prove that when the reconfiguration is possible, the number of basis exchange steps required is $O(r^{1.5})$ for a rank $r$ matroid. For a graphic matroid we improve the bound to $O(r \log r)$.

Joint work with Vinayak Pathak.

Splitter Theorems for Graph Immersions  [PDF]

Splitter theorems are powerful tools in the theory of graph minors. Generally speaking, they say that given two graphs $G, H$ with some specific property with $G\succ_{minor}H$, there is a way to move from $G$ to $H$ while maintaining the same specific property. Such a result exists, for instance, for $3$-connected graphs.

Turning towards graph immersions, in this talk we will present a splitter theorem for $k$-edge-connected graphs, for any even $k$, i.e. we see that if $G\succ_{im}H$, and both $G,H$ are $k$-edge-connected, there is a $k$-edge-connected graph $G_0\succ_{im}H$, that can be obtained from $G$ by deleting a single edge or splitting off a single pair of edges. We will also present our theorem for the family of $3$-edge-connected, and internally $4$-edge-connected graphs and derive as a corollary that if $G$ is in this family and $G\succ_{im}K_5$ with $|V(G)|\ge6$, then $G\succ_{im}K_{3,3}$ unless $G$ is isomorphic to octahedron.

RAN ZIV, Tel-Hai College
Fair Representation in the Intersection of Two Matroids  [PDF]

For a matroid $\mathcal M$ denote by $\beta({\mathcal M})$ the minimal number of edges from $\mathcal M$ needed to cover the ground set. We conjecture that the following is true for the intersection of two matroids: if $\mathcal D=\mathcal P \cap \mathcal Q$, where $\mathcal P,\mathcal Q$ are matroids on the same ground set $V$ and $\beta(\mathcal P), \beta(\mathcal Q) \le k$, then for every partition $A_1, \ldots, A_m$ of $V$ there exists a set $S \in \mathcal D$ meeting each $A_i$ in at least $\frac{1}{k}|A_i|-1$ elements. We verify the $m=2$ case for strong base orderable matroids. For general matroids we prove a weaker version: there is a set meeting each $A_i,\;i=1,2$, in at least $(\frac{1}{k}-\frac{1}{|V|})|A_i|-1$ elements. Joint work with Ron Aharoni, Eli Berger and Daniel Kotlar.


Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathmatiques The Fields Institute Pacific Institute for the Mathematical Sciences Socit mathmatique du Canada Université Ryerson Office of Naval Research Science and Technology