SSL Notes for meeting #2 (9/11)
Paul is the notetaker for today
The next note-takers will be Stephen (Tuesday) and Hal (Thursday)
Snacks will provided next time by Sam
Go around with names, and give a favorite math-quote.
Martin: "God invented the integers. All else is the work of man."
Emily: "This is completely insane." In the middle of the proof.
Abby: Sir Ronald Fischer
Josh: "I encourage you to work on it, but you won't get anywhere."
"What's purple and commutes? An abelian grape."
Hal: "Mathematicians are instruments that turn coffee into theorems."
Sam: "God exists because mathematics is consistent. The devil exists
because we cannot prove it."
Paul: "Because I can walk through this door, infinity exists."
Jim: "But don't you see, that just makes it more interesting." Barry
Mazur to Andrew Wiles, after finding a flaw in a proof.
Stephen: "The Littleton-Richardson rule helped man get to the moon,
but it wasn't proved until after they got there. The first part of
this is an exaggeration."
Everyone signed the contract, except for Hal, who exempted himself out of it.
Show tee-shirts
The shirt is about a specific recurrence. Example of a nonlinear recurrence
that results in whole numbers. On the shirt, these terms are also shown by
perfect matchings of different graphs. Ends in a bijective proof. Define
the relationship as perfect matchings of graphs instead of numbers and it
works better. Eventually, we should get to Somos sequences, but starting
with snakes is a good base.
The second teeshirt. Example of a combinatorial object pulled out of an
algebraic recurrence.
The last shirt is from years ago. Never figured out any real proofs about
the picture on the front. It is possible that we will come back to this
during this SSL term. The picture on the back is hals proof involving
Aztec diamonds.
What's the deal with making Maple available?
Student liscence for Maple 9 is about 120 dollars. Too late to crosslist
Math 491 with CS. CS people can get access to Maple.
Jim will talk to the CSL people to see if we can get access to Maple.
www.cs.wisc.edu/csl/. The version of maple is a unix version, and
the unix labs are never full, so the machines probably aren't overused.
Paul will look into the Wendt Library "renting Maple" system. We could
possibly find an older version of Maple for less money. Hal could avoid
studies that require Mathematica or Maple. Sam will probably buy Maple.
These are the only two people without access to either Mathematica or
Maple. Emily will try to burn the maple file on CD and give it to Sam.
No one requires more time in B107 for the use of Maple. The limiting factor
should be our time, not availability of computers!
Is everyone getting the email I've been sending out to ssl@math.wisc.edu?
Yes.
What's the deal with creating 80-character-wide ASCII files?
Everyone should look at their email and make certain that they are sending
things through ascii format. Hal thinks we should get a different protocol
such as imap.
Hal is trying to send mail through outlook express to see if he can send a
good email.
Commands in Outlook Express: imap server, incoming mail is wiscmail.wisc.edu,
outgoing mail is wiscmail.wisc.edu.
View the available folders. It is impossible to get clean emails through
wiscmail interface.
Get help from http://helpdesk.doit.wisc.edu/page.php?id=1376
There is a command called format. Jim saves email to a file.
fmt < testemail. If you are doing this from UNIX, you can use
this command. The program called pine should handle these things
correctly. Pine still shows the embedded html font, but does
wraparound correctly.
The solution for this is to use plain text format (for students),
and for Jim to use pine.
Let's look at
jamespropp.org/SSL/ (public stuff)
jamespropp.org/SSL/minutes.html
It is a new site that shows the minutes of our meetings.
jamespropp.org/SSL/markoff.txt has a description
of Jim's talk on Monday.
The file 03.09 in the private section of the SSL site has email
listings from SSL. It is password protected.
(how do I clear out password access?)
We need to close down and go to the break room (B115).
Thanks Abby for the brownies.
Two problems: Go around the room.
Steven: Forgot about the second problem. Has explicit formulas for
certain kinds of snakes.
Josh: Didnt work too hard on the snakes. Counted vertices and making
tables. For the recurrence relation, I think I got it.
Hal: Didn't work on either one.
Martin: Thought a little bit about counting the perfect matchings of
the snakes.
Emily: Noticed on the meandering snakes to break it into two cases.
Just take the across sections and makes it one case.
Look at the vertical case, too. Sort of an approach.
Didn't look at the bijection.
Abby: Found a procedure to count perfect matchings (just to the right
and up). For the bijection, I did it one way but not the other.
Sam: Found different recurrences for different classes of snakes.
Wants to find a better way to classify them to see the relationship
between them all and unify them. Found a lot of linear recurrences.
Couldn't find anything on the bijection.
Paul: Just worked on a couple of classes of snakes and found a few
relationships and integer sequences. The snake group that goes
over one up one has the least amount of perfect matches per box.
Didn't work on the bijection.
If the boxes don't meet, it doesn't matter if you go left or right,
but if they do meet, there will be different numbers of perfect
matchings.
Jim to give us some direction: imagine this snake is growing from infancy
and write down the perfect matchings in each box.
We should draw our pictures that way, so that the head grows up and to
the right, but the tail stays in the same space.
.__.__.
| 7| 9|
.__.__.__.__. and so on.
| 2| 3| 5|
.__.__.__.
Sam: So counting the boxes and trying to come up with something from that
is a wrong path?
Jim: I don't want to answer that. Has anyone gone down a wrong path?
Martin: I was looking at non-snakes and realized I couldn't get 2x2 box
because of the odd number of vertices.
Jim: Let's look for a proof for the sets of rectangular graphs such that
we know which ones we can find perfect matches to.
Martin: (to the board) I think you could do a checkerboard type argument.
Never mind, I'm full of lies. I'll sulk back to my seat.
Josh: If you take even number in the rows, just pair them.
.__. .__.
.__. .__.
.__. .__.
Jim: That does it. There are formulas for counting the perfect matchings
of rectangles. Some of them use trig, which is strange because it
give irrational numbers, but the combination of them give whole numbers.
Maybe it isnt so weird to use irrationals though, because the formula
for Fibonacci numbers have square root of five in it, but it never gives
an irrational as an answer. The following is not a homework problem,
but just something to think about. Look at a rectangular graph with
an odd number of vertices. Remove the corner dot so that we can make
perfect matches.
.__.__.__.__.
| | | | |
.__.__.__.__. doesn't have any perfect matchings, but
| | | | |
.__.__.__.__.
.__.__.__.
| | | |
.__.__.__.__.
| | | | |
.__.__.__.__.
maybe could (it has an even number of vertices).
Emily: The corners are all even.
Jim: How does the degree of the vertex relate to the perfect matchings?
(Jim marks the odd and even degree on the 3x5 (vertices) rectangle).
If we remove the upper left corner from 3x5, we have 6 vertices of odd degree.
If we remove the second one in, we have 8 odd vertices.
If we remove the middle upper dot, we have 6 odd vertices.
Stephen: Pick two vertices and drop all the edges. It decreases the degree
of that dot, but also the adjacent dot. The total parity always has
to be even.
Jim: There is a related thing that has to do with the handshake theorem.
There is an even number of us who have shaken hands an odd number of
times with other people in this group.
Say this is a diagram of four people (A,B,C,D).
A has degree one, B has degree four, D has degree two, C has degree one.
Sam: If you change one persons status of handshaking, you actually change
two, because there are two people involved in a handshake.
Jim: So your proof is an inductive one. Start where no one shakes hands
and add handshakes. Here is a direct way to see it.
The sum of the degrees of the graphs is the number of edges times two.
Switching back, why can't you find a perfect matching of an 8 by 8 grid
of vertices with two diagonally opposite corner vertices removed?
(If we mark the vertices so that each 1 is surrounded by 0s and vice
versa, then the two opposite corners have the same marking.)
Let's take a checkerboard 8x8 and cover it with 1x2 dominos. Take out
the opposite corners, and you can't do it. Why?
Sam: Because the corners are the same color. But 1x2 dominoes will
cover a black and a white square, so its impossible.
Jim: Let's make the example smaller. Let's take a four by four square
and cover it with 8 1x2 rectangles. My claim is that the ways to
do that is the same amount of the perfect matchings of the 4x4 graph.
Let's see how to do that.
Put dots in the middle of every square and draw dots. Connect and overlay,
and you will see the domino approach is the same as the graph approach.
This give us an idea of the answer to the problem with the deformed
3x5 graph. If we take away a vertex labeled 0, there would be 6 0's
and 8 1's. But in order to have perfect matchings, we need there to
be the same number of 1s and 0s.
1__0__1__0__1 0__1__0__1 1 1__0__1
| | | | | | | | | | | | |
0__1__0__1__0 0__1__0__1__0 has matchings whereas 0__1__0__1__0 does not.
| | | | | | | | | | | | | | |
1__0__1__0__1 1__0__1__0__1 1__0__1__0__1
Jim: I want you to look at what would happen if you took away a corner
vertex of a rectangular graph and compare it to a graph where you
take away a different vertex labeled the same. Compare the numbers
of perfect matchings. Devise a conjecture.
Any questions?
Sam: Did you want to mention the other problem? I think Josh had some
kind of work on it.
Jim: I wanted to leave that until next time. I only have this to say
about that problem. Try to make it more symmetrical, and if you can't,
that might be an interesting result as well. What we are really
interested in is a bijection between the perfect matchings of one graph
to another graph. You could actually create a map that commutes
with symmetry operations on the graphs.
S-->T
^ ^
| |
S-->T
Sam: Wouldn't the symmetric one be found first because it would intuitively
be easier?
Jim: I agree, if it exists.