REACH Minutes
Thursday February 27

[transcribed by Kyle and edited by Jim]

John will be note taker for Tuesday.

Andy presented some of his and Rui's work:

The Markov numbers are triples of whole numbers satisfying the relation
        a^2+b^2+c^2 = 3abc
(e.g., (a,b,c)=(1,5,2)).  Note that you can write the relation as a 
quadratic in one of the variables:
        a^2 - (3bc)a + (b^2+c^2) = 0
This implies that, given a Markov triple (a,b,c), we can obtain a new triple 
(a',b,c) by setting  aa' = b^2 + c^2  or  a+a' = 3bc.  Ditto for changing
b and c.  If we start with the initial triple (1,1,1), then a graphical 
representation of the Markov numbers is an infinite graph (a tree, in fact):
                             .   :   .
                              .  :  .
                              (1,2,1)
                                 |
                                 |
                              (1,1,1)
                              /     \
                             /       \
                       (2,1,1)       (1,1,2)
                       .  :  .       .  |  .
                      .   :   .     .   |   .
                                     (1,5,2)
                                     /  :  .
                                    /   :   .
                             (29,5,2)
                             .   :  .
                            .    :   .
There is a corresponding graph of triples of Laurent polynomials 

                             .   :   .
                              .  :  .
                         (x,(x^2+z^2)/y,z)
                                 |
                                 |
                              (x,y,z)
                              /     \
                             /       \
                ((y^2+z^2)/x,y,z)  (x,y,(x^2+y^2)/z)
                       .  :  .       .  :  .
                      .   :   .     .   :   .

where the polynomials in each triple (f,g,h) satisfy the relation
        f^2 + g^2 + h^2 = ((x^2+y^2+z^2)/xyz)fgh ;
we can obtain each triples from a simpler triple, going all the way
back to the initial triple (x,y,z), by means of the exchange rules

hh' = f^2 + g^2

or

h+h' = ((x^2+y^2+z^2)/xyz)fg

(and similarly for exchanging f or g).

Generally speaking there are corresponding triples of graphs (A,B,C) whose 
matchings are encoded by the Laurent polynomials by giving edges weights 
x,y, and z, and whose number of matchings are Markov triples.  How a new 
triple of graphs is obtained from an old, and all of the related proofs 
can be found on Andy's page: 

http://www.people.fas.harvard.edu/~itsara/www/index.html

Jim asked if there might be a three dimensional version of Andy and Rui's 
two dimensional graphs.

Jim showed us a correspondence between lattice paths and domino tilings.

Claim lattice paths from A to B of of the following graph correspond to 
domino tilings of a 2 by 4 rectangle:
                                  ___________________________
A-------o-------B                |      |      |      |      |
 \     / \     /                 A      |      o      |      B
  \   /   \   /     <--------->  |______|______|______|______| 
   \ /     \ /                   |      |      |      |      |
    o-------o                    |      o      |      o      |
                                 |______|______|______|______|
      
    Paths A->B                           Domino Tilings

The paths from A to B of the left hand side are in bijection with paths 
from A' to B' of the following graph, each of which corresponds to a 
perfect matching of the subsequent graph:

A'      o       o       B'          o          o--o          o--o          o
 \     / \     / \     /             \        /    \        /    \        /
  \   /   \   /   \   /               \      /      \      /      \      / 
   \ /     \ /     \ /                 \    /        \    /        \    /
    o       o       o                   o--o          o--o          o--o
     \     / \     /                        \        /    \        /   
      \   /   \   /      <--------->         \      /      \      /
       \ /     \ /                            \    /        \    /
        o       o                              o--o          o--o
         \     /                                   \        /
          \   /                                     \      / 
           \ /                                       \    /
            o                                         o--o

      Paths A'->B'                              Perfect Matchings

Some of the edges are forced in the matching graph, so we can consider 
matchings of the modified graph on the left below.  But we can replace 
----o----o---- with ----- to get a correspondence with the graph on the 
right below:

       o--o          o--o    
      /    \        /    \   
     /      \      /      \                      
    /        \    /        \ 
   o          o--o          o                   o----------o--o----------o
    \        /    \        /      <--------->    \        /    \        /
     \      /      \      /                       \      /      \      /
      \    /        \    /                         \    /        \    /
       o--o          o--o                           o--o----------o--o
           \        /
            \      /                                 Perfect Matchings 
             \    / 
              o--o      
         
         Perfect Matchings                            

With only a slight modification the graph on the right looks like a 2 by 4 
grid graph, whose matchings are clearly in bijection with domino tilings of 
a 2 by 4 rectangle.

Next Jim showed us how Urban Renewal could give a correspondence between 
tilings of 3 by 3 Aztec Diamonds and tilings of 2 by 2 Aztec Diamonds.  

   o       o                                       o-------o
    \     /                                        |       |
     o---o           (not a bijection)             |       |
     |   |          <----------------->            |       |
     o---o    (but a reversible correspondence)    |       |
    /     \                                        |       |
   o       o                                       o-------o


Begin with the 3 by 3 Aztec Diamond graph and add some extra edges:

    o       o       o                        o         o         o
   / \     / \     / \                       |         |         |
  /   \   /   \   /   \                      o         o         o
 /     \ /     \ /     \                     |         |         |
o       o       o       o                    o         o         o
 \     / \     / \     /                    / \       / \       / \
  \   /   \   /   \   /              o--o--o   o--o--o   o--o--o   o--o--o
   \ /     \ /     \ /                      \ /       \ /       \ / 
    o       o       o                        o         o         o
   / \     / \     / \                       |         |         |
  /   \   /   \   /   \                      o         o         o
 /     \ /     \ /     \                    / \       / \       / \
o       o       o       o  ------>   o--o--o   o--o--o   o--o--o   o--o--o
 \     / \     / \     /                    \ /       \ /       \ /
  \   /   \   /   \   /                      o         o         o
   \ /     \ /     \ /                       |         |         |
    o       o       o                        o         o         o
   / \     / \     / \                      / \       / \       / \
  /   \   /   \   /   \              o--o--o   o--o--o   o--o--o   o--o--o
 /     \ /     \ /     \                    \ /       \ /       \ /
o       o       o       o                    o         o         o
 \     / \     / \     /                     |         |         |
  \   /   \   /   \   /                      o         o         o
   \ /     \ /     \ /                       |         |         |
    o       o       o                        o         o         o

Then we perform urban renewal to reduce the problem to a 3 by 3 AD with some 
extra edges.  But since the extra edges are forced in any matching, we get a 
2 by 2 AD:

       o     o     o
       |     |     |
       o     o     o                        
      / \   / \   / \                       
     /   \ /   \ /   \                   
 o--o     o     o     o--o                       o     o
     \   / \   / \   /                          / \   / \  
      \ /   \ /   \ /                          /   \ /   \
       o     o     o                          o     o     o
      / \   / \   / \                          \   / \   / 
     /   \ /   \ /   \                          \ /   \ / 
 o--o     o     o     o--o    ------>            o     o
     \   / \   / \   /                          / \   / \
      \ /   \ /   \ /                          /   \ /   \
       o     o     o                          o     o     o
      / \   / \   / \                          \   / \   / 
     /   \ /   \ /   \                          \ /   \ /
 o--o     o     o     o--o                       o     o 
     \   / \   / \   /                     
      \ /   \ /   \ /                      
       o     o     o    
       |     |     |
       o     o     o

If we iterate this procedure, we can turn an Aztec diamond of order n
into an Aztec diamond of order 0 (which is trivial).  This is one way
to count domino tilings of large Aztec diamonds.

Similarly to Urban Renewal, there is a transformation for spanning trees 
that can help reduce problems to smaller problems.  The "Wye-Delta" move 
looks like the following:


      o_       _o           o---------o
        \_   _/              \       /
          \ /                 \     /     (like urban renewal, 
           o       <--->       \   /      this is not a bijection)
           |                    \ /
           o                     o

To see it in action consider spanning trees of the following triangular graph 
(suggestive of groves):


             o---------o---------o---------o
              \       / \       / \       /
               \     /   \     /   \     /   
                \   /     \   /     \   /
                 \ /       \ /       \ /
                  o---------o---------o
                   \       / \       /
                    \     /   \     /
                     \   /     \   /
                      \ /       \ /
                       o---------o
                        \       /
                         \     /
                          \   /
                           \ /
                            o

By applying Wye-Delta to every downward pointing triangle we get:

             o_       _o_       _o_       _o
               \_   _/   \_   _/   \_   _/
                 \ /       \ /       \ /   
                  o         o         o
                  |         |         |
                  o_       _o_       _o
                    \_   _/   \_   _/
                      \ /       \ /
                       o         o
                       |         |
                       o_       _o
                         \_   _/
                           \ /
                            o
                            |
                            o

Now apply Wye-Delta to the centermost vertex and its incident edges to obtain:

             o_       _o_       _o_       _o
               \_   _/   \_   _/   \_   _/
                 \ /       \ /       \ /   
                  o         o         o
                  |        / \        |
                  o_      /   \      _o
                    \_   /     \   _/
                      \ /       \ /
                       o---------o
                       |         |
                       o_       _o
                         \_   _/
                           \ /
                            o
                            |
                            o

Since we are only concerned with spanning trees we can replace ---o--- with 
---. So upon replacement we have a smaller graph whose spanning trees are in 
bijection with a 2 by 2 triangle graph (since the outermost edges are fixed):

        o_                           _o
          \_                       _/
            \                     /   
             o---------o---------o                   o---------o---------o
              \       / \       /                     \       / \       /
               \     /   \     /                       \     /   \     /
                \   /     \   /                         \   /     \   /
                 \ /       \ /                           \ /       \ /
                  o---------o        <---->               o---------o 
                   \       /                               \       /
                    \     /                                 \     /
                     \   /                                   \   /
                      \ /                                     \ /
                       o                                       o
                       |                                      
                       o                                      

Maybe this method of reduction is worth looking into when working on grove 
shuffling problems.  There is a paper on Wye-Delta moves.  Cecilia will 
make a copy of it for the web.  [Note: It is now available on the web via
http://wilbur.wellesley.edu/~clam/deltawye.pdf]

Jim mentioned a few more miscellaneous research topics:
1. Is there a condensation for graphs where the edges are labelled so that 
the sum at each vertex is a constant?
2. What is the right way to add/multiply two Somos sequences (thinking of 
them as sequences of points on an elliptic curve)?
3. Look at the cluster algebra structure of Apollonian packings (tangent 
circles) arising from the sort of packings described in the April 2002
issue of the American Mathematical Monthly
4. A large question: Is there a reasonable way of deciding what the right 
denominator should be for a Laurent monomial?  e.g. when is x really 
1/(1/x) ?
5. The (1,4) recurrence

We talked about how to better communicate- Cecilia offered to set up a web log
rather than send out lots of emails.  [Note: It is now available, as described
in Cecilia's email sent on February 28.] Jim will be gone next week so we 
should start working on problems.  But we still want to do things as a large 
group.  Gabriel will talk to Greg Price by Tuesday, so that he might present 
something in the meeting on Tuesday.  Kyle agreed to talk a little bit about 
limiting behavior of groves for Thursday.  There are several unwritten papers 
done by past REACHers.  They include:  Anti-Frieze patterns (Reid is working 
on this), Baxter permutations, and at least three pieces of work by David 
Speyer (number fences, transfer matrices, crosses and wrenches).  Jim says 
if you read a rough write up and think "Huh, wish I'd thought of that!" you 
can still help out by writing up the formal paper (after getting in touch 
with the original author, of course).

Incidentally, here is John Nash Jr.'s home page: 
        http://www.math.princeton.edu/jfnj/
In particular, in his texts_and_graphics directory, you might want to check out
        .../jfnj/texts_and_graphics/LOGIC/axioms.pict.jpg
(a picture of some notes on logic schemata --- I have no idea what it means),
        .../jfnj/texts_and_graphics/Equation_an_Interesting/equation.gif
(a thought of his, on cosmology I think), and
        .../jfnj/texts_and_graphics/RAND/k1361.a20
(a memo from his days at the RAND corporation --- a little spooky).