Matroid Theory II

Different Kinds of Matroids

Affine Matroids

Describing matroids by writing out each independent set can quickly get lengthy and unintuitive. Here we introduce a geometric way to describe matroids:

Definition of a affine matroid. Suppose that $V$ is a vector space of dimension $m$ over field $\mathbb{F}$. Suppose that $E$ is a sub-multiset of $V$. Define $\mathcal{I}$ to be the set of affinely-independent multisets, i.e. multisets $\{v_1,\cdots ,v_i\}$ such that there are $a_1,\cdots ,a_i\in \mathbb{F}$ with $\sum a_j=0$, $\sum a_j{v}_j=0$. Then $(E,\mathcal{I})$ is a matroid, and is called _affine over $\mathbb{F}$.

If a matroid $M$ is isomorphic to a affine matroid over $\mathbb{R}$, then we can actually draw it in Euclidean space. Often we can draw it in ${\mathbb{R}}^3$, with lines and planes depicting dependent sets, and any set of more than $3$ points are dependent. (Therefore only matroids of rank less than $3$ can be drawn in this way.) Loops are commonly drawn by nodes next to each other. Deletion of an element is simple by deleting the node associated with the element, the $3$-point lines passing through it, and $4$-point planes passing through it.

Duality

Dual of Graphic Matroid

A matroid $M(G)=(E,\mathcal{I})$ can be generated from a graph $G$, as follows: $E=E(G)$ and $\mathcal{I}$ contains all subsets of $E$ that spans an acyclic subgraph of $G$. If a matroid is isomorphic to some $M(G)$, call it graphic.

Theorem. If a matroid is graphic, then it is the matroid of some connected graph.

If a matroid is isomorphic to the dual of some $M(G)$, call it cographic. In order to relate the duality of matroids and graphs, we seek the condition for a cographic matroid to be also graphic. Obviously we hope that every cographic matroid is graphic. Unfortunately, that is not the case.

Proposition. $M(K_5{)}^{\ast }$ and $M(K_{3,3}{)}^{\ast }$ are not graphic.

Here we shall prove the statement for $K_5$ and the case for $K_{3,3}$ is similar.

Proof. Let $M=M(K_5{)}^{\ast }$ and suppose $M=M(G)$ for some graph $G$. We may assume that $G$ is connected. Now because $M(K_5)$ has $10$ elements and its maximal independent set has cardinality $4$ (i.e. has rank $4$), $M$ also has $10$ elements, and has rank $6$. Thus, $G$ has $7$ vertices and $10$ edges, which implies that $G$ has a vertex of degree at most two; that means $K_5$ has a cycle of length at most two, contradiction.

This result is strongly reminiscent of a classic result of Kuratowski:

Theorem of Kuratowski on planar graphs. A graph is planar if and only if it has a $K_5$ or $K_{3,3}$ minor.

We might come back to this later when we discuss minors.

Dual of Representable Matroid

Recall that we said matroids somewhat unifies graphs and vector spaces, by defining a general notion of independency. Naturally we can define a matroid $M[\mathbf{A}]=(E,\mathcal{I})$ from any matrix $\mathbf{A}$ over a field $F$: let $E$ be the column labels of $\mathbf{A}$, and $\mathcal{I}$ be the set of linearly independent sets.

If a matroid is isomorphic to some $M[\mathbf{A}]$, call it representable. Notice here that a representable matroid does not in general determine its underlying matrix. Actually one can verify that the matroid doesn't change under the following actions on the matrix:

1. Elementary row changes (in the common sense of a matrix).
2. Delete a zero row.
3. Replace every element with its image under a automorphism of $F$.

We will call all these three actions elementary row changes from now on. It's clear that any matrix can be reduced to the form $({\mathbf{I}}_r|\mathbf{D})$ under elementary row changes. $({\mathbf{I}}_r|\mathbf{D})$ is called a standard representative matrix for $M$.

We see the expected result that duality of representable matroids is actually the duality of orthogonality.

Theorem. If $M=M[{\mathbf{I}}_r|\mathbf{D}]$ where $\mathbf{D}$ is a $r\times (n-r)$ matrix over a field $F$, then $M^{\ast }=M[-{\mathbf{D}}^{\mathrm{\top }}|{\mathbf{I}}_{n-r}]$.

To see how this is related to orthogonality we need the following proposition. Denote the row space of $\mathbf{A}$ by $\mathcal{R}(A)$.

Proposition. The orthogonal subspace of $\mathcal{R}({\mathbf{I}}_r|\mathbf{D})$ is exactly $\mathcal{R}(-{\mathbf{D}}^{\mathrm{\top }}|{\mathbf{I}}_{n-r})$.

Contraction and Minors

An important topic in graph theory is the notion of a minor, formed by an action called contraction. By retracting an edge $e$, we "glue" the to end vertices of $e$ together to a new vertex. The new graph is denoted by $G/e$. We would like to generalize this to matroids.

Consider a planar graph $G$. What happens when we retract an edge, $e$? The direct impact is: $e$ disappears from $G^{\ast }$, its dual graph.

Definition of a contraction. For a matroid $M=(E,\mathcal{I})$ and $e\in E$, define the contraction $M/e$ as $(M^{\ast }\setminus e{)}^{\ast }$.

Drawing Contractions

We can visualize matroids by two ways, one by graphs, one by geometries. Contraction in graphic matroids is the same as contraction in graphs. What's more interesting is the case of geometries, which involves a procedure of projection.

We take the ${\mathbb{R}}^3$ case as an example. First, place your eye at the node to be contracted. Second, construct a plane (which will be projected to), such that every line or plane through the node intersects the plane. Finally, project all points, lines and planes to the plane constructed.

Notice how this shows that contraction reduces rank.

Minors

Proposition-Definition. For disjoint subsets $X$, $Y$ of $E$, $M/X\mathrm{\setminus }Y=M\mathrm{\setminus }Y/X$. Matroids of this form are called minors of $M$.

Minors of graphic matroids are graphic; minors of $\mathbb{F}$-representable matroids are $\mathbb{F}$-representable.