1

This is a question which is related to a previous one. It is about the proof of Theorem 0.7.10 in this PhD-Thesis. The question reduces to the following. Let $M=(E,\mathcal{A})$ be a matroid, that is:

A matroid $M$ is a pair $(E,\mathcal{A})$ of a finite set $E$ and a set $\mathcal{A}\subset 2^E$ s.t.

  1. $E\in\mathcal{A}$
  2. If $X,Y\in\mathcal{A}$ then $X\cap Y\in\mathcal{A}$
  3. For all $X,Y\in\mathcal{A},e\in E\backslash (X\cup Y)$, and $f\in X\backslash Y$ there exists $Z\in\mathcal{A}$ such that $e\in Z,f\notin Z$, and $X\cap Y\subset Z$.

An oriented matroid $\mathcal{M}$ is a pair $(E,\mathcal{F})$ of a finite set $E$ and a set $\mathcal{F}\subset\{-,+,0\}^E$ of sign vectors or covectors with some properties (can be found on page 21.). For a given oriented matroid $\mathcal{M}=(E,\mathcal{F})$ we can associate a matroid by $\underline{M}=(E,\{X^0|X\in\mathcal{F}\}$, where $X^0=\{e\in E|X_e=0\}$. The composition of $X$ and $Y$, denoted by $X\circ Y$ is given by $(X\circ Y)_e=X_e$ if $X_e\not=0$ and $Y_e$ otherwise. Furthermore we write $X\le Y$ if $X_e\not= 0$ implies $X_e=Y_e$ and $X<Y$ if $X\le Y$ and $X\not= Y$. And last we set $D(X,Y):=\{e\in E|X_e=-Y_e\not= 0\}$. All these things can be found on page 21.

For $S\subset E$, we define the span of $S$ as $$\operatorname{span}_M(S)=\cap_{X\in\mathcal{A},S\subset X} X$$ We denote the span by $\overline{S}$. Moreover we call a set $S\subset E$ independent if $\overline{S\backslash e}\not= \overline{S},\forall e\in E$. A basis $B$ of a subset $S\subset E$ is a maximal independent subset of $S$. One can prove that all bases have the same cardinality for a matroid. Let $M=(E,\mathcal{A})$ be a matroid. The uniquely determined cardinality of a basis of $X\in\mathcal{A}$ is called the rank of $X$ in $M$, denoted by $\operatorname{rank}_M(X)$. For a oriented matroid $\mathcal{M}=(E,\mathcal{F})$, we define $\operatorname{rank}(\mathcal{M}):=\operatorname{rank}_M(E)$ and for $X\in\mathcal{F}$, $\operatorname{rank}(X):=\operatorname{rank}(\mathcal{M})-\operatorname{rank}_{\underline{\mathcal{M}}}(X^0)$ (see above for the associated matroid $\underline{M}$). I have two question about this rank function:

  1. Let $M=(E,\mathcal{F})$ be an oriented matroid, $X,Y\in\mathcal{F}$ with $X<Y$ why is $\operatorname{rank}(X)<\operatorname{rank}(Y)$?
  2. Let $E^0:=\{e\in E|X_e=0,\forall X\in\mathcal{F}\}$ and suppose there is a $X\in\mathcal{F}$ such that $X^0=E^0$. Why is $\operatorname{rank}_{\underline{\mathcal{M}}}(E^0)=0$?
math
  • 4,347

1 Answers1

1

For 1, your definition of matroids is via the lattice of flats. One can show the rank of a flat X is the length of the longest chain from the minimal element of the lattice of flats to X. The maximal chains correspond to choosing an ordered basis $\{b_1,\ldots,b_r\}$ and considering the chain $X_i=Span(\{b_1,\ldots,b_i\}$ for $i=0,\ldots, r$. This can be found in standard texts on matroids.

Now the map $X\mapsto X_0$ from covectors to the lattice of flats is a surjective order reversing map which sends composition of covectors to intersection. Moreover, it preserves strict inequalities. It is not difficult to show that chains can be lifted. It follows from this that $rank(X_0)$ is the length of the longest ascending chain from $X$ to a tope. Hence $X<Y$, then $rank(X)<rank(Y)$.

For 2, clearly $E_0$ is the minimum flat and hence has rank 0 by what I said above. Basically the loops of the oriented matroid are the loops of the underlying matroid.

  • Sorry, checking your answer once more, I'm not sure about the second part. Why must $rank(E^0)=0$? – math Oct 18 '13 at 10:32
  • If you use that rank is the length of the longest chain from the minimum element to your element then the minimal element has rank 0. It is clear from the defs that $E^0$ is the minimum flat. – Benjamin Steinberg Oct 18 '13 at 13:48
  • Thanks again. I was also able to prove it with the pure definition of span :) But again thanks for your patience! – math Oct 18 '13 at 17:51