Gorenstein and Cohen-Macaulay Matching Complexes

It is easy to see that each maximal matching of a star and a star triangle have size 1 and $(n-1)/2$, respectively, where $n$ denotes the number of vertices of the graph. Assume that $H$ is a Cameron-Walker graph with bipartition $(X,Y)$. Let $M$ be a maximal matching of $H$ and $M_{1}$ be those edges of $M$ which are in the underlying bipartite graph and $M_{2}=M\setminus M_{1}$. Suppose that $X_{1}$ and $Y_{1}$ are vertices in $X$ and $Y$, respectively, incident to some edge in $M_{1}$ and $X_{2}=X\setminus X_{1}$, $Y_{2}=Y\setminus Y_{1}$. Then for each vertex $x\in X_{2}$ there should be exactly one leaf edge in $M_{2}$ incident to $x$ and for $x\in X_{1}$, none of the leaf edges at $x$ are in $M_{2}$. Also for each vertex $y\in Y$ the pendant triangles at $y$ form a star triangle. If $y\in Y_{2}$, then a maximal matching of the star triangle at $y$ must be in $M_{2}$ and its size as mentioned before equals the number $t_{y}$ of triangles in the star triangle at $y$. If $y\in Y_{1}$, then as $y$ is covered by $M_{1}$, only those edges of the star triangle can be in $M_{2}$, that do not meet $y$ and since $M$ is maximal, all of them must be in $M_{2}$. Therefore again the star triangle at $y$ contributes exactly $t_{y}$ edges to $M_{2}$. Consequently, $|M_{2}|=|X_{2}|+t$, where $t$ is the total number of pendant triangles in $H$. Because $|M_{1}|=|X_{1}|$, it follows that $|M|=|X|+t$ is independent of the choice of $M$. ∎

By [5, Theorem 1], $H$ is either a 5-cycle, a 7-cycle, an edge or a bipartite graph with bipartite sets $V_{1}$ and $V_{2}$ such that each vertex in $V_{1}$ is adjacent to a leaf and each vertex in $V_{2}$ is not adjacent to any leaf. Suppose that $H$ is not a star, a 5-cycle or a 7-cycle. If $L$ is the set of leaves of $H$, then by setting $X=V_{1}$ and $Y=V_{2}\setminus L$, then $H$ is a Cameron-Walker graph with bipartition $(X,Y)$. Note that the edges between $X$ and $L$ are the leaf edges at vertices of $X$. ∎

By [7], $H$ is either a star or a star triangle or a Cameron-Walker graph. If $H$ is a star then $G$ is a complete graph and by [19, Lemma 4], $\Delta=\Delta(\overline{G})$ is vertex decomposable.

For the case that $H$ is a star triangle or a Cameron-Walker graph, we use induction on the number of edges of $H$. Suppose that $H$ is a star triangle in which the common vertex of the triangles is $v$. Let $e$ be an edge incident to $v$. Then $\mathrm{link}_{\Delta}(e)=\Delta(\overline{\mathrm{L}(H-\mathrm{N}_{G}[e])})$ and $H-\mathrm{N}_{G}[e]$ is just a matching. Therefore $\mathrm{link}_{\Delta}(e)$ is a simplex. Also $\Delta-e=\Delta(\overline{\mathrm{L}(H-e)})$ and $H-e$ is either a star or a Cameron-Walker graph with less edges that $H$ and hence $\Delta-e$ is vertex decomposable by the induction hypothesis. Also if $M$ is a maximal matching of $H$ containing $e$, then $(M\setminus\{e\})\cup\{e^{\prime}\}$ is a matching of $H-e$, where $e^{\prime}$ is the edge in the same triangle as $e$ but not adjacent to $v$. This shows that $e$ is a shedding vertex of $\Delta$ and thus $\Delta$ is vertex decomposable.

Now assume that $H$ is a Cameron-Walker graph with bipartition $(X,Y)$. Let $e$ be an edge of the underlying bipartite graph with an endpoint $x\in X$. By the definition of Cameron-Walker graphs, $x$ is incident to a leaf edge $e^{\prime}$. Now every connected component of $H-e$ and $H-N_{G}[e]$ is either a star or a star triangle or a Cameron-Walker graph with less edges than $H$. Consequently, both $\Delta-e$ and $\mathrm{link}_{\Delta}(e)$ are vertex decomposable by induction hypothesis. Also if $M$ is a maximal matching of $H$ containing $e$, then $(M\setminus\{e\})\cup\{e^{\prime}\}$ is a matching of $H-e$, that is, $e$ is a shedding vertex of $\Delta$. Thus $\Delta$ is vertex decomposable. ∎

It is well-known that (i) $\Rightarrow$ (ii) $\Rightarrow$ (iii). Suppose that $\Delta$ is CM over a field $K$. Then $\Delta$ is pure and hence according to (3.2), $H$ is either a 5-cycle or a 7-cycle or a star or a Cameron-Walker graph. But by [19, Theorem 10] a 7-cycle is not CM over any field, so (iv) follows. Now assume that $H$ is a star or a Cameron-Walker graph. Then by (3.1) and (3.3), $\Delta$ is pure vertex decomposable. For the 5-cycle, the result follows from [19, Theorem 10]. ∎

Suppose that $n$ is even. Then each maximal matching of $K_{n}$ has size $n/2$. If $M$ and $M^{\prime}$ are maximal matchings of $K_{n}$ and $|M\cap M^{\prime}|=|M|-1$, then $M\cap M^{\prime}$ saturates $n-2$ vertices of $K_{n}$. If $u$ and $v$ are the only unsaturated vertices, then the only maximal matching containing $M\cap M^{\prime}$ is $(M\cap M^{\prime})\cup\{uv\}$, so $M=M^{\prime}$. Consequently, if $K_{n}$ has more than one maximal matchings, which holds if $n>2$, then $\Delta$ is not strongly connected.

Now assume that $n$ is odd. We use induction to show that there is a strong path between every two maximal matchings of $K_{n}$. Let $M_{1}$ and $M_{2}$ be maximal matchings of $K_{n}$. If $uv\in M_{1}\cap M_{2}$ then there is a strong path between $M_{1}\setminus\{uv\}$ and $M_{2}\setminus\{uv\}$ in $K_{n}-u-v\cong K_{n-2}$, by the induction hypothesis. Hence there is a strong path between $M_{1}$ and $M_{2}$. Suppose that $M_{1}\cap M_{2}=\emptyset$ and $a$ is a vertex saturated by both $M_{1}$ and $M_{2}$, say $ab\in M_{1}$ and $ac\in M_{2}$. If $c$ is not saturated by $M_{1}$, then by the previous part there is a strong path between $(M_{1}\setminus\{ab\})\cup\{ac\}$ and $M_{2}$. Thus it follows that there is such a path between $M_{1}$ and $M_{2}$. If $c$ is saturated by $M_{1}$, say $cd\in M_{1}$, then there is a strong path $P$ from $(M_{1}\setminus\{ab,cd\})\cup\{ac,bd\}$ to $M_{2}$. Note that since $n$ is odd, there is an vertex $e$ unsaturated in $M_{1}$. If we attach the following strong path at the start of $P$ we get a strong path from $M_{1}$ to $M_{2}$: $M_{1}$, $(M_{1}\setminus\{ab\})\cup\{ae\}$, $(M_{1}\setminus\{ab,cd\})\cup\{ae,bd\}$. ∎

If $n\leq 3$, then $\dim\Delta\leq 0$ and $\Delta$ is CM. If $n>2$ is even, then by (3.5) $\Delta$ is not strongly connected and hence not CM. If $n=5$, then $\dim\Delta=1$ and $\Delta$ is CM if and only if it is connected or equivalently strongly connected (see [2, Excercise 5.1.26]). Hence again the result follows from (3.5). Suppose that $n\geq 7$ is odd. Assume that $e$ is a vertex of $\Delta$, that is, $e=uv$, for vertices $u$ and $v$ of $K_{n}$. Then $\mathrm{link}_{\Delta}(e)$ is the matching complex of $K_{n}-u-v\cong K_{n-2}$. Thus if we show that for $n=9$, $\Delta$ is not CM over any field and for $n=7$, $\Delta$ is CM exactly when $K$ has characteristic $\neq 3$, then the proof is concluded. But letting $n=7$, for all vertices $e$ of $\Delta$, $\mathrm{link}_{\Delta}(e)$ is CM. Hence $\Delta$ is CM if and only if $\widetilde{H}_{i}(\Delta;K)=0$ for all $i<\dim\Delta=2$. By Table 6.1 of [16], we have $\widetilde{H}_{1}(\Delta;\mathbb{Z})=\mathbb{Z}_{3}$ and $\widetilde{H}_{0}(\Delta;\mathbb{Z})=0$ and hence by the universal coefficient theorem, $\widetilde{H}_{1}(\Delta;K)=\mathbb{Z}_{3}\otimes K$ is zero if and only if $\mathrm{char}K\neq 3$. Similar argument using Table 6.1 of [16] shows that if $n=9$, then $\widetilde{H}_{2}(\Delta,K)\neq 0$ for every field $K$ and $\Delta$ is not CM over any field. ∎