pith. sign in

arxiv: 2403.15298 · v2 · submitted 2024-03-22 · 🧮 math.CO

On the matching complexes of categorical product of path graphs

Raju Kumar Gupta , Sourav Sarkar , Sagar S. Sawant , Samir Shukla This is my paper

Pith reviewed 2026-05-24 02:53 UTC · model grok-4.3

classification 🧮 math.CO
keywords matching complexcategorical productpath graphhomotopy equivalencewedge of spheressimplicial complex
0
0 comments X

The pith

Matching complexes of the categorical product P_n × P_m are homotopy equivalent to wedges of spheres when 3 ≤ m ≤ 5.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the matching complex of P_n × P_m is homotopy equivalent to a wedge of spheres for all n at least 2 and m between 3 and 5. This extends the known case for m equal to 2. The result gives the precise number and dimensions of the spheres when m is 3, and the lowest and highest dimensions when m is 4 or 5. Such topological descriptions matter because matching complexes encode sets of disjoint edges and appear across combinatorics, geometry, and algebra.

Core claim

The authors show that for n ≥ 2 and 3 ≤ m ≤ 5 the matching complex M(P_n × P_m) is homotopy equivalent to a wedge of spheres. When m equals 3 they compute the exact number and dimension of each sphere in the wedge. When m equals 4 or 5 they give the minimum and maximum dimensions of the spheres that appear.

What carries the argument

The matching complex M(G), the simplicial complex whose faces are the matchings (sets of pairwise disjoint edges) of the graph G.

If this is right

  • For m=3 the explicit sphere counts determine the homology groups of the complex in every degree.
  • The dimension bounds for m=4 and 5 restrict the possible non-vanishing homology groups.
  • The same reduction technique applies uniformly once m is fixed in {3,4,5}, independent of n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The pattern suggests the homotopy type may simplify to a wedge of spheres for at least one larger value of m.
  • The explicit descriptions could be used to compare the topology of categorical products against other graph products such as Cartesian or strong products.

Load-bearing premise

The combinatorial reductions that establish the homotopy equivalence for a fixed small m continue to work without change as n grows arbitrarily large.

What would settle it

An explicit computation of the homology of M(P_n × P_3) for some n larger than those checked in the paper that yields a non-zero group outside the predicted sphere dimensions.

Figures

Figures reproduced from arXiv: 2403.15298 by Raju Kumar Gupta, Sagar S. Sawant, Samir Shukla, Sourav Sarkar.

Figure 1
Figure 1. Figure 1: Cartesian and categorical product of P7 and P5 Theorem 1.3. For n ≥ 2 and 3 ≤ m ≤ 5, M(Pn × Pm) is homotopy equivalent to a wedge of spheres. We explicitly compute the dimension and number of spheres in the homotopy type of M(Pn × P3) (see Theorem 5.5). For m ∈ {4, 5}, we give the minimum and maximum dimension of spheres appearing in the wedge in homotopy type of M(Pn × Pm). Proposition 1.4. For n ≥ 3, let… view at source ↗
Figure 2
Figure 2. Figure 2: Γn,5 Definition 3.2. For n ≥ 0, Λn,5 is a graph whose vertex set and edge set is given by V (Λn,5) ={l1, l2, l3, l4} ∪ V (Γn,5), E(Λn,5) ={l1l2, l2l3, l3l4, g11l1, g11l2, g21l1, g21l2, g31l3, g31l4, g41l3, g41l4} ∪ E(Γn,5). 1 2 n g41 g42 g43 g44 g45 · · · g4 2n+1 g2 2n+1 g3 2n+1 g22 g32 g24 g34 g21 g31 g23 g33 g25 g35 g11 g12 g13 g14 g15 · · · g1 2n+1 l1 l2 l3 l4 (b) Λn,5, for n ≥ 1 g11 g21 g31 g41 l1 l2 l… view at source ↗
Figure 3
Figure 3. Figure 3: Λn,5 Definition 3.3. For n ≥ 0, Γ˜ n,5 is a graph whose vertex set and edge set is given by V (Γ˜ n,5) = V (Γn,5) ∪ {g1 2n+2, g2 2n+2, g3 2n+2, g4 2n+2} E(Γ˜ n,5) = E(Γn,5) ∪ {gi 2n+1gi 2n+2 | i = 1, 2, 3, 4} ∪ {gi 2n+2gi+1 2n+2 | i = 1, 2, 3} ∪ {g2 2n+1g3 2n+2, g3 2n+1g2 2n+2}. 1 2 n g42 g43 g44 g45 g22 g32 g24 g34 g23 g33 g25 g35 g11 g12 g13 g14 g15 g21 g31 g41 · · · · · · g1 2n+2 g2 2n+2 g3 2n+2 g4 2n+2… view at source ↗
Figure 4
Figure 4. Figure 4: Γ˜ n,5 In the following section, we compute the homotopy type of Ind(Γn,5) and Ind(Λn,5), and the homotopy type of Ind(Γ˜ n,5) is computed in Section 3.2. Finally, we give the minimum and maximum dimension of spheres in the homotopy type of M(Pn × P5) in Section 3.3 [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: An,5 Claim 3.4. Ind(A0,5) ≃ S 1 ∨ S 1 ∨ S 1 . Proof. Since a1 is a simplicial vertex in the graph A0,5 with N(a1) = {g11, g21}, using Proposition 2.4 we get Ind(A0,5) ≃ ΣInd(A0,5 \ N[g11]) ∨ ΣInd(A0,5 \ N[g21]). However, A0,5 \ N[g11] is isomorphic to K3, and A0,5 \ N[g21] is isomorphic to K2. Therefore, Ind(A0,5 \ N[g11]) ≃ S 0 ∨ S 0 and Ind(A0,5 \ N[g21]) ≃ S 0 . Hence, we have the stated conclusion. (ii… view at source ↗
Figure 6
Figure 6. Figure 6: Bn,5 consists of two disjoint edges, we have Ind(B0,5 \ N[g31]) ≃ Ind(K2) ∗ Ind(K2), i.e., Ind(B0,5 \ N[g31]) ≃ S 1 . Similarly, N(b1) ⊆ N(b3) ∩ N(g11) ∩ N(g21) in the graph B0,5 \ N[b6] implies that Ind(B0,5 \ N[b6]) ≃ Ind(B0,5 \ {N[b6] ∪ {b3, g11, g21}}). Since B0,5\{N[b6]∪{b3, g11, g21}} is isomorphic to the graph K2, we have Ind(B0,5\N[b6]) ≃ S 0 . Therefore, using the fact that Ind(B0,5 \ N[g31]) ≃ S … view at source ↗
Figure 7
Figure 7. Figure 7: Cn,5 Claim 3.6. Ind(C0,5) ≃ S 1 . Proof. Since N(g11) ⊆ N(g31) in the graph C0,5, using Proposition 2.3, we conclude that Ind(C0,5) ≃ Ind(C0,5 \ {g31}). However, the graph C0,5 \ {g31} consists of two disjoint edges. Therefore, Ind(C0,5) ≃ S 1 . (iv) Graph Dn,5. For n ≥ 0, we define the graph Dn,5 as follows: V (Dn,5) =V (Γn,5) ∪ {d1, d2}, E(Dn,5) =E(Γn,5) ∪ {d1d2, d1g11, d1g21, d2g31, d2g41}. Claim 3.7. I… view at source ↗
Figure 8
Figure 8. Figure 8: Dn,5 (v) Graph En,5. For n ≥ 0, we define the graph En,5 as follows: V (En,5) =V (Γn,5) ∪ {e1}, E(En,5) =E(Γn,5) ∪ {e1g11, e1g21, e1g31, e1g41}. 1 2 n g41 g42 g43 g44 g45 · · · g4 2n+1 g2 2n+1 g3 2n+1 g22 g32 g24 g34 g21 g31 g23 g33 g25 g35 g11 g12 g13 g14 g15 · · · g1 2n+1 (b) En,5, for n ≥ 1 e1 e1 g11 g21 g31 g41 (a) E0,5 [PITH_FULL_IMAGE:figures/full_fig_p009_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: En,5 Claim 3.8. Ind(E0,5) ≃ S 0 . Proof. Since N(g11) ⊆ N(g31) in the graph E0,5, by Proposition 2.3, we get Ind(E0,5) ≃ Ind(E0,5 \ g31). Furthermore, N(g41) ⊆ N(g11) in En,5 \ g31, and an application of Proposition 2.3 provides us with Ind(E0,5) ≃ Ind(E0,5 \ {g11, g31}). Note that the graph E0,5 \ {g11, g31} is a path on three vertices. Therefore, Ind(E0,5) ≃ S 0 . (vi) Graph Fn,5. For n ≥ 0, we define th… view at source ↗
Figure 10
Figure 10. Figure 10: Fn,5 Claim 3.9. Ind(F0,5) ≃ ∨4S 1 [PITH_FULL_IMAGE:figures/full_fig_p009_10.png] view at source ↗
Figure 22
Figure 22. Figure 22: Γn,4 Claim 4.1. For n ≥ 0, Ind(Γn,4) ≃    S 0 if n = 0, S 1 ∨ S 1 if n = 1, ΣInd(An−1,4) ∨ Σ 2 Ind(Λn−2,4) if n ≥ 2. Proof. Since Γ0,4 is a path with three vertices (see [PITH_FULL_IMAGE:figures/full_fig_p026_22.png] view at source ↗
Figure 23
Figure 23. Figure 23: Λn,4 [PITH_FULL_IMAGE:figures/full_fig_p026_23.png] view at source ↗
Figure 24
Figure 24. Figure 24: An,4 Claim 4.3. For n ≥ 0, Ind(An,4) ≃    S 0 if n = 0, S 1 ∨ S 2 if n = 1, ΣInd(An−1,4) ∨ Σ 2 Ind(Bn−2,4) ∨ Σ 3 Ind(Cn−2,4) if n ≥ 2. g22 g13 g14 g1 2n+1 g32 g3 2n+1 g31 (a) A1 n,4 g23 g13 g14 g15 g1 2n+1 g34 g3 2n+1 g25 (b) A2 n,4 g23 g13 g14 g15 g1 2n+1 g34 g3 2n+1 g25 (c) A3 n,4 [PITH_FULL_IMAGE:figures/full_fig_p027_24.png] view at source ↗
Figure 26
Figure 26. Figure 26: Bn,4 Claim 4.4. For n ≥ 0, Ind(Bn,4) ≃    S 1 ∨ S 1 if n = 0, ∨3S 2 if n = 1, ΣInd(Bn−1,4) ∨ Σ 2 Ind(An−1,4) ∨ Σ 3 Ind(Dn−2,4) if n ≥ 2. Proof. Since b1 is a simplicial vertex in Bn,4 with N(b1) = {b3, b4}, we get Ind(Bn,4) ≃ ΣInd(Bn,4 \ N[b3]) ∨ ΣInd(Bn,4 \ N[b4]). In the case of n = 0, the graph B0,4 \ N[b3] consists of an isolated vertex, g31, and B0,4 \ N[b4] is isomorphic to the complete graph K… view at source ↗
Figure 27
Figure 27. Figure 27: Cn,4 Claim 4.5. For n ≥ 0, Ind(Cn,4) ≃    S 0 ∨ S 0 for n = 0, S 1 for n = 1, ΣInd(An−1,4) ∨ Σ 2 Ind(Bn−2,4) ∨ Σ 2 Ind(Dn−2,4) for n ≥ 2. Proof. Since N(g11) ⊆ N(g31) in the graph C0,4, we get Ind(C0,4) ≃ Ind(C0,4 \ g31). However, the graph C0,4 \ g31 is isomorphic to a cycle with three vertices, and therefore Ind(C0,4) ≃ S 0 ∨ S 0 . For n ≥ 1, the inclusion map Ind(Cn,4 \ N[g21]) ֒→ Ind(Cn,4 \ g21) … view at source ↗
Figure 29
Figure 29. Figure 29: Dn,4 Claim 4.6. For n ≥ 0, Ind(Dn,4) ≃    S 1 ∨ S 1 if n = 0, W 5 S 2 if n = 1, ΣInd(Bn−1,4) ∨ Σ 2 Ind(An−1,4) ∨ Σ 2 Ind(Cn−1,4) if n ≥ 2 [PITH_FULL_IMAGE:figures/full_fig_p030_29.png] view at source ↗
Figure 30
Figure 30. Figure 30: Γn,3 Claim 5.1. For n ≥ 0, Ind(Γn,3) ≃ S n. Proof. Since N(g11) ⊆ N(g22) and N(g21) ⊆ N(g12), Ind(Γn,3) ≃ Ind(Γn,3 \ {g12, g22}). It is straightforward to see that Γn,3 \{g12, g22} has two connected components; one com￾ponent is an edge g11g21, and the other is isomorphic to Γn−1,3. Therefore, Ind(Γn,3) ≃ ΣInd(Γn−1,3). Consequently, we get Ind(Γn,3) ≃ Σ n Ind(Γ0,3). Since Γ0,3 is isomorphic to K2, we have… view at source ↗
Figure 31
Figure 31. Figure 31: An,3 Claim 5.2. For n ≥ 0, Ind(An,3) ≃ W 2 ΣInd(An−1,3) ≃ W 2n+1 S n [PITH_FULL_IMAGE:figures/full_fig_p033_31.png] view at source ↗
Figure 32
Figure 32. Figure 32: Λn,3 1 2 n g11 g12 g13 g14 g15 g21 · · · g1 2n+2 g2 2n+2 (b) Λ˜ n,3 for n ≥ 1 g11 g21 g12 g22 (a) Λ˜ 0,3 [PITH_FULL_IMAGE:figures/full_fig_p034_32.png] view at source ↗
Figure 33
Figure 33. Figure 33: Λ˜ n,3 Claim 5.3. For n ≥ 0, Ind(Λn,3) ≃ W 2n+2−1 S n . Proof. The proof is by induction on n. Clearly, Ind(Λ0,3) ≃ W 3 S 0 . Assume that n ≥ 1 and the Claim 5.3 holds for all 0 ≤ k < n. Since g ′ 1 is a simplicial vertex and N(g ′ 1 ) = {g ′ 2 , g11, g21} in the graph Λn,3 (see [PITH_FULL_IMAGE:figures/full_fig_p034_33.png] view at source ↗
read the original abstract

The matching complex $\mathsf{M}(G)$ of a graph $G$ is a simplicial complex whose simplices are matchings in $G$. These complexes appear in various places and found applications in many areas of mathematics including computational geometry, representation theory, combinatorics, etc. In this article, we consider the matching complexes of the categorical product $P_n \times P_m$ of path graphs $P_n$ and $P_m$. For $m = 1$, $P_n \times P_m$ is a discrete graph and therefore its matching complex is the void complex. For $m = 2$, $\M(P_n \times P_m)$ has been proved to be homotopy equivalent to a wedge of spheres by Kozlov. We show that for $n \geq 2$ and $3 \leq m \leq 5$, the matching complex of $P_n \times P_m$ is homotopy equivalent to a wedge of spheres. For $m =3$, we explicitly compute the number and dimension of spheres appearing in the wedge. Furthermore, for $m \in \{4, 5\}$, we provide the minimum and maximum dimensions of spheres appearing in the wedge in the homotopy type of $\mathsf{M}(P_n \times P_m)$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript proves that the matching complex M(P_n × P_m) of the categorical product of paths is homotopy equivalent to a wedge of spheres for all n ≥ 2 and m ∈ {3,4,5}. For m=3 an explicit count and dimensions of the spheres are given; for m=4,5 only the minimal and maximal dimensions of the spheres in the wedge are supplied. The argument extends Kozlov’s m=2 case via combinatorial reductions, presumably discrete Morse theory or shellability.

Significance. If correct, the result supplies concrete homotopy information for a family of matching complexes on grid-like graphs, including explicit Betti numbers for m=3. Such data can be used in further topological or representation-theoretic applications of matching complexes.

major comments (1)
  1. [Proof of the main theorem (m=3 case)] The central claim requires that the acyclic matching (or shelling order) constructed for M(P_n × P_m) pairs every non-critical cell for every n ≥ 2 once m is fixed in {3,4,5}. The abstract and reader’s note indicate this is achieved by combinatorial reductions claimed to be uniform in n; the manuscript must exhibit the explicit local rule or recursive definition and verify that no unpaired cells arise from boundary or periodicity effects when n becomes arbitrarily large.
minor comments (1)
  1. [Abstract] The abstract states that applications exist in several fields but supplies only a single reference (Kozlov); a short additional sentence citing one or two further works on matching complexes would improve context.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed report and the recommendation for major revision. The primary concern is the need for greater explicitness in the combinatorial reduction used to establish the acyclic matching for all n ≥ 2. We address this point below and will revise the manuscript to incorporate additional detail.

read point-by-point responses

  1. Referee: [Proof of the main theorem (m=3 case)] The central claim requires that the acyclic matching (or shelling order) constructed for M(P_n × P_m) pairs every non-critical cell for every n ≥ 2 once m is fixed in {3,4,5}. The abstract and reader’s note indicate this is achieved by combinatorial reductions claimed to be uniform in n; the manuscript must exhibit the explicit local rule or recursive definition and verify that no unpaired cells arise from boundary or periodicity effects when n becomes arbitrarily large.

    Authors: The manuscript defines the acyclic matching via a recursive combinatorial reduction on the grid structure of P_n × P_m that is uniform in n: at each step, edges are paired according to a local rule that depends only on the parity and position within the fixed-width strip (m fixed). The proof proceeds by induction on n, showing that the matching is acyclic and that the critical cells are precisely those counted for m=3 (or bounded in dimension for m=4,5). We acknowledge that the local rule is described at a level that may not immediately make the absence of boundary or periodicity artifacts transparent for arbitrary n. In the revision we will add an explicit algorithmic description of the pairing rule together with a separate lemma verifying that, for each fixed m in {3,4,5}, the rule produces no unpaired cells outside the intended critical set when n grows; the argument relies on the fact that the reduction never wraps around and that boundary columns are handled by the same local criterion as interior columns. revision: yes

Circularity Check

0 steps flagged

Direct combinatorial argument; no circularity

full rationale

The paper claims a homotopy equivalence via discrete Morse theory or shellability reductions that are asserted to hold uniformly for fixed m in {3,4,5} and all n≥2. No quoted step reduces a claimed result to a fitted parameter, self-definition, or load-bearing self-citation chain; the derivation is presented as an independent combinatorial construction. This is the normal case for a self-contained proof paper.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard definitions of categorical product, matching complex, and homotopy equivalence of simplicial complexes. No free parameters or invented entities are indicated in the abstract. Axioms are the usual background results in algebraic combinatorics.

axioms (2)
  • standard math The categorical product of graphs is the standard one with vertices as pairs and edges when both coordinates are adjacent.
    Invoked in the definition of the graph whose matching complex is studied.
  • domain assumption Homotopy equivalence of simplicial complexes can be established by combinatorial methods such as discrete Morse theory.
    Underlying technique referenced via Kozlov and used for the new cases.

pith-pipeline@v0.9.0 · 5765 in / 1320 out tokens · 16965 ms · 2026-05-24T02:53:56.427603+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    Splittings of independence complexes and the powers of cycles

    Michal Adamaszek. Splittings of independence complexes and the powers of cycles. J. Combin. Theory Ser. A , 119(5):1031--1047, 2012

    work page 2012

  2. [2]

    Benjamin Braun and Wesley K. Hough. Matching and independence complexes related to small grids. Electron. J. Combin. , 24(4):Paper No. 4.18, 20, 2017

    work page 2017

  3. [3]

    General polygonal line tilings and their matching complexes

    Margaret Bayer, Marija Jeli\' c Milutinovi\' c , and Julianne Vega. General polygonal line tilings and their matching complexes. Discrete Math. , 346(7):Paper No. 113428, 12, 2023

    work page 2023

  4. [4]

    Bj\" o rner, L

    A. Bj\" o rner, L. Lov\' a sz, S. T. Vre\' c ica, and R. T. Z ivaljevi\' c . Chessboard complexes and matching complexes. J. London Math. Soc. (2) , 49(1):25--39, 1994

    work page 1994

  5. [5]

    S. Bouc. Homologie de certains ensembles de 2 -sous-groupes des groupes sym\' e triques. J. Algebra , 150(1):158--186, 1992

    work page 1992

  6. [6]

    Independence complexes of claw-free graphs

    Alexander Engstr\" o m. Independence complexes of claw-free graphs. European J. Combin. , 29(1):234--241, 2008

    work page 2008

  7. [7]

    C ohen- M acaulay complexes and group actions

    Peter Freedman Garst. C ohen- M acaulay complexes and group actions . ProQuest LLC, Ann Arbor, MI, 1979. Thesis (Ph.D.)--The University of Wisconsin - Madison

    work page 1979

  8. [8]

    Matching complexes of 3 n grid graphs

    Shuchita Goyal, Samir Shukla, and Anurag Singh. Matching complexes of 3 n grid graphs. Electron. J. Combin. , 28(4):Paper No. 4.16, 26, 2021

    work page 2021

  9. [9]

    Algebraic topology

    Allen Hatcher. Algebraic topology . Cambridge University Press, Cambridge, 2002

    work page 2002

  10. [10]

    Matching complexes on grids

    Jakob Jonsson. Matching complexes on grids. unpublished manuscript available at https://people.kth.se/ jakobj/doc/thesis/grid.pdf , 2005

    work page 2005

  11. [11]

    Simplicial complexes of graphs , volume 1928 of Lecture Notes in Mathematics

    Jakob Jonsson. Simplicial complexes of graphs , volume 1928 of Lecture Notes in Mathematics . Springer-Verlag, Berlin, 2008

    work page 1928

  12. [12]

    Dmitry N. Kozlov. Complexes of directed trees. J. Combin. Theory Ser. A , 88(1):112--122, 1999

    work page 1999

  13. [13]

    Combinatorial algebraic topology , volume 21 of Algorithms and Computation in Mathematics

    Dmitry Kozlov. Combinatorial algebraic topology , volume 21 of Algorithms and Computation in Mathematics . Springer, Berlin, 2008

    work page 2008

  14. [14]

    Matching complexes of small grids

    Takahiro Matsushita. Matching complexes of small grids. Electron. J. Combin. , 26(3):Paper No. 3.1, 8, 2019

    work page 2019

  15. [15]

    Matching complexes of polygonal line tilings

    Takahiro Matsushita. Matching complexes of polygonal line tilings. Hokkaido Math. J. , 51(3):339--359, 2022

    work page 2022

  16. [16]

    Matching complexes of trees and applications of the matching tree algorithm

    Marija Jeli\' c Milutinovi\' c , Helen Jenne, Alex McDonough, and Julianne Vega. Matching complexes of trees and applications of the matching tree algorithm. Ann. Comb. , 26(4):1041--1075, 2022

    work page 2022

  17. [17]

    A uniform approach to complexes arising from forests

    Mario Marietti and Damiano Testa. A uniform approach to complexes arising from forests. Electron. J. Combin. , 15(1):Research Paper 101, 18, 2008

    work page 2008

  18. [18]

    Z ivaljevi\' c and Sini s a T

    Rade T. Z ivaljevi\' c and Sini s a T. Vre\' c ica. The colored T verberg's problem and complexes of injective functions. J. Combin. Theory Ser. A , 61(2):309--318, 1992

    work page 1992

  19. [19]

    Topology of matching, chessboard, and general bounded degree graph complexes

    Michelle L Wachs. Topology of matching, chessboard, and general bounded degree graph complexes. Algebra Universalis , 49(4):345--385, 2003

    work page 2003

  20. [20]

    Douglas B. West. Introduction to Graph Theory . Prentice Hall, Upper Saddle River, N.J., second edition, 2001

    work page 2001