Regularity of 1-, 2-, and 3-Sums of Matroids

5 Special Matroids

Definition 64

Let \(A \in \mathbb {Q}^{X \times Y}\) be a matrix. If for all \(j \in Y\), one has that \(a_{i,j} = 0\) for all \(i \in X\), or that there exists \(i_1,i_2 \in X\) such that

\[ a_{i,j} = \begin{cases} 1 & \text{ if $i = i_1$} \\ -1 & \text{ if $i = i_2$} \\ 0 & \text{ otherwise}, \end{cases} \]

then we call \(A\) a node-incidence matrix for a (directed) graph whose nodes are indexed by \(X\) and whose edges are indexed by \(Y\).

Definition 65

We say that a matroid is graphic if it can be represented by a node-incidence matrix.

Definition 66

Let \(S\) be a standard representation given by matrix \(B\). The dual of \(S\) is given by \(-B^\intercal \).

Definition 67

We say a matroid is co-graphic if its dual is graphic.

Definition 68

The matroid with standard representation

\[ \begin{bmatrix} 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ \end{bmatrix} \]

over \(\mathbb {Z}_2\) is called \(R_{10}.\)

Theorem 69

The matroid \(R_{10}\) is regular.

Proof

See Lean implementation.

Theorem 70

Every graphic matroid is regular.

Proof

See Lean implementation.