Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

Restricted matchings in simplicial complexes or graphs

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)?

Restricted matchings in simplicial complexes or graphs

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)?