SSL Notes for meeting #4 (9/18)
Today's notetaker: Hal (Carl next time)
Today's snackprovider: Martin (Paul next time)
Present at the meeting were: Martin, Emily, Abby, Sam, Paul,
Stephen, Hal, Carl. Jim was an hour or so late. Stephen led
us until then.
Introduction.
We each went around and introduced ourselves and gave our
favorite math word.
MARTIN  "Combinator"  This term shows up in cs.
EMILY  "mathilicous"  She made this up; it means "good and
mathy." She then gave a real word she likes:
"quandles" which refers to binary operations on
knots.
ABBY  "binomial"  because it is a concept that shows up
in many places. Her least favorite math word is
"trivial".
SAM  "quaternion"  He's been learning about the
quaternions in algebra. Stephen asked if he meant the
group of quaternions that make up S^3 or just the
units. He answered the units.
PAUL  "annihilator" He saw this in 491.
STEPHEN  "coherent sheaves"  These are a generalization of
vector spaces.
HAL  "quine"  From _Goedal, Escher, Bach_, which everyone
should read.
CARL  "logarithm"  It has neat etymology. From the Greek
"number speech".
[At this point we move down the hall because we prefer the
intimacy of the other room. Perhaps we should meet there by
default in the future?]
Status Report:
MARTIN has checked out the status of the DVD. See his email for
details.
He also gave us a summary of the progress he made on the snake
recurrence. He presents a pictograph proof. What he did
was first break all snakes into two classes based on whether
the last two squares were added in the same direction:
[A] [B]
oooo ooo
:    or   
o...ooo ooo
: 
Dotted lines in this graph o...o
represent squares where we
are uncertain where the snake goes from here.
[A] gives us the Fibonaccitype recurrence.
oooo ooo o
:    > :   
o...ooo o...oo o
or
oo oo
: 
o...o oo
[B] is a little more difficult to deal with.
At this point Hal says that he has dealt with this case.
BEGIN:
First he introduces his notation. A box is marked _u_ for
"up" if it is above the previous box and _r_ if it is right of
the previous box. The first box is not either, so we call it
_e_. Therefore a staircase snake with 5 boxes might be
represented as eurur. Let M(x) be the set of all matchings of
snake x and let N(x) := M(x) = the cardinality of that set.
To use Hal's notation, Martin showed that
N(xrr) = N(x) + N(xr).
Either a snake is of the form xrr or xuu or it is of the form
xur or xru. The first two cases were dealt with by Martin,
but the second are insolvable without more information.
First case Hal will deal with is a snake of the form
e(ru)^k. This is a pure staircase snake.
oo
 u 
ooo
 u  r 
ooo
(ellipsis)  r 
oo oo
 u 
ooo
 e  r 
ooo
Try to match the last vertex to something:
oo
u
ooo
 u  r 
ooo
(ellipsis)  r 
oo oo
 u 
ooo N(e(ru)^{k1}r) ways to match this.
 e  r 
ooo
> OR <
o o
 
o o o

o o oo
(ellipsis)
o o oo By choosing not to match
 the last two vertices, we
o o oo force our choices all of
 the way down.
o oo There is only one matching.
Therefore, N(e(ru)^k) = N(e(ru)^{k1}r) + 1.
Also deal with the similar case of er(ur)^k. Then get the
general formulas:
N(e(ru)^k) = 2k + 2
N(e(ur)^k) = 2k + 2
N(er(ur)^k) = 2k + 3
N(eu(ru)^k) = 2k + 3
This agrees with our observations.
There is one other case we have not encountered. If a snake
does not end in rr or uu or is an staircase, then it must end
in a staircase of some length preceded by a rr or a uu. In
other words, of the form:
xrr(ur)^k
xr(ru)^k
xuu(ru)^k
xu(ur)^k
Hal gives an example of how to deal with that.
Let's look at xuu(ru)^k = xu(ur)^{k}u
oo
 u 
ooo
 u  r 
oooo
 r 
oo
(ellipsis)
oo
 u 
oooo
 u  r 
ooo
 u 
oo
 x  Because X is unknown, we don't know if it
oo needs in a r or a u
 
Just as before look at two cases
oo
ooo
 u  r 
oooo
 r 
oo
(ellipsis)
oo If the last two vertices are
 u  connected, then we are left
oooo with xu(ur)^{k}.
 u  r 
ooo
 u 
oo
 x 
oo
 
> OR <
o o
 
o o o

o o oo

o oo
(ellipsis)
o o

o o oo

o oo
The cascading leaves
oo us only with the snake x.
 x 
oo
 
Therefore,
N(xu(ur)^{k}u) = N(xu(ur)^{k}) + N(x).
This is identical to the arithmetic progression we noticed
before, with the number we are always adding being N(x).
In the proof, deal similarly with all of the other cases
listed before.
The proof goes like this: we have covered all of the possible
cases and expressed the number of matchings of each snake in
terms of the number of tilings of smaller snakes. Therefore
this is a true recursive algorithm for finding N(x).
END.
The consensus is that this proof could be turned into a nice
inductive proof.
We then talked about all of the ways to approach this
problem. The method that involves building long snakes out of
smaller one seems to be forwardlooking. The method of
reducing a long snake to smaller snakes seems to be
backwardlooking. And there there is the odd way of breaking a
snake in half down the middle, which is the odd man out.
EMILY worked on finding a combinatorial proof for
f_n * f_n = f_{n+1} * f_{n1} + (1)^n (*)
Which I will refer to as "equation (*)" in the notes.
She didn't have much to say about her progress.
CARL also worked on proving equation (*). He went to the
chalkboard and shared his progress. First there was a
discussion on how to count straight snake graphs. Do we refer
to them by the number of pairs of vertices (Carl prefers this)
or do we refer to them by the number of boxes? Also, when we
draw a unmatched bipartite graph, do we draw the edges or
leave them out?
First note:
f_{1} f_0 f_1 f_2 f_3 f_4
0 1 1 2 3 5
? {} o oo ooo oooo
         
o oo ooo oooo
Carl takes this as proof that we should count pairs of
vertices.
Carl explains some things, but I will boil it down to this
relationship, which he proves combinatorially.
f_n * f_m = f_{m+n}  f_{m1} * f_{n1}
Proof:
Consider of f_n * f_m to be the size of the set
M(Sn) disjoint_union M(Sm)
where Sn is the straight snake with 2*n vertices and n1 boxes
(Hal's kludgey notation).
Draw the two matchings side by side and consider them as a
matching of S{n+m}.
What matchings of S{n+m} never show up in this set?
Sn Sm
ooooooo oooo
          
ooooooo oooo
M(Sn) disjoint_union M(Sm)
S{n+m}
ooooooooooo
          
ooooooooooo
M(S{n+m})
S{n+m}  Sn * Sm
oooooo oo ooo
        
oooooo oo ooo
M(S{n+m})  (M(Sn) disjoint_union M(Sm))
bijection to
S{n1} S{m1}
oooooo ooo
        
oooooo ooo
M(Sn) U M(Sm) = M(S{n+m})  ( M(S{n1}) U M(S{m1}) )
f_n * f_m = f_{m+n}  f_{m1} * f_{n1}
But this doesn't end up going anywhere.
We asked which case would end up being bad enough to lead to
the extra matching that doesn't fit the equation? Carl said
the one with all horizontal lines.
SAM said he's like to relay a little misadventure that he had.
He said that the had a way to count the number of perfect
matchings on a snake graph with one bend and 2(n+m) vertices:
f_{m} * f_{n1} + f_{m1} * f_{n}
He then tried to prove equation (*) but failed.
Sam also produced a proof of the general snake recurrence that
was similar to Hal's.
* * *
[Sometime around here Jim shows up and we break for snacks.
Martin has provided cool cans of Diet Coke and a large bag of
goldfish.]
[At this point I remembered that we should ask for a notetaker
for next Tuesday. Carl volunteered. And Paul will provide
refreshment.]
* * *
JIM gives his favorite math word now that he's arrived:
"heteroskedastic".
ABBY found an algebraic proof of equation (*). She also asked for
a good example of a combinatorial proof. Why do we like
combinatorial proofs so much? Because they work in systems
too complicated for algebraic proofs.
PAUL had no luck with equation (*). In general, multiplication in
combinatorial equations means making an independent choice.
For instance, choosing from an disjoint union of sets.
HAL didn't do anything.
A proof of equation(*).
At this point we have finally finished status reports and Jim
wants to give a sweet proof of equation(*).
This example will use n = 8.
Start by choosing two random matchings of S8.
oo o oo oo o
 
oo o oo oo o
[1]
o oo o o oo o
   
o oo o o oo o
Then superimpose them like so:
oo ooo ooo o
      [2]
oo ooo ooo o
Then uncondense them into graphs of size n+1 and n1:
oo oo o o oo o
  
oo oo o o oo o
[3]
o o oo oo o
  
o o oo oo o
We made two independent choices, so there were four ways to do
it. But there were four pairs graphs in step [1] that would go to
the same graph at step [2].
Another example:
oo oo o o oo
 
oo oo o o oo
[1]
o oo o o o o o
     
o oo o o o o o
gives this sum:
oo o o o o oo o
      [2]
oo o o o o oo o
And we have exactly one choice when we decide how to break it up,
because we had one loop.
And what is the bad case that gives the (1)^n?
oo oo oo oo
oo oo oo oo
[1]
oo oo oo oo
oo oo oo oo
which gives
ooooooooo
ooooooooo
Which has no decomposition. Try:
oo oo oo oo o
oo oo oo oo o
[1]
oo oo oo o
oo oo oo o
This leaves unpaired vertices. "We're hosed."
And that concludes the proof.
Note: normally, the four vertices on the outside are connected to
the ones next to them, but in the bad case they are connected the
other way. Some kind of topological discrimination is taking
place.
Homework:
Do NOT read
http://front.math.ucdavis.edu/math.CO/0304090
Instead, look at snakes with vertices deleted.
First mark each vertex as belonging in two groups.
xoxo
   
xoxox
  
xoxoxo
    
oxoxo
Now choose four vertices, two of each kind, in such a way that as
you move along the boundary of the snake, you alternate between
types.
Then try and delete first none, then a pair (one o and one x) in
all four possible ways, then all four vertices. Here is what all
six will look like:
Delete vertices.
xoxo
   
x xox
  
xo o o
    
xoxo
Delete edges.
xoxo
  
x xox
 
xo o o
 
xoxo
Delete edges that can not be used:
xo xo
 
x x ox
 
xo o o
xo xo
That graph has two perfect matchings.
Look for an algebraic relationship. Also try it when you pick the
four vertices (two o's and two x's) so that they don't alternate
as you go around the boundary.