graph-theory
这是 拟阵笔记 的一章。 上一篇是 秩与闭包，下一篇是 子阵。
Flats and geometric lattices
### Motivation: hyperplane arrangements
A real hyperplane arrangement $\mathcal{A}$ has an intersection poset $L(\mathcal{A})$, whose elements are the intersections of subfamilies of $\mathcal{A}$, ordered by reverse inclusion.
Order: $x\le y$ in $L(\mathcal{A})$ if $x\supseteq y$. This is a poset. How much of the geometry of $\mathcal{A}$ is recorded by $L(\mathcal{A})$ (number of regions, bounded regions, topology)? A great deal. The next construction generalises this: from a matroid $M$ one builds the lattice of flats $L(M)$.
### Flats
Definition（Flat）. A flat of $M$ is a set $F\subseteq E$ with $\overline(F)=F$. Equivalently, $r(F\cup\{x\})=r(F)+1$ for every $x\notin F$.
Example. If $M$ is represented by a vector configuration, flats correspond to intersections of the configuration with linear subspaces. In the running example (labelling $1,\ldots,6$) the flats are \[ \{6\}; \{1,6\},\{2,6\},\{3,6\},\{4,5,6\}; \{1,2,6\},\{1,3,6\},\{1,4,5,6\},\{2,3,4,5,6\}; E. \] Ordered by inclusion they form the Hasse diagram below.
Definition（Poset）. A partially ordered set (poset) is a set $P$ with a binary relation $\le$ that is reflexive, antisymmetric, and transitive. For $a\neq b$ one may have $a
Example. Boolean lattice $2^{S}$ (by inclusion); divisor lattice $D_n$ (by divisibility); $(\mathbb{Z},\le)$; the flats of $M$ ordered by inclusion.
Say $a$ covers $b$, written $a\gtrdot b$, if $a>b$ and nothing lies strictly between them. The Hasse diagram of $P$ has an edge for each cover.
Definition（Lattice）. A poset is a lattice if every pair of elements has a least upper bound (join $a\vee b$) and a greatest lower bound (meet $a\wedge b$).
The Boolean lattice, $D_n$, and $(\mathbb{Z},\le)$ are lattices; the $N$-shaped Hasse diagram is not.
### The lattice of flats
Proposition. The flats of a matroid, ordered by inclusion, form a lattice $L(M)$.
*Proof.* Let $F,G$ be flats. The meet is $F\wedge G=F\cap G$: the intersection of flats is a flat, because if $x\notin F\cap G$ then $x\notin F$ or $x\notin G$, say $x\notin F$, and submodularity gives \[ r(F)+r((F\cap G)\cup\{x\}) \ge r(F\cup\{x\})+r(F\cap G) = r(F)+1+r(F\cap G), \] so $r((F\cap G)\cup\{x\})\ge r(F\cap G)+1$. The join is $F\vee G=\overline(F\cup G)$, which is the smallest flat containing both.
Definition. A poset is graded if it admits a rank function $r\colon P\to\mathbb{N}$ with $r=0$ on minimal elements and $r(y)=r(x)+1$ whenever $y$ covers $x$.
Proposition. $L(M)$ is graded by the matroid rank. The unique minimal element is $\overline(\varnothing)$ (the set of loops), of rank $0$. If $F\lessdot G$ and $x\in G\setminus F$, then $F\subsetneq \overline(F\cup\{x\})\subseteq G$ and $r(\overline(F\cup\{x\}))=r(F)+1$, so $G=\overline(F\cup\{x\})$.
Proposition（Semimodularity）. For flats $F,G$, $r(F)+r(G)\ge r(F\vee G)+r(F\wedge G)$.
*Proof.* Submodularity of matroid rank, together with $r(\overline(F\cup G))=r(F\cup G)$.
Proposition（Atomic）. Every flat is a join of rank-$1$ flats (atoms).
*Proof.* For $F\in L(M)$ and $f\in F$ the singleton closure $\overline(\{f\})$ is an atom contained in $F$ (or $f$ is a loop, hence already in $\overline(\varnothing)$). Then $F=\overline(\bigcup_{f\in F}\overline(\{f\})) =\bigvee_{f\in F}\overline(\{f\})$.
Finite meets and joins exist in any finite lattice: $F\wedge G\wedge\cdots=F\cap G\cap\cdots$ and $F\vee G\vee\cdots=\overline(F\cup G\cup\cdots)$ in $L(M)$.
### Geometric lattices
Definition. A finite lattice is geometric if it is semimodular and atomic. (Semimodularity implies graded.)
Theorem. A finite lattice is geometric if and only if it is the lattice of flats of a matroid.
*Proof.* We have already seen $L(M)$ is geometric. Conversely, let $L$ be geometric and let $E$ be its set of atoms (or $E=\varnothing$ if $L$ is a point). Define $r\colon 2^{E}\to\mathbb{N}$ by \[ r(\{e_1,\ldots,e_k\})=r_L(e_1\vee\cdots\vee e_k). \] This satisfies the local rank axioms
1. $r(\varnothing)=0$; 2. $r(A\cup\{a\})-r(A)\in\{0,1\}$; 3. if $r(A)=r(A\cup\{a\})=r(A\cup\{b\})$ then $r(A\cup\{a,b\})=r(A)$.
Indeed (R1$'$) is $r_L(\hat0)=0$. For (R2$'$), semimodularity gives \[ 0\le r_L(x\vee a)-r_L(x)\le r_L(a)-r_L(x\wedge a)\le 1 \] with $x=\bigvee A$. For (R3$'$), if $r(A)=r(A\cup\{a\})=r(A\cup\{b\})$ then $x=x\vee a=x\vee b$, so $x\vee a\vee b=x$.
These local axioms imply (R1)–(R3), so $r$ is a matroid rank function. Indeed: $r(\varnothing)=0$ is (R1$'$), and iterating (R2$'$) gives $0\le r(A)\le\lvert A\rvert$ and monotonicity. For submodularity, add the elements of $Y\setminus X$ one at a time; whenever an element does not increase rank, (R3$'$) says it remains redundant after any further additions, which is the local rank lemma and hence (R3). The map \[ \phi\colon L\to L(M), x\mapsto\{\text{atoms }a\le x\} \] is a poset isomorphism: it is well-defined (the image is a flat, else semimodularity would force a missing atom under $x$), injective because $L$ is atomic (so $x=\bigvee\{a:a\le x\}$), surjective by construction of $r$, and order-preserving in both directions.
### Simple matroids
The correspondence $M\mapsto L(M)$ loses loops and parallel elements, and nothing else.
Definition. A matroid is simple (a combinatorial geometry) if it has no loops and no parallel elements. The simplification of $M$ is obtained by deleting loops and keeping one element from each parallel class.
Proposition. Simple matroids are in bijection with geometric lattices.
Proposition. Geometric lattices are coatomic: every flat of corank $k$ is a meet of $k$ coatoms.
*Proof.* Coatoms of $L(M)$ are the rank-$(r(M)-1)$ flats, i.e.\ the hyperplanes (maximal non-spanning sets). Induct on $k$. Let $X$ be a flat of rank $r-k$, pick $y\notin X$, and set $Y=\overline(X\cup\{y\})$, so $Y$ covers $X$ and $r(Y)=r-k+1$. The board drawing of the two cases is unlabeled; the split is: if $E\setminus\{y\}$ is non-spanning let $H_Y$ be a hyperplane containing it and $X$; if $E\setminus\{y\}$ is spanning, enlarge $X$ inside $E\setminus\{y\}$ to a hyperplane $H_Y$. Either way $X=Y\wedge H_Y$ with $Y\not\le H_Y$. Apply induction to $Y$.
> *Supplement.* The several cryptomorphisms of the notes may be summarised as a single > dictionary. Each column determines the others. > > > {\centering > \small > > | data | recovers independence by | > | — | — | > | independent sets $\mathcal{I}$ | given | > | bases $\mathcal{B}$ | subsets of members of $\mathcal{B}$ | > | circuits $\mathcal{C}$ | sets containing no member of $\mathcal{C}$ | > | rank $r$ | $r(I)=\lvert I\rvert$ | > | closure $\overline$ | $x\notin\overline(I\setminus\{x\})$ for all $x\in I$ | > | flats $L(M)$ | $r$ on the lattice, after adding loops/parallels | > > \par} > > > > The missing direction from $L(M)$ back to $M$ is the simplification > discussed above: the lattice remembers the simple matroid, and one > restores loops and parallel classes by hand. Duality reads, on this > dictionary, as independent $\leftrightarrow$ spanning in the dual, > circuit $\leftrightarrow$ cocircuit, flat $\leftrightarrow$ cyclic flat > of the dual, and $r^{\ast}(X)=\lvert X\rvert-r(E)+r(E\setminus X)$.