Discrete Math Seminar: Tony Huynh

  • Date: 06/26/2012
  • Time: 14:30
Lecturer(s):
Tony Huynh (KAIST)
Location: 

Simon Fraser University

Topic: 

Intertwining Connectivities in Matroids

Description: 

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

Other Information: 

For more information please visit SFU Mathematics Department

Sponsor: