Discrete Math Seminar: Tony Huynh

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).