graph-theory
Three pictures of independence
The same combinatorial pattern appears in linear algebra, graph theory, and matching theory. Throughout these notes we keep a single six-element running example that realises all three pictures at once.
Example（Linear algebra）. Let $E=\{a,b,c,d,e,f\}$ be the list of vectors in $\mathbb{R}^3$ \[ a=(1,0,0), b=(0,1,0), c=(0,0,1), d=(0,\tfrac12,\tfrac12), e=(0,1,1), f=(0,0,0). \] Goal: choose a linearly independent subset of $E$.
Example（Graph theory）. Let $G$ be the graph on ground set $E=\{a,b,c,d,e,f\}$ drawn below ($f$ is a loop, $d$ and $e$ are parallel, and $a$ is a pendant edge). Goal: choose a set of edges containing no cycle.
Example（Matching theory）. Let $G$ be the bipartite graph with left vertices $\{1,2,3\}$ and right vertices $\{a,b,c,d,e,f\}$, with neighbourhoods \[ N(1)=\{a\}, N(2)=\{a,b,c\}, N(3)=\{a,b,c,d,e\}. \] (The isolated vertex $f$ is unmatched; the original notes add a joke which we omit.) Goal: choose a set of right-hand vertices that can be matched to distinct left-hand vertices.
### What is special about the elements?
Comparing the three models on the same ground set:
1. One element is unlike the others: $f$ is useless. It is the zero vector, a loop, and an unmatched vertex. One can never choose it. 2. Another element is unlike the others: $a$ is essential. It is the only vector with a nonzero first coordinate, a bridge (isthmus) in the graph, and the unique neighbour of vertex $1$. One should always choose it when building a maximal independent set. 3. Two further elements are unlike the others: $d$ and $e$ are twins (parallel). In the vector picture $e=2d$; in the graph they are parallel edges; in the matching they are interchangeable. One may choose at most one of them.
Matroid theory is the axiomatic study of this notion of independence. The three examples will turn out to be the same matroid.
> *Supplement.* Whitney introduced matroids in 1935 to isolate the combinatorial content > of linear dependence, and noticed at once that graphs supply a second > model. The later matching and algebraic models sit on the same axioms. > The word “matroid” is meant to sound like “matrix”: a matroid is what > remains of a matrix after one forgets the field and remembers only which > columns are independent.