Restricted matchings in simplicial complexes or graphs

asked 2025-06-04 12:32:53 +0200

Hola gravatar image

updated 2025-06-04 12:34:25 +0200

Let $\Delta$ be a simplicial complex. Let $F, G \in \mathcal{F}(\Delta)$. We say that $F$ and $G$ form a gap in $\Delta$ if $F \cap G = \emptyset$ and the induced subcollection on the vertex set $F \cup G$ is exactly $\langle F, G \rangle$. A matching $M$ of $\Delta$ is called a restricted matching if there exists a facet in $M$ that forms a gap with every other facet in $M$. The maximal size of a restricted matching of $\Delta$ is called the restricted matching number.

My question. In SageMath, is there any known algorithm to compute the restricted matching number of a simplicial complex, or at least of a graph (i.e., a 1-dimensional simplicial complex)?

edit retag flag offensive close merge delete

Comments

1

For simplicial complexes, searching the source code for "matching" yields only one thing that might be related: simplicial_complexes.MatchingComplex. You should write your own algorithm!

John Palmieri gravatar imageJohn Palmieri ( 2025-06-05 20:19:49 +0200 )edit