Seminar - Ahmad Abdi

Packing T-Joins, Colouring Problems, and Matching Theory

Abstract:

This is the first and introductory talk of the Graph Theory Seminar Series. In this talk, I will try to motivate and give an introduction to different areas of graph theory. We will start with a seemingly simple, yet notoriously difficult, problem stated as follows: given a graph and an even vertex subset T, how many pairwise edge disjoint T-joins can one find? Here, a T-join is a subgraph whose odd degree vertices are T.

To study this problem, we will take a stroll along the different areas of mathematics. These areas include graph minors, colouring problems on graphs, matching theory, as well as polyhedral theory. In particular, we will discuss the four colour theorem and its extensions, Edmonds' matching polytope, as well as Lovasz's spectacular result on the so-called matching lattice of a graph.