graph-theory
这是 拟阵笔记 的一章。 上一篇是 独立的三种图像，下一篇是 基。
Independent sets
### The running example
Example（Independent sets of vectors）. For the configuration of , the independent sets are \[ \begin{aligned} &\varnothing,\\ &\{a\},\{b\},\{c\},\{d\},\{e\},\\ &\{a,b\},\{a,c\},\{a,d\},\{a,e\},\{b,c\},\{b,d\},\{b,e\},\{c,d\},\{c,e\},\\ &\{a,b,c\},\{a,b,d\},\{a,b,e\},\{a,c,d\},\{a,c,e\}. \end{aligned} \] In particular $f$ appears in none of them, and $\{d,e\}$ is missing.
Exercise. Check that the acyclic edge-sets of and the matchable subsets of are exactly the same collection.
> *Filled in.* Write $M(G)$ for the cycle matroid of the graph in . > The unique loop is $f$. The unique $2$-circuit is $\{d,e\}$. The $3$-circuits > are $\{b,c,d\}$ and $\{b,c,e\}$. An edge-set is acyclic if and only if it > contains none of these, which is the list above. > > In the matching picture a set $A$ of right-hand vertices is matchable if > and only if it satisfies Hall's condition with respect to $\{1,2,3\}$. > Direct inspection again yields the same list: $f$ is never matchable, > $\{d,e\}$ is not (both can only be reached from vertex $3$), and the > maximal matchable sets are $\{a,b,c\}$, $\{a,b,d\}$, $\{a,b,e\}$, > $\{a,c,d\}$, $\{a,c,e\}$.
Matroid theory studies “independence”; in particular, it studies the common structure of Examples –.
### The independent-set axioms
Definition（Matroid）. A matroid is a pair $M=(E,\mathcal{I})$ where $E$ is a finite ground set and $\mathcal{I}\subseteq 2^{E}$ is a collection of independent sets satisfying:
1. $\varnothing\in\mathcal{I}$. 2. If $I\subseteq J$ and $J\in\mathcal{I}$, then $I\in\mathcal{I}$. 3. If $I,J\in\mathcal{I}$ and $\lvert I\rvert<\lvert J\rvert$, then there exists $j\in J\setminus I$ such that $I\cup\{j\}\in\mathcal{I}$.
> *Correction.* The scans write (I2) with a proper inclusion $I\subset J$. The correct > axiom is $I\subseteq J$ (which is automatic if $I=J$). We use $\subseteq$ > throughout.
Axiom (I3) is the augmentation (or independent-set exchange) axiom.
### The three models are matroids
Proposition（Linear matroids）. Let $E$ be a finite list of vectors in a vector space $V$, and let $\mathcal{I}$ be the collection of linearly independent sublists. Then $(E,\mathcal{I})$ is a matroid.
*Proof.* (I1) and (I2) are immediate. For (I3), let $I,J\in\mathcal{I}$ with $\lvert I\rvert<\lvert J\rvert$, and suppose for contradiction that $I\cup\{j\}\notin\mathcal{I}$ for every $j\in J\setminus I$. Write $I=\{v_1,\ldots,v_k\}$. For each such $j$ the set $I\cup\{j\}$ is dependent, so there is a linear relation \[ c_1 v_1+\cdots+c_k v_k + c j = 0 \] with not all coefficients zero. The coefficient $c$ of $j$ cannot vanish (else $I$ would be dependent), hence $j\in\operatorname{span}(I)$. Thus $J\subseteq\operatorname{span}(I)$, so $\operatorname{span}(J)\subseteq\operatorname{span}(I)$ and \[ \lvert J\rvert=\dim\operatorname{span}(J) \le\dim\operatorname{span}(I) =\lvert I\rvert, \] where the two equalities use that $I$ and $J$ are independent. This contradicts $\lvert I\rvert<\lvert J\rvert$.
Proposition（Graphic matroids）. Let $G=(V,E)$ be a graph (loops and multiple edges allowed), and let $\mathcal{I}$ be the collection of acyclic subsets of $E$. Then $(E,\mathcal{I})$ is a matroid, written $M(G)$ and called the cycle matroid (or graphic matroid) of $G$.
*Proof.* (I1) and (I2) are immediate. The key observation is:
Observation. If $I\subseteq E$ is acyclic, then the spanning subgraph $(V,I)$ has exactly $\lvert V\rvert-\lvert I\rvert$ connected components.
Indeed, a forest on $n$ vertices with $c$ components has $n-c$ edges.
Now let $I,J\in\mathcal{I}$ with $\lvert I\rvert<\lvert J\rvert$, and suppose $I\cup\{j\}\notin\mathcal{I}$ for all $j\in J\setminus I$. Then each such $j$ forms a cycle with $I$, so adding $j$ does not connect two components of $(V,I)$. Hence $(V,I\cup J)$ still has $\lvert V\rvert-\lvert I\rvert$ components, and therefore so does $(V,J)$. But $J$ is acyclic, so gives \[ \lvert V\rvert-\lvert J\rvert =\text{number of components of $(V,J)$} \ge \lvert V\rvert-\lvert I\rvert, \] hence $\lvert J\rvert\le\lvert I\rvert$, a contradiction.
Proposition（Transversal matroids）. Let $G$ be a bipartite graph with bipartition $(D,E)$, and let $\mathcal{I}$ be the collection of subsets of $E$ that can be matched into $D$. Then $(E,\mathcal{I})$ is a matroid.
*Proof.* The notes leave this as Homework 1. We record a complete argument.
(I1) and (I2) are immediate (the empty set is matched by the empty matching, and a subset of a matched set is matched). For (I3), let $I,J\subseteq E$ be matchable, with $\lvert I\rvert<\lvert J\rvert$, and fix matchings $M_I$ of $I$ and $M_J$ of $J$ into $D$. Consider the symmetric difference $M_I\triangle M_J$, a disjoint union of even cycles and alternating paths. Because $\lvert J\rvert>\lvert I\rvert$, some path $P$ in $M_I\triangle M_J$ is $M_I$-augmenting: if $j\in J\setminus I$ is the $E$-endpoint of $P$, then $M_I\triangle P$ is a matching of $I\cup\{j\}$.
### Isomorphism, and names for the three classes
Definition（Isomorphism）. Two matroids $(E,\mathcal{I})$ and $(E',\mathcal{I}')$ are isomorphic if there is a bijection $E\to E'$ sending $\mathcal{I}$ onto $\mathcal{I}'$. We often simply say they are “the same matroid”.
The three examples of are isomorphic; we treat them as one running example.
Definition. A matroid is linear (or representable over a field $\mathbb{F}$) if it is isomorphic to the matroid of a vector configuration in an $\mathbb{F}$-vector space. It is graphic if it is isomorphic to $M(G)$ for some graph $G$. It is transversal if it arises from a bipartite matching problem as in .
> *Supplement.* A fourth basic class, used constantly below: the uniform matroid > $U_{r,n}$ on an $n$-set has as independent sets all subsets of size at > most $r$. Thus $U_{n,n}$ is free (every set independent), $U_{0,n}$ consists > of $n$ loops, and $U_{1,n}$ is $n$ parallel non-loop elements. A generic > vector configuration of $n$ vectors in $\mathbb{F}^r$ realises $U_{r,n}$ whenever > $\lvert \mathbb{F}\rvert$ is large enough. > > The special elements of Lecture 1 have official names. An element $e$ is a > loop if $\{e\}$ is dependent, a coloop (isthmus) if > $e$ lies in every basis, and two non-loop elements are parallel > if they form a $2$-circuit. In the running example $f$ is a loop, $a$ is a > coloop, and $\{d,e\}$ is a parallel pair. > > In a graphic matroid the rank of an edge-set $A$ is > $r(A)=\lvert V\rvert-\kappa(A)$, where $\kappa(A)$ is the number of connected > components of $(V,A)$, counting isolated vertices. This is the same > counting that made (I3) work in . > > Hall's marriage theorem supplies a direct test for independence in a > transversal matroid: $A\subseteq E$ is matchable if and only if > $\lvert N(S)\rvert\ge\lvert S\rvert$ for every $S\subseteq A$, where $N(S)$ is the set > of left-hand neighbours of $S$. The running example fails Hall on > $\{d,e\}$ (both meet only vertex $3$) and on any set containing $f$. > > The philosophical list in the bases chapter mentions Dyck paths as a > fourth model of independence. A lattice path matroid > (Bonin–de Mier–Noy) has ground set the north-steps of lattice paths > from $(0,0)$ to $(m,r)$ lying between two bounding paths; a set of > north-steps is independent if it occurs in some such path. The > Catalan matroid is the special case whose bounds are the axes > and the diagonal: its bases correspond to Dyck paths of semilength $n$ > (rank $n$ on $2n$ elements). Lattice path matroids are transversal, hence > representable over every large enough field.