Dependencies

A complete census of $3$-connected binary matroids on $\le 8$ elements.

Any $\mathrm{\Delta }$-sum or $Y$-sum of two regular matroids is also regular.

$\mathrm{\Delta }Y$ exchanges maintain regularity.

Every $3$-connected binary matroid $M$ with at least $6$ elements has an $M(W_3)$ minor.

Let $\mathcal{M}$ be a class of binary matroids closed under isomorphism and under taking minors. Suppose $N$ given by $B^N$ of (6.3.12) is in $\mathcal{M}$, but the $1$- and $2$-element extensions of $N$ given by (6.3.21), (6.3.22), (6.3.23), and by the accompanying conditions are not in $\mathcal{M}$. Assume matroid $M\in \mathcal{M}$ has an $N$ minor. Then any $k$-separation of any such minor that corresponds to $(X_1\cup Y_1,X_2\cup Y_2)$ of $N$ under one of the isomorphisms induces a $k$-separation of $M$.

Theorem 7.2.1.a specialized to graphs.

Theorem 7.2.1.b specialized to graphs.

Let $G$ be a $3$-connected graph with a $3$-connected proper minor $H$ with at least $6$ edges. Assume $H$ is not a wheel. Then for some $t\ge 1$, there is a sequence of nested $3$-connected minors $G_0,\dots ,G_t=G$ where $G_0$ is isomorphic to $H$, and where each $G_{i+1}$ has exactly one edge beyond those of $G_i$.

Let $G$ be a $3$-connected graph with a $3$-connected proper minor $H$ with at least $6$ edges. Assume $H$ is a wheel. Then for some $t\ge 1$, there is a sequence of nested $3$-connected minors $G_0,\dots ,G_t=G$ where:

• $G_0$ is isomorphic to $H$,

• for some $0\le s\le t$ the subsequence $G_0,\dots ,G_t$ consists of wheels where each $G_{i+1}$ has exactly one additional spoke beyond those of $G_i$,

• in the subsequence $G_s,\dots ,G_t$ each $G_{i+1}$ has exactly one edge beyond those of $G_i$.

Specializes Theorem 7.3.4 to graphs.

todo: add name, label, uses, text

todo: add name, label, uses, text

todo: todo: add definition

todo: todo: add definition

todo: todo: add definition

todo: todo: add definition

todo: todo: add definition

todo: todo: add definition

$M$ is called minimal if it satisfies the following conditions.

• $M$ has an $N$ minor.

• $M$ has no $k$-separation induced by the exact $k$-separation $(F_1,F_2)$ of $N$.

• The matroid $M$ is minimal with respect to the above conditions.

$M$ is called minimal under isomorphism if it satisfies the following conditions.

• $M$ has at least one $N$ minor.

• Some $k$-separation of at least one such minor corresponding to the exact $k$-separation $(F_1,F_2)$ of $N$ under one of the isomorphisms fails to induce a $k$-separation of $M$.

• The matroid $M$ is minimal with respect to the above conditions.

todo: todo: add definition

todo: todo: add definition

todo: todo: add definition

todo: todo: add definition

todo: todo: add definition

todo: todo: add definition

todo: add

todo: todo: add definition

todo: todo: add definition

todo: todo: add definition

todo: add

todo: todo: add definition

Two matroids are isomorphic if they become equal upon a suitable relabeling of the elements.

See text after Proposition 3.3.18.

See text after Proposition 3.3.18.

todo: todo: add definition

todo: todo: add definition

todo: todo: add definition

todo: todo: add definition

todo: todo: add definition

todo: todo: add definition

todo: todo: add definition

todo: todo: add definition

todo: todo: add definition

todo: todo: add definition

todo: todo: add definition

todo: todo: add definition

todo: todo: add definition

A binary matroid $M$ is regular if some binary representation matrix $B$ of $M$ has a totally unimodular signing (i.e., assignment of signs to the $1$s in $B$ that results in a TU matrix).

todo: todo: add definition

Polynomial-time recursive procedure to search for an induced partition. Described on pages 132–133 and again on pages 137–138.

todo: todo: add definition

Let $\mathcal{M}$ be a class of binary matroids closed under isomorphism and under taking minors. Let $N$ be a $3$-connected minor of $\mathcal{M}$ on at least $6$ elements. If every $M\in \mathcal{M}$ with a proper $N$ minor has a $2$-separation, then $N$ is called a splitter of $\mathcal{M}$.

A rational matrix $A$ is totally unimodular if every square submatrix $D$ of $A$ has $\underset{\mathbb{Q}}{det}D=0$ or $\pm 1$.

todo: todo: add definition

todo: todo: add definition

$M(K_5)$ is a splitter of the regular matroids with no $M(K_{3,3})$ minors.

Every $3$-connected binary $1$-element expansion of $M(K_{3,3})$ is nonregular.

Any $1$- or $2$-sum of two regular matroids is also regular.

$M_2$ of (8.3.10) and (8.3.11) is regular iff $M_{2\mathrm{\Delta }}$ of (8.5.3) ($M_2$ converted by a $\mathrm{\Delta }Y$ exchange) is regular.

Any $3$-sum of two regular matroids is also regular.

Let $A$ be a matrix over a field $\mathcal{F}$, with $\mathcal{F}$-rank $A=k$. If both a row submatrix and a column submatrix of $A$ have $\mathcal{F}$-rank equal to $k$, then they intersect in a submatrix of $A$ with the same $\mathcal{F}$-rank. In particular, any $k$ $\mathcal{F}$-independent rows of $A$ and any $k$ $\mathcal{F}$-independent columns of $A$ intersect in a $k\times k$ $\mathcal{F}$-nonsingular submatrix of $A$.

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

Let $M$ be a binary matroid with a minor $\bar{M}$, and let $\bar{B}$ be a representation matrix of $\bar{M}$. Then $M$ has a representation matrix $B$ that displays $\bar{M}$ via $\bar{B}$ and thus makes the minor $\bar{M}$ visible.

Let $M$ be a binary matroid with a representation matrix $B$. Then $M$ is connected iff $B$ is connected.

The following statements are equivalent for a binary matroid $M$ with set $E$ and a representation matrix $B$ of $M$.

• $M$ is $3$-connected.

• $B$ is connected, has no parallel or unit vector rows and columns, and has no partition as in (3.3.17) with $\mathrm{GF}(2)$-rank $D^1=1$, $D^2=0$, and $|X_1\cup Y_1|,|X_2\cup Y_2|\ge 3$.

• Same as (ii), but $|X_1\cup Y_1|,|X_2\cup Y_2|\ge 5$.

Let $M$ be a binary matroid with a binary representation matrix $B$. Suppose the graph $BG(B)$ contains at least one cycle. Then $M$ has an $M(W_2)$ minor.

Let $M$ be a connected binary matroid with at least $4$ elements. Then $M$ has a $2$-separation or an $M(W_3)$ minor.

Let $N$ be a connected minor of a connected binary matroid $M$. Let $z\in M\setminus N$. Then $M$ has a connected minor $N^{\prime }$ that is a $1$-element extension of $N$ by $z$.

Let $N$ be a $3$-connected binary matroid on at least $6$ elements. Suppose a $1$-, $2$-, or $3$-element binary extension of $N$, say $M$, has no loops, coloops, parallel elements, or series elements. Then $M$ is $3$-connected.

Treats the case where $B$ has at least two additional rows or columns beyond those of $B^N$.

Expands case (i) of Lemma 6.3.15.

Expands case (ii) of Lemma 6.3.15.

Additional structural statements for cases (c.1) and (c.2) of Theorem 6.3.18.

Let $M$ be a binary matroid. Assume $M$ to be a $1$-sum of two matroids $M_1$ and $M_2$.

• If $M$ is graphic, then there exist graphs $G$, $G_1$, $G_2$ for $M$, $M_1$, $M_2$, respectively, such that identification of a node of $G_1$ with one of $G_2$ creates $G$.

• If $M_1$ and $M_2$ are graphic (resp. planar), then $M$ is graphic (resp. planar).

Any $2$-separation of a connected binary matroid $M$ produces a $2$-sum with connected components $M_1$ and $M_2$. Conversely, any $2$-sum of two connected binary matroids $M_1$ and $M_2$ is a connected binary matroid $M$.

Let $M$ be a connected binary matroid that is a $2$-sum of $M_1$ and $M_2$, as given via $B$, $B_1$, and $B_2$ of (8.2.3) and (8.2.4).

• If $M$ is graphic, then there exist $2$-connected graphs $G$, $G_1$, and $G_2$ for $M$, $M_1$, and $M_2$, respectively, with the following feature. The graph $G$ is produced when one identifies the edge $x$ of $G_1$ with the edge $y$ of $G_2$, and when subsequently the edge so created is deleted.

• If $M_1$ and $M_2$ are graphic (resp. planar), then $M$ is graphic (resp. planar).

Let $M$ be a $3$-connected binary matroid on a set $E$. Then any $3$-separation $(E_1,E_2)$ of $M$ with $|E_1|,|E_2|\ge 4$ produces a $3$-sum, and vice versa.

Derivation of a graph with $T$ nodes for $F_7$.

Derivation of a graph with $T$ nodes for $M(K_{3,3}{)}^{\ast }$.

Derivation of a graph with $T$ nodes for $R_{10}$.

Derivation of a graph with $T$ nodes for $R_{12}$.

The binary representation matrix $B^{12}$ for $R_{12}$.

Graph plus $T$ set representing $R_{10}$

Graph plus $T$ set representing $F_7$.

Partitioned version of matrix $B$ representing binary matroid $M$. (same as 3.3.3)

If for some $k\ge 1$, $|X_1\cup Y_1|,|X_2\cup Y_2|\ge k$, $\mathrm{GF}(2)$-rank $D^1+\mathrm{GF}(2)$-rank $D^2\le k-1$, then $(X_1\cup Y_1,X_2\cup Y_2)$ is called a (Tutte) $k$-separation of $B$ and $M$. This separation is exact if the rank condition holds with equality. Both $B$ and $M$ are called (Tutte) $k$-separable if they have a $k$-separation. For $k\ge 2$, $B$ and $M$ are (Tutte) $k$-connected if they have no $\ell$-separation for $1\le \ell <k$. When $M$ is $2$-connected, we also say that $M$ is connected.

$\mathrm{\Delta }Y$ exchange, case 1.

$\mathrm{\Delta }Y$ exchange, case 2.

Representation matrices for small wheels (from $M(W_1)$ to $M(W_4)$).

Representation matrix for $M(W_n)$, $n\ge 3$.

Partitioned version of matrix $B^N$ representing a minor $N$ of a binary matroid $M$, where $N$ has an exact $k$-separation for some $k\ge 1$.

Matrix $B$ for $M$ displaying partitioned $B^N$

Matrix $B$ for $M$ with partitioned $B^N$, row $x\in X_3$, and column $y\in Y_3$.

Matrix $B$ for $M$ with partitioned $B^N$, row $x\in X_3$, and column $y\in Y_3$.

Partitioned version of $B^N$: $B^N=\mathrm{diag}(A^1,A^2)$.

Special case where $B$ of a minimal $M$ contains just one row $x$ beyond $B^N$. This proposition gives properties of row subvectors of row $x$ by step $1$ of the separation algorithm.

Special case where $B$ of a minimal $M$ contains just one column $y$ beyond $B^N$. This proposition gives properties of column subvectors of column $y$ by step $1$ of the separation algorithm.

Matrix $B$ for $M$ minimal under isomorphism, case (a).

Matrix $B$ for $M$ minimal under isomorphism, case (b).

Matrix $\bar{B}$ for minor $\bar{M}$ of $M$ minimal under isomorphism.

Theorem 7.3.1 implies Theorem 7.2.1.

Observation in text on pages 160–161.

Matrix of $1$-separation.

Matrix of exact $2$-separation.

Matrices $B^1$ and $B^2$ of $2$-sum.

Matrix $B$ with exact $k$-separation.

The matrix $B$ representing a $3$-sum (after reasoning).

Representation matrices $B^1$ and $B^2$ of the components $M_1$ and $M_2$ of a $3$-sum (after reasoning).

Partition of $B$ displaying $k$-sum.

The (well-chosen) matrix $\bar{B}$ representing the connecting minor $\bar{M}$ of a $3$-sum.

Matrix $B^{2\mathrm{\Delta }}$ for $M_{2\mathrm{\Delta }}$.

Matrix $B^{12}$ of regular matroid $R_{12}$.

A swap of identification of nodes between two subgraphs induced by a $2$-separation of a graph. See description and illustration on page 45.

If a regular matroid has no $M(K_5)$, $M(K_5{)}^{\ast }$, $M(K_{3,3})$, or $M(K_{3,3}{)}^{\ast }$ minors, then it is planar.

If a regular matroid is planar, then it has no $M(K_5)$, $M(K_5{)}^{\ast }$, $M(K_{3,3})$, or $M(K_{3,3}{)}^{\ast }$ minors.

Let $M$ be a $3$-connected regular matroid with an $M(K_{3,3})$ minor. Assume that $M$ is not graphic and not cographic, but that each proper minor of $M$ is graphic or cographic. Then $M$ is isomorphic to $R_{10}$ or $R_{12}$.

If a $3$-connected regular matroid has no $R_{10}$ or $R_{12}$ minors, then it is graphic or cographic.

If $3$-connected regular matroid is graphic or cographic, then it has no $R_{10}$ or $R_{12}$ minors.

Any $1$-, $2$-, or $3$-sum of two regular matroids is regular.

In short: Restatement of 83 for $R_{12}$. Replacements: $\mathcal{M}$ is the class of regular matroids, $N$ is $R_{12}$, (6.3.12) is (11.3.6), (6.3.21-23) are (11.3.7-9).

Let $M$ be a regular matroid with $R_{12}$ minor. Then any $3$-separation of that minor corresponding to the $3$-separation $(X_1\cup Y_1,X_2\cup Y_2)$ of $R_{12}$ (see (11.3.11) – matrix $B^{12}$ for $R_{12}$ defining the $3$-separation) under one of the isomorphisms induces a $3$-separation of $M$.

In short: every regular matroid with $R_{12}$ minor is a $3$-sum of two proper minors.

Every binary matroid produced from graphic, cographic, and matroids isomorphic to $R_{10}$ by repeated $1$-, $2$-, and $3$-sum compositions is regular.

Every regular matroid $M$ can be decomposed into graphic and cographic matroids and matroids isomorphic to $R_{10}$ by repeated $1$-, $2$-, and $3$- sum decompositions. Specifically: If $M$ is a regular $3$-connected matroid that is not graphic and not cographic, then $M$ is isomorphic to $R_{10}$ or has an $R_{12}$ minor. In the latter case, any $3$-separation of that minor corresponding to the 3-separation $(X_1\cup Y_1,X_2\cup Y_2)$ of $R_{12}$ ((11.3.11)) under one of the isomorphisms induces a $3$-separation of $M$.

$R_{10}$ is a splitter of the class of regular matroids.

In short: up to isomorphism, the only $3$-connected regular matroid with $R_{10}$ minor is $R_{10}$.

Let $M$ be the graphic matroid of a connected graph $G$. Assume $(E_1,E_2)$ is a $k$-separation of $M$ with minimal $k\ge 1$. Define $G_1$ (resp. $G_2$) from $G$ by removing the edges of $E_2$ (resp. $E_1$) from $G$. Let $R_1,\dots ,R_g$ be the connected components of $G_1$, and $S_1,\dots ,S_h$ be those of $G_2$.

If $k$ = 1, then the $R_i$ and $S_j$ are connected in tree fashion.

Same setting as Theorem 3.2.25.a. If $k$ = 2, then the $R_i$ and $S_j$ are connected in cycle fashion.

Structural description of representation matrix (6.3.11) of a minimal $M$. Contains cases (a), (b), and (c) with sub-cases (c.1) and (c.2).

Let $M$ be minimal under isomorphism. Then one of $3$ cases holds for matrix representation of $M$.

Let $M$ be a $3$-connected binary matroid with a $3$-connected proper minor $N$. Suppose $N$ has at least $6$ elements. Then $M$ has a $3$-connected minor $N^{\prime }$ that is a $1$- or $2$-element extension of some $N$ minor of $M$. In the $2$-element case, $N^{\prime }$ is derived from the $N$ minor by one addition and one expansion.

Let $\mathcal{M}$ be a class of binary matroids closed under isomorphism and under taking minors. Let $N$ be a $3$-connected minor of $\mathcal{M}$ on at least $6$ elements. If $N$ is not a wheel, then $N$ is a splitter of $\mathcal{M}$ iff $\mathcal{M}$ does not contain a $3$-connected $1$-element extension of $N$.

Let $\mathcal{M}$ be a class of binary matroids closed under isomorphism and under taking minors. Let $N$ be a $3$-connected minor of $\mathcal{M}$ on at least $6$ elements. If $N$ is a wheel, then $N$ is a splitter of $\mathcal{M}$ iff $\mathcal{M}$ does not contain a $3$-connected $1$-element extension of $N$ and does not contain the next larger wheel.

$K_5$ is a splitter of the graphs without $K_{3,3}$ minors.

$W_3$ is a splitter of the graphs without $W_4$ minors.

Let $M$ be a $3$-connected binary matroid with a $3$-connected proper minor $N$ on at least $6$ elements. Assume $N$ is not a wheel. Then for some $t\ge 1$, there is a sequence $M_0,\dots ,M_t=M$ of nested $3$-connected minors where $M_0$ is isomorphic to $N$ and where the gap is $1$.

Let $M$ be a $3$-connected binary matroid with a $3$-connected proper minor $N$ on at least $6$ elements. Assume $N$ is a wheel. Then for some $t\ge 1$, there is a sequence $M_0,\dots ,M_t=M$ of nested $3$-connected minors where:

• $M_0$ is isomorphic to $N$,

• for some $0\le s\le t$ the subsequence $M_0,\dots ,M_s$ consists of wheels and has gap 2,

• the subsequence $M_s,\dots ,M_t$ has gap $1$.

Let $G$ be a $3$-connected graph on at least $6$ edges. If $G$ is not a wheel, then $G$ has some edge $z$ such that at least one of the minors $G/z$ and $G\setminus z$ is $3$-connected.

Theorem 7.3.3 can be rewritten for binary matroids instead of graphs.

Let $M$ be a $3$-connected binary matroid with a $3$-connected proper minor $N$ on at least $6$ elements. If $M$ does not contain a $3$-connected $1$-element expansion (resp. addition) of any $N$ minor, then $M$ has a sequence of nested $3$-connected minors $M_0,\dots ,M_t=M$ where $M_0$ is an $N$ minor of $M$ and where each $M_{i+1}$ is obtained from $M_i$ by expansions (resp. additions) involving some series (resp. parallel) elements, possibly none, followed by a $1$-element addition (resp. expansion).

A graph is planar if and only if it has no $K_{3,3}$ or $K_5$ minors.

A graph is planar if and only if it has no subdivision of $K_{3,3}$ or $K_5$.

A connected graph $G$ is vertex $k$-connected if and only if every two nodes are connected by $k$ internally node-disjoint paths. Equivalent is the following statement. $G$ is vertex $k$-connected if and only if any $m\le k$ nodes are joined to any $n\le k$ nodes by $k$ internally node-disjoint paths. One may demand that the $m$ nodes are disjoint from the $n$ nodes, but need not do so. Also, the $k$ paths can be so chosen that each of the specified nodes is an endpoint of at least one of the paths.