SSL Notes
2004-01-29 Thursday
Today's note-taker: Hal
Today's food-bringer: Sam

                                * * *

URS, the Undergraduate Research Symposium.

Is it happening this year?  If so, are we going to do it?  In past
years, we have presented a poster.  The proposals are due in February.

        http://www.learning.wisc.edu/ugsymposium/

Jim will have new contracts for us soon.

Next Tuesday's notetaker is Sam.

Next Tuesday's snackbringer is Paul.

Brendan is late.  He shows up later and mentions that he has a class
until 3:45.  Jim will consider moving the meeting time to TR
3:45-5:45. 

                                * * *

Jim discusses 2d models that are similar to what we did last
semester.  We'll start with plane partitions and Eric Kuo and then
move on to some open problems.

Jim:

Snakes are essentially 1d objects, but here's something similar that is
2d:  The Aztec Diamond Graph (AD) of order 3.
                *---*
                |   |
            *---*---*---*
            |   |   |   |
        *---*---*---*---*---*
        |   |   |   |   |   |
        *---*---*---*---*---*
            |   |   |   |
            *---*---*---*
                |   |
                *---*

A matching on that graph:

                *---*
                    
            *   *   *---*
            |   |       
        *   *   *   *   *   *
        |           |   |   |
        *   *---*   *   *   *
                        
            *---*   *---*
                    
                *---*

If we generalize the AD to order n, then it has 2^((n+1)*n/2)
matchings.  Note that the Aztec Diamond is dial to the Aztec Diamond
Graph.  You do tiling on Aztec Diamonds, and (perfect) matchings on
Aztec Diamond Graphs.

In the first part of Kuo's paper, he gave a theorem that we applied to 
snakes.  That theorem can be generalized for ADs.

Start by rotating the graph 45 degrees.  Call this graph G.

          o   o   o
         / \ / \ / \
        o   o   o   o
         \ / \ / \ /
          o   o   o
         / \ / \ / \
        o   o   o   o
         \ / \ / \ /
          o   o   o
         / \ / \ / \
        o   o   o   o
         \ / \ / \ /
          o   o   o
         
Now look only at the southwest corner of the graph:

          o   o   o

        o   o   o   o

          o   o   o
         / \ / \
        o   o   o   o
         \ / \ /
          o   o   o
         / \ / \
        o   o   o   o
         \ / \ /
          o   o   o

It's another AD!  Call it  Gsw.  Gsw is an order n-1 graph.
Define Gnw. Gne, Gse to be the other order n-1 graphs.  Define Gc like
this:


          o   o   o

        o   o   o   o

          o   o   o
             / \
        o   o   o   o
             \ /
          o   o   o

        o   o   o   o

          o   o   o

Gc is the intersection of all four corners.  It is an order n-2 AD.
Let M(g) be the set of matching of a graph g.

Kuo's Condensation Theorem:
        |M(G)| * |M(Gc)| = |M(Gnw)| * |M(Gse)| + |M(Gsw)| * |M(Gne)|

Dodgson Condensation
        det(M) * det(MC) = det(Mnw) * det(Mse) - det(Msw) * det(Mne)

where M is a square matrix.

There is a big, general result (Kuo, Robbins, Propp) that gives a
condensation formula for lambda-bideterminants that includes both
of these results as special cases.

Hal:

What is the fundamental thing about determinants and weighted
matchings that make them related?

Jim:

Look at this:

            ( a b c )
        M = ( d e f )
            ( g h i )
         
        det( M ) = aei + bfg - bdi  + ...

Now look at K_{3,3} with the left vertices associated with rows of M
and the right vertices associated with columns of M.  Then edges are
entries in M.  What is the weighted sum of matchings?

        aei + bfg + bdi + ...

We are okay so far up to the signs!

Also note that 6 of the 8 matchings of the order 2 AD correspond to
terms of det(M).  /* I don't quite see this - H */

Suppose G_n is the AD of order n.  We want to calculate |M(G_3)|.
From Kuo, we have:

        |M(G_3)| * |M(G_1)| = |M(G_2)| * |M(G_2)| + |M(G_2)| * |M(G_2)|

        |M(G_3)| * 2 = 8 * 8 + 8 * 8

        |M(G_3)| = 64.

By induction we could show that :

        |M(G_n)| = 2^{n(n+1)/2}.

THIS IS THE OCTAHEDRON RECURRENCE!

Just like Pascal's Triangle, where each row is determined by the row
above it, imagine a three-dimensional array of numbers packed together
in an octahedral way:
            _______________
           /              /
          /      a       /
         /              /
        /______________/___
           /   b    c     /
          /              /
         /   d    e     /
        /______________/___
           /              /
          /     f        /
         /              /
        /______________/

Where:

        f * a = b * e + lambda * c * d

Two sheets determine the entire system.

The Octahedron Recurrence gives Laurent polynomials!

Example:  f(n) * f(n-2) = f(n-1) * f(n-1) + 1, where
f(0) = x and f(1) = y.

/* May be missing a bit here. */

Instead of looking at ADs, look at hexagonal honeycomb lattices.
There are three parameters to its size.  |M(H_{2,2,2})| = 20.

/* May be missing a bit here. */

The Somos-5 Sequence.

        f(n) * f(n-5) = f(n-1) * f(n-4) + f(n-2) * f(n-3) 

The Somos-K sequence is:

f(n) * f(n-K) = f(n-1) * f(n-K+1) + f(n-2) * f(n-K+1) + ...
              = SUM_{i=1}{(K-1)/2} f(n-i) * f(n-K+i)  if K odd
              = SUM_{i=1}{K/2} f(n-i) * f(n-K+i)  if K even

Somos-5 is: 1,1,1,1,1,2,3,5,11,37,83,274,...  It always comes out as
an integer!  If the first five terms are a,b,c,d,e, then it always
comes out Laurent (Fomin & Zelevinsky).  With combinatorics it is
furthermore shown that the coefficients are all positive, because they
count something.

Or, we can consider

        f(n) * f(n-5) = alpha * f(n-1) * f(n-4) + beta  * f(n-2) * f(n-3) 

/* May be missing a bit here. */

Gale-Robinson Recurrence:

(*)     f(n) * f(n-m) = f(n-i) * f(n-m+i) + f(n-j) * f(n-m+j)

        for some value of (i,j,m).

(**)    f(n) * f(n-i-j-k) = f(n-i) * f(n-j-k)
                          + f(n-j) * f(n-i-k)
                          + f(n-k) * f(n-i-j)

        for some value of (i,j,k).

        For instance, let (i,j,k)=(1,2,4):

        f(n) * f(n-7) = f(n-1) * f(n-6)
                      + f(n-2) * f(n-5)
                      + f(n-3) * f(n-4)

There are recurrence relations that don't seem to fit the mold:

        f(n) f(n-4) = f(n-1) f( n-3) + f(n-2)

This always seems to come out integers.  We don't have any general
idea of why that works!

        #!/usr/bin/perl
        @f=(0,1,1,1,1);
        foreach $n (1..4) {print $f[$n], ", ";}
        foreach $n (5..40) {
            $f[$n] = ( $f[$n-1] * $f[$n-3] + $f[$n-2] ) / $f[$n-4];
            print $f[$n], ", ";
        }

        1, 1, 1, 1, 2, 3, 5, 13, 22, 41, 111, 191, 361, 982, 1693,
        3205, 8723, 15042, 28481, 77521, 133681, 253121, 688962,
        1188083, 2249605, 6123133, 10559062, 19993321, 54419231,
        93843471, 177690281, 483649942, 834032173, 1579219205,
        4298430243, 7412446082, 14035282561, 38202222241,
        65877982561.0001, 124738323841, ...

                                * * *

Then we went to the other room and looked at what Emilie has been up
to.  Her results live here:

        http://www.sit.wisc.edu/~eahogan/folder/mbrother.ppt

                                * * *