SSL Notes for meeting #4 (9/18)
Today's note-taker: Hal (Carl next time)
Today's snack-provider: 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]
		o---o---o---o			o---o---o
		:   |   |   |		or	|   |   |
		o...o---o---o			o---o---o
						:   |
	Dotted lines in this graph		o...o
	represent squares where we
	are uncertain where the snake goes from here.

	[A] gives us the Fibonacci-type recurrence.

		o---o---o---o	      	o---o---o   o
		:   |   |   |	-->   	:   |   |   |
		o...o---o---o	      	o...o---o   o
					  or
					o---o   o---o
					:   |        
					o...o   o---o

	[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.

		                       o---o
		                       | u |
		                   o---o---o
				   | u | r |
		                   o---o---o
			(ellipsis) | r |
		    o---o	   o---o
		    | u |
		o---o---o
		| e | r |
		o---o---o

	Try to match the last vertex to something:

		                       o---o
		                         u 
		                   o---o---o
				   | u | r |
		                   o---o---o
			(ellipsis) | r |
		    o---o	   o---o
		    | u |
		o---o---o	N(e(ru)^{k-1}r) ways to match this.
		| e | r |
		o---o---o

			     ---> OR <---

		                       o   o 
		                       |   | 
		                   o   o   o 
				   |         
		        o          o   o---o
			|(ellipsis)    
		    o   o	   o---o      By choosing not to match
		    |   		      the last two vertices, we
		o   o   o---o		      force our choices all of
		|     			      the way down.	      
		o   o---o	              There is only one matching.

	Therefore, N(e(ru)^k) = N(e(ru)^{k-1}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

		                       o---o
		                       | u |
		                   o---o---o
				   | u | r |
		                o--o---o---o
			           | r |
		                   o---o
                           (ellipsis)

		      o---o
		      | u |
		  o---o---o--o
		  | u | r |
		  o---o---o
		  | u |
		--o---o
		  | x |  Because X is unknown, we don't know if it
		--o---o  needs in a r or a u
		  |   |

	Just as before look at two cases
		                       o---o
		                          
		                   o---o---o
				   | u | r |
		               o---o---o---o
			           | r |
		                   o---o
                           (ellipsis)

		      o---o		If the last two vertices are
		      | u |		connected, then we are left
		  o---o---o--o		with xu(ur)^{k}.
		  | u | r |	
		  o---o---o
		  | u |
		--o---o
		  | x | 
		--o---o 
		  |   |
		              ---> OR <---

		                       o   o
		                       |   |
		                   o   o   o
				   |       
		               o   o   o---o
			       |       
		               o   o---o
                           (ellipsis)
		      o   o
		      |   
		  o   o   o--o
		  |       
		  o   o---o
					The cascading leaves
		--o---o			us only with the snake x.
		  | x | 
		--o---o 
		  |   |

	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 forward-looking.  The method of
	reducing a long snake to smaller snakes seems to be
	backward-looking.  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_{n-1} + (-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	o--o	o-o-o	o-o-o-o
				|	|  |	| | |	| | | |
				o	o--o	o-o-o	o-o-o-o

	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_{m-1} * f_{n-1}
	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 n-1 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
		o--o--o--o--o--o--o  o--o--o--o
		|  |  |  |  |  |  |  |  |  |  |
		o--o--o--o--o--o--o  o--o--o--o
		    M(Sn) disjoint_union M(Sm)


		       S{n+m}
		o--o--o--o--o--o--o--o--o--o--o
		|  |  |  |  |  |  |  |  |  |  |
		o--o--o--o--o--o--o--o--o--o--o
		        M(S{n+m})

		       S{n+m} - Sn * Sm
		o--o--o--o--o--o  o--o  o--o--o
		|  |  |  |  |  |        |  |  |
		o--o--o--o--o--o  o--o  o--o--o
		    M(S{n+m}) - (M(Sn) disjoint_union M(Sm))
			      bijection to

		       S{n-1}            S{m-1}
		o--o--o--o--o--o        o--o--o
		|  |  |  |  |  |        |  |  |
		o--o--o--o--o--o        o--o--o

	    M(Sn) U M(Sm)  =  M(S{n+m}) - ( M(S{n-1}) U M(S{m-1}) )

		f_n * f_m = f_{m+n} - f_{m-1} * f_{n-1}
			   
	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_{n-1} + f_{m-1} * 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 note-taker
	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.

		o---o   o   o---o   o---o   o
		        |                   |
		o---o   o   o---o   o---o   o
						      [1]
		    o   o---o   o   o   o---o   o
		    |           |   |           |
		    o   o---o   o   o   o---o   o

    Then superimpose them like so:

		o---o   o---o---o   o---o---o   o
		    |   |       |   |       |	|     [2]
		o---o   o---o---o   o---o---o	o

    Then uncondense them into graphs of size n+1 and n-1:

		o---o   o---o   o   o   o---o   o
		                |   |        	|
		o---o   o---o   o   o   o---o	o
                                                     [3]
		    o   o   o---o   o---o   o
		    |   |                   |
		    o   o   o---o   o---o   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:

		o---o   o---o   o   o   o---o
		                |   |       
		o---o   o---o   o   o   o---o
						      [1]
		    o   o---o   o   o   o   o   o
		    |           |   |   |   |   |
		    o   o---o   o   o   o   o   o

    gives this sum:

		o---o   o         o   o   o   o---o   o
		    |             ||  ||  |   |   |     [2] 
		o---o   o         o   o   o   o---o   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?

		o---o   o---o   o---o   o---o
		                            
		o---o   o---o   o---o   o---o
						      [1]
		    o---o   o---o   o---o   o---o
		                                
		    o---o   o---o   o---o   o---o

    which gives

		o---o---o---o---o---o---o---o---o
		                            
		o---o---o---o---o---o---o---o---o

    Which has no decomposition.  Try:

		o---o   o---o   o---o   o---o   o
		                            
		o---o   o---o   o---o   o---o   o
						      [1]
		    o---o   o---o   o---o   o
		                                
		    o---o   o---o   o---o   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.

                        x---o---x---o
 			|   |   |   |
                    x---o---x---o---x
		    |   |   |
	x---o---x---o---x---o
	|   |   |   |   |                            
	o---x---o---x---o

    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.
                        x---o---x---o
 			|   |   |   |
                    x--- ---x---o---x
		    |   |   |
	x---o--- ---o--- ---o
	|   |   |   |   |                            
	 ---x---o---x---o

    Delete edges.
                        x---o---x---o
 			    |   |   |
                    x       x---o---x
		    |       |
	x---o       o       o
	    |       |                                
	    x---o---x---o

    Delete edges that can not be used:

                        x---o   x---o
 			        |   |
                    x       x   o---x
		    |       |
	x---o       o       o
	                                             
	    x---o   x---o

    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.