graph-theory
这是 拟阵笔记 的一章。 上一篇是 回路，下一篇是 秩与闭包。
Duality
The viewpoints $\mathcal{I}$, $\mathcal{B}$, $\mathcal{C}$ are not isolated; they complement one another. Duality is the first illustration.
### The dual matroid
Theorem（Dual matroid）. Let $M=(E,\mathcal{B})$ be a matroid. Set \[ \mathcal{B}^{\ast}=\{E\setminus B:\ B\in\mathcal{B}\}. \] Then $M^{\ast}=(E,\mathcal{B}^{\ast})$ is a matroid, the dual of $M$.
Example. For the running example $\mathcal{B}=\{abc,abd,abe,acd,ace\}$ one has \[ \mathcal{B}^{\ast}=\{def, cef, cdf, bef, bdf\}. \] In the graphic picture, $M^{\ast}$ is the matroid of the “dual” drawing in which the loop $f$ becomes an isthmus and the parallel pair $\{d,e\}$ becomes a series pair. (In general the dual of a graphic matroid need not be graphic; it is planar-graphic precisely when $G$ is planar.)
The proof proceeds as: a lemma on circuits, a lemma on bases, then the theorem.
Lemma（Fundamental circuit）. If $I$ is independent and $I\cup\{e\}$ is dependent, then $I\cup\{e\}$ contains a unique circuit, and that circuit contains $e$. It is denoted $C(e,I)$ and called the fundamental circuit of $e$ with respect to $I$.
*Proof.* The set $I\cup\{e\}$ is dependent, so it contains some circuit $C$; $C\not\subseteq I$, hence $e\in C$. If $C'$ were another circuit in $I\cup\{e\}$ through $e$, then (C3) would produce a circuit contained in $(C\cup C')\setminus\{e\}\subseteq I$, contradicting independence of $I$.
Lemma（Symmetric exchange）. (B2$^{\ast}$). If $A,B\in\mathcal{B}$ and $b\in B\setminus A$, then there exists $a\in A\setminus B$ such that $(A\setminus\{a\})\cup\{b\}\in\mathcal{B}$.
*Proof.* $A$ is independent and $A\cup\{b\}$ is dependent (else $A$ was not a basis), so $C=C(b,A)$ exists. The only circuit in $A\cup\{b\}$ is $C$, so $(A\setminus\{a\})\cup\{b\}$ is independent — hence a basis — if and only if $a\in C$ and $a\neq b$. We need such an $a$ in $A\setminus B$. Since $B$ is independent and $C$ is dependent, $C\not\subseteq B$, so there is $a\in C\setminus B\subseteq A\setminus B$.
*Proof.* We check that $\mathcal{B}^{\ast}$ satisfies (B1)–(B2). Nonemptiness is immediate. For exchange, let $A^{\ast},B^{\ast}\in\mathcal{B}^{\ast}$ and $a\in A^{\ast}\setminus B^{\ast}$. Writing $A^{\ast}=E\setminus A$ and $B^{\ast}=E\setminus B$ we have $A,B\in\mathcal{B}$ and $a\in B\setminus A$. supplies $b\in A\setminus B$ with $(A\setminus\{b\})\cup\{a\}\in\mathcal{B}$, which rearranges to $(A^{\ast}\setminus\{a\})\cup\{b\}\in\mathcal{B}^{\ast}$.
Remark. Thus $(E,\mathcal{B})$ is a matroid if and only if $\mathcal{B}$ satisfies (B1) and (B2$^{\ast}$). Indeed, $M$ is a matroid if and only if $M^{\ast}$ is, and basis exchange for $M^{\ast}$ is symmetric exchange for $M$. See Oxley, Corollary 2.1.5.
### Linear duality
Let $V\subseteq \mathbb{F}^n$ be a $k$-dimensional subspace, with the standard coordinates. If the rows of a $k\times n$ matrix $A$ span $V$, then the column matroid of $A$ depends only on $V$; write it $M(V)$.
Proposition. The bases of $M(V)$ are the $k$-subsets $S\subseteq E=\{1,\ldots,n\}$ for which $V\cap X_{E\setminus S}=\{0\}$, where $X_A=\{x\in\mathbb{F}^n: x_i=0\text{ for all }i\notin A\}$ is the coordinate subspace on $A$.
*Proof.* The set $S$ is a basis of the column matroid if and only if the corresponding $k$ columns have rank $k$, if and only if the projection $\pi_S\colon \mathbb{F}^n\to X_S$ restricts to an injection on $V$. That happens if and only if $V\cap\ker\pi_S=\{0\}$. But $\ker\pi_S=X_{E\setminus S}$.
Theorem（Orthogonal complements are duals）. If $M$ is the matroid of a subspace $V\subseteq\mathbb{F}^n$, then $M^{\ast}$ is the matroid of the orthogonal complement $V^{\perp}$. In particular, the dual of a linear matroid is linear.
*Proof.* We use the identity $(U+W)^{\perp}=U^{\perp}\cap W^{\perp}$, whose proof is: $x\perp U+W$ if and only if $x\perp U$ and $x\perp W$. A set $S$ is a basis of $M(V^{\perp})$ if and only if $V^{\perp}\cap X_{E\setminus S}=\{0\}$, if and only if $V^{\perp}\cap X_S^{\perp}=\{0\}$ (since $X_{E\setminus S}=(X_S)^{\perp}$), if and only if $(V+X_S)^{\perp}=\{0\}$, if and only if $V+X_S=\mathbb{F}^n$, if and only if $V\cap X_S=\{0\}$, if and only if $E\setminus S$ is a basis of $M(V)$, if and only if $S$ is a basis of $M(V)^{\ast}$.
Remark. A generic $k$-plane meets a generic $(n-k)$-plane trivially, so a generic $k$-plane $V$ has every $k$-set as a basis: this is the uniform matroid $U_{k,n}$. The matroid $M(V)$ records how special $V$ is with respect to the coordinate subspaces.
### Graphic duality
Think of vertices as points and edges as continuous curves.
Definition. A graph is planar if it can be drawn in the plane with no two edges meeting except at a common endpoint. A plane graph is a graph already so drawn. The drawing divides the plane into regions, the faces.
Definition（Dual plane graph）. The dual $G^{\ast}$ of a plane graph $G$ is obtained by placing a vertex $f^{\ast}$ in each face $f$ of $G$, and, for each edge $e$ of $G$ incident to faces $f$ and $g$, drawing an edge $e^{\ast}$ from $f^{\ast}$ to $g^{\ast}$ that crosses $e$ and no other edge of $G$.
Observation. If $G$ is connected then $(G^{\ast})^{\ast}\cong G$.
Loops in $G$ become isthmuses in $G^{\ast}$ and conversely; a cycle in $G$ becomes a cut in $G^{\ast}$.
Example. A typical plane graph and its dual (the correspondence is $V\leftrightarrow F^{\ast}$, $E\leftrightarrow E^{\ast}$, $F\leftrightarrow V^{\ast}$):
Theorem. If $G$ is a connected plane graph and $G^{\ast}$ is its dual, then $M(G^{\ast})=M(G)^{\ast}$.
*Proof.* It is enough to show that $T\subseteq E$ is a spanning tree of $G$ if and only if $E\setminus T$ (viewed as edges of $G^{\ast}$) is a spanning tree of $G^{\ast}$. By duality it suffices to prove one implication and apply it to $G^{\ast}$.
Suppose $T$ is a spanning tree of $G$, and write $T^{\ast}=E\setminus T$ as a set of edges of $G^{\ast}$.
If $T^{\ast}$ were disconnected, two vertices $f^{\ast},g^{\ast}$ of $G^{\ast}$ would lie in different components of $(V(G^{\ast}),T^{\ast})$. The corresponding faces $f,g$ of $G$ would then be separated by a cut made of edges of $T$, forcing a cycle in $T$, a contradiction.
If $T^{\ast}$ contained a cycle $C^{\ast}$, take a vertex $v$ of $G$ inside $C^{\ast}$ and a vertex $w$ outside it. Any $v$–$w$ path in $G$ must cross $C^{\ast}$, hence use an edge of $T^{\ast}$, i.e.\ an edge not in $T$. Thus $v$ and $w$ are disconnected in $T$, contradicting that $T$ is spanning.
Corollary（Euler's formula）. For a connected plane graph, $\lvert V\rvert-\lvert E\rvert+\lvert F\rvert=2$.
*Proof.* A spanning tree $T$ of $G$ has $\lvert V\rvert-1$ edges. The complementary spanning tree $T^{\ast}$ of $G^{\ast}$ has $\lvert F\rvert-1$ edges (including the unbounded face). But $T^{\ast}=E\setminus T$, so \[ \lvert F\rvert-1=\lvert E\rvert-(\lvert V\rvert-1), \] which rearranges to Euler's formula.
Observation. Different plane embeddings of the same abstract graph may produce non-isomorphic dual graphs $G_1^{\ast}\not\cong G_2^{\ast}$. Nevertheless $M(G_1^{\ast})=M(G_2^{\ast})=M(G)^{\ast}$.
($G_1^{\ast}$ has a vertex of degree $6$; $G_2^{\ast}$ does not.) Natural projects: (i) how are the various duals of $G$ related? (ii) when is $M(G)\cong M(H)$?
> *Supplement.* Duality is an involution: $(M^{\ast})^{\ast}=M$, because taking > complements twice recovers every basis. The dual rank formula > \[ > r_{M^{\ast}}(X)=\lvert X\rvert-r(M)+r(E\setminus X) > \] > is recorded with a proof in the minors chapter; it is the numerical > content of “bases of $M^{\ast}$ are complements of bases of $M$”. > Loops of $M$ are coloops of $M^{\ast}$, and circuits of $M$ are > cocircuits of $M^{\ast}$. > > Whitney's planarity criterion is the global form of > : an abstract graph $G$ is planar if and only if > $M(G)^{\ast}$ is graphic. Combined with Tutte's excluded-minor theorem > for graphic matroids, this recovers Kuratowski–Wagner ($K_5$ and > $K_{3,3}$) as the statement that $M(K_5)^{\ast}$ and $M(K_{3,3})^{\ast}$ > are the extra forbidden minors beyond $U_{2,4}$, $F_7$, and $F_7^{\ast}$.
### Transversal duality
Definition（Routing）. Let $G$ be a directed graph and $X,Y\subseteq V(G)$ with $\lvert X\rvert=\lvert Y\rvert=r$. A routing from $X$ to $Y$ is a set of $r$ directed paths, vertex-disjoint, starting in $X$ and ending in $Y$. (A path may be a single vertex.)
Theorem（Mason, 1972）. Let $G=(V,E)$ be a digraph and $B_0\subseteq V$. The collection \[ L(G,B_0)=\{X\subseteq V:\ \text{there is a routing from $X$ to $B_0$}\} \] is the set of bases of a matroid on $V$. Such matroids are called cotransversal (or strict gammoids).
> *Filled in.* The board notes state Mason's theorem without a proof. Independence of a > set $X$ can be read as the existence of $\lvert X\rvert$ vertex-disjoint directed > paths from $X$ into $B_0$; the augmentation axiom is then Menger's theorem > in the digraph obtained by attaching a source to $X$ and a sink to $B_0$.
Theorem（Ingleton–Piff, 1973）. Cotransversal matroids are precisely the duals of transversal matroids.
> *Filled in.* The notes defer this to Homework 3. A later sketch (Ardila, 2006) runs: > transversal matroids are linear, represented by row-spaces $V\subseteq\mathbb{R}^n$; > cotransversal matroids are linear, represented by subspaces $W\subseteq\mathbb{R}^n$; > and the subspaces arising in the two constructions are orthogonal > complements. Combined with this yields Ingleton–Piff.