PROOF OF TWO CONJECTURES OF ZUBER ON FULLY PACKED LOOP CONFIGURATIONS

FABRIZIO CASELLI^{†} AND CHRISTIAN KRATTENTHALER^{†}

Abstract. Two conjectures of Zuber [“On the counting of fully packed loops configurations. Some new conjectures,” Electronic J. Combin. 11 (2004), Article #R13] on the enumeration of configurations in the fully packed loop model on the square grid with periodic boundary conditions, which have a prescribed linkage pattern, are proved. Following an idea of de Gier [“Loops, matchings and alternating-sign matrices,” Discrete Math., to appear], the proofs are based on bijections between such fully packed loop configurations and rhombus tilings, and the hook-content formula for semistandard tableaux.

1. Introduction

The fully packed loop model (FPL model, for short; see for example [1]) is a model of (not necessarily closed) polygons on a lattice such that each vertex of the lattice is on exactly one polygon. Whether or not these polygons are closed, they will be also referred to as loops. Throughout this article, we consider this model on the square grid of side length n − 1, which we denote by Q_{n}. See Figure 1.1 for a picture of Q_{7}.

Figure 1.1. The square grid Q_{7}

The polygons consist of horizontal or vertical edges connecting vertices of Q_{n}, and edges that lead outside of Q_{n} from a vertex along the border of Q_{n}, see Figure 1.2 for an example of an allowed configuration in the FPL model. We call the edges that stick outside of Q_{n} external links. The reader is referred to Figure 1.3 for an illustration of the external links of the square Q_{11}. (The labels should be ignored at this point.) It should be noted that the four corner points are incident to a horizontal and a vertical external link. We shall be interested here in allowed configurations in the FPL model, in the sequel referred to as FPL configurations, with periodic boundary conditions. These are FPL configurations where, around the border of Q_{n}, every other external link of Q_{n} is part of a polygon. The FPL configuration in Figure 1.2 is in fact a configuration with periodic boundary conditions.

2000 Mathematics Subject Classification. Primary 05A15; Secondary 05B45 05E05 05E10 82B23.

Key words and phrases. Fully packed loop model, rhombus tilings, plane partitions, hook-content formula.

†Research supported by EC’s IHRP Programme, grant HPRN-CT-2001-00272, “Algebraic Combinatorics in Europe".

Figure 1.2. An FPL configuration on Q_{7} with periodic boundary conditions

PSfrag replacements 1 2 3 4n − 1 4n …

Figure 1.3. The labelling of the external links

It is well-known that FPL configurations with periodic boundary conditions are in bijection with configurations in the six vertex model with domain wall boundary conditions, which, in their turn, are in bijection with alternating sign matrices (see, e.g., [8, Sec. 3] for a description of these bijections).

Every FPL configuration with periodic boundary condition defines a matching on the external links taken by the polygons, by matching those which are on the same polygon. There has been a lot of interest recently in the enumeration of fully packed loop configurations on Q_{n} with periodic boundary conditions, in which the matching on the external links is fixed. To a big part this is due to the fact that it was (conjecturally) discovered that these numbers appear as the coordinates of the groundstate vectors of certain Hamiltonians in the dense O(1) loop model. (See [8] for a survey of these developments and conjectures).

Although it is (probably) hopeless to expect a nice closed formula in general, that is, for the number of FPL configurations with periodic boundary conditions corresponding to a fixed matching, for an arbitrary such matching, there exist several conjectures on these numbers for special matchings (see, for example, [15, Sec. 8]). In [16], Zuber added several new ones, one of which he proved immediately in joint work with Di Francesco and Zinn–Justin [6]. Another conjecture in this direction for different boundary conditions, due to Mitra et al. [10], was proved by de Gier in [8, Sec. 5] (which is, in fact, the inspiration for [6], and also the present article). It is our purpose to prove two further conjectures from [16] in this paper, see Theorems 3.2 and 4.2.

In all the proofs, the basic idea is to set up a bijection between the FPL configurations in question and rhombus tilings of certain regions, and then use known results on the enumeration of rhombus tilings to conclude the proof. This is also the procedure which we shall follow here. While in [8] the base of de Gier’s result has been a theorem of Ciucu and the second author [2], and in [6] the base of the result by Di Francesco, Zinn–Justin and Zuber has been MacMahon’s formula for plane partitions contained inside a given box [9], here it is Stanley’s hook-content formula [13, Theorem 15.3] (see Theorem 2.5 below) for the number of semistandard tableaux of a given shape with bounded entries which is at the heart of our proofs. (We remark that this formula implies MacMahon’s, see, e.g., [14, proof of Theorem 7.21.7].) In difference to [6, 8], we are faced here with an added difficulty in the proofs, as it is necessary to split the enumeration problems considered here into several different subcases. Another point worthy of note is the fact that our proofs use Wieland’s remarkable theorem of rotational symmetry [15] (see Theorem 2.1 below) in an essential way, which is not necessary in [6, 8]. That is, our proofs depend crucially on the way the matching is “placed around the square Q_{n}.” We do in fact not know how to do the enumeration if we place the matching in a different way around Q_{n}. On the other hand, it is obvious that, using our approach, one can as well prove the conjectures in Appendix A of [6], although we did not work out the details. We do indeed hope that a refinement of the ideas presented in this article will as well lead to a proof of Conjectures 6 and 7 in [16]. This is work currently in progress.

In the next section, we collect all notation and the facts that we need in our proofs. The proof of Conjecture 4 from [16] is then given in Section 3, while the proof of Conjecture 5 from [16] is the contents of Section 4.

2. Preliminaries

We start by introducing the notation that we are going to use for encoding FPL configurations and their associated matchings. The reader should recall from the introduction that any FPL configuration defines a matching on the external links taken by the polygons, by matching those which are on the same polygon. We call this matching the matching associated to the FPL configuration. When we think of the matching as being fixed, and when we consider all FPL configurations having this matching as associated matching, we shall also speak of these FPL configurations as the “FPL configurations corresponding to this fixed matching.”

We label the 4n external links around Q_{n} by the elements of ℤ/4nℤ clockwise starting from the left-most link on the top side of the square, see Figure 1.3. If A is an external link of the square, we denote by L(A) its label and by LN(A) the representative of L(A) in [−2n + 1, 2n]. Throughout this paper, all the FPL configurations that are considered are configurations which correspond to matchings of either the even labelled external links or the odd labelled external links.

Let M be any matching of the set of even (odd) labelled external links. Let M̃ be the “rotated" matching of the odd (even) external links defined by the property that the links labelled i and j in M are matched if and only if the links labelled i + 1 and j + 1 are matched in M̃. Let F P L(M) denote the number of FPL configurations corresponding to the matching M. Wieland [15] proved the following surprising result.

Theorem 2.1 (Wieland). For any matching M of the even (odd) labelled external links, we have

F P L(M) = F P L(M̃).

In other terms, the number of FPL configurations corresponding to a given matching is invariant under rotation of the “positioning" of the matching around the square. This being the case, we can represent matchings in terms of chord diagrams of 2n points placed around a circle (see Figure 2.1 for the chord diagram representation of the matching corresponding to the FPL configuration in Figure 1.2).

Figure 2.1. The chord diagram representation of a matching

In our proofs we shall also use the following observation of de Gier [8, Lemma 8]. It is an assertion about the edges that are taken by any FPL configuration if one makes certain assumptions.

Lemma 2.2. Let c be an FPL configuration which contains the edges shown to the left of the implication symbol in Figure 2.2. We assume furthermore that the top and the bottom edges do not belong to the same loop and that one of the following two conditions is satisfied:

i) The middle edge belongs to a third loop.

ii) The middle edge is on the same loop as the top (bottom) one only if the loop contains the edge between the left vertex of the top (bottom) edge and the right vertex of the middle edge.

Then c contains all the edges on the right of the implication symbol.

Figure 2.2.

The following result is a consequence of an iterated use of Lemma 2.2. There, and in the sequel, when we speak of fixed edges we always mean edges that have to be occupied by any FPL configuration under consideration.

Lemma 2.3. Let A = A_{1}, A_{2}, …, A_{k} = B be a sequence of external links, where LN(A_{i}) = a + 2i mod 4n, for some fixed a, that is, the external links A_{1}, A_{2}, …, A_{k} comprise every second external link along the stretch between A and B along the border of Q_{n} (clockwise). Furthermore, we suppose that one of the following conditions holds:

(1) A and B are both on the top side of Q_{n}, that is, 1 ≤ LN(A) < LN(B) ≤ n;

(2) A is on the top side and B is on the right side of Q_{n}, that is, 1 ≤ LN(A) ≤ n < LN(B) and n − LN(A) > LN(B) − (n + 1);

(3) A is on the left side and B is on the right side of Q_{n}, that is, n < LN(B) ≤ 2n and −n < LN(A) ≤ 0.

PROOF OF TWO CONJECTURES OF ZUBER ON FULLY PACKED LOOP CONFIGURATIONS 5

PSfrag replacements

O A B A′ B′

Figure 2.3. The possible regions of fixed edges determined by a sequence of external links belonging to distinct loops

Figure 2.4. The hexagon H(5, 3, 2)

Then, for the FPL configurations for which the external links A_{1}, A_{2}, …, A_{k} belong to different loops, the regions of fixed edges are (essentially) triangular (see Figure 2.3 for illustrations; the “essentially” refers to the fact that in Cases (2) and (3) parts of the triangle are cut off). More precisely, if one places the origin O of the coordinate system one unit to the left of the top-left corner of Q_{n}, the coordinates of the triangle are given in the following way: let A′ and B′ be the points on the x-axis with x-coordinates LN(A) and LN(B), respectively, then the region of fixed edges is given by the intersection of the square Q_{n} and the (rectangular isosceles) triangle having the segment A′B′ as basis.

In Cases (2) and (3), the configurations are completely fixed as “zig-zag" paths in the corner regions of Q_{n} where a part of the triangle was cut off (see again Figure 2.3). More precisely, in Case (2), this region is the reflexion of the corresponding cut off part of the triangle in the right side of Q_{n}, and in Case (3) it is that region and also the reflexion of the corresponding cut off part on the left in the left side of Q_{n}.

We next turn our attention to rhombus tilings of subregions of the regular triangular lattice in the plane. Here, and in the sequel, by a rhombus tiling we mean a tiling by rhombi of unit side lengths and angles of 60^{∘} and 120^{∘}. We first recall MacMahon’s theorem mentioned in the Introduction. Let H(p, q, r) be the hexagon with side lengths p, q, r, p, q, r (in clockwise order), all of its angles being 120^{∘}. We imagine H(p, q, r) to be embedded in a triangular lattice. See Figure 2.4 for an illustration of the hexagon H(5, 3, 2). It is well known (see [5]) that rhombus tilings of H(p, q, r) are in bijection with plane partitions contained in a p × q × r box. The number of the latter plane partitions was computed by MacMahon [9, Sec. 429, q → 1; proof in Sec. 494]. Therefore we have the following theorem for the number h(p, q, r) of rhombus tilings of H(p, q, r).

Theorem 2.4 (MacMahon). Let p, q, r ∈ ℕ. Then

h(p, q, r) = \frac{p¡ q¡ r¡ (p + q + r)¡}{(p + q)¡ (p + r)¡ (q + r)¡},

where n¡ := (n − 1)! ⋯ 2! 1! denotes the n-th hyperfactorial.

In the subsequent sections, we shall need a more general result for regions which are indexed by partitions. We recall that a partition is a vector λ = (λ_{1}, λ_{2}, …, λ_{ℓ}) of positive integers such that λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{ℓ}. If there are repetitions among the λ_{i}’s, then, for convenience, we shall sometimes use exponential notation. For example, the partition (3, 3, 3, 2, 1, 1) will also be denoted as (3^{3}, 2, 1^{2}). To each partition λ, one associates its Ferrers diagram, which is the left-justified arrangement of cells with λ_{i} cells in the i-th row, i = 1, 2, …, ℓ. See Figure 2.5 for the Ferrers diagram of the partition (7, 5, 2, 2, 1, 1). (At this point, the labels should be disregarded.) The partition conjugate to λ is the partition λ′ = (λ′_{1}, λ′_{2}, …, λ′_{λ_{1}}), where λ′_{j} is the length of the j-th column of the Ferrers diagram of λ. Given a partition λ, we write (i, j) for the cell in the i-th

PROOF OF TWO CONJECTURES OF ZUBER ON FULLY PACKED LOOP CONFIGURATIONS 7

PSfrag replacements h_{1} h_{2} h_{3} h_{4} v_{1} v_{2} v_{3} v_{4}

Figure 2.5. A Ferrers diagram

row and j-th column in the Ferrers diagram of λ, 1 ≤ j ≤ λ_{i}. We use the notation u = (i, j) ∈ λ to express the fact that u is a cell of (the Ferrers diagram of) λ. Given a cell u, we denote by c(u) := j − i the content of u and by h(u) := λ_{i} + λ′_{j} − i − j + 1 the hook length of u.

The enumeration result for rhombus tilings given in Theorem 2.6 below is a corollary of the hook-content formula for semistandard tableaux of a given shape with bounded entries. Here, semistandard tableaux of shape λ are fillings of the cells of the Ferrers diagram of λ with positive integers such that the entries along rows are weakly increasing and entries along columns are strictly increasing. See Figure 2.8 for a semistandard tableau of shape (7, 5, 2, 2, 1, 1). We denote by SSY T (λ, n) the set of semistandard tableaux of shape λ with entries less than or equal to n. Then Stanley’s hook-content formula [13, Theorem 15.3] reads as follows.

Theorem 2.5 (Stanley). Let λ be a partition, and let n be a positive integer. Then

|SSY T (λ, n)| = ∏_{u∈λ} \frac{c(u) + n}{h(u)}.

Given a partition λ, we are now going to define a region in the regular triangular lattice which depends on λ. The bottom-right border of the Ferrers diagram of λ is a path consisting of positive unit horizontal and vertical steps. This path determines the Ferrers diagram, and hence the corresponding partition, uniquely. It may alternatively be described by the sequence of lengths of its maximal horizontal and vertical pieces (h_{1}, v_{1}, h_{2}, v_{2}, …, h_{k,}, v_{k}). For example this sequence for the partition in Figure 2.5 is (1, 2, 1, 2, 3, 1, 2, 1).

Given a partition λ and a nonnegative integer r, we define the region R(λ, r) as a hexagon with some notches along the top side. More precisely (the reader should consult Figures 2.5 and 2.6 in parallel, the latter showing the region R(λ, 2), where λ is the partition in Figure 2.5), R(λ, r) is the region with base side λ_{1}, bottom-left side λ′_{1}, top-left side r, a top side with notches which will be explained in just a moment, top-right side v_{k}, and bottom-right side r + ∑_{i=1}^{k−1} v_{i}. Along the top side, we start with a horizontal piece of length h_{1}, followed by a notch of size v_{1}, followed by a horizontal piece of length h_{2}, followed by a notch of size v_{2}, …, and finally a horizontal piece of length h_{k}.

We can now state the announced enumeration result for rhombus tilings of the regions R(λ, r).

Theorem 2.6. Given a partition λ and a positive integer r, the number of rhombus tilings of R(λ, r) is given by |SSY T (λ, r + λ′_{1})|.

Proof. There is a standard bijection between our rhombus tilings and families (P_{1}, …, P_{λ_{1}}) of nonintersecting lattice paths, where P_{i} is a path consisting of positive unit horizontal and negative unit vertical steps from (i − λ′_{i}, λ′_{1} − λ′_{i} + i + r) to (i, i) (see, e.g., [3, 4]). Here, “non-intersecting"

8 FABRIZIO CASELLI AND CHRISTIAN KRATTENTHALER

PSfrag replacements h_{1} h_{2} v_{1} v_{2} h_{k} v_{k} r λ_{1} λ′_{1}

r + ∑_{i=1}^{k−1} v_{i}

Figure 2.6. A hexagon with notches

PSfrag replacements 1 2 3 4 5 6 7 8

Figure 2.7. Bijection between rhombus tilings and non-intersecting lattice paths

means the property that no two paths in a family have a point in common. The bijection is obtained as follows. One places vertices in each of the mid-points of edges along the base side of R(λ, r), and as well in each mid-point along the horizontal edges on the top of R(λ, r). The vertices of the top edges are subsequently connected to the vertices along the base side by paths, by connecting the mid-points of opposite horizontal edges in each rhombus of the tiling, see the tiling on the left of Figure 2.7. Clearly, by construction, the paths are non-intersecting. If the paths are slightly rotated, and deformed so that they become rectangular paths, then one obtains families of paths with starting and final points as described above. The family of paths which results from our example rhombus tiling is shown on the right of Figure 2.7 (the labels should be ignored at the moment).

These families of non-intersecting lattice paths are, on the other hand, in bijection with semistandard tableaux of shape λ with entries between 1 and r + λ′_{1} (see, e.g., [7]; it should be noted that Figure 8 in [7] has to be reflected in a vertical line to correspond to our picture). In this bijection, one labels the horizontal steps of the paths in such a way, that a step from (i, j) to (i + 1, j) gets the label j − i, see Figure 2.7. A tableau is then formed by making the labels of the j-th path the entries of the j-th column of a tableau. The tableau corresponding to the family of paths in Figure 2.7 is shown in Figure 2.8. □

PROOF OF TWO CONJECTURES OF ZUBER ON FULLY PACKED LOOP CONFIGURATIONS 9

PSfrag replacements 1 2 3 4 5 6 7 8

Figure 2.8. A semistandard tableau

PSfrag replacements

q

r p

q − 1

r + 1 p + 1

Figure 2.9. K(p, q, r)

We need four special cases of this theorem in particular. We list them explicitly in the following two lemmas.

Lemma 2.7. Let K(p, q, r) be the region R(((p + 1)^{q−1}, p), r) (see Figure 2.9 for an example with p = 10, q = 2 and r = 9). Let k(p, q, r) be the number of rhombus tilings of K(p, q, r). Then

k(p, q, r) = \frac{(p + q + r + 1)¡ (p + 1)¡ q¡ r¡}{(p + q + 2)¡ (p + r + 2)¡ (q + r)¡}(p + q)! (p + r)! q (p + 1) (p + q + 1).

In order to state the next lemma more conveniently, we introduce the following short notation:

a(p, q, r) := \frac{(p + q + r + 2)¡ r¡ q¡ (p + 2)¡}{(p + q + 4)¡ (p + r + 4)¡ (q + r)¡}(p + q + 1)! (p + q + 2)! (p + r + 3)! (p + r)!.

Lemma 2.8. Let L(p, q, r) = R(((p + 2)^{q}, 1, 1), r − 2), M(p, q, r) = R(((p + 2)^{q−1}, p + 1, 1), r − 1), and N(p, q, r) = R(((p + 2)^{q−1}, p), r) (see Figure 2.10 for illustrations of these regions and the corresponding Ferrers diagrams in the case that p = 4, q = 3, and r = 5). Let l(p, q, r), m(p, q, r), and n(p, q, r) be the numbers of rhombus tilings of L(p, q, r), M(p, q, r), and N(p, q, r), respectively. Then

(1) l(p, q, r) = a(p, q, r)\frac{1}{2}(p + 2)(p + 3)(p + r + 1)(p + r + 2)r(r − 1);

(2) m(p, q, r) = a(p, q, r)(p + 1)(p + 3)(p + q + 3)(p + r + 1)qr;

(3) n(p, q, r) = a(p, q, r)\frac{1}{2}(p + 1)(p + 2)(p + q + 2)(p + q + 3)q(q + 1).

Finally, we need the following well-known result about local moves applied to rhombus tilings, see, for example, [12, Theorem 3.1].

Lemma 2.9. Let D be a simply connected region in the triangular lattice. Then the local moves shown in Figure 2.11 act transitively on the set of rhombus tilings of D.

PSfrag replacements q + 1 r − 1

1 p

q − 1 r + 1 p + 2

q r 2

q + 2 r − 2 p + 1

L(p, q, r) M(p, q, r) N(p, q, r)

Figure 2.10. Some regions in the triangular lattice and the corresponding Ferrers diagrams

Figure 2.11. The local moves for rhombus tilings

PSfrag replacements

q r

p − 1

Q R P

Figure 3.1. The matching in Theorem 3.2

3. Proof of conjecture 4 in [16]

The goal of this section is to enumerate the fully packed loop configurations whose associated matching is given by the matching indicated in the left half of Figure 3.1.

Note that we have n = p + q + r + 1. We call the centres of the p − 1, q, and r nested arches P, Q, and R, respectively, see the right half of Figure 3.1. We suppose first that p is even, and we let p = 2s. Thanks to Wieland’s Theorem 2.1, we may place the linkage pattern of the matching arbitrarily around Q_{n}. To prove the conjecture, we shall make use of a particular placement, which we are going to explain next.

We place the centre P on the external link labelled r + s + 1. This choice forces the other centres R and Q to be respectively on the external links labelled by 5s + 3r + 4q + 3 = 3n + (q − s) and 5s + 2q + r + 3 = (2n + 1) + (s − r). In the sequel, by an FPL configuration we shall always mean an FPL configuration corresponding to the particular matching in Figure 3.1. Note that R is located on the bottom side of the square if and only if s ≥ q, and similarly Q is on the bottom PSfrag replacements

O

P Q

R R′

R′′ Q

Q′ Q′′ V W

Figure 3.2. The region of fixed edges

side of the square if and only if s ≥ r. Note also that we have a perfect right-to-left symmetry by exchanging the roles of q and r.

A priori, we have three essentially distinct cases to deal with:

(1) R and Q are both on the bottom side;

(2) R is on the bottom side and Q is on the right side;

(3) R is on the left side and Q is on the right side. We are going to concentrate on Case (2). The Cases (1) and (3) can be treated in exactly the same way. In fact, all the claims that we are going to make for Case (2) are as well true for Cases (1) and (3).

For notational convenience we embed our square in the Cartesian plane in such a way that the left side and the bottom side of the square belong to the y-axis and the x-axis, respectively, with unit length equal to the unit of the square, as shown in Figure 3.2. We let R′′ := (0, n−1+s+r−2), Q′′ := (n − 1, n − 1 + s + q − 2), R′ := (0, q − s) and Q′ := (n − 1, r − s). Then, by Lemma 2.3, R′ and R′′ are two vertices of the triangle of fixed edges determined by the distinct external links between P and R, and similarly for the triangle of fixed edges determined by the distinct external PSfrag replacements

P

R Q

Figure 3.3. The set of fixed edges

links between P and Q (see Figure 3.2). The choice of the position of the centres will ensure that the set of fixed edges has certain useful properties. In fact, if we call V and W the other vertices of these triangles, as shown in Figure 3.2, we can easily see that they have the same y-coordinate y_{V} = y_{W} = s + q + r − 1 and that x_{W} − x_{V} = p − 2. So, the total set of fixed edges will be as indicated in Figure 3.3.

If p is odd, we lose some of the symmetry of the case of even p just discussed. Nevertheless, the argument remains essentially valid. To be more precise, in this case we place P on the external link labelled r + s + 1 where s = \frac{1}{2}(p − 1). The analogues of Figures 3.2 and 3.3 are essentially identical, except that the y-coordinates of the vertices V and W differ by 1.

For both p even and odd, every vertex of the square belongs to at least one fixed edge. If a vertex belongs to exactly one fixed edge we call it a free vertex, and we say that two free vertices are neighbours if they can be joined by a non-fixed edge. Now consider the vertical fixed edge just below P (marked in bold-face in Figure 3.3). It is evident that the two other edges emanating from its vertices have to be both on the right or both on the left, otherwise we could not close the two small loops next to P.

Lemma 3.1. There exists a fully packed loop configuration for both of these choices.

Proof. This is very similar to the proof of [6, Lemma 3] and is hence omitted. □

Theorem 3.2. Let Z_{1}(p, q, r) be the number of fully packed loop configurations determined by the matching in Figure 3.1. Then,

Z_{1}(p, q, r) = \frac{(p + q + r + 1)¡ (p + 1)¡ q¡ r¡}{(p + q + 2)¡ (p + r + 2)¡ (q + r)¡}(p + q)!(p + r)!

× ((p + 1)(q(p + q + 1) + r(p + r + 1)) + p(p + q + 1)(p + r + 1)).

Proof. We treat the case where the edges emanating from the bold-face edge are both on the left of it. This covers also the case where these edges are both on the right, as is seen by an exchange PSfrag replacements

A
B
C
D
E
F

Figure 3.4. The triangles around free vertices

of q and r. Then, following an idea of de Gier [8, Sec. 5], we draw a triangle around any free vertex of our region in such a way that two free vertices are neighbours if and only if the corresponding triangles share an edge. This is illustrated in Figure 3.4 for the example of Figure 3.3 (the two added fixed edges are marked in bold-face).

Next we determine the dimensions of the region covered by these triangles. Let A, B, C, D, E, F be the mid-points of the external links with labels as indicated in the following table. See also Figure 3.4.

point  link’s label
A  s + r
B  s + r + 2
C  3s + r + 2q
D 3s + 3r + 2q + 2
E 7s + 3r + 2q + 4
F 7s + 3r + 4q + 6

Given this information, the lengths of the sides of the region covered by the triangles (measured in terms of triangle edges) are \overline{BC} = \frac{1}{2}((3s + r + 2q) − (s + r + 2)) = s + q − 1, \overline{CD} = r + 1, \overline{DE} = p + 1, \overline{EF} = q + 1 and \overline{F A} = \frac{1}{2}((s + r) + 4n − (7s + 3r + 4q + 6)) = s + r − 1, where in the PSfrag replacements

q + 1

s + r − 1 s − 1 p − 1

s + q − 1

r + 1 p + 1

Figure 3.5. The eared hexagon

last equality we have used the previously observed fact that n = p + q + r + 1 = 2s + q + r + 1. Note the symmetry of these lengths with respect to q and r.

After an appropriate deformation of the region in such a way that it fits in a regular triangular lattice, we obtain a hexagon with two “ears”, see Figure 3.5 for the result of the deformation applied to the region of triangles in Figure 3.4.

It is clear that any tiling of this region defines a fully packed loop configuration just by drawing a segment between the two free vertices corresponding to any tile. By Lemma 3.1, we know that there is an FPL configuration for the case which we are discussing at the moment. Any FPL configuration corresponds to a rhombus tiling of our eared hexagon. By Lemma 2.9, one can go from any rhombus tiling of the eared hexagon to any other by the local moves shown in Figure 2.11. It is easy to see that, under the translation of FPL configurations into rhombus tilings, these moves correspond to the local moves for FPL configurations shown in Figure 3.6. It is an important property of these latter moves that they do not change the matching corresponding to the FPL configurations. It follows that this correspondence establishes a bijection between FPL configurations having the two prescribed edges and rhombus tilings of the eared hexagon.

Figure 3.6. Local moves for FPL configurations

We now embark on the enumeration of the rhombus tilings of the hexagon with two ears. In fact, in the left ear, and in a strip along the left border, the tiles are uniquely determined (see Figure 3.7). Hence we can reduce our calculation to the number of tilings of a hexagon with just one ear, see Figure 3.8 (the shaded triangles should be disregarded for the moment). We call this region F (p, q, r, s).

At this point, the crucial observation is that exactly one of the two tiles which “connect” the hexagon and the remaining ear (these are the shaded tiles in Figure 3.8) must be chosen in any tiling of F (p, q, r, s), otherwise our region would be cut in two subregions with an odd number of triangles. If the right tile is chosen, then our region is split into two separate hexagons, a hexagon H(p + 1, q, r) and a hexagon H(s − 1, 1, 1) (see Section 2 for the definition of H(p, q, r)). Hence PSfrag replacements

q + 1

s + r − 1 s − 1 p − 1

s + q − 1

r + 1 p + 1

Figure 3.7. Fixed rhombi in the eared hexagon

PSfrag replacements

q

r p

s − 1 s + q − 1

r + 1 p + 1

Figure 3.8. Cutting the right ear

the number of rhombus tilings in this case is

h(p + 1, q, r) h(s − 1, 1, 1) = \frac{(p + q + r + 1)¡ (p + 1)¡ q¡ r¡}{(p + q + 1)¡ (p + r + 1)¡ (q + r)¡}s

= \frac{(p + q + r + 1)¡ (p + 1)¡ q¡ r¡}{(p + q + 2)¡ (p + r + 2)¡ (q + r)¡}(p + q)! (p + r)! (s(p + q + 1)(p + r + 1)).

If the left tile is chosen, then the tiling of the ear is uniquely determined, and the remaining region is K(p, q, r). Thanks to Lemma 2.7, we already know the number of corresponding rhombus tilings. Altogether, we obtain that the number of rhombus tilings of F (p, q, r, s) is

f(p, q, r, s) = \frac{(p + q + r + 1)¡ (p + 1)¡ q¡ r¡}{(p + q + 2)¡ (p + r + 2)¡ (q + r)¡}(p+q)! (p+r)! (q(p+1)(p+q+1)+s(p+q+1)(p+r+1)).

Hence, in total, there are Z_{1}(p, q, r) = f(p, q, r, p/2) + f(p, r, q, p/2) FPL configurations. It is easy to verify that this agrees with our claim.

If p is odd, then, using the same approach, one shows that in this case we have Z_{1}(p, q, r) = f(p, q, r, \frac{1}{2}(p − 1)) + f(p, r, q, \frac{1}{2}(p + 1)), which again agrees with our claim. □

Remark. As Jean-Bernard Zuber pointed out to us, Theorem 3.2 confirms the main conjecture of Razumov and Stroganov in [11] (given there in three equivalent forms as Conjectures 1–3; see also PSfrag replacements

q
r
p

Figure 3.9. The “three bridges" matching

PSfrag replacements

q
r
p − 1
Q
R
P

Figure 4.1. The matching in Theorem 4.2

[8, Conj. 1, case H_{2n}^{P}]) and the enumeration result of Di Francesco, Zinn–Justin and Zuber in [6]. To be more precise, the conjecture of Razumov and Stroganov implies the relation

(3.1)  (2(p + q + r) − 3)Z_{0}(p, q, r) = Z_{1}(p − 1, q, r) + Z_{1}(q − 1, r, p) + Z_{1}(r − 1, p, q),

valid for all p, q, r ≥ 2, where Z_{0}(p, q, r) is the number of FPL configurations determined by the matching in Figure 3.9. (This is seen by specializing Conjecture 2 of [11] to the case where π is the matching in Figure 3.9.) Indeed, a direct verification shows that Equation (3.1) is satisfied when the expression for Z_{1}(p, q, r) given by Theorem 3.2 is substituted in (3.1), and when h(p, q, r) is substituted in place of Z_{0}(p, q, r), the equality Z_{0}(p, q, r) = h(p, q, r) being the enumeration result demonstrated in [6].

4. Proof of Conjecture 5 in [16]

In this section we solve the problem of enumerating fully packed loop configurations whose corresponding matching is described in the left half of Figure 4.1. Our method of proof will be analogous to the one in the proof of Theorem 3.2, though many more technicalities will occur.

First of all, we note that this time we have n = p + q + r + 2 (see Figure 4.1). Again we first suppose p to be even, and we let p = 2s. We call the centres of the p − 1, q, and r nested arches P, Q, and R, respectively, as before, see the right half of Figure 4.1. We place P on the external link numbered r+s+2. Consequently Q is on the external link labelled 5s+2q+r+6 = (2n+1)+s−r+1, and R is on the external link labelled 5s + 4q + 3r + 6 = 3n + (q − s). We introduce the same system of coordinates as in Section 3, and we let R′ := (0, q − s), R′′ := (0, (n − 1) + r + s − 3), Q′ := (n − 1, r − s − 1) and Q′′ := (n − 1, (n − 1) + s + q − 2). Then these points determine the triangles of fixed edges (see Figure 4.2). Again, the vertices V and W of these triangles have the same height, y_{V} = y_{W} = s + q + r − 1, and we have x_{W} − x_{V} = p − 2.

At this point, by Lemma 2.3, we can easily draw the set of fixed edges corresponding to our choice of the position of the centres P, Q and R (see Figure 4.3).

PSfrag replacements

O P Q

R R′ R′′ Q

Q′ Q′′

V W

Figure 4.2. The region of fixed edges

PSfrag replacements

P Q

R

Figure 4.3. The set of fixed edges

Again, any vertex of the square grid belongs to at least one fixed edge. However, here we have to split our problem into four cases, according to the local configuration around the centre P. There are indeed four mutually exclusive possible configurations near P, see Figure 4.4.

Lemma 4.1. There exists a fully packed loop configuration for any of the four local configurations shown in Figure 4.4.

Proof. Again the proof is omitted since it is very similar to the proof of [6, Lemma 3]. □

PSfrag replacements

P q + 1

r − 1 1 p

q − 1 r + 1 p + 2

q r 2

q + 2 r − 2 p + 1

r + s − 2 s − 2 q + s s − 1

q + s − 1 s

Figure 4.4. The possible local configurations and the corresponding regions

Theorem 4.2. Let Z_{2}(p, q, r) be the number of fully packed loop configurations determined by the matching in Figure 4.1. Then

Z_{2}(p, q, r) = \frac{a(p, q, r)}{2}(p + 2)((p + 1)(p + q + 3)(p + r + 1)(p(p + r + 2) + pq + 4qr)+

+ 2p(p + q + 3)q(p + r + 1)(p + q + 2) + 2(p + 1)(p + q + 3)(p + r + 1)(p + r + 2)r+

+ (p + 3)(p + r + 1)(p + r + 2)r(r − 1) + (p + 1)(p + q + 2)(p + q + 3)q(q + 1)).

Proof. Again, we only discuss the case where p is even, since the other case is completely analogous. We already know that Z_{2}(p, q, r) is the sum of four parts corresponding to the local configurations described in Figure 4.4. In each of these cases we proceed similarly as in the proof of Theorem 3.2.

We draw a triangle around any free vertex in such a way that triangles share an edge if and only if the corresponding vertices are adjacent. After a suitable deformation of the corresponding regions, we can fit these regions in the regular triangular lattice. Again, there are certain parts which are covered by forced tiles and which may hence be eliminated. See Figure 4.4 for an illustration of the resulting regions in each of the four cases (the shaded triangles should be disregarded for the moment). We now observe that Lemmas 2.9 and 4.1 imply that in each of the four cases there is a bijection between the fully packed loop configurations and rhombus tilings of the corresponding region in the triangular lattice. So the number of fully packed loop configurations is equal to the sum of the number of tilings of these four regions. We treat them one at a time. Below, the numbers (1)–(4) refer to the corresponding numbers in Figure 4.4.

(1) Consider the three shaded tiles. It is easy to see that exactly two of them should be chosen in any tiling of this region. If we choose the first two, then the region is split into two hexagons, a hexagon H(s − 2, 1, 2) and a hexagon H(p + 2, q, r). If we choose the first and the third, then the region is split into a hexagon H(s − 1, 1, 1) and a region K(p + 1, r, q). Finally, if we choose the second and the third tile, our region reduces to a region L(p, q, r). Hence the total number of rhombus tilings in this case is

\frac{1}{2}s(s − 1) · h(p + 2, q, r) + s · k(p + 1, r, q) + l(p, q, r).

(2) Any tiling of the second region must contain exactly one of the two shaded tiles on the left and exactly one of the two shaded tiles on the right. If we choose the first on both the right and the left, then we obtain a hexagon H(s − 2, 1, 1) and a region K(p + 1, q, r). If we choose the first on the left and the second on the right, we split the region into three hexagons, a hexagon H(s − 2, 1, 1), a hexagon H(p + 2, q, r), and a hexagon H(s, 1, 1). If we choose the second on the left and the first on the right, we obtain a region M(p, q, r). Finally, if we choose the second on both the left and the right, we split the region into a hexagon H(s, 1, 1) and a region K(p + 1, r, q). Hence the number of rhombus tilings in this case is

(s − 1) · k(p + 1, q, r) + (s^{2} − 1) · h(p + 2, q, r) + m(p, q, r) + (s + 1) · k(p + 1, r, q).

(3) Again, we have to choose exactly one of the two shaded tiles. If we choose the first one, we get a region K(p + 1, q, r), and if we choose the second one, we get two disjoint hexagons, a hexagon H(s, 1, 1) and a hexagon H(p + 2, q, r). Hence the number of rhombus tilings in this case is

k(p + 1, q, r) + (s + 1) · h(p + 2, q, r).

(4) In this last case we have to choose exactly one of the three tiles. If we choose the first one, we get a region N(p, q, r). If we choose the second, we obtain a hexagon H(s − 1, 1, 1) and a region K(p + 1, q, r), and if we choose the third one, we get a hexagon H(s − 1, 1, 2) and a hexagon H(p + 2, q, r). Hence the number of rhombus tilings in this case is

n(p, q, r) + s · k(p + 1, q, r) + \frac{1}{2}s(s + 1) · h(p + 2, q, r).

Putting everything together, the total number Z_{2}(p, q, r) is given by the sum of these four expressions, that is

Z_{2}(p, q, r) = (2s^{2} + s) · h(p + 2, q, r) + 2s · k(p + 1, q, r) + (2s + 1) · k(p + 1, r, q)

+ l(p, q, r) + m(p, q, r) + n(p, q, r).

Now note that, by Theorem 2.4 and Lemma 2.7, there hold

h(p + 2, q, r) = a(p, q, r)(p + q + 2)(p + q + 3)(p + r + 1)(p + r + 2),
k(p + 1, q, r) = a(p, q, r)(p + 2)(p + q + 3)q(p + r + 1)(p + q + 2),

and

k(p + 1, r, q) = a(p, q, r)(p + 2)(p + q + 3)(p + r + 1)(p + r + 2)r.

If we also recall Lemma 2.8, then it follows that

Z_{2}(p, q, r) = a(p, q, r)(\frac{p}{2}(p + 1)(p + q + 2)(p + q + 3)(p + r + 1)(p + r + 2)

+ p(p + 2)(p + q + 3)q(p + r + 1)(p + q + 2)

+ (p + 1)(p + 2)(p + q + 3)(p + r + 1)(p + r + 2)r

+ \frac{1}{2}(p + 2)(p + 3)(p + r + 1)(p + r + 2)r(r − 1)

+ (p + 1)(p + 3)(p + q + 3)(p + r + 1)qr

+ \frac{1}{2}(p + 1)(p + 2)(p + q + 2)(p + q + 3)q(q + 1))

= \frac{a(p, q, r)}{2}(p + 2)((p + 1)(p + q + 3)(p + r + 1)(p(p + r + 2) + pq + 4qr)

+ 2p(p + q + 3)q(p + r + 1)(p + q + 2) + 2(p + 1)(p + q + 3)(p + r + 1)(p + r + 2)r

+ (p + 3)(p + r + 1)(p + r + 2)r(r − 1) + (p + 1)(p + q + 2)(p + q + 3)q(q + 1)),

which agrees with the expression in the assertion of the theorem. □

Acknowledgement

We thank Jean-Bernard Zuber for several corrections and interesting remarks on earlier versions of this paper.

References

[1] M. T. Batchelor, H. W. J. Blöte, B. Nienhuis and C. M. Yung, “Critical behaviour of the fully packed loop model on the square lattice,” J. Phys. A 29 (1996), L399–L404.

[2] M. Ciucu and C. Krattenthaler, “Enumeration of lozenge tilings of hexagons with cut-off corners,” J. Combin. Theory Ser. A 100 (2002), 201-231.

[3] M. Ciucu, T. Eisenkölbl, C. Krattenthaler and D. Zare, “Enumeration of lozenge tilings of hexagons with a central triangular hole,” J. Combin. Theory Ser. A 95 (2001), 251–334.

[4] M. Ciucu and C. Krattenthaler, “Plane partitions II: 5 \frac{1}{2} symmetry classes,” Combinatorial Methods in Representation Theory, M. Kashiwara, K. Koike, S. Okada, I. Terada, H. Yamada, eds., Advanced Studies in Pure Mathematics, vol. 28, RIMS, Kyoto, 2000, 83–103.

[5] G. David and C. Tomei, “The problem of the calissons,” Amer. Math. Monthly 96 (1989), 429–431.

[6] P. Di Francesco, P. Zinn-Justin and J.-B. Zuber, “A bijection between classes of fully packed loops and plane partitions,” preprint. math.CO/0311220.

[7] M. Fulmek and C. Krattenthaler, “Lattice path proofs for determinant formulas for symplectic and orthogonal characters,” J. Combin. Theory Ser. A 77 (1997), 3–50.

[8] J. de Gier, “Loops, matchings and alternating-sign matrices,” Discrete Math., to appear.

[9] P. A. MacMahon, “Combinatory Analysis,” vol.~2, Cambridge University Press, 1916; reprinted by Chelsea, New York, 1960.

[10] S. Mitra, B. Nienhuis, J. de Gier and M. Batchelor, “Exact expression for correlations in the ground state of the dense O(1) model,” preprint. cond-mat/0401245.

[11] A. V. Razumov and Yu. G. Stroganov, “Combinatorial nature of the ground state vector of O(1) loop model,” Theoret. Math. Phys. 138 (2004), 333–337. math.CO/0104216.

[12] N. C. Saldanha and C. Tomei, “An overview of domino and lozenge tilings,” Resenhas 2 (1995), 239–252.

   math.CO/9801111.

[13] R. P. Stanley, “Theory and applications of plane partitions: Part 2,” Stud. Appl. Math. 50 (1971), 259–279.

[14] R. P. Stanley, “Enumerative Combinatorics,” Vol. 2, Cambridge University Press, Cambridge, 1999.

[15] B. Wieland, “A large dihedral symmetry of the set of alternating sign matrices,” Electronic J. Combin. 7 (2000), Article #R37.

[16] J. B. Zuber, “On the counting of fully packed loops configurations. Some new conjectures,” Electronic J. Combin. 11 (2004), Article #R13.

Institut Girard Desargues, Université Claude Bernard Lyon-I, 21, avenue Claude Bernard, F-69622 Villeurbanne Cedex, France