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.