What Is... Seminar

Ed SwartzCornell University
What is the dual of a nonplanar graph?

Wednesday, February 5, 2020 - 5:30pm
Malott 207

Let G be a graph embedded in the plane. The geometric dual of G, denoted G*, has as its vertices the connected components of the complement of the graph. Each edge e of G corresponds to an edge e* in G* incident to the two regions that the edge borders. For instance, if G is a hexagon, then G* has two vertices to represent the two connected components of the plane in the complement of G. Since all 6 of the edges of the hexagon border both of these regions, G* consists of two vertices and 6 distinct edges between the two vertices.

In 1935 Hassler Whitney answered the question “What is the dual of a nonplanar graph?" by introducing matroids, a combinatorial abstraction of linear independence. We will start by explaining what a matroid is and why it is a reasonable answer to the question. Then we will try to get a sense of the remarkable number of directions research involving matroids has taken in the last 80+ years.