Unimodular matrix representations for pseudo-orientable ribbon graphs

Posted on by

This is a guest post by Donggyu Kim, who recently posted about the cycles of ribbon graphs. In this post, Donggyu introduces a generalisation of orientable ribbon graphs, pseudo-orientable ribbon graphs, based on recent work with Changxin Ding [2].

In my previous post, we saw that orientable ribbon graphs admit principally unimodular matrix representations. More precisely, for any orientable ribbon graph $\mathbb{G}$ and quasi-tree $X$, there exists a principally unimodular matrix $\mathbf{A}$ such that

$$\det(\mathbf{A}[Q \triangle X]) =\begin{cases}1 & \text{if $Q$ is a quasi-tree},\\0 & \text{otherwise},\end{cases}\qquad\qquad\tag{$*$}$$

where $Q\triangle X:= (Q\setminus X) \cup (X\setminus Q)$ denotes the symmetric difference of $Q$ and $X$, and $\mathbf{A}[Q \triangle X]$ is the principal submatrix of $\mathbf{A}$ indexed by $Q \triangle X$.

As noted in the previous post, the construction of such a matrix $\mathbf{A}$ relies heavily on the orientability of $\mathbb{G}$, and indeed it is not hard to find non-orientable ribbon graphs that do not admit such PU matrix representations.

Today, I will introduce a new class of ribbon graphs, called pseudo-orientable, which generalizes orientable ribbon graphs and admits PU matrix representations satisfying (*). For simplicity, we will restrict our attention to bouquets, that is, ribbon graphs with a single vertex. However, the results extend easily to general ribbon graphs by making use of the partial duality introduced by Chmutov [1]. We will also identify bouquets with signed chord diagrams; see Figure 1.

A bouquet (left) with three edges, where the edge $1$ is twisted/non-orientable (red) and the edges $2$ and $3$ are untwisted/orientable (blue). The corresponding signed chord diagram (right) is obtained by drawing chords on the boundary of the vertex and assigning signs (in this figure, the colors red and blue) to the chords according to the orientability of the corresponding edges.

Pseudo-orientability

Let’s begin by defining pseudo-orientable bouquets.

Definition. A bouquet $\mathbb{G}$ is pseudo-orientable if the boundary of the vertex admits two closed segments $S_1$ and $S_2$ such that

  • $S_1 \cap S_2$ is the set of two distinct points,
  • for each orientable edge, both of its ends lie in the interior of the same segment, either $S_1$ or $S_2$, and
  • for each non-orientable edge, one end lies in the interior of $S_1$ and the other end lies in the interior of $S_2$.

See Figure 2 (left) for an example of a pseudo-orientable bouquet.

The adjustment $\widehat{\mathbb{G}}$ of $\mathbb{G}$ at $(S_1,S_2)$ is the orientable bouquet obtained in the following way:

  1. Cut the bouquet along $S_2$ and then reglue it with a half-twist. Note that all edges are orientable in the new bouquet.
  2. Add a new orientable edge, denoted by $\widehat{e}$, connecting the two points in $S_1\cap S_2$.

Figure 2 (right) illustrates the resulting orientable bouquet $\widehat{\mathbb{G}}$.

The left figure is a pseudo-orientable bouquet $\mathbb{G}$, whose orientable edges are colored blue and non-orientable edges are colored red. A pair $(S_1,S_2)$ is indicated by dotted arrows. The right figure is the adjustment $\widehat{\mathbb{G}}$ of $\mathbb{G}$ at $(S_1,S_2)$, obtained by flipping the bottom segment $S_2$. The three blue-red dashed lines indicate orientable edges that were non-orientable in $\mathbb{G}$. The new edge $\widehat{e}$ is depicted as the blue dashed line. All edges in $\widehat{\mathbb{G}}$ are orientable.

Every orientable bouquet is pseudo-orientable, because we can get a pair $(S_1,S_2)$ by letting $S_1$ be a small boundary segment containing no ends of edges, and $S_2$ be the remaining boundary segment.

We also remark that the class of pseudo-orientable ribbon graphs is closed under taking ribbon graph minors.

 

PU matrix representations for pseudo-orientable bouquets

The Matrix–Quasi-tree Theorem for pseudo-orientable bouquets is as follows.

Theorem. Let $\mathbb{G}$ be a pseudo-orientable bouquet. Then there is an $E(\mathbb{G})$-by-$E(\mathbb{G})$ matrix $\mathbf{M}$ such that

$$\det(\mathbf{M}[Q])=\begin{cases}1 & \text{if $Q$ is a quasi-tree},\\0 & \text{otherwise}.\end{cases}$$

In particular, $\det(\mathbf{I} + \mathbf{M})$ is the number of quasi-trees of $\mathbb{G}$.

Remarkably, the matrix $\mathbf{M}$ is neither skew-symmetric nor symmetric in general, but can be expressed as the sum of a skew-symmetric matrix and a rank-one symmetric matrix. The theorem follows from two parallel stories on ribbon graphs and matrices, with delta-matroids underlying both.

For a subset $S$ of $[n]:=\{1,2,\ldots,n\}$, let

$$\widehat{S} :=\begin{cases}S & \text{if $|S|$ is even},\\S\cup\{n+1\} & \text{if $|S|$ is odd}.\end{cases}$$

Ribbon graphs. Let $\mathbb{G}$ be a pseudo-orientable bouquet, and let $\widehat{\mathbb{G}}$ be an adjustment of $\mathbb{G}$. We set $E(\mathbb{G}) = [n]$ and $\widehat{e} = n+1$. Then the following equivalence holds:

$$\text{$Q$ is a quasi-tree of $\mathbb{G}$} \iff \text{$\widehat{Q}$ is a quasi-tree of $\widehat{\mathbb{G}}$}.\tag{1}$$

Matrices. Let $\mathbf{A}$ be an $(n+1)$-by-$(n+1)$ PU skew-symmetric matrix representing $\widehat{\mathbb{G}}$. We can write it as

$$\mathbf{A} =\begin{pmatrix}\mathbf{A}’ & \mathbf{v}\\-\mathbf{v}^T & 0\end{pmatrix},$$

and let $\mathbf{M} := \mathbf{A}’ + \mathbf{v}\mathbf{v}^T$.

Then we have

$$\det(\mathbf{M}[Q])=\det(\mathbf{A}[\widehat{Q}])\tag{2}$$

for each $Q\subseteq [n]$.

By the property (*) of the matrix $\mathbf{A}$ representing $\widehat{\mathbb{G}}$ (with $X=\emptyset$) together with (1) and (2), we deduce the theorem.

Delta-matroids. Delta-matroids are already lurking in the two pictures above. Recall that a ribbon graph gives rise to a delta-matroid via its quasi-trees, and a (skew-)symmetric matrix gives rise to a delta-matroid via the index sets of nonsingular principal submatrices. Moreover, the delta-matroid associated with an orientable ribbon graph is even. What, then, can we say about the delta-matroid associated with a pseudo-orientable ribbon graph?

A delta-matroid $D$ is strong if it satisfies the simultaneous basis exchange property: for any bases $B,B’$ and $x\in B\triangle B’$, there is $y\in B\triangle B’$ such that $B\triangle\{x,y\}$ and $B’\triangle\{x,y\}$ are bases.

Every matroid, even delta-matroid, and ribbon-graphic delta-matroid is strong, but not every delta-matroid is. For example, the delta-matroid $([3],\{\emptyset,\{1\},\{2\},\{3\},\{1,2,3\}\})$ is not strong.

Murota [4] gave a concise relationship between strong and even delta-matroids, attributing it to Geelen:

Proposition. Let $D = ([n],\mathcal{B})$ be a set system. Then $D$ is a strong delta-matroid if and only if $\widehat{D} := ([n+1],\widehat{\mathcal{B}})$ is an even delta-matroid, where $\widehat{\mathcal{B}} := \{ \widehat{B} : B\in\mathcal{B} \}$.

Finally, pseudo-orientable ribbon graphs are precisely those ribbon graphs $\mathbb{G}$, up to ribbon graph $2$-isomorphism [3], for which $\widehat{D(\mathbb{G})}$ is ribbon-graphic — this characterization captures our original motivation for the study [2].

Acknowledgements

I thank Changxin Ding and Jorn van der Pol for helpful comments.

References

[1] Sergei Chmutov. Generalized duality for graphs on surfaces and the signed Bollobas–Riordan polynomial. J. Combin. Theory Ser. B 99(3):617–638, 2009. doi:10.1016/j.jctb.2008.09.007
[2] Changxin Ding and Donggyu Kim. Pseudo-orientable ribbon graphs: Matrix–Quasi-tree theorem and log-concavity, 2026. arXiv preprint.
[3] Iain Moffatt and Jeaseong Oh. A 2-isomorphism theorem for delta-matroids. Adv. in Appl. Math. 126, Paper No. 102133, 2021. doi:10.1016/j.aam.2020.102133
[4] Kazuo Murota. A note on M-convex functions on jump-systems. Discrete Appl. Math. 289:492–502, 2021. doi:10.1016/j.dam.2020.09.019

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.