Pseudo-orientable ribbon graphs: Matrix--Quasi-tree Theorem and log-concavity

Abstract

One of the most important classes of even $\hat{I}”$-matroids arises from orientable ribbon graphs, which play a role analogous to that of graphic matroids in matroid theory. Motivated by a natural correspondence between strong $\hat{I}”$-matroids and even $\hat{I}”$-matroids due to Geelen and Murota, we characterize the class of strong $\hat{I}”$-matroids that correspond to orientable ribbon-graphic $\hat{I}”$-matroids. These are precisely the $\hat{I}”$-matroids associated with what we call pseudo-orientable ribbon graphs. Moreover, we present a geometric construction that transforms a pseudo-orientable ribbon graph into an orientable ribbon graph, thereby realizing this correspondence. As consequences, we obtain the Matrix--Quasi-tree Theorem, the Hurwitz stability of quasi-tree generating polynomials, and a log-concavity result for the sequence counting quasi-trees of size $2i-1$ or $2i$ for pseudo-orientable ribbon graphs. To establish the log-concavity, we generalize Stanley's log-concavity theorem for regular matroids to regular $\hat{I}”$-matroids. Finally, we exhibit an infinite family of non-pseudo-orientable ribbon graphs that fail to satisfy the Matrix--Quasi-tree theorem and Hurwitz stability.

1) We added counterexamples to some questions posed in the previous version. 2) We added a characterization of pseudo-orientability suggested by Mark Ellingham. 3) Because of this new characterization, we simplified a proof and reorganized the material in Section 3