Discrete Math Seminar: Tony Huynh
- Date: 06/26/2012
- Time: 14:30
Simon Fraser University
Intertwining Connectivities in Matroids
Abstract:
An \\emph{intertwine} of two graphs $G$ and $H$ is a graph that has both $G$ and $H$ as a minor and is minor-minimal with this property. In 1979, Lov\\'{a}sz and Unger conjectured that for any two graphs $G$ and $H$, there are only a finite number of intertwines. This now follows from the graph minors project of Robertson and Seymour, although no `elementary' proof is known.
In this talk, we consider intertwining problems for matroids. Bonin proved that there are matroids $M$ and $N$ that have infinitely many intertwines. However, it is conjectured that if $M$ and $N$ are both representable over a fixed finite field, then there are only finitely many intertwines. We prove a weak version of this conjecture where we intertwine `connectivities' instead of minors. No knowledge of matroid theory will be assumed.
This is joint work with Bert Gerards (CWI, Amsterdam) and Stefan van Zwam (Princeton University).
For more information please visit SFU Mathematics Department