Matroid theory studies the abstract notion of independence that underlies linear algebra, graph theory, matching theory, and optimization. A matroid is a finite combinatorial structure in which one can speak of independent sets, bases, rank, circuits, closure, and duality in a way that simultaneously generalizes linearly independent vectors and forests in a graph. This course develops matroids as a language for recognizing when greedy algorithms work, for comparing different notions of dependence, and for moving between combinatorial, algebraic, geometric, and algorithmic viewpoints.

The main themes are abstraction, duality, structure, and optimization. Early chapters introduce the independence axioms and the basic examples, then build the standard toolkit of rank functions, closures, circuits, flats, and greedy bases. The course then turns to dual matroids, deletion and contraction, and minors, which provide the structural operations used throughout the subject. Representability over fields and graphic and cographic matroids connect the abstract theory back to matrices and graphs.

The later chapters broaden the theory toward deeper applications and modern developments. Matroid intersection, union, transversal matroids, gammoids, and matching matroids show how matroids organize major combinatorial optimization problems. Characteristic and Tutte polynomials introduce enumerative invariants, while tropical geometry and valuated matroids connect matroid theory to piecewise-linear geometry. The final chapter surveys log-concavity and modern structure theory, showing how classical matroid ideas continue to shape current research in combinatorics.

# Introduction

Matroid theory begins from a repeated phenomenon: several different parts of mathematics use the word independent, and many of their strongest theorems have the same formal shape. Linear algebra studies independent columns of a matrix, graph theory studies forests inside a graph, and optimization studies when a greedy choice can be made without later regret. The aim of the course is to isolate the shared combinatorial structure behind these examples and then develop the consequences of that abstraction.

This introductory chapter sets the scope of the course before the axioms begin in Chapter 1. It records the guiding examples, the central questions, and the main themes: equivalent axiom systems, duality, minors, representability, and greedy algorithms. The goal is not to prove the main theorems yet, but to explain why the subject has a natural internal logic.

## Independence as a Common Pattern

What does it mean for a collection of objects to have no redundancy? In a [vector space](/page/Vector%20Space), redundancy means that some vector lies in the span of the others. In a graph, redundancy means that adding an edge has created a cycle. In a matching problem, redundancy can mean that too many chosen objects demand the same limited resource.

The first theme of the course is that these examples behave alike under deletion of chosen objects and under an exchange principle. If a set has no redundancy, then any smaller set has no redundancy. If two non-redundant sets have different sizes, then the larger one contains an element that can be added to the smaller one without creating redundancy. These two principles will become the independent-set axioms.

Before stating the formal definition in the next chapter, it is useful to name the kind of structure the course studies.

[definition: Matroid Informal Model] A matroid is a finite combinatorial structure consisting of a ground set $E$ together with a specified collection of subsets of $E$ called independent sets, satisfying hereditary and exchange rules. [/definition]

This is only a preview of the formal definition, but it already indicates the course's point of view. The elements of $E$ might be columns of a matrix, edges of a graph, or members of an abstract finite set. The matroid remembers which subsets are independent and forgets the extra coordinates, embeddings, labels, or drawings that produced those dependencies.

[example: Three Sources of Independence] Let the ground set be the column labels of $A$, the edge set of $G$, or the finite set $E$ in the partitioned example. These give three independence rules: \begin{align*} I \text{ is independent exactly when the columns } \{A_i:i\in I\}\text{ are linearly independent over }k. \end{align*} \begin{align*} F \text{ is independent exactly when } F\text{ contains no cycle in }G. \end{align*} \begin{align*} I \text{ is independent exactly when } |I\cap E_j|\le b_j\text{ for every }j. \end{align*} Each rule is hereditary. For column sets, if $J\subset I$ and \begin{align*} \sum_{j\in J} c_jA_j=0, \end{align*} then extending the coefficients by $c_i=0$ for every $i\in I\setminus J$ gives \begin{align*} \sum_{i\in I} c_iA_i=0. \end{align*} Since the columns indexed by $I$ are linearly independent, every coefficient is zero, so every $c_j=0$. For forests, a cycle contained in $J\subset F$ would also be a cycle contained in $F$. For the partition rule, if $J\subset I$, then for each block $E_\ell$, \begin{align*} |J\cap E_\ell|\le |I\cap E_\ell|\le b_\ell. \end{align*} The same three examples also illustrate exchange. For vectors, if $I$ and $J$ are linearly independent and $|I|<|J|$, then \begin{align*} \dim \operatorname{span}\{A_i:i\in I\}=|I|. \end{align*} Also, \begin{align*} \dim \operatorname{span}\{A_j:j\in J\}=|J|. \end{align*} Since $|I|<|J|$, the span of the columns indexed by $J$ cannot be contained in the span of the columns indexed by $I$. Choose $e\in J$ with $A_e\notin \operatorname{span}\{A_i:i\in I\}$. If a relation \begin{align*} c_eA_e+\sum_{i\in I} c_iA_i=0 \end{align*} had $c_e\ne 0$, then \begin{align*} A_e=-c_e^{-1}\sum_{i\in I} c_iA_i, \end{align*} contradicting $A_e\notin \operatorname{span}\{A_i:i\in I\}$. Hence $c_e=0$, and then [linear independence](/page/Linear%20Independence) of $I$ forces every $c_i=0$, so $I\cup\{e\}$ is independent. For forests, let $F$ and $H$ be forests on the same vertex set $V$ with $|F|<|H|$. A forest on $V$ with edge set $S$ has $|V|-|S|$ connected components, so \begin{align*} |V|-|F|>|V|-|H|. \end{align*} Thus $F$ has more connected components than $H$. If every edge of $H\setminus F$ joined two vertices already connected in $F$, then adding all edges of $H$ could not reduce the number of connected components below that of $F$, contradicting the displayed inequality. Therefore some $e\in H\setminus F$ joins two different components of $F$, and adding such an edge cannot create a cycle. For the partition rule, suppose $I$ and $J$ satisfy all capacity inequalities and $|I|<|J|$. If every block had $|I\cap E_\ell|\ge |J\cap E_\ell|$, then summing over the partition would give $|I|\ge |J|$, a contradiction. Hence some block $E_\ell$ satisfies \begin{align*} |I\cap E_\ell|<|J\cap E_\ell|\le b_\ell. \end{align*} Choose $e\in (J\cap E_\ell)\setminus I$. Then \begin{align*} |(I\cup\{e\})\cap E_\ell|=|I\cap E_\ell|+1\le |J\cap E_\ell|\le b_\ell, \end{align*} and all other block counts are unchanged. Thus in all three settings, removing elements preserves independence, and a larger independent set can donate an element to a smaller one without creating redundancy. [/example]

The example also warns us that matroids are not only disguised vector spaces or disguised graphs. Vector matroids and graphic matroids are motivating families, but partition and transversal matroids show that the language is broader. A recurring question will be which matroids come from linear algebra, which come from graphs, and which are genuinely outside both worlds.

## Bases and Greedy Choice

Why should an abstraction of independence be useful for optimization? The practical reason is that many optimization problems ask for a largest or heaviest independent set. In linear algebra, a basis is a maximal independent set; in a connected graph, a spanning tree is a maximal forest; in a resource allocation problem, a maximal feasible selection uses the available capacities as far as possible.

The course will make this precise by proving that the exchange axiom forces all maximal independent sets to have the same size. These maximal independent sets are the bases of the matroid. Once bases are available, the greedy algorithm becomes the first major bridge between structure and computation.

[definition: Basis Informal Model] A basis of a matroid is a maximal independent subset of its ground set. [/definition]

The word maximal is with respect to inclusion, not necessarily with respect to a numerical weight. This raises the first algorithmic test for the definition: if bases are the right abstraction of maximal non-redundant sets, then choosing the best available element at each step should succeed exactly in the matroidal setting. The next preview theorem states this criterion.

[quotetheorem:6597]