Matriod Theory

Matriod Theory

-
Melody Chan, Princeton University
Fine Hall 214

Every maximal acyclic subgraph of a given graph has the same number of edges. Every maximal independent subset of a given set of vectors in $\mathbb{R}^n$ has the same size. The common generalization of these lies in matroid theory, which, roughly speaking, is an abstraction of the notion of linear independence. Despite the fact that matroids "forget" quite a lot of structure, they are immensely useful to graph theorists. In this talk, I'll give an introduction to the theory of matroids and point to some of its highlights, keeping graph theory in mind as our primary motivation and source of examples.