ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 22 (2022) #P1.03 / 41–55
https://doi.org/10.26493/1855-3974.1988.220
(Also available at http://amc-journal.eu)
The cubical matching complex revisited*
Duško Jojić
University of Banja Luka, Faculty of Science,
Mladena Stojanovića 2, 78 000 Banja Luka, Bosnia and Herzegovina
Received 15 April 2019, accepted 29 April 2021, published online 4 April 2022
Abstract
Ehrenborg noted that all tilings of a bipartite planar graph are encoded by its cubical
matching complex and claimed that this complex is collapsible. We point out to an over-
sight in his proof and explain why these complexes can be the disjoint union of two or more
collapsible complexes. We also prove that all links in these complexes are suspensions up
to homotopy. Furthermore, we extend the definition of a cubical matching complex to
planar graphs that are not necessarily bipartite, and show that these complexes are either
contractible or a disjoint union of contractible complexes. For a simple connected region
that can be tiled with dominoes (2×1 and 1×2) and 2×2 squares, let fi denote the number
of tilings with exactly i squares. We prove that f0 − f1 + f2 − f3 + · · · = 1 (established
by Ehrenborg) is the only linear relation for the numbers fi.
Keywords: Domino tilings, independence complexes, matching, cubical complexes.
Math. Subj. Class. (2020): 52C20, 05C70
1 Introduction
Let G = (V,E) be a bipartite planar graph that admits a perfect matching. Assume that G
is embedded in the plane. This embedding splits the plane into the regions, the connected
components of R2 \ |G| (here |G| denotes the embedding of G into R2). An elementary
cycle of G is a cycle that encircles a single region R different from the outer region R∗.
Throughout this paper, we identify an elementary cycle with the region it encircles as well
as with its set of vertices or edges.
A tiling of G is a partition of the vertex set V into disjoint blocks of the following two
types:
(1) an edge {x, y} of G; or
*We are very grateful to the referee for numerous remarks and suggestions which considerably improved the
presentation of results in the paper.
E-mail address: dusko.jojic@pmf.unibl.org (Duško Jojić)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
42 Ars Math. Contemp. 22 (2022) #P1.03 / 41–55
(2) an elementary cycle R (the set of vertices of R).
The set of all tilings of G form a cubical complex C(G) (called the cubical matching
complex) defined by Ehrenborg in [6]. Note that C(G) depends not only on G, but also on
the choice of the embedding of that graph in the plane.
A face F of C(G) has the form F = MF ∪CF = (MF , CF ), where CF is a collection
CF = {R1, R2, . . . , Rt} of vertex-disjoint elementary cycles of G, and MF is a perfect
matching on G \
(
R1 ∪ R2 ∪ · · · ∪ Rt
)
. The dimension of F is |CF |, and the vertices of
C(G) are the perfect matchings of G.
All tilings of G covered by F = (MF , CF ) can be obtained by deleting an elementary
cycle R from CF , and adding every other edge of R into MF (there are two possibilities to
do this). Therefore, for two faces F1 = (MF1 , CF1) and F2 = (MF2 , CF2), we have that(
F1 ⊂ F2
)
⇐⇒
(
CF1 ⊂ CF2 and MF1 ⊃ MF2
)
. (1.1)
Let G◦ denote the weak dual graph of a planar graph G. The vertices of G◦ are all
bounded regions of G, and two regions that share a common edge are adjacent in G◦.
The independence complex of a graph H is a simplicial complex I(H) whose faces are
the independent subsets of vertices of H . Note that for any face F = (MF , CF ) of C(G),
the set CF contains independent vertices of G◦, i.e., CF is a face of I(G◦).
Since two elementary cycles of G sharing a common edge cannot be in a common face
of C(G), it may seem at the first glance that C(G) can be computed from the independence
complex I(G◦).
A B C
G1 G2 G3
C(G1) C(G2) C(G3)
A B C A
B
C
AC
B
A
B
C
AC
Figure 1: The three graphs with the same weak dual, but different cubical matching com-
plexes.
However, Figure 1 shows three graphs with the same weak dual but different cubical
matching complexes. The facets of the complexes on Figure 1 are labeled by corresponding
subsets of pairwise disjoint elementary regions. This example points out that the require-
ment that G \ (R1 ∪ · · · ∪Rt) admits a perfect matching is a substantial one.
D. Jojić: The cubical matching complex revisited 43
Example 1.1. Let Ln and Cn denote the independence complexes of Pn and Cn (the path
and cycle with n vertices) respectively. The homotopy types of these complexes are deter-
mined by Kozlov in [10]:
Ln ≃
{
a point , if n = 3k + 1;
S⌊
n−1
3 ⌋, otherwise.
Cn ≃
{
Sk−1, if n = 3k ± 1;
Sk−1 ∨ Sk−1, if n = 3k.
We will use these complexes later, see Corollary 2.2 and Remark 2.5. An interested reader
can find more details about combinatorial and topological properties of Ln and Cn (and
about independence complexes in general) in [7, 8] and [9].
There are some cubical complexes that cannot be realized as subcomplexes of the d-
cube Cd = [0, 1]d, see Chapter 4 of [5].
Proposition 1.2. Let G be a bipartite planar graph that has a perfect matching. If G has
d elementary regions, then its cubical matching complex C(G) can be embedded into Cd.
Proof. We use an idea from [12] to describe the coordinates of vertices of C(G) explicitly.
Let R1, R2, . . . , Rd be a fixed linear order of elementary regions of G. We choose an
arbitrary perfect matching M0 of G (a vertex of C(G)) to be the origin 0 = (0, 0, . . . , 0) in
Rd. For another vertex M of C(G) the symmetric difference M △ M0 is a disjoint union of
cycles. Now, to a given perfect matching M of G, we assign the vertex VM = (x1, . . . , xd)
of Cd, where
xi =
{
1, if Ri is contained in an odd number of cycles of M △ M0;
0, otherwise.
If M ′ and M ′′ are two perfect matchings of G such that M ′ △ M ′′ = Rj (meaning
that these two matchings differ just on an elementary region Rj), then their corresponding
vertices VM ′ and VM ′′ of Cd differ only at the j-th coordinate.
Therefore, all 1-dimensional faces of C(G) that correspond to the same region Ri are
mutually parallel edges of Cd. The face F = (MF , CF ) of C(G) is embedded in Cd as the
convex hull of its 2|C(F )| vertices.
2 The local structure of C(G)
The star of a face F in a cubical complex C is the set of all faces of C that contain F
star(F ) = {F ′ ∈ C : F ⊂ F ′}.
The link of a vertex v in a cubical complex C is the simplicial complex linkC(v) that can
be realized in C as a “small sphere” around the vertex v. More formally, the vertices of
linkC(v) are the edges of C containing v. A subset of vertices of linkC(v) is a face of
linkC(v) if and only if the corresponding edges belong to a common face of C.
The link of a face F in a cubical complex C is defined in a similar way. The set of
vertices of linkC(F ) is
{F ′ ∈ C : F ⊂ F ′ and dimF ′ = 1 + dimF},
and a subset A of the set of vertices is a face of linkC(F ) if and only if all elements of A
are contained in a same face of C.
44 Ars Math. Contemp. 22 (2022) #P1.03 / 41–55
Ehrenborg investigated the links of the cubical complexes associated to tilings of a
region by dominos or lozenges.
Here we describe the links in the cubical matching complex C(G) for any bipartite
planar graph G. For a face F = (MF , CF ) of C(G), let RF denote the set of all elementary
regions of G for which every second edge is contained in MF . Further, let GF denote the
subgraph of the weak dual graph G◦ induced with the regions from RF .
From the definition of the link in a cubical complex and (1.1), we obtain the next state-
ment.
Proposition 2.1. For any face F = (MF , CF ) of C(G) we have that
linkC(F ) ∼= I(GF ).
The above proposition explains the appearance of complexes Ln and Cn as links in
cubical the matching complexes, see Theorem 3.3 and Section 4 in [6].
Assume that all elementary regions of G are quadrilaterals. In that case, for any face
F of C(G), a region in RF has exactly two opposite edges in MF , and the degree of a
vertex in GF is at most two. Therefore, GF is a disjoint union of paths and cycles. If
the regions (quadrilaterals) R1, R2, . . . , Rt are vertices of a cycle in GF , then the edges of
these regions that are not in MF form two cycles of length t in G. As G is bipartite, the
length of any cycle in GF is even.
Corollary 2.2. If all elementary regions of G are quadrilaterals, then linkC(F ) is a join
of complexes Lp and C2q .
Theorem 2.3. Let G be a bipartite planar graph that has a perfect matching. For any face
F = (MF , CF ) of C(G) the graph GF is bipartite.
Proof. Assume that GF contains an odd cycle R1, R2, . . . , R2m+1. Recall that Ri is an
elementary region of G and the that every second edge of Ri is contained in MF . Two
neighborly regions Ri−1 and Ri have to share the odd number of edges, the first and the
last of their common edges belong to MF . Therefore, for each region Ri, there is an odd
number of common edges of Ri and Ri−1 that belong to MF . Obviously, the same holds
for Ri and Ri+1.
So, we can conclude that there is an odd number of edges of Ri that are between
Ri∩Ri−1 and Ri∩Ri+1 (the first and the last one of these edges are not in MF ). Therefore,
the union of these edges (for all regions Ri) forms an odd cycle in G. This is a contradiction
with the assumption that G is a bipartite graph.
Barmak proved in [1] (see also in [11]) that the independence complexes of bipartite
graphs are suspensions up to homotopy type. This implies the next result.
Corollary 2.4. All links in C(G) are homotopy equivalent to suspensions. Therefore, the
link of any face in C(G) has at most two connected components.
For any simplicial complex K there exists a bipartite graph G such that the indepen-
dence complex of G is homotopy equivalent to the suspension over K, see [1]. Skwarski
proved in [13] (see also [1]) that there exists a planar graph G whose independence complex
is homotopy equivalent to an iterated suspension of K.
We prove that the links of faces in cubical matching complexes are independence com-
plexes of bipartite planar graphs. What can be said about homotopy types of these com-
plexes?
D. Jojić: The cubical matching complex revisited 45
Remark 2.5. There is a natural question, posed by Ehrenborg in [6]: For what graphs G
would the cubical matching complex C(G) be pure and/or shellable? The complexes Ln
are non-pure for n > 4, and the complexes Cn are non-shellable for n > 5. Therefore, these
complexes can be used to show that the cubical matching complex of a concrete graph is
non-pure or non-shellable.
3 Collapsibility and contractibility of cubical matching complexes
The next statement that we discuss was the main result of [6]. We identify a problem with
the proof, describe counterexamples (infinitely many), recover a weaker result, and give a
generalization.
Theorem 3.1 (Theorem 1.2 in [6]). For a planar bipartite graph G that has a perfect
matching, the cubical matching complex C(G) is collapsible.
The proof of the above statement is based on the following two results:
(i) (Propp, Theorem 2 in [12]) The set of all perfect matchings of a bipartite planar
graph is a distributive lattice (under a certain ordering, the details of which may be
found in [12]).
(ii) (Kalai, see in [14], Solution to Exercise 3.47 c) The cubical complex associated (see
[14]) to a meet-distributive lattice is collapsible.
Note however that Propp in his proof of (i) assumed the following two additional con-
ditions for bipartite planar graph G:
(∗) Graph G is connected, and
(∗∗) Any edge of G is contained in some matching of G but not in others.
The next statement is the correct version of Theorem 3.1.
Theorem 3.2. For a connected planar bipartite graph G that has a perfect matching and
whose any edge is contained in some matching of G but not in others, the cubical matching
complex C(G) is collapsible.
G
C(G)
Figure 2: A bipartite planar graph G for which C(G) is not collapsible.
46 Ars Math. Contemp. 22 (2022) #P1.03 / 41–55
Example 3.3. The figure below shows a bipartite planar graph whose cubical matching
complex is not collapsible. Note that the subdividing of the edges between the inner and
outer quadrilaterals in Figure 2 gives us an infinite family of counterexamples for Theo-
rem 3.1. Also, we can use this example to obtain a graph whose cubical complex has ar-
bitrarily many connected components. Simply, we continue by inserting a new square into
the smallest quadrilateral of the already constructed graph, and connect two non-adjacent
vertices of the new square with the corresponding vertices of the old graph. This counterex-
ample is motivated by the Jockusch example (page 27 in [12]). In his example we find a
bipartite planar graph with 20 edges, but just 12 of them can be used in a perfect matching,
and its cubical matching complex is a disjoint union of four segments.
Now we prove a weaker version of Theorem 3.1.
Theorem 3.4. For a planar bipartite graph G that has a perfect matching, the cubical
matching complex C(G) is either collapsible or a disjoint union of collapsible complexes.
The proof will be established in a series of lemmas. Through these lemmas we assume
that G is a planar bipartite graph that has a perfect matching.
The edges that do not appear in any perfect matching of G (the forbidden edges) can
be deleted. Also, if the edge xy is a forced edge (xy appears in all perfect matching of G),
then we may consider the graph G− {x, y}.
e e e
Figure 3: If a new region can be included in a tiling of G− e, then e is not forbidden.
Lemma 3.5. Let e denote a forbidden edge in G and let G′ = G − e. The possible new
elementary region of G′, that appears after we delete e, can not be included in a tiling of
G′.
Proof. Assume that a new region R that contains e can be included in a tiling of G′. Then
e divides R into two regions of the old graph G, and we can find a perfect matching of G
that contains e, see Figure 3.
In a similar way we may prove that a new region appearing after deleting the vertices
of a forced edge can not be included in a tiling of new graph.
Corollary 3.6. Let G denote the graph obtained by deleting all forced and forbidden edges
from G. Then the cubical matching complexes of G and G are isomorphic.
Lemma 3.7. Assume that G is a not connected, and let G1, G2, . . . , Gk be the connected
components of G. If these components are separated (there is no component of G that is
D. Jojić: The cubical matching complex revisited 47
contained in an elementary region of another component) then C(G) ∼= C(G1)× C(G2)×
· · · × C(Gk).
Proof. For a tiling F = (MF , CF ) of G let Fi = (Mi, Ci) denote the corresponding face
of C(Gi) (i.e., Mi = MF ∩E(Gi) and Ci is the set of regions of Gi that are included into
CF ). Then we have that F ∼= F1 × F2 × · · · × Fk.
Lemma 3.8. Assume that G has two different connected components G1 and G2 such that
G1 is contained in an elementary region R of G2. Then we have that
C(G) = C(G1)× (C(G2) \ {R}) . (3.1)
If there exists a tiling of G2 that uses the region R, then C(G) is a disjoint union of col-
lapsible complexes.
Here C(G2) \ {R} denotes the cubical complex obtained from C(G2) by deleting the
faces (tilings) that contain R.
Proof. The proof of (3.1) is the same as in the previous lemma. Recall that C(G2) can
be embedded in a cube, and that the edges corresponding to R are mutually parallel, see
Proposition 1.2. Therefore, C(G2) \ {R} is a disjoint union of collapsible complexes.
Now, we consider the cubical matching complex for all planar graphs that have a perfect
matching (but that are not necessarily bipartite).
Definition 3.9. Let G be a planar graph that admits a perfect matching. A tiling of G is a
partition of the vertex set V into disjoint blocks of the following two types:
• an edge {x, y} of G; or
• the set of vertices {v1, v2, . . . , v2m} of an even elementary cycle R.
Let C(G) denote the set of all tilings of G. Note that C(G) is also a cubical complex.
Example 3.10. If G is a graph of a triangular prism (embedded in the plane so that the
outer region is a triangle), then C(G) is a union of three 1-dimensional segments that share
the same vertex, see the left side of Figure 4. Each segment of C(G) corresponds to a
rectangle of prism. The link of the common vertex of these segments is a 0-dimensional
complex with three points. This situation, where a link has 3 connected components, is not
possible in a bipartite planar graph, as shown by Corollary 2.4. Further, the planar graph on
the right-hand side on Figure 4 satisfies the conditions (∗) and (∗∗), but the corresponding
cubical complex is not collapsible, it is a union of three disjoint edges. Therefore, the
assumption that G is a bipartite graph is substantial in Theorem 3.2.
The next theorem describe the homotopy type of the cubical matching complex associ-
ated to a planar graph that admits a perfect matching.
Theorem 3.11. Let G be a planar graph that has a perfect matching. The cubical complex
C(G) is contractible or a disjoint union of contractible complexes.
While contractibility is weaker than collapsibility, we partly relax the bipartite condi-
tion and obtain a weaker version of a corrected Theorem 3.1, with a different proof.
48 Ars Math. Contemp. 22 (2022) #P1.03 / 41–55
Figure 4: Non-bipartite graphs and their cubical matching complexes.
Proof. We use induction on the number of edges of G. Let e = xy denote an edge that
belongs to the outer region R∗. Let R ̸= R∗ denote the elementary region that contains e.
If R is an odd region, then all tilings of G can be divided into two disjoint classes:
(a) The tilings of G that do not use e. These tilings are just the tilings of G \ e.
(b) The tilings of G that contain e as an edge in a partial matching correspond to the
tilings of G \ {x, y}, and the subcomplex of C(G) generated by these tilings is iso-
morphic to C(G \ {x, y}).
In that case we obtain that C(G) = C(G\{x, y})∪C(G\e) is a disjoint union of contractible
complexes by inductive assumption.
If R is an even elementary region, then some tilings of G may contain R, and these
tilings are not considered in (a) and (b). Note that there is a bijection between tilings of G
that contain R and all tilings of G \ R (the graph obtained from G by deleting all vertices
from R). The subcomplex of C(G) generated by tilings that contain R forms a prism over
C(G \ R), i.e., this subcomplex is isomorphic to Prism(C(G \ R)) = C(G \ R) × [0, 1].
Therefore, we obtain that
C(G) = C(G \ {x, y}) ∪ C(G \ e) ∪ Prism(C(G \R)). (3.2)
Let Ce denote the subcomplex of C(G\e) formed by all tilings that contain every second
edge of R (but do not contain e, obviously). Further, let Cx,y denote the subcomplex of
C(G \ {x, y}), defined by tilings that contain every second edge of R (these tilings have to
D. Jojić: The cubical matching complex revisited 49
contain e). Note that both of complexes Ce and Cx,y are isomorphic to C(G \R), and
C(G \ e) ∩ Prism(C(G \R)) = Ce and C(G \ {x, y}) ∩ Prism(C(G \R)) = Cx,y.
The complexes on the right-hand side of (3.2) are disjoint unions of contractible com-
plexes by the inductive hypothesis. Assume that
C(G \ {x, y}) = A1 ∪A2 ∪ · · · ∪As and Cx,y = B1 ∪B2 ∪ · · · ∪Bt,
where Ai and Bj denote the contractible components of corresponding complexes. Obvi-
ously, each complex Bj is contained in some Ai. Now, we need the following lemma.
Lemma 3.12. Each connected component of C(G\{x, y}) contains at most one component
of Cx,y .
Proof of Lemma 3.12. Assume that a component of C(G\{x, y}) contains two components
of Cx,y . In that case, there are two vertices of Cx,y (perfect matchings of G that contain
xy) that are in different components of Cx,y , but in the same component of C(G \ {x, y}).
Assume that M ′ and M ′′ are two such vertices, chosen so that the distance between them
in C(G \ {x, y}) is minimal. Let
M ′ = M0
R0 M1 . . . Mi
Ri Mi+1 . . . Mn
Rn Mn+1 = M
′′ (3.3)
denote the shortest path from M ′ to M ′′ in C(G \ {x, y}). The perfect matching Mi+1 is
obtained from Mi by removing the edges of Mi contained in an elementary region Ri, and
by inserting the complementary edges. In other words, we have that Mi+1 = Mi △ Ri, for
an elementary region Ri contained in RFi ∩RFi+1 .
Note that R0 must be adjacent (share a common edge) with R. Otherwise, both of
vertices M0 and M1 belong to the same component of Cx,y , and we obtain a contradiction
with the assumption that the distance between M ′ and M ′′ is minimal.
In a similar way, we obtain that for any i = 1, 2, . . . , n, the region Ri must be adjacent
with at least one of regions R,R0, R1, . . . , Ri−1. If not, we have that the perfect matching
M = M0 △ Ri belongs to Cx,y , and M and M ′ are contained in the same component of
Cx,y . In that case we obtain a contradiction, because the path
M = M0
R0 M1 . . . M i−1
Ri−1 M i+1
Ri+1 . . . Mn
Rn Mn+1 = M
′′
is shorter than (3.3). Here we let that M j+1 = M j △ Rj .
Let e′ denote a common edge of regions R0 and R that is contained in M ′. Note that
e′ is not contained in M1. However, this edge is again contained in M ′′, and we conclude
that the region R0 has to reappear again in (3.3).
Let Ri0 = R0 denote the first appearance of R0 in (3.3) after the first step. There are
the following three possible situations that enable the reappearance of R0:
(a) The regions R1, R2, . . . , Ri0−1 are disjoint with R0.
In that case, we can omit the steps in (3.3) labelled by R0 and Ri0 , and obtain a
shorter path between M ′ and M ′′.
(b) Each of regions that shares at least one edge with R0 appears an odd number of times
between R0 and Ri0 .
This is impossible, because R (that share an edge with R0) can not appear in (3.3).
50 Ars Math. Contemp. 22 (2022) #P1.03 / 41–55
(c) There is t < i0 such that the region Rt = R̄ shares an edge with R0, but the fragment
of the sequence (3.3) between R0 and Ri0 does not contain all region that shares an
edge with R0.
Then the same region R̄ has to appear again as Rs, for some s such that t < s < i0.
Again, if all regions Rj are disjoint with R̄ (for j = t + 1, . . . , s − 1), we can omit
Rt and Rs, and obtain a contradiction. If not, there exist indices t′ and s′ such that
t < t′ < s′ < s and R′t = R
′
s. We continue in the same way, and from the finiteness
of the path, obtain a shorter path than (3.3).
Proof of Theorem 3.11, continued: We built C(G) by starting with C(G \ e), that is a
disjoint union of contractible complexes by assumption. Then we glue the components of
Prism(C(G \R)) one by one.
After that, we glue all components of C(G \ {x, y}). At each step we are gluing
two contractible complexes along a contractible subcomplex, or we just add a new con-
tractible complex, disjoint with previously added components. From the Gluing Lemma
(see Lemma 10.3 in [4]) we obtain that C(G) is contractible, or a disjoint union of con-
tractible complexes.
Corollary 3.13. If G has two odd elementary regions that share the same edge e = xy,
then its cubical complex C(G) = C(G \ {x, y}) ∪ C(G \ e) has at least two connected
components. The same holds if there is an odd elementary region of G that shares an edge
with the outer region R∗.
4 The f -vector of domino tilings
The concept of tilings of a bipartite planar graph generalizes the notion of domino tilings.
Let R be a simple connected region, compound of unit squares in the plane, that can be
tiled with domino tiles 1×2 and 2×1. The set of all tilings of R by domino tiles and 2×2
squares defines a cubical complex, denoted by C(R). If we consider R as a planar graph
(all of its elementary regions are unit squares), and if G denotes the weak dual graph of R
(the unit squares of R are vertices of G), then C(R) is isomorphic to the cubical matching
complex C(G), see Section 3 in [6] for details. Note that the number of i-dimensional faces
of C(G) counts the number of tilings of R with exactly i squares 2× 2.
Ehrenborg used collapsibility of C(G) to conclude (see Corollary 3.1. in [6]) that the
entries of f -vector of f(C(G)) = (f0, f1, . . . , fd) satisfy
f0 − f1 + f2 − · · ·+ (−1)dfd = 1. (4.1)
Let G denote the weak dual graph of a region R that admits a domino tiling. Choose
a concrete perfect matching M of G, and let e = xy denote the edge in M that contains
the vertex (square) in the left corner of the top row of R. The complex C(G \ {x, y}) is
nonempty and contractible by induction. The simple connectivity of R implies that the
other two complexes that appear on the right-hand side of the relation (3.2) are either both
empty or contractible (by induction). If both of these complexes are nonempty, when we
glue them as in the proof of Theorem 3.11, we obtain that C(G) is contractible. So, we
conclude that the relation (4.1) is true in any case, disregarding possible problems with
Theorem 3.1.
In this section we will prove that (4.1) is the only linear relation for f -vectors of cubical
complexes of domino tilings. We follow the idea from [2], where Bayer and Billera deter-
mine the affine span of the flag f -vectors of polytopes by constructing polytopes whose
D. Jojić: The cubical matching complex revisited 51
flag f -vectors are affinely independent. Here we describe d + 1 simple connected regions
whose cubical complexes are d-dimensional and their f -vectors are affinely independent.
For all n ∈ N, we let Gn denote the following graph 1 2 n .
This graph (also known as the ladder graph) has 2n + 2 vertices, 3n + 1 edges and n
elementary regions (squares). For i = 1, 2, . . . , n, let Gn,i denote the graph obtained by
adding one unit square below the i-th square of Gn.
Now, we describe some recursive relations for f -vectors of C(Gn) and C(Gn,i).
Proposition 4.1. For all positive integers n the entries of f -vectors of C(Gn) and C(Gn,i)
satisfy the following recurrences:
fi(C(Gn+2)) = fi(C(Gn+1)) + fi(C(Gn)) + fi−1(C(Gn)), (4.2)
fi(C(Gn+2,i)) = fi(C(Gn+1,i)) + fi(C(Gn,i)) + fi−1(C(Gn,i)), (4.3)
fi(C(Gn+2,i)) = fi(C(Gn+1,i−1)) + fi(C(Gn,i−2)) + fi−1(C(Gn,i−2)). (4.4)
Proof. All formulas follow from relation (3.2), see the proof of Theorem 3.11. To obtain
the formula (4.2), we apply (3.2) on Gn+2. The rightmost vertical edge and the rightmost
unit square in Gn+2 act as e and R in (3.2), see the first row on the next figure.
= ∪ ∪
= ∪ ∪
= ∪ ∪
(4.2)
(4.3)
(4.4)
Figure 5: The “geometric proof” of recursive relations for f(C(Gn)) and f(C(Gn,i)).
In the same way we can prove the remaining two relations. For each relation, we choose
an adequate elementary region R, a corresponding edge e of R, and use relation (3.2), see
Figure 5.
The f -vector (f0, f1, f2, . . . , f⌈n2 ⌉) of C(Gn) can be encoded by the polynomial Fn:
Fn = FC(Gn)(x) = f0 + f1x+ f2x
2 + · · ·+ f⌈n2 ⌉x
⌈n2 ⌉.
Similarly, we define the polynomials Fn,i to encode the f -vector of C(Gn,i). Directly from
(4.2) and (4.3) we obtain that
Fn+2(x) = Fn+1(x) + (x+ 1)Fn(x), Fn+2,i(x) = Fn+1,i(x) + (x+ 1)Fn,i(x).
Now, we define new polynomials Pn and Pn,i by
Pn = Pn(x) = Fn(x− 1), Pn,i = Pn,i(x) = Fn,i(x− 1).
52 Ars Math. Contemp. 22 (2022) #P1.03 / 41–55
This is a variant of h-polynomial associated to a cubical complex.
From Proposition 4.1 it follows that the polynomials Pn and Pn,i satisfy the following
recurrences
Pn+2(x) = Pn+1(x) + xPn(x), (4.5)
Pn+2,i(x) = Pn+1,i(x) + xPn,i(x), (4.6)
Pn+2,i(x) = Pn+1,i−1(x) + xPn,i−2(x). (4.7)
Remark 4.2. We can use (4.5) to obtain the polynomials Pn explicitly
P2d−1 =
(
d
d
)
xd + · · ·+
(
d+ k
d− k
)
xk + · · ·+
(
2d− 1
1
)
x+
(
2d
0
)
, and
P2d =
(
d+ 1
d
)
xd + · · ·+
(
d+ k + 1
d− k
)
xk + · · ·+
(
2d
1
)
x+
(
2d+ 1
0
)
.
Note that the polynomials Pn are related with Fibonacci polynomials, see Section 9.4
in [3] for the definition and a combinatorial interpretation of coefficients. The coefficients
of these polynomials are positive integers and the sum of coefficients of Pn is a Fibonacci
number. Note that this is just the number of vertices in C(Gn).
Assume that we embedded C(Gn) into n-cube as in Proposition 1.2, so that the perfect
matching M0 = of Gn is the vertex in the origin. Now, the coefficient
of xk in Pn counts the number of vertices of C(Gn) for which the sum of coordinates is k,
i.e., it is the number of vertices of C(Gn) whose distance from M0 is k.
Also, following [3], we can recognize the coefficient of xk in Pn as the number of
k-element subsets of [n] that do not contain two consecutive integers. Similarly, we can
interpret the coefficient of xk in Pn,i as the number of k-element subsets of the multiset
M = {1, 2, . . . , i− 1, i, i, i+1, . . . , n} that do not contain two consecutive integers. Note
that the multiplicity of i in M is two, and all other elements have the multiplicity one.
Definition 4.3. Let Pd denote the vector space of all polynomials of degree at most d. We
define the linear map Ad : Pd → Pd+1 recursively by
Ad(x
k) = xAd−1(x
k−1) for all k > 0, (4.8)
A0(1) = 1 + 2x and Ad(1) = P2d+1 −Ad(P2d−1 − 1). (4.9)
Lemma 4.4. For any non-negative integer d, we have that
Ad(P2d−1) = P2d+1, Ad(P2d) = P2d+2 and Ad+1(P2d) = P2d+2.
Proof. From (4.9) it follows that Ad(P2d−1) = P2d+1. For the proof of the second formula
we use (4.5), (4.8) and induction
Ad(P2d) = Ad(P2d−1 + xP2d−2) = P2d+1 + xAd−1(P2d−2) = P2d+1 + xP2d = P2d+2.
The last formula in this lemma follows from (4.5) and earlier proved formulas
Ad+1(P2d) = Ad+1(P2d+1 − xP2d−1) = P2d+3 − xAd(P2d−1)
= P2d+3 − xP2d+1 = P2d+2.
D. Jojić: The cubical matching complex revisited 53
Lemma 4.5. For all integers i and d such that 1 ⩽ i ⩽ ⌊d2⌋, the following holds:
Ad(P2d−1,i) = P2d+1,i and Ad(P2d,i) = P2d+2,i.
Proof. For i = 1 and i = 2 we apply relation (3.2) in a similar way as in the proof of
Proposition 4.1. We just delete the only square in the second row of Gn,1 and Gn,2, and
obtain that
P2d−1,1 = P2d−1 + xP2d−3, P2d−1,2 = P2d−1 + xP2d−4.
By using Lemma 4.4, we obtain that
Ad(P2d−1,1) = Ad(P2d−1 + xP2d−3) = P2d+1 + xP2d−1 = P2d+1,1, and
Ad(P2d−1,2) = Ad(P2d−1 + xP2d−4) = P2d+1 + xAd−1(P2d−4)
= P2d+1 + xP2d−2 = P2d+1,2.
In a similar way, we can prove that
Ad(P2d,1) = P2d+2,1 and Ad(P2d,2) = P2d+2,2.
Assume that the statement of this lemma is true for P2d−1,j and P2d,j when j < i + 1.
Now, we use (4.7) and induction to calculate
Ad(P2d,i+1) = Ad(P2d−1,i + xP2d−2,i−1) = Ad(P2d−1,i) + xAd−1(P2d−2,i−1)
= P2d+1,i + xP2d,i−1 = P2d+2,i+1.
From (4.6) we obtain that
Ad(P2d−1,i+1) = Ad(P2d,i+1 − xP2d−2,i+1) = Ad(P2d,i+1)− xAd−1(P2d−2,i+1)
= P2d+2,i+1 − xP2d,i+1 = P2d+1,i+1.
From Definition 4.3 and Remark 4.2 we can obtain the concrete formula for the linear
map Ad.
Proposition 4.6. For all d, k ∈ N such that d ⩾ k ⩾ 1, we have that:
Ad(x
k) = xk
(
1 + 2x− x2 + 2x3 − 5x4 + 14x5 − 42x6 + · · ·+ (−1)d−kCd−kxd−k+1
)
.
Here Cm denotes the m-th Catalan number.
Proof. From (4.8) it is enough to prove that
Ad(1) = 1 + 2x− x2 + 2x3 − 5x4 + · · ·+ (−1)dCdxd+1. (4.10)
For all integers n and k such that n ⩾ k ⩾ 1 (by using the induction and the Pascal’s
Identity), we can obtain the next relation(
n
k
)
=
k∑
i=0
(−1)i
(
n+ 1 + i
k − i
)
Ci. (4.11)
54 Ars Math. Contemp. 22 (2022) #P1.03 / 41–55
Now, we assume that (4.10) is true for all positive integers less than d, and calculate Ad(1)
by definition:
Ad(1) = P2d+1 −Ad(P2d−1 − 1)
=
d+1∑
i=0
(
2d+ 2− i
i
)
xi −
d∑
i=1
(
2d− i
i
)
xiAd−i(1).
The coefficients of 1, x and x2 in Ad(1) are respectively:(
2d+ 2
0
)
= 1,
(
2d+ 1
1
)
−
(
2d− 1
1
)
= 2,
(
2d
2
)
−
(
2d− 2
2
)
− 2
(
2d− 1
1
)
= −1.
For k > 1 the coefficient of xk+1 in the polynomial Ad(1) is(
2d+ 1− k
k + 1
)
−
(
2d− k − 1
k + 1
)
− 2
(
2d− k
k
)
−
k−1∑
i=1
(−1)i
(
2d− k + i
k − i
)
Ci.
From (4.11) we obtain that the coefficient of xk+1 in Ad(1) is (−1)kCk.
Corollary 4.7. For any positive integer d the linear map Ad is injective.
Now, we consider all simple connected regions for which the degree of the associated
polynomial PR(x) = FR(x − 1) is equal to d. Let Fd denote the affine subspace of Pd
spanned by these polynomials.
Lemma 4.8. The polynomial P2d+1,d is not contained in Ad(Fd).
Proof. From (4.7) and (4.6) it follows that
P2d+1,d − P2d+1,d−1 = (P2d,d−1 + xP2d−1,d−2)− (P2d,d−1 + xP2d−1,d−1)
= −x(P2d−1,d−1 − P2d−1,d−2) = (−1)d+1(xd+1 + xd).
We know that P2d+1,d−1 = Ad(P2d−1,d−1). If there exists a polynomial p ∈ Fd such that
Ad(p) = P2d+1,d then we obtain
xd+1 + xd = ±Ad(p− P2d−1,d−1),
which is impossible from Proposition 4.6.
Theorem 4.9. The polynomials P2d−1, P2d, P2d−1,1, . . . , P2d−1,d−1 are affinely indepen-
dent in Fd.
Proof. We use induction on the degree. Assume that d polynomials P2d−3, P2d−2, P2d−3,1,
. . . , P2d−3,d−2 are affinely independent in Fd−1. From Lemmas 4.4 and 4.5 and Corol-
lary 4.7, we conclude that P2d−1, P2d, P2d−1,1, . . . , P2d−1,d−2 are affinely independent.
These polynomials span a (d − 1)-dimensional affine subspace of Fd. From Lemma 4.8
follows that P2d−1,d−1 is not contained in Ad−1(Fd−1).
Corollary 4.10. The Euler-Poincare relation (4.1) is the only linear relation for the f -
vectors of tilings.
This answer the question of Ehrenborg question about numerical relations between the
numbers of different types of tilings, see [6].
D. Jojić: The cubical matching complex revisited 55
ORCID iDs
Duško Jojić https://orcid.org/0000-0003-4572-0637
References
[1] J. A. Barmak, Star clusters in independence complexes of graphs, Adv. Math. 241 (2013), 33–
57, doi:10.1016/j.aim.2013.03.016.
[2] M. M. Bayer and L. J. Billera, Generalized Dehn-Sommerville relations for polytopes,
spheres and Eulerian partially ordered sets, Invent. Math. 79 (1985), 143–157, doi:10.1007/
bf01388660.
[3] A. T. Benjamin and J. J. Quinn, Proofs that Really Count: The Art of Combinatorial Proof,
volume 27 of The Dolciani Mathematical Expositions, Mathematical Association of America,
Washington, DC, 2003, doi:10.5948/9781614442080.
[4] A. Björner, Topological methods, in: R. L. Graham, M. Grötschel and L. Lovász (eds.), Hand-
book of Combinatorics, Volume 2, Elsevier Sci. B. V., Amsterdam, pp. 1819–1872, 1995.
[5] V. M. Buchstaber and T. E. Panov, Toric Topology, volume 204 of Mathematical Surveys and
Monographs, American Mathematical Society, Providence, RI, 2015, doi:10.1090/surv/204.
[6] R. Ehrenborg, The cubical matching complex, Ann. Comb. 18 (2014), 75–81, doi:10.1007/
s00026-013-0212-7.
[7] R. Ehrenborg and G. Hetyei, The topology of the independence complex, Eur. J. Comb. 27
(2006), 906–923, doi:10.1016/j.ejc.2005.04.010.
[8] A. Engström, Complexes of directed trees and independence complexes, Discrete Math. 309
(2009), 3299–3309, doi:10.1016/j.disc.2008.09.033.
[9] J. Jonsson, Simplicial Complexes of Graphs, volume 1928 of Lecture Notes in Mathematics,
Springer-Verlag, Berlin, 2008, doi:10.1007/978-3-540-75859-4.
[10] D. N. Kozlov, Complexes of directed trees, J. Comb. Theory Ser. A 88 (1999), 112–122, doi:
10.1006/jcta.1999.2984.
[11] U. Nagel and V. Reiner, Betti numbers of monomial ideals and shifted skew shapes, Electron.
J. Comb. 16 (2009), #R3 (59 pages), doi:10.37236/69.
[12] J. Propp, Lattice structure for orientations of graphs, 2020, arXiv:0209005 [math.CO].
[13] J. Skwarski, Operations on a graph G that shift the homology of the independence complex of
G, Master’s thesis, Kungliga Tekniska Högskolan, 2010, https://www.math.kth.se/
xComb/skwarski.
[14] R. P. Stanley, Enumerative Combinatorics, Volume I, The Wadsworth & Brooks/Cole Mathe-
matics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, CA, 1986,
doi:10.1007/978-1-4615-9763-6.