Here is the condition, which arose in contemplating polytopes associated to matroid quotients:

Let $M$ and $N$ be matroids on $E$. If $X \subseteq Y \subseteq E$ such that $X$ is indepedent in $N$ and $Y$ is spanning in $M$, then $X$ is independent in $M$ and $Y$ is spanning in $N$.


If $M \to N$ is a matroid quotient, then this condition does hold.

Proof: First, recall that $M \to N$ is a matroid quotient if and only if the following exchange condition holds: if $B_N$ is a basis of $N$, $B_M$ is a basis of $M$, and $i \in B_N - B_M$, then there exists $j \in B_M - B_N$ such that $B_N-i+j$ and $B_M-j+i$ are both bases. This follows since the fundamental cocircuit of $(B_N,i)$ and fundamental circuit of $(B_M,i)$ must intersect in more than one element.

If $X\subseteq Y \subseteq E$ such that $X$ is independent in $N$ and $Y$ is spanning in $M$, then there is a basis $B_N \supseteq X$ of $N$ and a basis $B_M \subseteq Y$ of $M$, respectively. To show $Y$ is spanning in $N$: Let $B \supset X$ be a basis of $N$ such that $|B-Y|$ is minimized. Then if $x \in B - Y$, $x$ is not in $B_M$, and the above exchange condition gives a $y \in B_M - B$ such that $B - x + y$ is a basis of $N$, which contradicts our construction of $B$. Hence, $B \subseteq Y$ and so $Y$ is spanning in $N$. The argument for $X$ is dual.


The proof of this condition only uses one half of the quotient basis exchange condition at a time. However, for a single matroid, the strong and weak basis exchange conditions are equivalent, which gives me hope (although the proof of this equivalence does not seem to generalize to this problem).

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.