Special Events and Conferences

Tutorials Lecturer: Anastasia Chavez, in collaboration with Andrés Vindas-Melendez

Tutorial Lecture: An introduction to matroid theory

Abstract:

Let us first begin with a thought experiment. Consider four dots on a page and draw lines connecting every pair of dots only once. We call this the complete graph on four vertices (i.e. dots) which has six edges (i.e., lines connecting dots). Now I ask: what are the sets of edges that we can make such that every vertex is contained in an edge and no closed path is formed? Staring at that data, now I ask a strange question: what if we forget the graph … what does this data really mean? It is this line of exploration that leads one to discover the exciting theory of matroids.

Independently introduced by Whitney and Nakasawa in the 1930’s, matroids are a fundamental combinatorial object that miraculously links together many areas of mathematics: graph theory, linear algebra, abstract algebra, and many more! This means that results about matroids can have far reaching implications. And, results from many areas of mathematics may be able to be translated into matroid language, then applied in other fields. The connections seem limitless. Indeed, Gian-Carlo Rota, one of the lead researchers in matroid theory, wrote about the potential of matroids to unify all of mathematics.

In these tutorials, we will begin by exploring the humble graphical beginnings of matroids and build towards a linear algebraic definition. This will eventually lead to several equivalent definitions of matroids that become a springboard to many other areas. We will get to know important matroids and their properties, apply matroid operations inspired by graphs, and see their geometric interpretations as polytopes – a higher dimensional version of the polygon. Our goal is to have you leave with a set of mathematical tools that will allow you to begin finding matroids everywhere you go.