# 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
<EMAIL_ADDRESS>
###### 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 oversight in his proof and explain why these complexes can be
the union of collapsible complexes. Also, we 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\times 1$ and
$1\times 2$) and $2\times 2$ squares, let $f_{i}$ denote the number of tilings
with exactly $i$ squares. We prove that $f_{0}-f_{1}+f_{2}-f_{3}+\cdots=1$
(established by Ehrenborg) is the only linear relation for the numbers
$f_{i}$.

###### Key words and phrases:

domino tilings, independence complexes, matching, cubical complexes

##  1\. Introduction

Let $G=(V,E)$ be a bipartite planar graph that allows a perfect matching.
Assume that $G$ is embedded in a plane. An elementary cycle of $G$ is a cycle
that encircles a single region $R$ different than 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

  * (2)

an elementary cycle $R$ (the set of vertices of $R$).

The set of all tilings of $G$ form a cubical complex $\mathcal{C}(G)$ (called
the cubical matching complex) defined by Ehrenborg in [5]. Note that
$\mathcal{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 $\mathcal{C}(G)$ has the form $F=M_{F}\cup C_{F}=(M_{F},C_{F}),$
where $C_{F}$ is a collection $C_{F}=\\{R_{1},R_{2},\ldots,R_{t}\\}$ of
vertex-disjoint elementary cycles of $G$, and $M_{F}$ is a perfect matching on
$G\setminus\big{(}R_{1}\cup R_{2}\cup\cdots\cup R_{t}\big{)}$. The dimension
of $F$ is $|C_{F}|$, and the vertices of $\mathcal{C}(G)$ are all perfect
matchings of $G$.

All tilings of $G$ covered by $F=(M_{F},C_{F})$ can be obtained by deleting an
elementary cycle $R$ from $C_{F}$, and adding every other edge of $R$ into
$M_{F}$ (there are two possibilities to do this). Therefore, for two faces
$F_{1}=(M_{F_{1}},C_{F_{1}})$ and $F_{2}=(M_{F_{2}},C_{F_{2}})$, we have that

(1) $\big{(}F_{1}\subset
F_{2}\big{)}\Longleftrightarrow\Big{(}C_{F_{1}}\subset C_{F_{2}}\textrm{ and
}M_{F_{1}}\supset M_{F_{2}}\Big{)}.$

Let $G^{\circ}$ denote the weak dual graph of a planar graph $G$. The vertices
of $G^{\circ}$ are all bounded regions of $G$, and two regions that share a
common edge are adjacent in $G^{\circ}$.

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=(M_{F},C_{F})$ of $\mathcal{C}(G)$, the set $C_{F}$ contains independent
vertices of $G^{\circ}$, i.e., $C_{F}$ is a face of $I(G^{\circ})$.

At the first sight, the complex $\mathcal{C}(G)$ is related with the
independence complex $I(G^{\circ})$ of its weak dual graph.

ABC$G_{1}$$G_{2}$$G_{3}$$\mathcal{C}(G_{1})$$\mathcal{C}(G_{2})$$\mathcal{C}(G_{3})$ABC$A$$B$$C$$AC$$B$$A$$B$$C$$AC$
Figure 1. The three graphs with the same weak dual, but different cubical
matching complexes.

However, Figure 1 shows the 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.

######  Example 1.

Let $\mathcal{L}_{n}$ and $\mathcal{C}_{n}$ denote the independence complexes
of $P_{n}$ and $C_{n}$ (the path and cycle with $n$ vertices) respectively.
The homotopy types of these complexes are determined by Kozlov in [9]:

$\mathcal{L}_{n}\simeq\left\\{\begin{array}[]{ll}\textrm{ a point },&\hbox{if
$n=3k+1$;}\\\ S^{\lfloor\frac{n-1}{3}\rfloor},&\hbox{otherwise.}\\\
\end{array}\right.\mathcal{C}_{n}\simeq\left\\{\begin{array}[]{ll}S^{k-1},&\hbox{if
$n=3k\pm 1$;}\\\ S^{k-1}\vee S^{k-1},&\hbox{if $n=3k$.}\\\ \end{array}\right.$

We will use these complexes later, see Corollary 4 and Remark 7. More details
about combinatorial and topological properties of $\mathcal{L}_{n}$ and
$\mathcal{C}_{n}$ (and about the independence complexes in general), an
interested reader can find in [6], [7] and [8].

There are some cubical complexes that cannot be realized as subcomplexes of a
$d$-cube $C^{d}=[0,1]^{d}$, see Chapter $4$ of [4].

######  Proposition 2.

Let $G$ be a bipartite planar graph that has a perfect matching. If $G$ has
$d$ elementary regions, then its cubical matching complex $\mathcal{C}(G)$ can
be embedded into $C^{d}$.

###### Proof.

We use an idea from [10] to describe the coordinates of vertices of
$\mathcal{C}(G)$ explicitly. Let $R_{1},R_{2},\ldots,R_{d}$ be a fixed linear
order of elementary regions of $G$. We choose an arbitrary perfect matching
$M_{0}$ of $G$ (a vertex of $\mathcal{C}(G)$) to be the origin
$\mathbf{0}=(0,0,\ldots,0)$ in $\mathbb{R}^{d}$. For another vertex $M$ of
$\mathcal{C}(G)$, we consider the symmetric difference $M\triangle M_{0}$.
Note that $M\triangle M_{0}$ is a disjoint union of cycles. For a given
perfect matching $M$ of $G$, we assign the vertex $V_{M}=(x_{1},\ldots,x_{d})$
of $C^{d}$, where

$x_{i}=\left\\{\begin{array}[]{ll}1,&\hbox{if $R_{i}$ is contained into an odd
number of cycles of $M\triangle M_{0}$;}\\\ 0,&\hbox{otherwise.}\\\
\end{array}\right.$

If $M^{\prime}$ and $M^{\prime\prime}$ are two perfect matchings of $G$ such
that $M^{\prime}\triangle M^{\prime\prime}=R_{j}$ (meaning that these two
matchings differ just on an elementary region $R_{j}$), then their
corresponding vertices $V_{M^{\prime}}$ and $V_{M^{\prime\prime}}$ of $C^{d}$
differ only at the $j$-th coordinate.

Therefore, the face $F=(M_{F},C_{F})$ is embedded in $C^{d}$ as the convex
hull of its $2^{|C(F)|}$ vertices.

∎

##  2\. The local structure of $\mathcal{C}(G)$

The star of a face $F$ in a cubical complex $\mathcal{C}$ is the set of all
faces of $\mathcal{C}$ that contain $F$

$star(F)=\\{F^{\prime}\in\mathcal{C}:F\subset F^{\prime}\\}.$

The link of a vertex $v$ in a cubical complex $\mathcal{C}$ is the simplicial
complex $link_{\mathcal{C}}(v)$ that can be realized in $\mathcal{C}$ as a
“small sphere“ around the vertex $v$. More formally, the vertices of
$link_{\mathcal{C}}(v)$ are the edges of $\mathcal{C}$ containing $v$. A
subset of vertices of $link_{\mathcal{C}}(v)$ is a face of
$link_{\mathcal{C}}(v)$ if and only if the corresponding edges belong to a
same face of $\mathcal{C}$.

The link of a face $F$ in a cubical complex $\mathcal{C}$ is defined in a
similar way. The set of vertices of $link_{\mathcal{C}}(F)$ is

$\\{F^{\prime}\in\mathcal{C}:F\subset F^{\prime}\textrm{ and
}dim\,F^{\prime}=1+dim\,F\\},$

and a subset $A$ of the set of vertices is a face of $link_{\mathcal{C}}(F)$
if and only if all elements of $A$ are contained in a same face of
$\mathcal{C}$.

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 $\mathcal{C}(G)$
for any bipartite planar graph $G$. For a face $F=(M_{F},C_{F})$ of
$\mathcal{C}(G)$, let $\mathcal{R}_{F}$ denote the set of all elementary
regions of $G$ for which every second edge is contained in $M_{F}$. Further,
let $G_{F}$ denote the subgraph of the weak dual graph $G^{\circ}$ spanned
with the regions from $\mathcal{R}_{F}$.

From the definition of the link in a cubical complex and (1), we obtain the
next statement.

######  Proposition 3.

For any face $F=(M_{F},C_{F})$ of $\mathcal{C}(G)$ we have that

$link_{\mathcal{C}}(F)\cong I(G_{F}).$

The above proposition explains the appearance of complexes $\mathcal{L}_{n}$
and $\mathcal{C}_{n}$ as the links in cubical the matching complexes, see
Theorem 3.3 and Section 4 in [5].

Assume that all elementary regions of $G$ are quadrilaterals. In that case,
for any face $F$ of $\mathcal{C}(G)$, the degree of a vertex in $G_{F}$ is at
most two. Therefore, $G_{F}$ is a union of paths and cycles.

######  Corollary 4.

If all elementary regions of $G$ are quadrilaterals, then
$link_{\mathcal{C}}(F)$ is a join of complexes $\mathcal{L}_{p}$ and
$\mathcal{C}_{2q}$.

######  Theorem 5.

Let $G$ be a bipartite planar graph that has a perfect matching. For any face
$F=(M_{F},C_{F})$ of $\mathcal{C}(G)$ the graph $G_{F}$ is bipartite.

###### Proof.

Assume that $G_{F}$ contains an odd cycle $R_{1},R_{2},\ldots,R_{2m+1}$.
Recall that $R_{i}$ is an elementary region of $G$ and the that every second
edge of $R_{i}$ is contained in $M_{F}$. Two neighborly regions $R_{i}$ and
$R_{i+1}$ have to share the odd number of edges, the first and the last of
their common edges belong to $M_{F}$. Therefore, for each region $R_{i}$,
there is an odd number of common edges of $R_{i}$ and $R_{i-1}$ that belong to
$M_{F}$. Obviously, the same holds for $R_{i}$ and $R_{i+1}$.

So, we can conclude that there is an odd number of edges of $R_{i}$ that are
between $R_{i}\cap R_{i-1}$ and $R_{i}\cap R_{i+1}$ (the first and the last
one of these edges are not in $M_{F}$). The union of all of these edges (for
all regions $R_{i}$) is an odd cycle in $G$, which is a contradiction.

∎

Barmak proved in [1] (see also in [11]) that the independence complexes of
bipartite graphs are suspensions, up to homotopy. This implies the next
result.

######  Corollary 6.

All links in $\mathcal{C}(G)$ are homotopy equivalent to suspensions.
Therefore, the link of any face in $\mathcal{C}(G)$ has at most two connected
components.

For any simplicial complex $K$ there exists a bipartite graph $G$ such that
the independence complex of $G$ is homotopy equivalent to the suspension over
$K$, see [1]. Skwarski proved in [12] (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 complexes of bipartite planar graphs. What can be said about
homotopy types of these complexes?

######  Remark 7.

There is a natural question, posed by Ehrenborg in [5]: For what graphs $G$
would the cubical matching complex $\mathcal{C}(G)$ be pure, shellable, non-
pure shellable?

The complexes $\mathcal{L}_{n}$ are non-pure for $n>4$, and the complexes
$\mathcal{C}_{n}$ 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 theorem is the main result in [5].

######  Theorem 8 (Theorem 1.2 in [5]).

For a planar bipartite graph $G$ that has a perfect matching, the cubical
matching complex $\mathcal{C}(G)$ is collapsible.

The proof of the above statement is based on the next two results:

  * $(i)$

(Propp, Theorem 2 in [10]) The set of all perfect matchings of a bipartite
planar graph is a distributive lattice.

  * $(ii)$

(Kalai, see in [13], Solution to Exercise 3.47 c) The cubical complex of a
meet-distributive lattice is collapsible.

Note however that Propp in his proof of $(i)$ assumed the following two
additional conditions 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.

######  Example 9.

The next figure shows a bipartite planar graph whose cubical matching complex
is not collapsible.

$G$$\mathcal{C}(G)$ Figure 2. A bipartite planar graph $G$ for which
$\mathcal{C}(G)$ is not collapsible.

Also, the Jockusch example (page 41 in [10], a bipartite planar graph with
$20$ edges, but just $12$ of them can be used in a perfect matching), describe
a graph $G$ whose cubical matching complex is a disjoint union of four
segments.

The edges that do not appear in any perfect matching of a graph $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.

######  Remark 10.

Let $e$ denote a forbidden edge in $G$ and let $G^{\prime}=G-e$. The possible
new elementary region of $G^{\prime}$, that appears after we delete $e$, can
not be included in a tiling of $G^{\prime}$. Otherwise, we can find a perfect
matching of $G$ that contains $e$, see Figure 3. In a similar way we conclude
that the new regions that appear after deleting a forced edge can not be
included in a tiling of $G^{\prime}$.

Let $G^{\prime}$ denote the graph obtained from $G$ after all deletions.
Unfortunately, this new graph (after deleting all forced and forbidden edges)
may be non-connected.

If $G^{\prime}$ is connected, then the collapsibility of
$\mathcal{C}(G^{\prime})$ follows from Ehrenborg’s proof. Also, if
$G^{\prime}$ is non-connected, and all of its connected components are
separated (there is no component of $G^{\prime}$ that is contained in an
elementary region of another component), then $\mathcal{C}(G^{\prime})$ is
collapsible as a product of collapsible complexes.

By using Remark 10, we can establish an obvious bijection between tilings of
$G^{\prime}$ and tilings of $G$ (we just add all forced edges). Therefore,
Theorem 8 holds if $G^{\prime}$ is connected or if all of its connected
components are separated.

However, Theorem 8 fails if $G^{\prime}$ has two different connected
components $G_{1}$ and $G_{2}$ such that $G_{1}$ is contained in an elementary
region $R$ of $G_{2}$, see Example 9. In that case we have that

$\mathcal{C}(G^{\prime})=\mathcal{C}(G_{1})\times\left(\mathcal{C}(G_{2})\setminus\\{R\\}\right),$

and $\mathcal{C}(G^{\prime})$ is a union of collapsible complexes. Here
$\mathcal{C}(G_{2})\setminus\\{R\\}$ denote the cubical complex obtained from
$\mathcal{C}(G_{2})$ by deleting all tilings (faces) that contain $R$ as an
elementary region.

Figure 4. Non-bipartite graphs and their cubical matching complexes.

Now, we consider the cubical matching complex for all planar graphs that have
a perfect matching (not necessarily bipartite).

######  Definition 11.

Let $G$ be a planar graph that allows 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 $\\{v_{1},v_{2},\ldots,v_{2m}\\}$ of an even elementary
cycle $R$.

Let $\mathcal{C}(G)$ denote the set of all tilings of $G$. Note that
$\mathcal{C}(G)$ is also a cubical complex.

######  Example 12.

If $G$ is a graph of a triangular prism (embedded in the plane so that the
outer region is a triangle), then $\mathcal{C}(G)$ is a union of three
$1$-dimensional segments that share the same vertex, see the left side of
Figure 4. Each of segments of $\mathcal{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. Such situation is no possible for bipartite planar
graphs, see Corollary 6.

The next theorem describe the homotopy type of the cubical matching complex
associated to a planar graph that allows a perfect matching.

######  Theorem 13.

Let $G$ be a planar graph that has a perfect matching. The cubical complex
$\mathcal{C}(G)$ is contractible or a disjoint union of contractible
complexes.

This is a weaker version (we prove contractibility instead collapsibility) of
corrected Theorem 8, with a different proof.

###### Proof.

We use the induction on the number of edges of $G$. Let $e=xy$ denote an edge
that belongs to the outer region $R^{*}$. Let $R\neq 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\setminus e$.

  * (b)

The tilings of $G$ that contain $e$ as an edge in a partial matching
correspond to the tilings of $G\setminus\\{x,y\\}$.

In that case we obtain that
$\mathcal{C}(G)=\mathcal{C}(G\setminus\\{x,y\\})\sqcup\mathcal{C}(G\setminus
e)$ is a disjoint union of contractible complexes by inductive assumption.

If $R$ is an even elementary region, then some tilings of $G$ may to contain
$R$. Note that these tilings are not considered in (a) and (b). To describe
the corresponding faces of $\mathcal{C}(G)$, we consider $G\setminus R$, the
graph obtained from $G$ by deleting all vertices from $R$.

Let $\mathcal{C}_{e}$ denote the subcomplex of $\mathcal{C}(G\setminus e)$
formed by all tilings that contain every second edge of $R$ (but do not
contain $e$, obviously). Further, let $\mathcal{C}_{x,y}$ denote the
subcomplex of $\mathcal{C}(G\setminus\\{x,y\\})$, defined by tilings that
contain every second edge of $R$ (these tilings have to contain $e$). Note
that the both of complexes $\mathcal{C}_{e}$ and $\mathcal{C}_{x,y}$ are
isomorphic to $\mathcal{C}(G\setminus R)$. In that case we obtain

(2) $\mathcal{C}(G)=\mathcal{C}(G\setminus\\{x,y\\})\cup\mathcal{C}(G\setminus
e)\cup Prism(\mathcal{C}(G\setminus R)).$

Further, we have that

$\mathcal{C}(G\setminus e)\cap Prism(\mathcal{C}(G\setminus
R))=\mathcal{C}_{e}\textrm{ and }\mathcal{C}(G\setminus\\{x,y\\})\cap
Prism(\mathcal{C}(G\setminus R))=\mathcal{C}_{x,y}.$

The complexes on the right-hand side of (2) are disjoint unions of
contractible complexes by the inductive hypothesis. Assume that

$\mathcal{C}(G\setminus\\{x,y\\})=A_{1}\sqcup A_{2}\sqcup\cdots\sqcup
A_{s}\textrm{ and }\mathcal{C}_{x,y}=B_{1}\sqcup B_{2}\sqcup\cdots\sqcup
B_{t},$

where $A_{i}$ and $B_{j}$ denote the contractible components of corresponding
complexes. Obviously, each complex $B_{j}$ is contained in some $A_{i}$. Now,
we need the following lemma.

######  Lemma 14.

Each of connected component of $\mathcal{C}(G\setminus\\{x,y\\})$ contains at
most one component of $\mathcal{C}_{x,y}$.

Proof of Lemma: Assume that a component of $\mathcal{C}(G\setminus\\{x,y\\})$
contains two components of $\mathcal{C}_{x,y}$. In that case, there are two
vertices of $\mathcal{C}_{x,y}$ (perfect matchings of $G$ that contain $xy$)
that are in different components of $\mathcal{C}_{x,y}$, but in the same
component of $\mathcal{C}(G\setminus\\{x,y\\})$. Assume that $M^{\prime}$ and
$M^{\prime\prime}$ are two such vertices, chosen so that the distance between
them in $\mathcal{C}(G\setminus\\{x,y\\})$ is minimal. Let

(3) $M^{\prime}=M_{0}\frac{{}_{R_{0}}}{}M_{1}\frac{\textrm{\,\,\,\,
}}{}\ldots\frac{\textrm{\,\,\,\,
}}{}M_{i}\frac{{}_{R_{i}}}{}M_{i+1}\frac{\textrm{\,\,\,\,
}}{}\ldots\frac{\textrm{\,\,\,\,
}}{}M_{n}\frac{{}_{R_{n}}}{}M_{n+1}=M^{\prime\prime}$

denote the shortest path from $M^{\prime}$ to $M^{\prime\prime}$ in
$\mathcal{C}(G\setminus\\{x,y\\})$. The perfect matching $M_{i+1}$ is obtained
from $M_{i}$ by removing the edges of $M_{i}$ contained in an elementary
region $R_{i}$, and by inserting the complementary edges. In other words, we
have that $M_{i+1}=M_{i}\triangle R_{i}$, for an elementary region $R_{i}$
contained in $\mathcal{R}_{F_{i}}\cap\mathcal{R}_{F_{i+1}}$.

Note that $R_{0}$ must be adjacent (share the common edge) with $R$.
Otherwise, both of vertices $M_{0}$ and $M_{1}$ belong to the same component
of $\mathcal{C}_{x,y}$, and we obtain a contradiction with the assumption that
the path described in (3) is minimal.

In a similar way, we obtain that for any $i=1,2,\ldots,n$, the region $R_{i}$
must be adjacent with at least one of regions $R,R_{0},R_{1},\ldots,R_{i-1}$.
If not, we have that the perfect matching $\overline{M}=M_{0}\triangle R_{i}$
belongs to $\mathcal{C}_{x,y}$, and $\overline{M}$ and $M^{\prime}$ are
contained in the same component of $\mathcal{C}_{x,y}$. In that case we obtain
a contradiction, because the path

$\overline{M}=\overline{M}_{0}\frac{{}_{R_{0}}}{}\overline{M}_{1}\frac{\textrm{\,\,\,\,
}}{}\ldots\frac{\textrm{\,\,\,\,
}}{}\overline{M}_{i-1}\frac{{}_{R_{i-1}}}{}\overline{M}_{i+1}\frac{{}_{R_{i+1}}}{}\ldots\frac{\textrm{\,\,\,\,
}}{}\overline{M}_{n}\frac{{}_{R_{n}}}{}\overline{M}_{n+1}=M^{\prime\prime}$

is shorter than (3). Here we let that
$\overline{M}_{j+1}=\overline{M}_{j}\triangle R_{j}$.

Let $e^{\prime}$ denote a common edge of regions $R_{0}$ and $R$ that is
contained in $M^{\prime}$. Note that $e^{\prime}$ is not contained in $M_{1}$.
However, this edge is again contained in $M^{\prime\prime}$, and we conclude
that the region $R_{0}$ has to reappear again in (3).

Let $R_{i_{0}}=R_{0}$ denote the first appearance of $R_{0}$ in (3) after the
first step. There are the following three possible situations that enable the
reappearance of $R_{0}$:

  1. $(a)$

All regions $R_{k}$ (for $k$ between $0$ and $i_{0}$) are disjoint with
$R_{0}$.
In that case, we can omit the steps in (3) labelled by $R_{0}$ and
$R_{i_{0}}$, and obtain a shorter path between $M^{\prime}$ and
$M^{\prime\prime}$.

  2. $(b)$

Any region that shares at least one edge with $R_{0}$ appears an odd number of
times between $R_{0}$ and $R_{i_{0}}$.
This is impossible, because $R$ (that share an edge with $R_{0}$) can not
appear in (3).

  3. $(c)$

There is $t<i_{0}$ such that $R_{t}=\bar{R}$ shares an edge with $R_{0}$, but
the fragment of the sequence (3) between $R_{0}$ and $R_{i_{0}}$ does not
contain all region that shares an edge with $R_{0}$.
Then the same region $\bar{R}$ has to appear again as $R_{s}$, for some $s$
such that $t<s<i_{0}$. Again, if all regions $R_{j}$ are disjoint with
$\bar{R}$ (for $j=t+1,\ldots,s-1$), we can omit $R_{t}$ and $R_{s}$, and
obtain a contradiction. If not, there exist indices $t^{\prime}$ and
$s^{\prime}$ such that $t<t^{\prime}<s^{\prime}<s$ and
$R_{t}^{\prime}=R_{s}^{\prime}$. We continue in the same way, and from the
finiteness of the path, obtain a shorter path than (3).

∎

Continue of Proof: We built $\mathcal{C}(G)$ by starting with
$\mathcal{C}(G\setminus e)$, that is a union of contractible complexes by
assumption. Then we glue the components of $Prism(\mathcal{C}(G\setminus R))$
one by one.

After that, we glue all components of $\mathcal{C}(G\setminus\\{x,y\\})$. At
each step we are gluing two contractible complexes along a contractible
subcomplex, or we just add a new contractible complex, disjoint with
previously added components. From the Gluing Lemma (see Lemma 10.3 in [3]) we
obtain that $\mathcal{C}(G)$ is contractible, or a disjoint union of
contractible complexes.

∎

######  Remark 15.

For a connected bipartite planar graph $G$ that satisfy the condition $(**)$,
the cubical matching complex $\mathcal{C}(G)$ is collapsible, see Theorem 8.
The planar graph on the right side on Figure 4 satisfies the condition $(**)$,
but the corresponding cubical complex is not collapsible, it is a union of
three disjoint edges. So, there is a natural question:

Is there a property of $G$ that provides the collapsibility of its cubical
complex $\mathcal{C}(G)$? Obviously, if all complexes that appear on the
right-hand side of (2) are nonempty and contractible, then $\mathcal{C}(G)$ is
contractible.

##  4\. The $f$-vector of domino tilings

The concept of tilings of a bipartite planar graph generalizes the notion of
domino tilings. Let $\mathcal{R}$ be a simple connected region, compound of
unit squares in the plane, that can be tiled with domino tiles $1\times 2$ and
$2\times 1$. The set of all tilings of $\mathcal{R}$ by domino tiles and
$2\times 2$ squares defines a cubical complex, denoted by
$\mathcal{C}(\mathcal{R})$. If we consider $\mathcal{R}$ as a planar graph
(all of its elementary regions are unit squares), and if $G$ denotes the weak
dual graph of $\mathcal{R}$ (the unit squares of $\mathcal{R}$ are vertices of
$G$), then $\mathcal{C}(\mathcal{R})$ is isomorphic to the cubical matching
complex $\mathcal{C}(G)$, see Section 3 in [5] for details. Note that the
number of $i$-dimensional faces of $\mathcal{C}(G)$ counts the number of
tilings of $\mathcal{R}$ with exactly $i$ squares $2\times 2$.

Ehrenborg used collapsibility of $\mathcal{C}(G)$ to conclude (see Corollary
3.1. in [5]) that the entries of $f$-vector of
$f(\mathcal{C}(G))=(f_{0},f_{1},\ldots,f_{d})$ satisfy

(4) $f_{0}-f_{1}+f_{2}-\cdots+(-1)^{d}f_{d}=1.$

If $G$ is the weak dual graph of a region $\mathcal{R}$ that admits a domino
tiling, then all complexes that appear on the right-hand side of the relation
(2) are contractible by induction, and therefore $\mathcal{C}(G)$ is
contractible, see Remark 15. So, we obtain that the relation (4) is true in
any case, disregarding possible problems with Theorem 8. In this Section we
will prove that (4) is the only linear relation for $f$-vectors of cubical
complexes of domino tilings.

For all $n\in\mathbb{N}$, we let $G_{n}$ denote the following graph
$\begin{tabular}[]{|c|c|c|c|c|c|}\hline\cr$1$&$2$&&&&$n$\\\
\hline\cr\end{tabular}.$

This graph (also known as the ladder graph) has $2n+2$ vertices, $3n+1$ edges
and $n$ elementary regions (squares). For $i=1,2,\ldots,n$, let $G_{n,i}$
denote the graph obtained by adding one unit square below the $i$-th square of
$G_{n}$. Now, we describe some recursive relations for $f$-vectors of
$\mathcal{C}(G_{n})$ and $\mathcal{C}(G_{n,i})$.

######  Proposition 16.

The entries of $f$-vectors of $\mathcal{C}(G_{n})$ and $\mathcal{C}(G_{n,i})$
satisfy the following recurrences:

(5)
$f_{i}(\mathcal{C}(G_{n+2}))=f_{i}(\mathcal{C}(G_{n+1}))+f_{i}(\mathcal{C}(G_{n}))+f_{i-1}(\mathcal{C}(G_{n})),$
(6)
$f_{i}(\mathcal{C}(G_{n+2,i}))=f_{i}(\mathcal{C}(G_{n+1,i}))+f_{i}(\mathcal{C}(G_{n,i}))+f_{i-1}(\mathcal{C}(G_{n,i})),$
(7)
$f_{i}(\mathcal{C}(G_{n+2,i}))=f_{i}(\mathcal{C}(G_{n+1,i-1}))+f_{i}(\mathcal{C}(G_{n,i-2}))+f_{i-1}(\mathcal{C}(G_{n,i-2})).$

###### Proof.

All formulas follow from relation (2), see the proof of Theorem 13. To obtain
the formula (5), we apply (2) on $G_{n+2}$. The rightmost vertical edge and
the rightmost unit square in $G_{n+2}$ act as $e$ and $R$ in (2).

$=$$\sqcup$$\sqcup$$=$$\sqcup$$\sqcup$$=$$\sqcup$$\sqcup$$(5)$$(6)$$(7)$
Figure 5. The “geometric proof“ of recursive relations for
$f(\mathcal{C}(G_{n}))$ and $f(\mathcal{C}(G_{n,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 (2), see Figure 5.

∎

The $f$-vector $(f_{0},f_{1},f_{2},\ldots,f_{\lceil\frac{n}{2}\rceil})$ of
$\mathcal{C}(G_{n})$ can be encoded by the polynomial $F_{n}$:

$F_{n}=F_{\mathcal{C}(G_{n})}(x)=f_{0}+f_{1}x+f_{2}x^{2}+\cdots+f_{\lceil\frac{n}{2}\rceil}x^{\lceil\frac{n}{2}\rceil}.$

Similarly, we define the polynomials $F_{n,i}$ to encode the $f$-vector of
$\mathcal{C}(G_{n,i})$. Directly from (5) and (6) we obtain that

$F_{n+2}(x)=F_{n+1}(x)+(x+1)F_{n}(x),\hskip
5.69046ptF_{n+2,i}(x)=F_{n+1,i}(x)+(x+1)F_{n,i}(x).$

Now, we define new polynomials $P_{n}$ and $P_{n,i}$ by

$P_{n}=P_{n}(x)=F_{n}(x-1),\hskip 11.38092ptP_{n,i}=P_{n,i}(x)=F_{n,i}(x-1).$

This is a variant of $h$-polynomial associated to corresponding cubical
complexes.
From Proposition 16 it follows that the polynomials $P_{n}$ and $P_{n,i}$
satisfy the following recurrences

(8) $P_{n+2}(x)=P_{n+1}(x)+xP_{n}(x),$ (9)
$P_{n+2,i}(x)=P_{n+1,i}(x)+xP_{n,i}(x),$ (10)
$P_{n+2,i}(x)=P_{n+1,i-1}(x)+xP_{n,i-2}(x).$

######  Remark 17.

We can use (8) to obtain the polynomials $P_{n}$ explicitly

$P_{2d-1}={d\choose d}x^{d}+\cdots+{d+k\choose d-k}x^{k}+\cdots+{2d-1\choose
1}x+{2d\choose 0}\textrm{, and}$ $P_{2d}={d+1\choose
d}x^{d}+\cdots+{d+k+1\choose d-k}x^{k}+\cdots+{2d\choose 1}x+{2d+1\choose 0}.$

Note that the polynomials $P_{n}$ are related with Fibonacci polynomials, see
Section 9.4 in [2] for the definition and a combinatorial interpretation of
coefficients. The coefficient of these polynomials are positive integers and
the sum of coefficients of $P_{n}$ is a Fibonacci number. Note that this is
just the number of vertices in $\mathcal{C}(G_{n})$.

Assume that we embedded $\mathcal{C}(G_{n})$ into $n$-cube as in Proposition
2, so that the perfect matching
$M_{0}=\begin{tabular}[]{|c|c|c|c|c|c|}\hdashline&&&&&\\\
\hdashline\end{tabular}$ of $G_{n}$ is the vertex in the origin. Now, the
coefficient of $x^{k}$ in $P_{n}$ counts the number of vertices of
$\mathcal{C}(G_{n})$ for which the sum of coordinates is $k$, i.e., it is the
number of vertices of $\mathcal{C}(G_{n})$ whose distance from $M_{0}$ is $k$.

Also, following [2], we can recognize the coefficient of $x^{k}$ in $P_{n}$ as
the number of $k$-element subsets of $[n]$ that do not contain two consecutive
integers. Similarly, we can interpret the coefficient of $x^{k}$ in $P_{n,i}$
as the number of $k$-element subsets of the multiset
$M=\\{1,2,\ldots,i-1,i,i,i+1,\ldots,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 18.

Let $\mathcal{P}^{d}$ denote the vector space of all polynomials of degree at
most $d$. We define the linear map
$A_{d}:\mathcal{P}^{d}\rightarrow\mathcal{P}^{d+1}$ recursively by

(11) $A_{d}(x^{k})=xA_{d-1}(x^{k-1})\textrm{ for all }k>0,$ (12)
$A_{0}(1)=1+2x\textrm{ and }A_{d}(1)=P_{2d+1}-A_{d}(P_{2d-1}-1).$

######  Lemma 19.

For any non-negative integer $d$, we have that

$A_{d}(P_{2d-1})=P_{2d+1},A_{d}(P_{2d})=P_{2d+2}\textrm{ and
}A_{d+1}(P_{2d})=P_{2d+2}.$

###### Proof.

From (12) it follows that $A_{d}(P_{2d-1})=P_{2d+1}$. For the proof of the
second formula we use (8), (11) and induction

$A_{d}(P_{2d})=A_{d}(P_{2d-1}+xP_{2d-2})=P_{2d+1}+xA_{d-1}(P_{2d-2})=P_{2d+1}+xP_{2d}=P_{2d+2}.$

The last formula in this lemma follows from (8) and earlier proved formulas

$A_{d+1}(P_{2d})=A_{d+1}(P_{2d+1}-xP_{2d-1})=$
$P_{2d+3}-xA_{d}(P_{2d-1})=P_{2d+3}-xP_{2d+1}=P_{2d+2}.$

∎

######  Lemma 20.

For all integers $i$ and $d$ such that $1\leq i\leq\lfloor\frac{d}{2}\rfloor$,
the following holds:

$A_{d}(P_{2d-1,i})=P_{2d+1,i}\textrm{ and }A_{d}(P_{2d,i})=P_{2d+2,i}.$

###### Proof.

For $i=1$ and $i=2$ we apply relation (2) in a similar way as in the proof of
Proposition 16. We just delete the only square in the second row of $G_{n,1}$
and $G_{n,2}$, and obtain that

$P_{2d-1,1}=P_{2d-1}+xP_{2d-3},P_{2d-1,2}=P_{2d-1}+xP_{2d-4}.$

By using Lemma 19, we obtain that

$A_{d}(P_{2d-1,1})=A_{d}(P_{2d-1}+xP_{2d-3})=P_{2d+1}+xP_{2d-1}=P_{2d+1,1}\textrm{,
and }$
$A_{d}(P_{2d-1,2})=A_{d}(P_{2d-1}+xP_{2d-4})=P_{2d+1}+xA_{d-1}(P_{2d-4})=$
$=P_{2d+1}+xP_{2d-2}=P_{2d+1,2}.$

In a similar way, we can prove that

$A_{d}(P_{2d,1})=P_{2d+2,1},A_{d}(P_{2d,2})=P_{2d+2,2}.$

Assume that the statement of this lemma is true for $P_{2d-1,j}$ and
$P_{2d,j}$ when $j<i+1$. Now, we use (10) and induction to calculate

$A_{d}(P_{2d,i+1})=A_{d}(P_{2d-1,i}+xP_{2d-2,i-1})=A_{d}(P_{2d-1,i})+xA_{d-1}(P_{2d-2,i-1})=$
$=P_{2d+1,i}+xP_{2d,i-1}=P_{2d+2,i+1}.$

From (9) we obtain that

$A_{d}(P_{2d-1,i+1})=A_{d}(P_{2d,i+1}-xP_{2d-2,i+1})=A_{d}(P_{2d,i+1})-xA_{d-1}(P_{2d-2,i+1})=$
$=P_{2d+2,i+1}-xP_{2d,i+1}=P_{2d+1,i+1}.$

∎

From Definition 18 and Remark 17 we can obtain the concrete formula for the
linear map $A_{d}$.

######  Proposition 21.

For all $d,k\in\mathbb{N}$ such that $d\geq k\geq 1$, we have that:

$A_{d}(x^{k})=x^{k}\left(1+2x-x^{2}+2x^{3}-5x^{4}+14x^{5}-\cdots+(-1)^{d-k}C_{d-k}x^{d-k+1}\right).$

Here $C_{m}$ denotes the $m$-th Catalan number.

###### Proof.

From (11) it is enough to prove that

(13) $A_{d}(1)=1+2x-x^{2}+2x^{3}-5x^{4}+\cdots+(-1)^{d}C_{d}x^{d+1}.$

For all integers $n$ and $k$ such that $n\geq k\geq 1$ (by using the induction
and the Pascal’s Identity), we can obtain the next relation

(14) ${n\choose k}=\sum_{i=0}^{k}(-1)^{i}{n+1+i\choose k-i}C_{i}.$

Now, we assume that (13) is true for all positive integers less than $d$, and
calculate $A_{d}(1)$ by definition:

$A_{d}(1)=P_{2d+1}-A_{d}(P_{2d-1}-1)=$ $=\sum_{i=0}^{d+1}{2d+2-i\choose
i}x^{i}-\sum_{i=1}^{d}{2d-i\choose i}x^{i}A_{d-i}(1).$

The coefficients of $1,x$ and $x^{2}$ in $A_{d}(1)$ are respectively:

${2d+2\choose 0}=1,{2d+1\choose 1}-{2d-1\choose 1}=2,{2d\choose
2}-{2d-2\choose 2}-2{2d-1\choose 1}=-1.$

For $k>1$ the coefficient of $x^{k+1}$ in the polynomial $A_{d}(1)$ is

${2d+1-k\choose k+1}-{2d-k-1\choose k+1}-2{2d-k\choose
k}-\sum_{i=1}^{k-1}(-1)^{i}{2d-k+i\choose k-i}C_{i}.$

From (14) we obtain that the coefficient of $x^{k+1}$ in $A_{d}(1)$ is
$(-1)^{k}C_{k}$.

∎

######  Corollary 22.

For any positive integer $d$ the linear map $A_{d}$ is injective.

Now, we consider all simple connected regions for which the degree of the
associated polynomial $P_{\mathcal{R}}(x)=F_{\mathcal{R}}(x-1)$ is equal to
$d$. Let $\mathcal{F}^{d}$ denote the affine subspace of $\mathcal{P}^{d}$
spanned by these polynomials.

######  Lemma 23.

The polynomial $P_{2d+1,d}$ is not contained in $A_{d}(\mathcal{F}^{d})$.

###### Proof.

From (10) and (9) we have that

$P_{2d+1,d}-P_{2d+1,d-1}=(P_{2d,d-1}+xP_{2d-1,d-2})-(P_{2d,d-1}+xP_{2d-1,d-1})=$
$-x(P_{2d-1,d-1}-P_{2d-1,d-2})=(-1)^{d+1}(x^{d+1}+x^{d}).$

We know that $P_{2d+1,d-1}=A_{d}(P_{2d-1,d-1})$. If there exists a polynomial
$p\in\mathcal{F}^{d}$ such that $A_{d}(p)=P_{2d+1,d}$ then we obtain

$x^{d+1}+x^{d}=\pm A_{d}(p-P_{2d-1,d-1}),$

which is impossible from Proposition 21.

∎

######  Theorem 24.

The polynomials $P_{2d-1},P_{2d},P_{2d-1,1},\ldots,P_{2d-1,d-1}$ are affinely
independent in $\mathcal{F}^{d}$.

###### Proof.

We use induction on the degree. Assume that $d$ polynomials $P_{2d-3}$,
$P_{2d-2}$, $P_{2d-3,1}$, $\ldots,P_{2d-3,d-2}$ are affinely independent in
$\mathcal{F}^{d-1}$. From Lemmas 19 and 20 and Corollary 22, we conclude that
$P_{2d-1}$, $P_{2d}$, $P_{2d-1,1}$, $\ldots,P_{2d-1,d-2}$ are affinely
independent. These polynomials span a $(d-1)$-dimensional affine subspace of
$\mathcal{F}^{d}$. From Lemma 23 follows that $P_{2d-1,d-1}$ is not contained
in $A_{d-1}(\mathcal{F}^{d-1})$.

∎

######  Corollary 25.

The Euler-Poincare relation (4) 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 [5].

## References

  * [1] J. A. Barmak, Star clusters in independence complexes of graphs. Adv. Math. 241 (2013), 33–57.
  * [2] A. T. Benjamin, J. J.Quinn, Proofs that really count. The art of combinatorial proof. The Dolciani Mathematical Expositions, 27. Mathematical Association of America, Washington, DC, 2003
  * [3] A. Björner, Topological methods. in: R. Graham, M. Grötschel, L. Lovàsz (Eds.), Handbook of Combinatorics, North Holland, Amsterdam, 1995, pp.1819–1872.
  * [4] V. M. Buchstaber, T. E. Panov, Toric Topology. Mathematical Surveys and Monographs, vol.204, American Mathematical Society, Providence, RI, 2015.
  * [5] R. Ehrenborg, The cubical matching complex. Ann. Comb., 18 (1) (2014), 75–81.
  * [6] R. Ehrenborg, G. Hetyei, The topology of the independence complex. European J. Combin. 27(6) (2006), 906–923.
  * [7] A. Engström, Complexes of directed trees and independence complexes., Discrete Math. 309 (2009), 3299–3309.
  * [8] J. Jonsson, Simplicial Complexes of Graphs. Lecture Notes in Math., vol.1928, Springer, 2008.
  * [9] D. N. Kozlov, Complexes of directed trees. J. Combin. Theory Ser. A 88(1) (1999), 112–122
  * [10] J. Propp, Lattice structure for orientations of graphs., https://arxiv.org/abs/math/0209005 Preprint (2002),
  * [11] U. Nagel, V. Reiner, Betti numbers of monomial ideals and shifted skew shapes. Electron. J. Combin. 16 (2009), no. 2, Special volume in honor of Anders Björner, Research Paper 3,
  * [12] J. Skwarski, Operations on a graph $G$ that shift the homology of the independence complex of $G$. Examensarbete, Kungliga Tekniska Högskolan, (2010).
  * [13] R. P. Stanley, Enumerative Combinatorics. Vol. I, Second edition. Cambridge Studies in Advanced Mathematics, 49., 2012.