[Back to my homepage] [Version française]

"Fully-packed loop configurations" (FPL) are fascinating objects with connections to statistical physics (the "6-vertex model") and mathematics (they are in one-to-one correspondence with "alternating-sign matrices", which generalize permutation matrices and appear in determinant formulae due do Dodgson.

An FPL of size *N* is a subgraph of an *NxN* square grid,
where *each vertex has degree exactly 2*. Border conditions are
defined as follows: half the border vertices, alternatively, have a
single edge leaving the grid (which leaves only degree 1 inside the
grid); corners count as two vertices for the border conditions.

As an example, here is one of the 129534272700 FPL of size 10, chosen uniformly at random using the "coupling from the past" (CFTP) technique.

In each FPL, the *2N* border edges are connected to one
another by paths, which define a (perfect, noncrossing) matching of
the *2N* endpoints. On each such matching, one can pick any two
endpoints and "cross links":

There are many conjectures on the number of FPL which show a given
matching. One of them can be expresses as: *there exists an ergodic
Markov chain whose state space is the set of FPL of size N, whose
stationary distribution is uniform, and which, when "projected" on the
corresponding matchings, yields a new Markov chain whose steps
correspond to picking (uniformly at random) two adjacent endpoints and
crossing their links*.

The Markov chain on matchings is obviously invariant by a rotation
of *1/2N* turn; that the distribution of matchings on FPLs has
the same property was proved by B. Wieland, who described a very
elegant bijection on FPLs which has the effect of "rotating" the
matchings. This bijection is illustrated below on an FPL of size
20.

(I am cheating slightly here: in one frame out of two, the exterior edges are the wrong ones, and the picture is the complementary of a proper FPL. The animation is just easier to read this way.)

The "coupling from the past" technique due to Propp and Wilson can easily be applied to generate uniformly random FPLs, and this is how all the pictures on this page were obtained.

Here is a small gallery of pictures, all in PDF format:

- "Unconstrained" (non-symmetric) FPLs of sizes 40, 60, 80, 100, 200.
- "Half-turn symmetric" (invariant under a half-turn rotation) FPLs, sizes 40, 60, 80, 100, 200.
- "Quarter-turn symmetric" (invariant under a quarter-turn rotation) FPLs, sizes 40, 60, 80, 100, 200.
- The three largest above (size 200), with a single path (selected for its length) drawn in red: unconstrained, half-turn symmetric, quarter-turn symmetric.
- The same, with the circle inscribed in the square
superimposed. Here some of the squares in the grid are color-coded:
those that are local extrema of the corresponding height matrix are
deep blue or pink, and those that are "almost" local extrema
(
*i.e.*, three out of four of the neihbouring squares are,*e.g.*, higher, while the last is lower) are light blue or light pink. unconstrained, half-turn symmetric, quarter-turn symmetric.

[Back to my homepage] [Version française]