Let $J_n := \{1,2,3,\ldots,n,1^*,2^*,\ldots,n^*\}$ with the involution $x\mapsto x^*$ exchanging $i$ and $i^*$ for $1\leq i\leq n$. The following is supposed to be standard, but to avoid any doubt as to the definition (since I am asking about possibly equivalent conditions): a symplectic matroid of rank $k$ on $J_n$ means a set $\mathscr{B}$ of $k$-element subsets of $J_n$, all of which satisfy $B \cap B^* = \varnothing$ (such subsets are called "admissible"), and such that for every total order $\preceq$ on $J_n$ for which $x \preceq y$ implies $y^* \preceq x^*$ for all $x,y\in J_n$ (such orders are also called "admissible") there is a $\preceq$-greatest $B \in \mathscr{B}$, where two admissible $k$-element subsets $A,B$ of $J_n$ are compared by letting $A \preceq B$ mean $a_i \preceq b_i$ for all $i$, where $A = \{a_1\preceq \cdots \preceq a_k\}$ and $B = \{b_1\preceq \cdots \preceq b_k\}$. This is essentially the definition found in Borovik, Gelfand & White, Coxeter Matroids (Birkhäuser 2003, Progress in Mathematics 216), §3.1.3.

The same book states, in §3.8, that more direct definitions of symplectic matroids, analogous to the definition of ordinary matroids using their sets of basis in the form of the basis exchange property, are not known (except in the particular case of Lagrangian matroids). They refer to a paper by Tim Chow, "Symplectic Matroids, Independent Sets, and Signed Graphs" (Discrete Math. 263 (2003), 35–45), which proves the equivalence of symplectic matroids with a complicated exchange property on independent sets, and proposes a conjectural equivalent property in terms of bases.

This is very odd, because in the older paper by I. M. Gelfand & V. V. Serganova (И. М. Гельфанд & В. В. Серганова, "Комбинаторные геометрии и страты тора на однородных компактных многообразиях", Успехи Мат. Наук 42 (1987), 107–134; English translation: "Combinatorial geometries and torus strata on homogeneous compact manifolds", Russian Math. Surveys 42 (1987), 133–168), where the concept of symplectic and (what are now called) Coxeter matroids first originated, the definition given of symplectic matroids is as a set $\mathscr{B}$ of admissible $k$-element subsets of $J_n$ satisfying the conjunction of the following two conditions:

(†1) for any $A,B\in\mathscr{B}$ and $a\in A\setminus B$ there is $b\not\in A$ such that either $(A\setminus\{a\})\cup\{b\} \in \mathscr{B}$ or $(A\setminus\{a,b^*\})\cup\{a^*,b\} \in \mathscr{B}$;

(†2) for any $A,B\in\mathscr{B}$ and $b\in B\setminus (A\cup A^*)$ there is $a\in A$ such that $(A\setminus\{a\})\cup\{b\} \in \mathscr{B}$.

The proposition 4 of §8.2 in the Gelfand-Serganova paper (p. 127 in the original, p. 158 in the translation) asserts that the conjunction of these conditions (which I'll call (†)) is equivalent to the definition of a symplectic matroid using the maximality property (i.e., the one given above). They do not bother to give a proof, and the obviousnes of the fact escapes me.

So, what is going on here? I can imagine several things:

  • Either (†) is indeed equivalent to the condition of being a symplectic matroid (in the sense given at the top of this post), but for some reason it is not considered a satisfactory "basis exchange property". In this case, I would like to know why, and also where I can find the proof which Gelfand and Serganova omit.

  • Or the Gelfand-Serganova paper is wrong in stating that (†) is equivalent to being a symplectic matroid (in the sense given at the top of this post), and for some reason no later paper bothers to actually point out this mistake (this is particularly strange since the paper by Borovik, Gelfand and White, "Symplectic Matroids", J. Algebraic Combin. 8 (1998), 235–252, points out a different mistake in the Gelfand-Serganova, but makes no comment whatsoever concerning this characterization of symplectic matroids). In this case, I would like to know a counterexample to the equivalence (and also, if at least one implication holds between (†) and "being a symplectic matroid").

Finally, what is the status of Chow's proposed conjecture, or more generally, of the characterization of symplectic matroids using an exchange-like condition on bases?


I recall being told (by Neil White I think, but he might have been reporting an observation of Borovik) that the Gelfand–Serganova exchange condition is wrong. Unfortunately I no longer recall the counterexample, and I agree with you that this is an unfortunate lacuna in the literature. I would suggest contacting Borovik. Of course if you can straighten out the matter yourself and give a clear report, that would be even better.

I am not aware of any progress on my conjecture or of basis exchange for Coxeter matroids, but on the other hand people have sometimes proved a conjecture of mine without notifying me, so don't take this as the final word.

  • 1
    $\begingroup$ Do you at least remember whether the G-S exchange condition fails at being necessary or fails at being sufficient? Neither direction seems obvious to me, but I'm very bad at reasoning with these sorts of things. $\endgroup$ – Gro-Tsen Apr 3 '17 at 17:12
  • $\begingroup$ @Gro-Tsen : No, I'm afraid that I don't remember offhand; it's been a long time since I've thought about this stuff. But I think that if you compare their exchange condition with the one in my paper, it should point you in the direction of a counterexample. $\endgroup$ – Timothy Chow Apr 3 '17 at 18:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.