betaFeedback

WorksMathematics

Perfect Matching Complexes of 3×2n3\times 2n Grid Graph

Abstract

The perfect matching complex of a simple graph GG is an abstract simplicial complex whose facets (maximal faces) are precisely the perfect matchings of GG. In this article, we study the topology of the perfect matching complex of the 3×2n3\times 2n grid graph and show that it is homotopy equivalent to a wedge of fn−1f_{n-1} copies of (n−1)(n-1)-dimensional spheres, where fkf_{k} denotes the kk-th Fibonacci number. This proves a particular case of the conjecture given by Chandrakar and Singh for perfect matching complex of grid graphs.

Introduction

Matchings in a graph are fundamental objects in graph theory and have been studied extensively from both combinatorial and algebraic points of view ([15]). The collections of matchings of a graph naturally give rise to a simplicial complex, called the matching complex. Over the years, the topology of matching complexes has been studied extensively, leading to several interesting results concerning their homotopy types and connectivity ([3, 6, 12, 13, 14, 17]). It is also worth mentioning that the occurrence of torsion in the homology groups of matching complexes highlights intriguing and subtle aspects of their topology ([7, 17, 16]).

Another interesting graph theoretic concept closely related to matchings is that of perfect matchings. Recently, Bayer et al. introduced the notion of the perfect matching complex of a graph, which is a subcomplex of its matching complex [4]. Since its introduction, the topology of perfect matching complexes has attracted considerable attention.

Bayer et al. initiated the study of perfect matching complexes of honeycomb graphs (or hexagonal grid graphs), with the broader aim of understanding the topology of matching complexes associated with these graphs. In particular, they studied the perfect matching complexes of hexagonal grid graphs. Their approach combines discrete Morse theory with combinatorial methods involving plane partitions and other topological techniques.

Subsequently, Chandrakar et al. studied perfect matching complexes of polygonal line tilings, with particular emphasis on the 2×n2 \times n grid graph, also known as the ladder graph [8]. They introduced the notion of bad matchings (non-extendable matchings), namely, matchings that cannot be extended to perfect matchings, and used this characterization together with discrete Morse theory and the fold lemma for independence complexes ([10, 11]) to determine the homotopy types of these complexes. More recently, Agarwal et al. investigated perfect matching complexes of Möbius ladder graphs [2]. Moreover, the matching complexes of 3×n3 \times n grid graphs have recently been studied by Chauhan et al. [9], who determined their topological connectivity.

2010 Mathematics Subject Classification. Primary: 05C70, 05E45; Secondary: 55P15.

Key words and phrases. Perfect matching complex, grid graphs, domino tiling.

Chandrakar is partially supported by a grant from the Infosys Foundation.

Chau is partially supported in part by the Pacific Institute for the Mathematical Sciences and a grant from the Simons Foundation International [SFI-MPS-T-Institutes-00020822, OY].

Goyal is partially supported by the NFSG grant N5/25/1045.

The approach based on bad matchings is particularly effective for the 2×n2 \times n grid graph. A bad matching (see [8 Definition 2.3]) is a matching that cannot be extended to a perfect matching but whose proper subsets can all be extended to perfect matchings. Thus, bad matchings correspond precisely to the minimal nonfaces of the perfect matching complex. Chandrakar et al. showed that every bad matching in the 2×n2 \times n grid graph consists of exactly two edges (see [8 Lemma 3.1]). Recall that a simplicial complex is called a flag complex if every minimal nonface has exactly two elements. Moreover, any two edges that share a vertex cannot belong to the same matching and hence form a minimal nonface of the perfect matching complex. Therefore, every minimal nonface of the perfect matching complex of the 2×n2 \times n grid graph has size two, and hence the complex is a flag complex. Consequently, it can be realized as the independence complex of a suitable graph, making results from the theory of independence complexes available for studying its topology.

The next natural case to consider in the family of m×nm \times n grid graphs is the 3×n3 \times n grid graph. Since each edge covers exactly two vertices, a graph admitting a perfect matching must have an even number of vertices. Thus, for the 3×n3 \times n grid graph to admit a perfect matching, nn must be even. Accordingly, in this article, we study the perfect matching complex of the 3×2n3 \times2n grid graph. However, extending the approach based on bad matchings from the 2×n2 \times n grid graph to this family is not straightforward. While every bad matching in the former consists of exactly two edges, bad matchings consisting of three edges can occur in the latter. Consequently, the perfect matching complex of the 3×2n3 \times2n grid graph need not be a flag complex and cannot, in general, be realized as the independence complex of a graph. Thus, the methods based on this correspondence do not directly extend to this case, making the computation of its homotopy type more challenging.

In [8], it is conjectured that the perfect matching complex of grid graphs is homotopy equivalent to a wedge of spheres. In this article, we settle this conjecture for the case 3×2n3 \times2n. More precisely, we prove the following result.

Theorem 1.1 (Theorem 3.5). The perfect matching complex of the $3 \times 2n$ grid graph is contractible for n=1n = 1, while for n≥2n \ge2, it is homotopy equivalent to a wedge of fn−1f_{n-1} spheres of dimension n−1n-1, where fkf_k denotes the kkth Fibonacci number, with $f_1 = f_2 = 1.

The article is organized as follows. Section 2 presents the necessary preliminaries, including the relevant definitions and results used throughout the article. In Section 3, we begin by formally defining the 3×2n3 \times2n grid graph and specifying the labelling of its vertices and edges. We then establish a few lemmas, which are used to prove our main theorem.

Preliminaries

Let GG be an undirected simple graph with vertex set V(G)V(G) and edge set E(G)E(G). Then a subset MM of E(G)E(G) is said to be a matching if endpoints of no two edges in MM are same. Furthermore, a matching MM is said to be a perfect matching if the set of end points of all the edges of MM equals V(G)V(G).

Example 2.1. Let GG be the 66-cycle graph with V(G)={x1,…,x6}V(G) = \{x_1,\ldots,x_6\} and E(G)={{xi,xi+1}∣i=1,…,6}E(G) = \{\{x_i,x_{i+1}\} \mid i = 1,\ldots,6\}, where x7=x1x_7 = x_1. The set of edges {{x1,x2},{x3,x4},{x5,x6}}\{\{x_1,x_2\},\{x_3,x_4\},\{x_5,x_6\}\} is a perfect matching since all vertices appear as endpoints. On the other hand, the matching {{x1,x2},{x4,x5}}\{\{x_1,x_2\},\{x_4,x_5\}\} is not perfect, despite it being a maximal matching, in the sense that no strictly larger matching contains it.

We begin by recalling some standard definitions concerning simplicial complexes. Let VV be a finite set. An (abstract) simplicial complex KK on the set VV is a family of subsets of VV with the property that whenever F∈KF \in K, every subset of FF is also contained in KK. The members of KK are called faces, and the inclusion-maximal faces are called facets.

If F={x1,x2,…,xn}⊂VF = \{x_1, x_2, \ldots, x_n\} \subset V is a facet, we denote by ⟨x1,x2,…,xn⟩\langle x_1, x_2, \ldots, x_n\rangle the subcomplex of KK given by the power set of FF.

The dimension of a face FF is given by dim⁡F=∣F∣−1\dim F = |F|-1, where ∣F∣|F| denotes the number of elements in FF, and in such a case FF is said to be (∣F∣−1)(|F|-1)-dimensional face of KK. A 0-dimensional face of KK is called a vertex of KK. The dimension of the simplicial complex KK is defined as the largest dimension among its faces, i.e.,

dim⁡(K)=max⁡F∈K{dim⁡(F)}.\dim(K) = \max_{F \in K}\{\dim(F)\}.

Let KK and LL be two simplicial complexes, then join of simplicial complexes KK and LL is defined as

K∗L={FK∪FL∣FK∈K,FL∈L}.K * L = \{F_K \cup F_L \mid F_K \in K, F_L \in L\}.

Let F∈KF \in K be a face. The link, lk⁡K(F)\operatorname{lk}_K(F) and deletion, del⁡K(F)\operatorname{del}_K(F) of FF in KK are subcomplexes of KK defined as

lk⁡K(F)={F′∈K:F∩F′=∅,F∪F′∈K},del⁡K(F)={F′∈K:F′∩F=∅}.\operatorname{lk}_K(F) = \{F' \in K : F \cap F' = \varnothing, F \cup F' \in K\}, \quad\operatorname{del}_K(F) = \{F' \in K : F' \cap F = \varnothing\}.

Let a,ba,b be two vertices that are not in KK. The suspension ΣK\Sigma K of KK is defined as

ΣK=K∪{σ∪{a},σ∪{b}∣σ∈K}.\Sigma K = K \cup\{\sigma\cup\{a\}, \sigma\cup\{b\} \mid\sigma\in K\}.

The wedge K∨LK \vee L is the simplicial complex obtained by identifying one vertex each from KK and LL.

Lemma 2.2 ([1 Proposition 3.1]). Let KK be a simplicial complex and vv be a vertex of KK. If the inclusion map lk⁡K(v)→del⁡K(v)\operatorname{lk}_K(v) \to\operatorname{del}_K(v) is null-homotopic, then

K≃del⁡K(v)∨Σ(lk⁡K(v)),K \simeq\operatorname{del}_K(v) \vee\Sigma(\operatorname{lk}_K(v)),

where ∨\vee denotes the wedge of spaces, and Σ\Sigma denotes the suspension of space.

The star of a face F∈KF \in K, st⁡K(F)\operatorname{st}_K(F) is a subcomplex of KK defined as

st⁡K(F)={F′∈K:F∪F′∈K}.\operatorname{st}_K(F) = \{F' \in K : F \cup F' \in K\}.

It is easy to verify that st⁡K(F)\operatorname{st}_K(F) is a contractible subcomplex of KK for any face FF of KK.

Lemma 2.3 ([5 Lemma 10.4]). Let Δ=Δ0∪Δ1∪⋯∪Δn\Delta= \Delta_0 \cup\Delta_1 \cup\cdots\cup\Delta_n be a simplicial complex with contractible subcomplexes Δi\Delta_i such that Δi∩Δj⊆Δ0\Delta_i \cap\Delta_j \subseteq\Delta_0 for $0 < i < j \leq n$, then

Δ≃⋁1≤i≤nΣ(Δ0∩Δi).\Delta\simeq\bigvee_{1 \leq i \leq n} \Sigma(\Delta_0 \cap\Delta_i).

In this article, we will use the particular case of the above theorem for n=1n = 1.

Main results

Let m,nm,n be natural numbers. The m×nm \times n grid graph Gm×nG_{m \times n} is a graph with the vertex set V(Gm×n)={pi,j:1≤i≤m,1≤j≤n}V(G_{m \times n}) = \{p_{i,j} : 1 \leq i \leq m, 1 \leq j \leq n\} and edges E(Gm×n)={{pi,j,pk,l}:∣i−k∣+∣j−l∣=1}E(G_{m \times n}) = \{\{p_{i,j}, p_{k,l}\} : |i-k|+|j-l|=1\}.

For a graph GG, let Mp(G)\mathcal{M}_p(G) denote the perfect matching complex of GG, i.e., the simplicial complex with facets being the perfect matchings of GG.

We denote the perfect matching complex Mp(G3×2n)\mathcal{M}_p(G_{3 \times2n}) by Δn\Delta_n. For 1≤j≤2n1 \leq j \leq2n, let aj,bja_j,b_j denote the edges {p1,j,p2,j}\{p_{1,j},p_{2,j}\}, {p2,j,p3,j}\{p_{2,j},p_{3,j}\}, respectively and for 1≤j≤2n−11 \leq j \leq2n-1, let cj={p1,j,p1,j+1}c_j = \{p_{1,j},p_{1,j+1}\}, dj={p2,j,p2,j+1}d_j = \{p_{2,j},p_{2,j+1}\} and ej={p3,j,p3,j+1}e_j = \{p_{3,j},p_{3,j+1}\}, see Figure 1.

Figure 1. The grid graph G3×2nG_{3\times2n}

Lemma 3.1. For n≥1n \ge1, we have

Δn=st⁡Δn(a2n)∪st⁡Δn(c2n−1).\Delta_n = \operatorname{st}_{\Delta_n}(a_{2n}) \cup\operatorname{st}_{\Delta_n}(c_{2n-1}).

Proof. Note that any perfect matching of G3×2nG_{3\times2n} should contain either c2n−1c_{2n-1} or a2na_{2n} to cover the vertex p1,2np_{1,2n}. Thus, every facet of Δn=Mp(G3×2n)\Delta_n = \mathcal{M}_p(G_{3\times2n}) will contain either c2n−1c_{2n-1} or a2na_{2n}. The result then follows from the definition of the star of a vertex.

For the ease of notation, we will write st⁡(v)\operatorname{st}(v) to denote the st⁡Δn(v)\operatorname{st}_{\Delta_n}(v). For n≥1n \ge1, let us denote the intersection of st⁡(a2n)\operatorname{st}(a_{2n}) and st⁡(c2n−1)\operatorname{st}(c_{2n-1}) by XnX_n, i.e.,

Xn=st⁡(a2n)∩st⁡(c2n−1).X_n = \operatorname{st}(a_{2n}) \cap\operatorname{st}(c_{2n-1}).

Let σ\sigma be a facet of st⁡(a2n)\operatorname{st}(a_{2n}), then the edges b2nb_{2n}, c2n−1c_{2n-1}, and d2n−1d_{2n-1} being adjacent to a2na_{2n}, we get σ∩{b2n,c2n−1,d2n−1}=∅\sigma\cap\{b_{2n}, c_{2n-1}, d_{2n-1}\} = \varnothing. Moreover, to cover the vertex p3,2np_{3,2n}, the edge e2n−1e_{2n-1} should belong to σ\sigma, implying that e2n−2e_{2n-2} and b2n−1b_{2n-1} cannot belong to σ\sigma. This implies that

σ∩{b2n,b2n−1,c2n−1,d2n−1,e2n−2}=∅.\sigma\cap\{b_{2n}, b_{2n-1}, c_{2n-1}, d_{2n-1}, e_{2n-2}\} = \varnothing.

Similarly, if σ\sigma is a facet of st⁡Δn(c2n−1)\operatorname{st}_{\Delta_n}(c_{2n-1}), then the edges a2na_{2n}, a2n−1a_{2n-1}, and c2n−2c_{2n-2} will not be in σ\sigma as they are adjacent to c2n−1c_{2n-1}, that is, σ∩{a2n,a2n−1,c2n−2}=∅\sigma\cap\{a_{2n}, a_{2n-1}, c_{2n-2}\} = \varnothing.

Thus, if σ∈st⁡(a2n)∩st⁡(c2n−1)\sigma\in\operatorname{st}(a_{2n}) \cap\operatorname{st}(c_{2n-1}), then

σ∩{a2n,a2n−1,b2n,b2n−1,c2n−1,c2n−2,d2n−1,e2n−2}=∅.(1)\sigma\cap\{a_{2n}, a_{2n-1}, b_{2n}, b_{2n-1}, c_{2n-1}, c_{2n-2}, d_{2n-1}, e_{2n-2}\} = \varnothing. \tag*{(1)}

If τ\tau is a facet of XnX_n, then since τ∈st⁡(c2n−1)\tau\in\operatorname{st}(c_{2n-1}), τ∪{c2n−1}∈Δn\tau\cup\{c_{2n-1}\} \in\Delta_n. Let τc2n−1\tau_{c_{2n-1}} be a facet of Δn=Mp(G3×2n)\Delta_n = \mathcal{M}_p(G_{3\times2n}) containing τ∪{c2n−1}\tau\cup\{c_{2n-1}\}, then τc2n−1\tau_{c_{2n-1}} is a perfect matching containing c2n−1c_{2n-1}, extending the facet τ∈Xn\tau\in X_n. Similarly, let τa2n\tau_{a_{2n}} be a perfect matching of Δn=Mp(G3×2n)\Delta_n = \mathcal{M}_p(G_{3\times2n}) containing a2na_{2n}, extending the facet τ∈Xn\tau\in X_n.

Lemma 3.2. If τ\tau is a facet of XnX_n then d2n−2d_{2n-2} and e2n−1e_{2n-1} cannot appear simultaneously in τ\tau, that is {d2n−2,e2n−1}⊈τ\{d_{2n-2}, e_{2n-1}\} \not\subseteq\tau.

Proof. On the contrary, if {d2n−2,e2n−1}⊆τ\{d_{2n-2}, e_{2n-1}\} \subseteq\tau, then τc2n−1\tau_{c_{2n-1}} is a perfect matching containing {c2n−1,d2n−2,e2n−1}\{c_{2n-1}, d_{2n-2}, e_{2n-1}\}. Hence τc2n−1∩{d2n−1,a2n,b2n}=∅\tau_{c_{2n-1}} \cap\{d_{2n-1}, a_{2n}, b_{2n}\} = \varnothing, which implies that the vertex p2,2np_{2,2n} is uncovered, contradicting the fact that τc2n−1\tau_{c_{2n-1}} is a perfect matching.

For 1≤k≤n−11 \le k \le n - 1, let AkA_k be the subcomplex of Δn\Delta_n given by

Ak={⟨d2n−2,d2n−4,…,d4,d2⟩if k=1,⟨d2n−2,d2n−4,…,d2k+2,d2k⟩∗Δk−1if 2≤k≤n−1.A_k = \begin{cases} \langle d_{2n-2}, d_{2n-4}, \ldots, d_4, d_2\rangle& \text{if } k = 1,\\ \langle d_{2n-2}, d_{2n-4}, \ldots, d_{2k+2}, d_{2k}\rangle* \Delta_{k-1} & \text{if } 2 \le k \le n - 1. \end{cases}

Lemma 3.3. If τ\tau is a facet of XnX_n and if d2n−2∈τd_{2n-2} \in\tau, then τ∈⋃i=1n−1Ai\tau\in\bigcup_{i=1}^{n-1} A_i ::

Proof. Since d2n−2∈τd_{2n-2} \in\tau, we have

τ∩{a2n−1,a2n−2,b2n−1,b2n−2,d2n−3,d2n−1}=∅.(2)\tau\cap\{a_{2n-1},a_{2n-2},b_{2n-1},b_{2n-2},d_{2n-3},d_{2n-1}\}=\varnothing. \tag*{(2)}

By Lemma 3.2, we also have e2n−1∉τe_{2n-1} \notin\tau.

For 2≤i≤n2 \leq i \leq n, we define

Ti={{a2i−2,a2i−3,b2i−2,b2i−3,c2i−3,d2i−3,e2i−3}for i=2,{a2i−2,a2i−3,b2i−2,b2i−3,c2i−4,c2i−3,d2i−3,e2i−4,e2i−3}otherwise.T_i = \begin{cases} \{a_{2i-2},a_{2i-3},b_{2i-2},b_{2i-3},c_{2i-3},d_{2i-3},e_{2i-3}\} & \text{for } i=2,\\ \{a_{2i-2},a_{2i-3},b_{2i-2},b_{2i-3},c_{2i-4},c_{2i-3},d_{2i-3},e_{2i-4},e_{2i-3}\} & \text{otherwise.} \end{cases}

We claim that τ∩Tn=∅\tau\cap T_n = \varnothing. Since τc2n−1\tau_{c_{2n-1}} is a perfect matching containing d2n−2d_{2n-2}, in order to cover the vertex p1,2n−2p_{1,2n-2} it should contain c2n−3c_{2n-3}, and thus a2n−3,c2n−4∉τc2n−1a_{2n-3},c_{2n-4} \notin\tau_{c_{2n-1}}, therefore not in τ\tau. Similarly, since τa2n\tau_{a_{2n}} is a perfect matching containing d2n−2d_{2n-2}, to cover the vertex p1,2n−1p_{1,2n-1} it should contain c2n−2c_{2n-2}, hence c2n−3∉τa2nc_{2n-3} \notin\tau_{a_{2n}}, and thus not in τ\tau either. In order to cover the vertex p3,2n−2p_{3,2n-2}, the perfect matching τc2n−1\tau_{c_{2n-1}} should contain e2n−2e_{2n-2}, hence e2n−3∉τc2n−1e_{2n-3} \notin\tau_{c_{2n-1}} and the perfect matching τa2n\tau_{a_{2n}} should contain e2n−3e_{2n-3}, hence e2n−4,b2n−3∉τa2ne_{2n-4},b_{2n-3} \notin\tau_{a_{2n}}. This implies e2n−3,e2n−4,b2n−3∉τe_{2n-3},e_{2n-4},b_{2n-3} \notin\tau, hence we have τ∩Tn=∅\tau\cap T_n = \varnothing.

We now examine the remaining dd-edges. Since d2n−2∈τd_{2n-2} \in\tau and τ∩Tn=∅\tau\cap T_n = \varnothing, the next dd-edge to be considered is d2n−4d_{2n-4}. If d2n−4∉τd_{2n-4} \notin\tau, then τ∈⟨d2n−2⟩∗Δn−1=An−1\tau\in\langle d_{2n-2}\rangle* \Delta_{n-1}=A_{n-1}. If d2n−4∈τd_{2n-4} \in\tau, then the above argument can be repeated with the indices shifted by two. Thus, τ∩Tn−1=∅\tau\cap T_{n-1} = \varnothing. Since τ∩Tn=∅\tau\cap T_n = \varnothing, we get τ∩(Tn∪Tn−1)=∅\tau\cap(T_n \cup T_{n-1}) = \varnothing. Moreover, as before, if d2n−6∉τd_{2n-6} \notin\tau, then τ∈⟨d2n−2,d2n−4⟩∗Δn−2=An−2\tau\in\langle d_{2n-2},d_{2n-4}\rangle* \Delta_{n-2}=A_{n-2}. Proceeding similarly, if d2n−2,d2n−4…,d2n−2k+2,d2n−2k∈τd_{2n-2},d_{2n-4}\ldots,d_{2n-2k+2},d_{2n-2k} \in\tau where 1≤k≤n−11 \leq k \leq n-1, then

τ∩(⋃i=0k−1Tn−i)=∅.\tau\cap\left(\bigcup_{i=0}^{k-1}T_{n-i}\right)=\varnothing.

If d2n−2(k−1)∉τd_{2n-2(k-1)} \notin\tau, then τ∈An−k\tau\in A_{n-k}. This shows that τ∈⋃i=1n−1Ai\tau\in\bigcup_{i=1}^{n-1} A_i.

With the two lemmas above, we can prove the following result.

Lemma 3.4. For n≥2n \geq2, we have,

Xn=(⋃i=1n−1Ai)∪(⟨e2n−1⟩∗Δn−1),X_n=\left(\bigcup_{i=1}^{n-1}A_i\right)\cup\left(\langle e_{2n-1}\rangle*\Delta_{n-1}\right),

where Ak={⟨d2n−2,d2n−4,…,d4,d2⟩if k=1,⟨d2n−2,d2n−4,…,d2k+2,d2k⟩∗Δk−1if 2≤k≤n−1.A_k=\begin{cases} \langle d_{2n-2},d_{2n-4},\ldots,d_4,d_2\rangle& \text{if } k=1,\\ \langle d_{2n-2},d_{2n-4},\ldots,d_{2k+2},d_{2k}\rangle*\Delta_{k-1} & \text{if } 2\leq k\leq n-1. \end{cases}

Proof. We first show that, Xn⊆(⋃i=1n−1Ai)∪(⟨e2n−1⟩∗Δn−1)X_n \subseteq\left(\bigcup_{i=1}^{n-1}A_i\right)\cup\left(\langle e_{2n-1}\rangle*\Delta_{n-1}\right). Let τ\tau be a facet of XnX_n, by Lemma 3.2, since e2n−1e_{2n-1} and d2n−2d_{2n-2} cannot simultaneously belong to τ\tau. We have

Case 1: Consider the case when e2n−1∈τe_{2n-1} \in\tau.

Observe that for τc2n−1\tau_{c_{2n-1}}, we have c2n−1,e2n−1∈τc2n−1c_{2n-1},e_{2n-1}\in\tau_{c_{2n-1}}. In order to cover p2,2np_{2,2n}, it follows that d2n−1∈τc2n−1d_{2n-1}\in\tau_{c_{2n-1}}, hence τc2n−1∩{d2n−2}=∅\tau_{c_{2n-1}}\cap\{d_{2n-2}\}=\varnothing. This along with Equation (1), implies that

τ∩{a2n,b2n,c2n−1,a2n−1,b2n−1,d2n−1,d2n−2,c2n−2,e2n−2}=∅.\tau\cap\{a_{2n},b_{2n},c_{2n-1},a_{2n-1},b_{2n-1},d_{2n-1},d_{2n-2},c_{2n-2},e_{2n-2}\}=\varnothing.

Hence we have τ∈⟨e2n−1⟩∗Δn−1\tau\in\langle e_{2n-1}\rangle*\Delta_{n-1}.

Case 2: Suppose e2n−1∉τe_{2n-1} \notin\tau. Since every facet in st⁡(a2n)\operatorname{st}(a_{2n}) contains e2n−1e_{2n-1}, we have e2n−1∉τc2n−1e_{2n-1}\notin\tau_{c_{2n-1}}. If d2n−2∉τd_{2n-2}\notin\tau, Equation (1) implies τ∈Δn−1\tau\in\Delta_{n-1}, in which case τ∪{e2n−1}∈Xn\tau\cup\{e_{2n-1}\}\in X_n, implies

that τ\tau is not a facet of XnX_n. Hence d2n−2∈τd_{2n-2} \in\tau. Then by Lemma 3.3, we have τ∈⋃i=1n−1Ai\tau\in\bigcup_{i=1}^{n-1} \mathcal{A}_i.

This shows that Xn⊆(⋃i=1n−1Ai)∪(⟨e2n−1⟩∗Δn−1)X_n \subseteq\left(\bigcup_{i=1}^{n-1} \mathcal{A}_i\right) \cup(\langle e_{2n-1}\rangle* \Delta_{n-1}).

We now prove the reverse inclusion. Let τ∈(⋃i=1n−1Ai)∪(⟨e2n−1⟩∗Δn−1)\tau\in\left(\bigcup_{i=1}^{n-1} \mathcal{A}_i\right) \cup(\langle e_{2n-1}\rangle* \Delta_{n-1}) be a facet. We need to show that τ∈Xn=st⁡(c2n−1)∩st⁡(a2n)\tau\in X_n = \operatorname{st}(c_{2n-1}) \cap\operatorname{st}(a_{2n}).

If τ∈⟨e2n−1⟩∗Δn−1\tau\in\langle e_{2n-1}\rangle* \Delta_{n-1}, then τ∪{c2n−1,d2n−1}\tau\cup\{c_{2n-1}, d_{2n-1}\} is a perfect matching containing c2n−1c_{2n-1} and hence belongs to st⁡(c2n−1)\operatorname{st}(c_{2n-1}). Similarly, τ∪{a2n−1,a2n}\tau\cup\{a_{2n-1}, a_{2n}\} is a perfect matching that contains a2na_{2n} and hence belongs to st⁡(a2n)\operatorname{st}(a_{2n}). This implies τ∈Xn\tau\in X_n.

If τ∈⋃i=1n−1Ai\tau\in\bigcup_{i=1}^{n-1} \mathcal{A}_i, then τ1\tau_1 defined as

τ1={τ∪{b1,b2n,c1,c3,…,c2n−1,e2,e4,…,e2n−2}if τ∈A1=⟨d2n−2,d2n−4,…,d2⟩τ∪{b2i−1,b2n,c2i−1,c2i+1,…,c2n−1,e2i,e2i+2,…,e2n}if τ∈Ai,2≤i≤n−1,\tau_1 = \begin{cases} \tau\cup\{b_1, b_{2n}, c_1, c_3, \ldots, c_{2n-1}, e_2, e_4, \ldots, e_{2n-2}\} & \text{if } \tau\in\mathcal{A}_1 = \langle d_{2n-2}, d_{2n-4}, \ldots, d_2\rangle\\ \tau\cup\{b_{2i-1}, b_{2n}, c_{2i-1}, c_{2i+1}, \ldots, c_{2n-1}, e_{2i}, e_{2i+2}, \ldots, e_{2n}\} & \text{if } \tau\in\mathcal{A}_i, 2 \le i \le n-1, \end{cases}

is a perfect matching containing c2n−1c_{2n-1} and hence belongs to st⁡(c2n−1)\operatorname{st}(c_{2n-1}). Similarly τ2\tau_2 defined as

τ2={τ∪{a1,a2n,c2,c4,…,c2n−2,e1,e3,…,e2n−1}if τ∈A1=⟨d2n−2,d2n−4,…,d2⟩τ∪{a2i−1,a2n,c2i,c2i+2,…,c2n−2,e2i−1,e2i+1,…,e2n−1}if τ∈Ai,2≤i≤n−1,\tau_2 = \begin{cases} \tau\cup\{a_1, a_{2n}, c_2, c_4, \ldots, c_{2n-2}, e_1, e_3, \ldots, e_{2n-1}\} & \text{if } \tau\in\mathcal{A}_1 = \langle d_{2n-2}, d_{2n-4}, \ldots, d_2\rangle\\ \tau\cup\{a_{2i-1}, a_{2n}, c_{2i}, c_{2i+2}, \ldots, c_{2n-2}, e_{2i-1}, e_{2i+1}, \ldots, e_{2n-1}\} & \text{if } \tau\in\mathcal{A}_i, 2 \le i \le n-1, \end{cases}

is a perfect matching containing a2na_{2n}, therefore τ2∈st⁡(a2n)\tau_2 \in\operatorname{st}(a_{2n}) and hence τ∈Xn\tau\in X_n. From the above discussion, we have (⋃i=1n−1Ai)∪(⟨e2n−1⟩∗Δn−1)⊆Xn\left(\bigcup_{i=1}^{n-1} \mathcal{A}_i\right) \cup(\langle e_{2n-1}\rangle* \Delta_{n-1}) \subseteq X_n. This completes the proof. □

Theorem 3.5. Let Δn\Delta_n be the perfect matching complex of 3×2n3 \times2n grid graph, then Δ1\Delta_1 is contractible, and for n≥2n \ge2,

Δn≃⋁fn−1Sn−1\Delta_n \simeq\bigvee_{f_{n-1}} S^{n-1}

where fkf_k denotes the kk-th Fibonacci number with f1=f2=1f_1 = f_2 = 1.

Proof. Note that since Δ1=⟨a1,a2,e1⟩∪⟨b1,b2,c1⟩∪⟨c1,d1,e1⟩\Delta_1 = \langle a_1, a_2, e_1\rangle\cup\langle b_1, b_2, c_1\rangle\cup\langle c_1, d_1, e_1\rangle, it is easy to see that Δ1\Delta_1 is contractible. For n≥2n \ge2, from Lemma 3.1, we get Δn=st⁡(a2n)∪st⁡(c2n−1)\Delta_n = \operatorname{st}(a_{2n}) \cup\operatorname{st}(c_{2n-1}). Since both st⁡(a2n)\operatorname{st}(a_{2n}) and st⁡(c2n−1)\operatorname{st}(c_{2n-1}) are contractible, we apply Lemma 2.3 to get

Δn=Σ(st⁡(a2n)∩st⁡(c2n−1)).(3)\Delta_n = \Sigma\left(\operatorname{st}(a_{2n}) \cap\operatorname{st}(c_{2n-1})\right). \tag*{(3)}

Therefore, it suffices to determine the homotopy type Xn=st⁡(a2n)∩st⁡(c2n−1)X_n = \operatorname{st}(a_{2n}) \cap\operatorname{st}(c_{2n-1}). From Lemma 3.4, we have

Xn=(⋃i=1n−1Ai)∪(⟨e2n−1⟩∗Δn−1),(4)X_n = \left(\bigcup_{i=1}^{n-1} \mathcal{A}_i\right) \cup(\langle e_{2n-1}\rangle* \Delta_{n-1}), \tag*{(4)}

where,

Ai={⟨d2,d4,…,d2n−2⟩if i=1,⟨d2i,d2i+2,…,d2n−2⟩∗Δi−1if 2≤i≤n−1.\mathcal{A}_i = \begin{cases} \langle d_2, d_4, \ldots, d_{2n-2}\rangle& \text{if } i=1, \\ \langle d_{2i}, d_{2i+2}, \ldots, d_{2n-2}\rangle* \Delta_{i-1} & \text{if } 2 \le i \le n-1. \end{cases}

Using Equation (4), we obtain X2=⟨d2⟩∪(⟨e3⟩∗Δ1)X_2 = \langle d_2\rangle\cup(\langle e_3\rangle* \Delta_1). Since both components are contractible and disjoint, it follows that X2≃S0X_2 \simeq S^0. Hence,

Δ2=ΣX2≃S1.\Delta_2 = \Sigma X_2 \simeq S^1.

Let n≥3n \ge3 and τ∈Xn\tau\in X_n be a facet. It is easy to see that if d2n−2∉τd_{2n-2} \notin\tau, then τ∈del⁡Xn(d2n−2)\tau\in\operatorname{del}_{X_n}(d_{2n-2}), else τ∖{d2n−2}∈del⁡Xn(d2n−2)\tau\setminus\{d_{2n-2}\} \in\operatorname{del}_{X_n}(d_{2n-2}) is a facet. This along with Equation (4) implies

del⁡Xn(d2n−2)=(⋃i=1n−1Ai′)∪(⟨e2n−1⟩∗Δn−1)\operatorname{del}_{X_n}(d_{2n-2}) = \left(\bigcup_{i=1}^{n-1} \mathcal{A}'_i\right) \cup\left(\langle e_{2n-1}\rangle* \Delta_{n-1}\right)

where Ai′\mathcal{A}'_i is obtained by removing d2n−2d_{2n-2} from every facet of Ai\mathcal{A}_i. That is,

Ai′={⟨d2,d4,…,d2n−4⟩if i=1,⟨d2i,d2i+2,…,d2n−4⟩∗Δi−1if 2≤i≤n−2,Δn−2if i=n−1.\mathcal{A}'_i = \begin{cases} \langle d_2,d_4,\ldots,d_{2n-4}\rangle& \text{if } i=1,\\ \langle d_{2i},d_{2i+2},\ldots,d_{2n-4}\rangle* \Delta_{i-1} & \text{if } 2 \le i \le n-2,\\ \Delta_{n-2} & \text{if } i=n-1. \end{cases}

Since di∈Δn−1d_i \in\Delta_{n-1} for i≤2n−3i \le2n-3, it follows that Ak′\mathcal{A}'_k is a subcomplex of Δn−1\Delta_{n-1} for 1≤k≤n−11 \le k \le n-1. Therefore, del⁡Xn(d2n−2)=⟨e2n−1⟩∗Δn−1\operatorname{del}_{X_n}(d_{2n-2}) = \langle e_{2n-1}\rangle* \Delta_{n-1}, implying that del⁡Xn(d2n−2)\operatorname{del}_{X_n}(d_{2n-2}) is contractible. Hence, the inclusion lk⁡Xn(d2n−2)↪del⁡Xn(d2n−2)\operatorname{lk}_{X_n}(d_{2n-2}) \hookrightarrow\operatorname{del}_{X_n}(d_{2n-2}) is null-homotopic. Therefore by Lemma 2.2, Xn≃del⁡Xn(d2n−2)∨Σ(lk⁡Xn(d2n−2))≃Σ(lk⁡Xn(d2n−2))X_n \simeq\operatorname{del}_{X_n}(d_{2n-2}) \vee\Sigma(\operatorname{lk}_{X_n}(d_{2n-2})) \simeq\Sigma(\operatorname{lk}_{X_n}(d_{2n-2})), and hence Δn≃Σ2(lk⁡Xn(d2n−2))\Delta_n \simeq\Sigma^2(\operatorname{lk}_{X_n}(d_{2n-2})). Therefore it suffices to determine the homotopy type of lk⁡Xn(d2n−2)\operatorname{lk}_{X_n}(d_{2n-2}).

For n≥3n \ge3, let Zn=lk⁡Xn(d2n−2)Z_n = \operatorname{lk}_{X_n}(d_{2n-2}). From Equation (4), we see that

Zn=lk⁡Xn(d2n−2)=⋃i=1n−1Ai′=Δn−2∪(⟨d2n−4⟩∗⋃i=1n−2Ai′′)(5)Z_n = \operatorname{lk}_{X_n}(d_{2n-2}) = \bigcup_{i=1}^{n-1} \mathcal{A}'_i = \Delta_{n-2} \cup\left(\langle d_{2n-4}\rangle* \bigcup_{i=1}^{n-2} \mathcal{A}''_i\right) \tag*{(5)}

where Ai′\mathcal{A}'_i is as before, and Ai′′\mathcal{A}''_i is obtained by removing d2n−4d_{2n-4} from every facet of Ai′\mathcal{A}'_i, for 1≤i≤n−21 \le i \le n-2.

When n=3n=3, Z3=Δ1∪⟨d2⟩Z_3 = \Delta_1 \cup\langle d_2\rangle. Since both of these are contractible and disjoint, we get Z3≃S0Z_3 \simeq S^0. Therefore,

Δ3≃Σ2Z3≃S2.\Delta_3 \simeq\Sigma^2 Z_3 \simeq S^2.

Observe that, for n≥4n \ge4, ⋃i=1n−2Ai′′\bigcup_{i=1}^{n-2} \mathcal{A}''_i is precisely Zn−1Z_{n-1}. Therefore, the expression for ZnZ_n, for n≥4n \ge4 simplifies to

Zn=Δn−2∪(⟨d2n−4⟩∗Zn−1) and Δn≃Σ2Zn.(6)Z_n = \Delta_{n-2} \cup\left(\langle d_{2n-4}\rangle* Z_{n-1}\right) \text{ and } \Delta_n \simeq\Sigma^2 Z_n. \tag*{(6)}

We now examine the link and deletion of d2n−4d_{2n-4} in ZnZ_n. Similar argument used before for lk⁡Xn(d2n−2)\operatorname{lk}_{X_n}(d_{2n-2}) and del⁡Xn(d2n−2)\operatorname{del}_{X_n}(d_{2n-2}) implies that lk⁡Zn(d2n−4)=Zn−1\operatorname{lk}_{Z_n}(d_{2n-4}) = Z_{n-1} and del⁡Zn(d2n−4)=Δn−2\operatorname{del}_{Z_n}(d_{2n-4}) = \Delta_{n-2}, respectively.

From Equation (5) and Equation (4), it follows that Zn−1Z_{n-1} is a subcomplex of Xn−2X_{n-2}. Since the inclusion of st⁡Δn−2(a2n−4)\operatorname{st}_{\Delta_{n-2}}(a_{2n-4}) in Δn−2\Delta_{n-2} is null-homotopic, this implies that composition of inclusions

Zn−1↪Xn−2↪st⁡Δn−2(a2n−4)↪Δn−2Z_{n-1} \hookrightarrow X_{n-2} \hookrightarrow\operatorname{st}_{\Delta_{n-2}}(a_{2n-4}) \hookrightarrow\Delta_{n-2}

is null-homotopic. However, Δn−2=del⁡Zn(d2n−4)\Delta_{n-2} = \operatorname{del}_{Z_n}(d_{2n-4}). Therefore, lk⁡Zn(d2n−4)↪del⁡Zn(d2n−4)\operatorname{lk}_{Z_n}(d_{2n-4}) \hookrightarrow\operatorname{del}_{Z_n}(d_{2n-4}) is null-homotopic. Then, by Lemma 2.2, we have

Zn≃del⁡Zn(d2n−4)∨Σlk⁡Zn(d2n−4)≃Δn−2∨ΣZn−1.(7)Z_n \simeq\operatorname{del}_{Z_n}(d_{2n-4}) \vee\Sigma\operatorname{lk}_{Z_n}(d_{2n-4}) \simeq\Delta_{n-2} \vee\Sigma Z_{n-1}. \tag*{(7)}

Therefore, using Equation (7) and Equation (6), we get

Δn≃Σ2Zn≃Σ2(Δn−2∨ΣZn−1)≃Σ2Δn−2∨Σ(Σ2Zn−1)≃Σ2Δn−2∨ΣΔn−1.\begin{aligned} \Delta_n &\simeq\Sigma^2 Z_n \\ &\simeq\Sigma^2\left(\Delta_{n-2} \vee\Sigma Z_{n-1}\right) \\ &\simeq\Sigma^2\Delta_{n-2} \vee\Sigma\left(\Sigma^2 Z_{n-1}\right) \\ &\simeq\Sigma^2\Delta_{n-2} \vee\Sigma\Delta_{n-1}. \end{aligned}

The above expression along with Δ2≃S1\Delta_2 \simeq S^1 and Δ3≃S2\Delta_3 \simeq S^2 implies that for n≥2n \ge2, we have

Δn≃⋁fn−1Sn−1.\Delta_n \simeq\bigvee_{f_{n-1}} S^{n-1}.

This completes the proof. □

Concluding remarks

The appearance of Fibonacci numbers in our result is interesting in view of their connection with perfect matchings of ladder graphs. It is well known that the perfect matchings of the 2×n2 \times n grid graph are in bijective correspondence with domino tilings of a 2×n2 \times n rectangular board, and the number of all the domino tilings is given by the Fibonacci number fn+1f_{n+1}. Here, each vertex of the grid graph is viewed as the centre of a square in the board. However, our result reveals a different occurrence of Fibonacci numbers, as they determine the number of spheres appearing in the homotopy decomposition of the perfect matching complex of the 3×2n3 \times2n grid graph. This makes the result particularly interesting, as it shows that Fibonacci numbers arise not only in counting perfect matchings, but also in describing the topology of the associated complex. This leads to the following question.

Question 3.6. Which graph theoretic property leads to the occurrence of the Fibonacci sequence in the homotopy type of the perfect matching complex of the 3×2n3 \times2n grid graph?

Acknowledgements

The project started at the Frontiers of Combinatorics: Topology, Algebra and Data-Driven Insights conference hosted by the Birla Institute of Technology & Science (BITS), Pilani. We would like to thank BITS Pilani for providing us with wonderful facilities leading to a productive stay. Chandrakar also acknowledges Dr. Anurag Singh for his helpful suggestions during the early stages of this work. Chennai Mathematical Institute, Siruseri, Tamil Nadu, India. Email address: [email protected]

University of Manitoba, Winnipeg, Manitoba, Canada. Email address: [email protected]

Birla Institute of Technology and Science Pilani, Pilani Campus, Rajasthan, India Email address: [email protected]

UPES Dehradun, India Email address: [email protected]

Indian Institute of Science Education and Research, Tirupati, Andhra Pradesh, India. Email address: [email protected]

References

  1. [1]Michal Adamaszek. “Splittings of independence complexes and the powers of cycles”. In: Journal of Combinatorial Theory, Series A 119.5 (2012), pp. 1031–1047.arxiv.org/abs/1106.6250
  2. [2]Anshu Agarwal and Biplab Basak. The Homotopy Types of the Independence and Perfect Matching Complexes of Möbius and Circular Ladder Graphs. 2026.arxiv.org/abs/2608.30601
  3. [4]Margarete Bayer, Marija Jelić Milutinović, and Julianne Vega. “Perfect matching complexes of honeycomb graphs”. In: Electron. J. Combin. 30.2 (2023), Paper No. 2.45, 23.arxiv.org/abs/2209.02803
  4. [5]A. Björner. “Topological methods”. In: Handbook of combinatorics, Vol. 1, 2. Elsevier Sci. B. V., Amsterdam, 1995, pp. 1819–1872.
  5. [8]Himanshu Chandrakar and Anurag Singh. “Perfect Matching Complexes of Polygonal Line Tilings”. In: Annals of Combinatorics 29 (2025), pp. 1211–1233.DOI
  6. [9]Pratiksha Chauhan, Anchal Sharma, and Samir Shukla. Homology of matching complexes of 3 × n grid graphs. 2026.arxiv.org/abs/2609.27366

Paper details

vlnc:W_hzywp755
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents