arXiv:1708.07054v1 [math.AC] 23 Aug 2017

MINIMAL FREE RESOLUTIONS OF 2 × n DOMINO TILINGS
RACHELLE R. BOUCHAT AND TRICIA MULDOON BROWN

Abstract. We introduce a squarefree monomial ideal associated to the set of domino tilings of a 2 × n
rectangle and proceed to study the associated minimal free resolution. In this paper, we use results of Dalili
and Kummini to show that the Betti numbers of the ideal are independent of the underlying characteristic
of the field, and apply a natural splitting to explicitly determine the projective dimension and CastelnuovoMumford regularity of the ideal.

1. Introduction
Squarefree monomial ideals lie in the intersection of three areas of mathematics: commutative algebra,
combinatorics, and simplicial topology. As initial ideals of any arbitrary ideal in a polynomial ring are
monomial, much effort has been made to understand monomial ideals, with the groundwork on the study of
initial ideals due to Stanley and Reisner. (See Miller and Sturmfels [15] for a comprehensive overview of these
results.) Many natural combinatorial objects can be used to generate squarefree monomial ideals. Making
a connection to the field of graph theory, Conca and De Negri [5] introduced the study of edge ideals which
are squarefree monomial ideals generated from the edges of a graph. Of interest is to explicitly describe the
minimal free resolution associated to the monomial ideal using combinatorial objects. In particular, we wish
to associate the Betti numbers of the minimal free resolution with these combinatorial or topological objects.
Edge ideal results have been extended to the study of path ideals by Bouchat, Há, and O’Keefe in [4] and
further generalized to facet ideals of simplicial complexes by Faridi [8] and to path ideals of hypergraphs by
Há and Van Tuyl [12].
For the purposes of this paper, we associate squarefree monomial ideals with domino tilings of 2 × n
rectangles, that is disjoint arrangements of 2 × 1 tiles placed horizontally or vertically to completely cover the
area of the rectangle. Domino tilings are well-studied classical combinatorial objects with many interesting
properties. For example, a classic exercise can show the number of domino tilings of a 2 × n rectangle is given
by the (n − 1)st Fibonacci number, and a survey paper by Ardilla and Stanley [1] gives many results for
domino and more generalized tilings of the plane. Tilings have been studied in terms of their enumeration,
intersection, and graph theory. See Fisher and Temperley [10] and Kasteleyn [14] for the first enumerative
results, Butler, Horn, and Tressler [3] for intersection results, or Benedetto and Loehr [2] for graph theoretical
results. This myriad of results suggests that interpretation as monomial ideals will also be of interest. In
this work, we show the Betti numbers of the ideal corresponding to the set of all 2 × n domino tilings are
independent of the characteristic of the underlying field. Further, we apply a natural splitting to the facet
ideals generated by the ideals of domino tilings to give a recursion on the Betti numbers and determine the
projective dimension and Castelnuovo-Mumford regularity.
We note, the generating elements of these ideals formed from the set of all 2 × n domino tilings can
also be viewed as paths of a graph. However, the ideals are not path ideals, as their generating sets do not
correspond to all paths of a specified length within a graph, but rather just a subset (see Example 2.3).
1991 Mathematics Subject Classification. 05E40, 13A15.
Key words and phrases. Betti numbers, squarefree monomial ideals, domino tiling.
1

2

RACHELLE R. BOUCHAT AND TRICIA MULDOON BROWN

2. Minimal free resolutions and domino tilings
We begin with some background on minimal free resolutions. Let R = k[x1 , . . . , xn ] be the polynomial ring
in the variables x1 , . . . , xn over the field k, and let M be a finitely generated graded R-module. Associated
to M is a minimal free resolution, which is of the form
M
M
δp M
δp−1
δ1
0→
R(−a)βp,a (M) −→
R(−a)βp−1,a (M) −→ · · · −→
R(−a)β0,a (M) → M → 0
a

a

a

where the maps δi are exact and where R(−a) denotes the translation of R obtained by shifting the degree
of elements of R by a ∈ Nn . The numbers βi,a (M ) are called the multi-graded Betti numbers (or Nn -graded
Betti numbers) of M , and they correspond to the number of minimal generators of degree a occurring in the
ith -syzygy module of M . Of more
M interest here are the graded Betti numbers (or N-graded Betti numbers)
βi,a (M ) where a = (a1 , . . . , an ).
of M defined as βi,j (M ) :=
a1 +···+an =j

There are two invariants corresponding to the minimal free resolution of M which measure the size of
the resolution.
2.1. Definition. Let M be a finitely generated graded R-module.
(1) The projective dimension of M , denoted pd(M ), is the length of the minimal free resolution associated to M .
(2) The Castelnuovo-Mumford regularity (or regularity), denoted reg(M ), is
reg(M ) := max{j − i | βi,j (M ) 6= 0}.
We will define the squarefree monomial ideals of interest in this paper by associating dominos from a
tiling of a 2 × n array as follows:
i. From left to right, each vertical position composed of squares (1, k) and (2, k) is associated with the
domino identified by the variable yk for 1 ≤ k ≤ n.
ii. Each horizontal position composed of squares (1, k) and (1, k + 1) is associated with the domino
given by the variable xk for 1 ≤ k ≤ n − 1; and similarly, each horizontal position with squares (2, k)
and (2, k + 1) is labeled with the domino variable xn−1+k for 1 ≤ k ≤ n − 1.
As the dominos are disjoint, a tiling of the array by n dominos can then be represented as a squarefree
monomial of degree n. More formally, we state the following definitions.
2.2. Definition. Consider a 2 × n rectangle, D.
(1) A tiling τ of D is a degree n squarefree monomial τ = z1 z2 · · · zn where
zi ∈ {x1 , x2 , . . . , x2n−2 , y1 , y2 , . . . , yn } and, when considering the variables as dominos in the array,
we have zi ∩ zj = ∅ for all 1 ≤ i, j ≤ n. We will let Tn denote the set of all tilings τ of D.
(2) The domino ideal corresponding to Tn is the ideal generated by all tilings in Tn , i.e.
In := (τ | τ ∈ Tn ) ⊆ R = k[x1 , . . . , x2n−2 , y1 , . . . , yn ].
We note, because these are tilings of rectangles with height two, if xk |τ then consequently xn−1+k |τ .
Further, in a slight abuse of notation, we will let τ denote both the tiling and the monomial in the ring R
corresponding to the tiling.
2.3. Example. Consider the domino ideal, I3 , corresponding to the domino tilings of a 2 × 3 rectangle:
Tn = {x1 x3 y3 , x2 x4 y1 , y1 y2 y3 }

In = (x1 x3 y3 , x2 x4 y1 , y1 y2 y3 )

MINIMAL FREE RESOLUTIONS OF 2 × n DOMINO TILINGS

3

Notice that the generators of I3 , namely the tilings of the 2 × 3 rectangle, are a subset of the paths of length
two in the path graph of length six given below:
x1

x3

y3

y2

y1

x4

x2

In order to understand the minimal free resolutions of the ideals In for n ≥ 1, we need to investigate
how the generating domino tilings interact. In particular, we wish to understand the graded Betti numbers,
βi,j (In ), in terms of sets of domino tilings of the 2 × n array; that is, in terms of sets S = {τ1 , τ2 , . . . , τk }
where τi ∈ Tn for all 1 ≤ i ≤ k and for some k ≥ 0.
Each set of domino tilings may be represented by a squarefree monomial xS with variables from the set
{x1 , x2 , . . . , x2n−2 , y1 , y2 , . . . , yn } where a|xS if and only if a|τi for some τi ∈ S. We note, that the set of
domino tilings S associated with a squarefree monomial xS is not unique. Thus, sets of domino tilings are
first grouped into equivalence classes by distinct monomials with x being the representative of the equivalence
class. Example 2.4 illustrates such an equivalency.
2.4. Example. The pair of tilings
S1 =
is equivalent to the pair of tilings
S2 =




x1
x

x3

x1
x

y3 x4




5

5




y5 , y1 y2 y3 x4
x8

x7

,

x8

y1 y2 x3
x7



y5





,

because the corresponding monomial x = x1 x3 x4 x5 x7 x8 y1 y2 y3 y5 is the same for both pairs of tilings.
As before, without loss of generality, the monomial x may represent both a monomial in the ring R as
well as the set of domino tilings x = {τ ∈ Tn : τ |x}.
In addition to these definitions, we need the following results from simplicial topology.
2.5. Definition.
(1) An abstract simplicial complex, ∆, on a vertex set X = {x1 , . . . , xn } is a collection of subsets of X
satisfying:
(a) {xi } ∈ ∆ for all i, and
(b) F ∈ ∆, G ⊂ F =⇒ G ∈ ∆.
The elements of ∆ are called faces of ∆, and the maximal faces (under inclusion) are called facets
of ∆. The simplicial complex ∆ with facets F1 , . . . , Fs will be denoted by hF1 , . . . , Fs i.
(2) For any Y ⊆ X , an induced subcollection of ∆ on Y, denoted by ∆Y , is the simplicial complex whose
vertex set is a subset of Y and whose facet set is given by {F | F ⊆ Y and F is a facet of ∆}.
(3) If F is a face of ∆ = hF1 , . . . , Fs i, the complement of F in ∆ is given by FXc = X \ F , and the
complementary complex is then ∆cX = h(F1 )cX , . . . , (Fs )cX i.
In a extension of a result of Hochster, this complementary complex, ∆cX , can be used to determine the
Betti numbers of the ideal.
2.6. Theorem (Alilooee and Faridi, Theorem 2.8 in [9]). Let R = K[x1 , . . . , xn ] be a polynomial ring over a
field K, and I be a pure squarefree monomial ideal in R. Then the N-graded Betti numbers of I are given by
X
e i−1 (Γc
)
dimK H
βi,d (I) =
Vert(Γ)

Γ⊂∆(I),|Vert Γ|=d

4

RACHELLE R. BOUCHAT AND TRICIA MULDOON BROWN

where the sum is taken over the induced subcollections of Γ of ∆(I) which have d vertices.
Also of interest, are two subcomplexes of ∆.
2.7. Definition. Let ∆ be a simplicial complex having vertex set V = {x1 , . . . , xn }, and let x ∈ V .
(1) The deletion of ∆ with respect to the vertex x is del∆ (x) = ∆|V \{x} .
(2) The link of x in ∆ is lk∆ (x) = {F ∈ ∆|F ∩ {x} = ∅ and F ∪ {x} ∈ ∆}.
The following example illustrates the link and deletion complexes for the domino tilings of a 2×4 rectangle.
2.8. Example. In the case n = 4, the ideal generated by the set of all possible domino tilings is
I4 = (x1 x3 x4 x6 , x1 x4 y3 y4 , x2 x5 y1 y4 , x3 x6 y1 y2 , y1 y2 y3 y4 ),
with complementary complex given by
Γc4 = hx2 x5 y1 y2 y3 y4 , x2 x3 x5 x6 y1 y2 , x1 x3 x4 x6 y2 y3 , x1 x2 x4 x5 y3 y4 , x1 x2 x3 x4 x5 x6 i.
The deletion and link with respect to the vertex y3 are:
del(y3 ) =
lk(y3 ) =

hx2 x5 y1 y2 y4 , x2 x3 x5 x6 y1 y2 , x1 x3 x4 x6 y2 , x1 x2 x4 x5 y4 , x1 x2 x3 x4 x5 x6 i
hx2 x5 y1 y2 y4 , x1 x3 x4 x6 y2 , x1 x2 x4 x5 y4 i

Let us identify the vertices corresponding to stacked pairs of horizontal tiles; that is, x1 with x4 , x2 with x5 ,
and x3 with x6 . Then, the deletion complex of y3 is contractible to Figure 1 on the left, and the link of y3 ,
which is homotopic to a sphere of dimension one, is given by Figure 2 on the right.
y1

y1
y2

y2

y4

y4
x2

x3

x1

Figure 1. del(y3 )

x2

x3

x1

Figure 2. lk(y3 )

In the case n = 3, the deletion and link with respect to the vertex y2 also correspond to a ball and a
sphere in lower dimensions. In this case, the ideal generated by the set of all possible domino tilings is
I3 = (x1 x3 y3 , x2 x4 y1 , y1 y2 y3 )
and the complementary complex is given by
Γc3 = hx2 x4 y1 y2 , x1 x3 y2 y3 , x1 x2 x3 x4 i.
The deletion and link with respect to the vertex y2 are:
del(y2 )
lk(y2 )

= hx2 x4 y1 , x1 x3 y3 , x1 x2 x3 x4 i.
= hx2 x4 y1 , x1 x3 y3 i

which, after identifying stacked horizontal dominos, correspond to a 2-dimensional ball and 0-dimensional
sphere, respectively.
In the next section, we will utilize the link and deletion complexes and apply results of Dalili and
Kummini [6] to show the graded Betti numbers of In are independent of the characteristic of the field k.

MINIMAL FREE RESOLUTIONS OF 2 × n DOMINO TILINGS

5

3. Independence of Characteristic
In order to show independence of characteristic for domino ideals, we will explore the deletion and link
of a certain vertical domino in the complementary complex, but first we need a result on the homotopy type
of the complementary complex Γcn .
3.1. Proposition. Let Γcn be the complementary complex associated to the domino ideal In . Then, Γcn is
homotopic to a sphere of dimension n − 2.
Proof. We proceed by induction on n. In the base case, when n = 3, we have
Γc3 = hx2 x4 y1 y2 , x1 x3 y2 y3 , x1 x2 x3 x4 i.
Applying a deformation retraction which identifies the vertices x1 and x2 , respectively, with x3 and x4 ,
respectively, Γc3 is homotopic to the complex hx2 y1 y2 , x1 y2 y3 , x1 x2 i, that is, the complex of two triangles
adjoined at a point with two other vertices connected by a line. Thus Γc3 is homotopic to a 1-dimensional
sphere.
For n > 3, we separate the generators of In into sets of those containing yn and those containing xn−1
and, continuing to identify xk with xk+n−1 , the complementary complex is the union
Γcn = Γcn−1 ∗ xn−1 ∪ Γn−2 ∗ xn−2 yn−1 yn .
Because Γcn−1 can similarly be written as Γcn−2 ∗ xn−2 ∪ Γcn−3 ∗ yn−1 and because every face in Γcn−3 is a face
of Γcn−2 , we see every face of Γcn−1 is contained in a face of Γcn−2 ∗ xn−2 yn−1 . Further, each face F ∈ Γcn−1 is
contained in the face F ∗ yn ∈ Γcn−2 ∗ xn−2 yn−1 yn . In particular, because the faces of Γcn−1 make up a (n − 3)dimensional sphere and because yn is not contained in Γcn−1 , we have that Γcn−1 ∪ Γcn−2 ∗ xn−2 yn−1 yn is the
cone by yn over the sphere and thus is homotopic to a (n − 2)-dimensional ball. Without loss of generality,
we may assume the faces of Γcn−1 are the boundary of this (n − 2)-dimensional ball. Finally, we note that
xn−1 is not contained in any face of Γcn−2 ∗ xn−2 yn−1 yn , and so we see that Γcn−1 ∗ xn−1 ∪ Γn−2 ∗ xn−2 yn−1 yn
is the cone by xn−1 of the boundary of the (n − 2)-dimensional ball. Therefore, Γcn is homotopic to a sphere
of dimension n − 2.

Now consider the link and deletion of the complementary complex with respect to the vertical domino yn−1 .
3.2. Proposition. Let Γcn be the complementary complex associated to the domino tiling ideal In . Then,
the link, lkΓcn (yn−1 ), is homotopic to a sphere of dimension n − 3 for n ≥ 3. Further, the deletion complex,
delΓcn (yn−1 ), is contractible.
Proof. Divide the set of 2 × n tilings into three disjoint sets as follows:
i. An = {τ ∈ Tn : yn−1 yn |τ }
ii. Bn = {τ ∈ Tn : xn−1 x2n−2 |τ }
iii. Cn = {τ ∈ Tn : xn−2 x2n−3 yn |τ }
Each of these sets is described by the tiles comprising the rightmost two or three dominos of the tiling. The
facet complexes can also be described this way, because the complements will not contain these two or three
dominos. The facet complexes generated by the complements of the elements in these sets are
i. Acn = Γcn−2 ∗ {xn−1 xn−2 x2n−3 x2n−2 }
ii. Bnc = Γcn−2 ∗ {xn−2 x2n−3 yn−1 yn }
iii. Cnc = Γcn−3 ∗ {xn−3 xn−1 x2n−4 x2n−2 yn−1 yn−2 }
where ∗ represents the simplicial join. We then have
del(yn−1 ) = Γcn \ {yn−1 } = Acn ∪ (Bnc \ {yn−1 }) ∪ (Cnc \ {yn−1 })

6

RACHELLE R. BOUCHAT AND TRICIA MULDOON BROWN

and
lk(yn−1 ) = (Bnc \ {yn−1 }) ∪ (Cnc \ {yn−1 }).
Using a straight-forward deformation retraction, we simplify the complexes by identifying the vertices x2n−4 ,
x2n−3 , and x2n−2 , respectively, with their corresponding horizontal tiles xn−3 , xn−2 , and xn−1 , respectively.
Thus,
lk(yn−1 ) = (Γcn−2 ∗ {xn−2 yn }) ∪ (Γcn−3 ∗ {xn−3 xn−1 yn−2 }).
Applying Proposition 3.1, Γcn−2 is homotopic to a sphere of dimension n − 4. By taking the cone over
by the line hxn−2 yn i we remove the singularity and effectively fill in the (n − 4)-dimensional hole,
creating a complex homotopic to a ball of dimension n − 3.
Γcn−2

We note that the vertices xn−2 , xn−1 , and yn are not elements of either Γcn−2 nor Γcn−3 . So without
loss of generality, we can assume Γcn−2 is on the boundary of the (n − 3)-dimensional ball Γcn−2 ∗ {xn−2 yn }.
Further, both xn−3 and yn−2 are included in Γcn−2 . In fact, the maximal faces of Γcn−2 can be partitioned
disjointly into faces which contain xn−3 and faces which contain yn−2 , because the generating tilings must
have exactly one of these two tiles. More specifically,

(3.1)

Γcn−2 = (Γcn−3 ∗ {xn−3 }) ∪ (Γcn−4 ∗ {xn−4 yn−3 yn−2 }).

We can now consider the rest of the complex, namely Γcn−3 ∗ {xn−3 xn−1 yn−2 }. We know that Γcn−3 is
homotopic to a (n − 5)-dimensional sphere and is a subcomplex of Γcn−2 by extension of the relationship
given above in Equation 3.1. We wish to show Γcn−3 ∗ {xn−3 yn−2 } contains every facet of Γcn−2 ; therefore by
adjoining xn−1 , we create a cone over the boundary of a (n − 3)-dimensional ball which is a homotopic to a
sphere dimension n − 3.
First, we easily have that Γcn−3 ∗ {xn−3 yn−2 } contains all faces of Γcn−2 which contain xn−3 as needed
for the first term in the union given in Equation 3.1. Next, we note that Γcn−4 ∗ {xn−4 } is contained in
the complex Γcn−3 , so Γcn−3 ∗ {yn−2 } contains all facets F ∗ {xn−4 yn−2 } where F ∈ Γcn−4 . Further, every
maximal face on the boundary Γcn−2 that contains xn−4 yn−2 also contains the vertex yn−3 . As yn−3 is a
part of every face in Γcn−4 ∗ {xn−4 yn−3 yn−2 }, we may simply retract yn−3 into any other vertex in the part
of the boundary determined by Γcn−4 ∗ {xn−4 yn−3 yn−2 }. Thus we have homotopy equivalence, and we see
that Cnc \ {yn−1 } is the cone of the vertex xn−1 over the complex Γcn−3 which is homotopic to the boundary
of a (n − 3)-dimensional ball given by Bnc \ {yn−1 }. As the interior of this ball, given by faces containing
xn−2 or yn , is not contained in Cnc \ {yn−1 }, therefore, lk(yn−1 ) is homotopic to the sphere S n−3 .
It is now straight-forward to show the del(yn−1 ) is contractible. The complex del(yn−1 ) differs from the
link by the complex Acn = Γcn−2 ∗ {xn−1 xn−2 x2n−3 x2n−2 }. In particular, the vertex xn−1 is joined with Γcn−2 .
This join fills the interior of the sphere given by the link. Thus, del(yn−1 ) is homotopic to a ball of dimension
n − 2, and hence is contractible. (See Example 3.3 for a concrete demostration of this process.)

The following example illustrates Proposition 3.2 using generating tilings of a 2 × 4 rectangle.
3.3. Example. Recall, the domino ideal corresponding to T4 , namely
I4 = (x1 x3 x4 x6 , x1 x4 y3 y4 , x2 x5 y1 y4 , x3 x6 y1 y2 , y1 y2 y3 y4 ).
The generators of I4 are divided into three disjoint sets with corresponding facet complexes:

MINIMAL FREE RESOLUTIONS OF 2 × n DOMINO TILINGS

A4

= {x1 x4 y3 y4 , y1 y2 y3 y4 }

Ac4

B4

= {x1 x3 x4 x6 , x3 x6 y1 y2 }

B4c

C4

= {x2 x5 y1 y5 }

C4c

=
=
=
=
=
=
=
=

7

hx2 x3 x4 x6 y1 y2 , x1 x2 x3 x4 x5 x6 i
hx2 x3 x5 x6 i ∗ hy1 y2 , x1 x4 i
hx2 x3 x5 x6 i ∗ Γc2
hx2 x5 y1 y2 y3 y4 , x1 x2 x4 x5 y3 y4 i
hx2 x5 y3 y4 i ∗ hy1 y2 , x1 x4 i
hx2 x5 y3 y4 i ∗ Γc2
hx1 x3 x4 x6 y2 y3 i
hx1 x3 x4 x6 y2 y3 i ∗ Γc1

Identifying horizontal pairs, xi and xn+i−1 , we have
lk(y3 ) = B4c \ {y3 } ∪ C4c \ {y3 } = hx2 x5 y4 i ∗ Γc2 ∪ hx1 x3 x4 x6 y2 i ∗ Γc1 .
Thus, B4c \ {y3 } is the tetrahedron x2 y1 y2 y4 along with the triangle x1 x2 y4 , and C4c \ {y3 } is the triangle
x1 x3 y2 . The tetrahedron x2 x3 y1 y2 and triangle x1 x2 x3 of Ac4 , pictured in Figure 3, fill in the hole in the
link in del(y3 ) = V4c ∪ B4c \ {y3 } ∪ C4c \ {y3 }. Ac4 is the simplicial join of the line x2 x3 with Γc2 = hx1 , y1 y2 i.
The complex del(y3 ) differs from the link by Ac4 , thus del(y3 ) is contractible.
y1

y1
y2

y2
y4

x2

x3

Figure 3. Ac4

x1

x2

x3

x1

Figure 4. del(y3 )

We now wish to apply the results of Dalili and Kummini [6] to show independence of characteristic.
3.4. Proposition (Dalili and Kummini, Remark 2.2 and Discussion 2.5). Let ∆ be a simplicial complex.
(1) Let V be the vertex set of ∆ with x ∈ V . If H̃∗ (del∆ (x); Z) = 0, then H̃i+1 (∆; Z) ≃ H̃i (lk∆ (x); Z)
for all i ≥ 0.
(2) Let I be the Stanley Reisner ideal of ∆. Then, β(I) depends on char K if and only if the groups
H∗ (∆; Z) have torsion.
Thus, we can state our main theorem.
3.5. Theorem. Let R = k[x1 , . . . , x2n−2 , y1 , . . . , yn ], and let In be the domino ideal corresponding to Tn .
Then βi,j (In ) is independent of char(k) for all i, j ∈ Z.
Proof. The theorem is a consequence of Proposition 3.2 and Dalili and Kummini’s remarks, because H̃i−1 (Γcn ; Z) ≃
H̃i (lkΓcn (yn−1 ); Z) and as spheres the homology groups H∗ (lkΓcn (yn−1 ); Z) have no torsion.

In the next section, we describe a splitting of the domino ideal, In , into two smaller ideals, Vn and Un , in
order to provide a recursive description for the graded Betti numbers of In as well as determine projective
dimension and Castelnuovo-Mumford regularity.

8

RACHELLE R. BOUCHAT AND TRICIA MULDOON BROWN

4. Splitting Ideals
Splittable monomial ideals were introduced by Eliahou and Kervaire [7] in order to separate a monomial
ideal into simpler components. We give the definition from their work where G(I) denotes the canonical
generating set of the ideal I.
4.1. Definition. We say that I is splittable if I is the sum of two non-zero monomial ideals V and U such
that
(1) G(I) is the disjoint union of G(V ) and G(U ), and
(2) there is a splitting function
G(V ∩ U ) → G(V ) × G(U )
w

→ (φ(w), ψ(w))

satisfying the following properties:
(S1) w = lcm(φ(w), ψ(w)) for all w ∈ G(W ) = G(V ∩ U ), and
(S2) for every subset G′ ⊂ G(W ), both lcm φ(G′ ) and lcm ψ(G′ ) strictly divide lcm G′ .
We will split the generators of the ideal In into disjoint sets by rightmost dominoes in the tiling. A tiling
must either end with the vertical domino, yn , or two horizontal dominoes, xn−1 and x2n−2 . Thus, set Vn to
be the ideal generated by the set of tilings containing a rightmost vertical tile; that is, Vn = {τ ∈ Tn : yn |τ }.
Let Un be the ideal generated by tilings containing two rightmost horizontal tiles; that is, Un = {τ ∈ Tn :
xn−1 x2n−2 |τ }. We check the conditions for this to be a splitting.
4.2. Proposition. Let Tn be the set of domino tilings of a 2 × n rectangle, and let In be the domino ideal
associated to Tn . Then In = Vn + Un is a splitting (where Vn and Un are defined as above).
Proof. By definition, the set of minimal monomial generators of In , G(In ), is the disjoint union of the sets of
minimal monomial generators of Vn and Un , G(Vn ) and G(Un ) (respectively) as a domino tiling can either
contain the tile yn or the pair of tiles {xn−1 , x2n−2 } but not both. Further, we define the splitting function
w
w
(φ, ψ) : G(Vn ∪ Un ) → G(Vn ) × G(Un ) where φ(w) =
and ψ(w) =
. Now, we see
xn−1 x2n−2
yn


w
w
=w
,
lcm(φ(w), ψ(w)) = lcm
xn−1 x2n−2 yn
so (S1) is satisfied. To check condition (S2), we have

lcm(φ(S)) = lcm



w1
w2
wk
,
,...,
xn−1 x2n−2 xn−1 x2n−2
xn−1 x2n−2



=

lcm(w1 , w2 , . . . , wk )
< lcm(w1 , w2 , . . . , wk ) = lcm(S),
xn−1 x2n−2

and similarly for ψ(S). Thus, In can be split by Vn and Un .



We can now apply the following theorem due to Eliahou and Kervaire [7] for Betti numbers, which appears
as a condition to Francisco, Há, and Van Tuyl’s Proposition 2.1 categorizing Betti splittings in [11].
4.3. Theorem. Suppose that I is a splittable monomial ideal with splitting I = V + U . Then for all i, j ≥ 0,
βi,j (I) = βi,j (V ) + βi,j (U ) + βi−1,j (V ∩ U ).
First we explore the ideals Vn , Un , and Vn ∩ Un .

MINIMAL FREE RESOLUTIONS OF 2 × n DOMINO TILINGS

9

4.4. Proposition. The graded Betti numbers of Vn and Un are given by the graded Betti numbers of In−1
and In−2 , respectively. That is,
βi,j (Vn ) = βi,j−1 (In−1 )
βi,j (Un ) = βi,j−2 (In−2 )
for i, j ≥ 0.
Proof. The results follow immediately after observing that Vn = yn In−1 and Un = xn−1 x2n−2 In−2 .



We also have another splittable ideal, Vn ∩ Un . These two splittable ideals, namely In and Vn ∩ Un , will
play an integral role in the proof of the formula for pd(In ) in Proposition 4.8.
bn where
4.5. Proposition. The intersection Vn ∩ Un can be split into Vn ∩ Un = Vbn + U
Vbn
bn
U

=
=

{τ ∈ Vn ∩ Un : yn−1 |τ }
{τ ∈ Vn ∩ Un : xn−2 x2n−3 |τ }.

Proof. We are splitting an ideal’s minimal generators into two disjoint sets indexed by a vertical domino and
by the corresponding pair of horizontal dominos. The splitting function is defined similarly to the splitting
In = Vn + Un given in Proposition 4.2, so we omit it here.

Then it follows by the result of Eliahou and Kervaire [7] that
bn ) + βi−2,j (Vbn ∩ U
bn ),
βi−1,j (Vn ∩ Un ) = βi−1,j (Vbn ) + βi−1,j (U

bn , we have:
4.6. Proposition. Using the previous definitions of Vn , Un , Vbn , and U
(1) βi−1,j (Vbn ) = βi−1,j−4 (In−2 ),
bn ) = βi−1,j−2 (Vn−1 ∩ Un−1 ), and
(2) βi−1,j (U
b
bn ) = βi−2,j−3 (Vn−1 ∩ Un−1 ).
(3) βi−2,j (Vn ∩ U

Proof. Notice that every minimal generator in the ideal Vn ∩ Un contains the factors yn , xn−1 , and x2n−2 .
bn be defined as in Proposition 4.5.
Let Vbn and U

To check the remaining claims, we observe that all tilings of a 2 × (n − 2) array from the set Tn−2
correspond to a minimal generator in both Vn and Un , namely yn−1 yn Tn−2 ⊆ Vn and xn−1 x2n−2 Tn−2 ⊆ Un .
Thus, minimal generators in Vbn correspond to elements of the form yn−1 yn xn−1 x2n−2 τ for τ ∈ Tn−2 , and
hence βi−1,j (Vbn ) = βi−1,j−4 (In−2 ).
bn , so we consider the map Φ : U
bn −→ Vn−1 ∩ Un−1 where if τ =
Next, we note yn−1 ∤ τ ∈ U
τbxn−2 xn−1 x2n−3 x2n−2 yn , then Φ(τ ) = τbxn−2 x2n−3 yn−1 . Clearly Φ(τ ) ∈ Vn−1 ∩ Un−1 , as the map only
removes two dominos, xn−1 and x2n−2 , and relabels another domino. The map may be reversed giving a
bn ) = βi−1,j−2 (Vn−1 ∩ Un−1 ).
bijection, and thus βi−1,j (U

bn −→ Vn−1 ∩ Un−1 for which the element
Similarly, define the bijection φ : Vbn ∩ U
b
bn is mapped onto the element τbxn−2 x2n−3 yn−1 ∈ Vn−1 ∩ Un−1
τ = τbxn−2 xn−1 x2n−3 x2n−2 yn−1 yn ∈ Vn ∩ U
bn ) = βi−2,j−3 (Vn−1 ∩ Un−1 ).
by removing the three dominos xn−1 x2n−2 yn . This proves βi−2,j (Vbn ∩ U


10

RACHELLE R. BOUCHAT AND TRICIA MULDOON BROWN

4.7. Proposition. Let Tn be the set of domino tilings of a 2 × n rectangle, and let In be the domino ideal
corresponding to Tn . Then for n ≥ 4,
n−4
m  
XX
m
βi,j (In ) = βi,j−1 (In−1 ) + βi,j−2 (In−2 ) +
βi−1−k,j−4−2m−k (In−2−m )
k
m=0 k=0
n−4
X n − 4
+
(βi−1−k,j−2n+6−k (V3 ∩ U3 ) + βi−2−k,j−2n+5−k (V3 ∩ U3 ))
k
k=0

where β1,5 (V3 ∩ U3 ) = β1,6 (V3 ∩ U3 ) = β2,7 (V3 ∩ U3 ) = 1 and βi,j (V3 ∩ U3 ) = 0 elsewhere.
Proof. Applying Theorem 4.3 and Proposition 4.4, we have
βi,j (In ) =
=

βi,j (Vn ) + βi,j (Un ) + βi−1,j (Vn ∩ Un )
βi,j−1 (In−1 ) + βi,j−2 (In−2 ) + βi−1,j (Vn ∩ Un )

It is immediate that the first two summands agree. We now apply Propositions 4.5 and 4.6, to repeatedly
split the ideal (Vk ∩ Uk ) for k = n − 1, n − 2, . . . , 4. Each time the ideal is split, we have
βi′ ,j ′ (Vn′ ∩ Un′ ) = βi′ ,j ′ −4 (In′ −2 ) + βi′ ,j ′ −2 (Vn′ −1 ∩ Un′ −1 ) + βi′ −1,j ′ −3 (Vn′ −1 ∩ Un′ −1 ).
In particular, consider the first splitting of Vn ∩ Un :
(4.1)

βi−1,j (In ) = βi−1,j−2 (Vn−1 ∩ Un−1 ) + βi−2,j−3 (Vn−1 ∩ Un−1 )

The index m in the sum of Proposition 4.7 counts the number of times the Propositions 4.5 and 4.6 have
been applied to equation 4.1; that is, the number of times we have split the ideal Vk ∩ Uk in order to calculate
Betti numbers in terms of Ik−2 and Vk−1 ∩ Uk−1 . For m > 0, each βi′ ,j ′ (In−2−m ) appears as the summand
of a splitting applied to βi′ ,j ′ +4 (Vn−m ∩ Un−m ). To determine how many times this term appears in the sum
we note, the recursive relationship between the Betti numbers with index i′ and n′ is the same as that of
binomial coefficients; thus any time the term βi′ ,j ′ (Vn′ ∩ Un′ ) appears we find, through splitting, the terms
βi′ ,j ′ −4 (Vn′ −1 ∩ Un′ −1 ) + βi′ −1,j−3 (Vn′ −1 ∩ Un′ −1 ). Therefore a particular Betti number was determined by
a higher-dimensional Betti number such that either the i′ index remains constant and the j ′ index decreases
by two or the i′ index decreases by one and the j ′ decreases by three. The index k in Proposition 4.7 counts
′
the number of times
 in m splittings that the index i decreases by one. Thus, beginning with the index
m
i − 1 there are k terms who index has decreased to i − 1 − k. Further, each splitting decreases the second
index j by two or three, and precisely k of those times it decreases by three. Hence, the j index decreases to
m
j − 2m − k; that is presence
 of the term βi−1,j (Vn ∩ Un ) implies k copies of βi−1−k,j−2m−k (Vn−m ∩ Un−m )
m
which in turn implies k copies of βi−1−k,j−2m−k−4 (In−m−2 ).

Now applying this to Equation 4.1 and summing over each 0 ≤ k ≤ m and m ≥ 0, it is left to check the end
conditions. When m = n −
 4, Propositions 4.5 and 4.6 are applied to the intersection ideal Vn−m ∩ Un−m =
V4 ∩ U4 . As there are n−4
copies of the Betti number βi−1−k,j−2n−k+8 (V4 ∩ U4 ) for 0 ≤ k ≤ n − 4, when this
k
n−4
X n − 4
ideal is split and for all k, we are left with
(βi−1−k,j−2n+6−k (V3 ∩ U3 ) + βi−2−k,j−2n+5−k (V3 ∩ U3 )),
k
k=0
completing the sum.

4.8. Proposition. Let Tn be the set of domino tilings of a 2 × n rectangle, and let In be the domino ideal
corresponding to Tn . Then, pd(In ) = n − 1.
Proof. We will induct on n ≥ 3. For n = 3, I3 = (y1 y2 y3 , x1 x3 y3 , x2 x4 y1 ) and pd(In ) = 2 with β2,7 (I3 ) = 1.
Assume pd(In−1 ) = n − 2 and is achieved at βn−2,3n−5 (In−1 ) = 1. Since In = Vn + Un is a splitting for all

MINIMAL FREE RESOLUTIONS OF 2 × n DOMINO TILINGS

11

n ≥ 3 Theorem 4.3 and Proposition 4.4 provide:
βi,j (In ) =
=

(⋆)

βi,j (Vn ) + βi,j (Un ) + βi−1,j (Vn ∩ Un )
βi,j−1 (In−1 ) + βi,j−2 (In−2 ) + βi−1,j (Vn ∩ Un )

Furthermore, from Proposition 4.5, we obtain:
βi,j (In ) =
=

bn ) + βi−2,j (Vbn ∩ U
bn )
βi,j−1 (In−1 ) + βi,j−2 (In−2 ) + βi−1,j (Vbn ) + βi−1,j (U
βi,j−1 (In−1 ) + βi,j−2 (In−2 ) + +βi−1,j−4 (In−2 ) + βi−1,j−2 (Vn−1 ∩ Un−1 ) + βi−2,j−3 (Vn−1 ∩ Un−1 )

Consider i = n − 1 and j = 3n − 2. Since pd(In−1 ) = n − 2 and pd(In−2 ) = n − 3, we obtain:
βn−1,3n−2 (In ) = βn−2,3n−4 (Vn−1 ∩ Un−1 ) + βn−3,3n−5 (Vn−1 ∩ Un−1 )

(⋆⋆)

From the inductive hypothesis, pd(In−1 ) = n − 2 and βn−2,3n−5 (In−1 ) = 1. It follows from (⋆) that:
βn−2,3n−5 (In−1 ) =

βn−2,3n−6 (In−2 ) + βn−2,3n−7 (In−3 ) + βn−3,3n−5 (Vn−1 ∩ Un−1 ).

Since pd(In−3 ) = n − 4 and pd(In−2 ) = n − 3, it follows from the inductive hypothesis that:
βn−2,3n−5 (In−1 )

= βn−3,3n−5 (Vn−1 ∩ Un−1 ).

Moreover, since pd(In−1 ) = n − 2, we can conclude that βn−3,3n−5 (Vn−1 ∩ Un−1 ) = 1. Then from (⋆⋆),
βn−1,3n−2 (In ) = 1.
Further, because the deletion complex is contractible, Proposition 3.4 implies the link completely determines the complementary complex Γcn . Because the link is homotopic to a sphere of dimension n − 3,
the complementary complex is homotopic to a sphere of dimension n − 2. Thus, applying the variant of
Hochster’s formula due to Allilooee and Faridi in Theorem 2.6, n − 1 is the maximum index i for non-zero
Betti numbers βi,j , and therefore pd(In ) = n − 1.

4.9. Corollary. Let Tn be the set of domino tilings of a 2 × n rectangle, and let In be the domino ideal
corresponding to Tn . Then, reg(In ) = 2n − 1.
Proof. From Proposition 4.8, pd(In ) = n − 1 with βn−1,3n−2 (In ) ≥ 1. Since 3n − 2 is the greatest graded
shift, reg(In ) = (3n − 2) − (n − 1) = 2n − 1.

References
References
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
[11]

Federico Ardila and Richard P. Stanley, Tilings, Math. Intelligencer 32 (2010), no. 4, 32–43.
Katherine Benedetto and Nicholas Loehr, Domino tiling graphs, Ars Combinatorica, 109 (2013), pp. 3–29.
Steve Butler, Paul Horn, and Eric Tressler, Intersection Domino Tilings, Fibonacci Quarterly 48 (2010), no. 2, pp. 114–120.
Rachelle Bouchat, Augustine O’Keefe, and Huy Tài Hà, Path ideals of rooted trees and their graded Betti numbers, Journal
of Combinatorial Theory, Series A, 118 (2011), pp. 2411–2425.
Aldo Conca and Emanuela De Negri, M-sequences, graph ideals, and ladder ideals of linear type, Journal of Algebra, 211
(1999), no. 2, pp. 599-624.
Kia Dalili and Manoj Kummini, Dependence of Betti Numbers on Characteristic, Communications in Algebra, 42 (2014),
no. 2, pp. 563-570.
Shalom Eliahou and Michael Kervaire, Minimal Resolutions of Some Monomial Ideals, Journal of Algebra, 129 (1990),
1-25.
Sara Faridi, The facet ideal of a simplicial complex, Manuscripta Math., 109 (2002), pp. 159–174.
Ali Alilooee and Sara Faridi, On the resolution of path ideals of cycles, Communications in Algebra, 43 (2015), no. 12,
5413-5433.
Harold Temperley and Michael Fisher, Dimer problem in statistical mechanics-an exact result, Philosophical Magazine,
6(68) (1961), pp. 1061–1063.
Christopher A. Francisco, Huy Tái Há, and Adam Van Tuyl, Splittings of Monomial Ideas, Proceedings of the American
Mathematical Society, 137 No. 10 (2009), 3271-3282.

12

RACHELLE R. BOUCHAT AND TRICIA MULDOON BROWN

[12] Huy Tài Hà and Adam Van Tuyl, Monomial ideals, edge ideals of hyper graphs, and their graded Betti numbers, Journal
of Algebraic Combinatorics, 27 (2008), no. 2, pp. 215-245.
[13] Huy Yái Há and Adam Van Tuyl, Resolutions of squarefree monomial ideals via facet ideals: a survey. Contemporary
Mathematics, 448 (2007) 91-117.
[14] Pieter Kasteleyn, The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice,
Physica, 27(12) (1961), pp. 1209–1225.
[15] Ezra Miller and Bernd Sturmfels, Combinatorial Commutative Algebra, Springer Graduate Texts in Mathematics (2005).
[16] N. J. A. Sloane, editor, The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org, (2016).
Department of Mathematics, Indiana University of Pennsylvania, 1011 South Drive, Indiana, PA, 15705, USA
E-mail address:

rbouchat@iup.edu

Department of Mathematics, Armstrong State University, 11935 Abercorn Street, Savannah, GA 31419, USA
E-mail address: patricia.brown@armstrong.edu

