Monthly Archives: April 2026

Unimodular matrix representations for pseudo-orientable ribbon graphs

Posted on by
Reply

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

Packing versus covering binary matroid minors

Posted on by
Reply

Many different areas of combinatorics and optimization are interested in objects that admit a rough duality between packing and covering. A classic example is that every bipartite graph either has a matching of size $k$, or has a set of at most $k-1$ vertices which “hit” every edge (i.e. a vertex cover of size $k$; this is Kőnig’s theorem).

Another example where only a rough duality is possible was proven by Erdős and Pósa. They showed that every graph either has $k$ cycles that are pairwise vertex-disjoint, or has a set of $\mathcal{O}(k \log{k})$ many vertices which hit every cycle (i.e. a set of vertices whose deletion yields a forest). Note that this is not an exclusive “or”; some graphs have both. But any graph with a hitting set of size $r$ has at most $r$ pairwise vertex-disjoint cycles.

In general, for any problem which is suitable to study within this framework, the maximum size of a packing should be at most the minimum size of a covering (or at least roughly so). This is typically the easy direction (I would love to hear in the comments about any natural examples where it is not the easy direction!). If the other direction is also (roughly) satisfied, then the set of objects is said to have the Erdős-Pósa property, meaning that if there is no packing of size $k$, then there is a covering of size at most $f(k)$, for some function $f$.

Related Topics

I have discussed examples of exact combinatorial min-max theorems before, and how these problems often have an underlying matroid. One of the most general theorems about which hypergraphs admit a rough duality between packing and covering is due to Ding, Seymour, and Winkler and generalizes well-known results on VC-dimension. Other key terms are LP-rounding, total unimodularity, clutters, … . Erdős-Pósa problems are very actively researched; see for instance the recent workshop in Poland. Geelen and Kabell also proved a different matroidal Erdős-Pósa property.

Binary Matroids

For binary matroids there is a somewhat different notion of covering. It is convenient to think of a graph with a “small vertex cover” as being “close to” a graph whose largest packing has size zero. So instead of deleting a small set of vertices, we add a low-rank matrix. Formally, consider a binary matroid $M$ which is represented by the columns of an $n \times m$ binary matrix $A$. A rank-$k$ perturbation of $M$ is then any matroid $M’$ which can be represented by the columns of $A+B$, where $B$ is an $n \times m$ binary matrix of rank at most $k$. We perform addition over the binary field.

Campbell, Gollin, Hatzel, Kwon, Oum, Wiederrecht, and I proved the following theorem. Given a graph $H$, we write $M(H)$ for its cycle matroid.

Theorem
For any planar graph $H$, there is a function $f_H$ so that for every integer $k$, every binary matroid either has the cycle matroid of $k$ vertex-disjoint copies of $H$ as a minor, or has a rank-$f_H(k)$ perturbation which does not have $M(H)$ as a minor.

This really is an Erdős-Pósa property in the sense that it gives a rough min-max theorem for packing $M(H)$ minors. When $H$ is a cycle and the matroid is graphic, one should roughly think of the theorem as saying the following. Note that this is a conjecture; it does NOT just follow from our theorem. This is because, informally, our perturbations are allowed to leave the graphic world, and the ones below are not.

Conjecture
There exists a function $f$ so that for any integer $k$, every multigraph either 1) has a minor with $k$ different blocks, each of which is a cycle, or 2) can be turned into a forest by performing the following operations at most $f(k)$ times:

  • identify two vertices $u$ and $v$ into a single vertex. This operation does not change the number of edges. So for instance if $u$ and $v$ were adjacent originally, there will be a loop at the new vertex after identification.
  • split a vertex $v$ into two vertices $v_1$ and $v_2$. This operation is the opposite of identification.

Thank you to Mathieu Rundström for correcting the previous wrong version of the conjecture!