SSL Notes for meeting #7 (9/30) Today's note-taker: Martin (on deck: Emilie, Sam) Note-taker for next time: Emilie and Sam on Thursday, Paul on Tuesday Today's snack-provider: Stephen Snack-provider for next time: Carl. Note that cups are in Jim's office; tell him to bring them if necessary. Go around with names, and ask everyone to talk about their favorite weird-sounding or weird-looking name of a mathematician or mathematicians: Stephen: Bruhat and Tits (pronounced "Teets") John: Kolmogorov-Arnold-Moser (KAM of KAM Theory) Carl: Jacobi and Mobius Paul: Chebyshev Emilie: Mobius (because of an instructor who pronounced it "Meebius") Abby: Irizarri (genetic statistician) Sam: Erdos Martin: Szelepcsenyi (undergrad who solved open question in complexity theory) Jim: Huygens, Lekkerkerker Remind about Thursday: Ten-minute meetings with everyone. Paul, Emilie, Abby, Josh, Sam, Martin, Joe, Hal, Carl 3:30: Paul 3:45: Emilie 4:00: Carl 4:15: Hal 4:30: Sam 4:45: Martin 5:00: Abby 5:15: Josh 5:30: Let's go around and talk about what people are working on, and what they're finding interesting: Martin: Looked at 2 x n rectangle graphs. Appeared to be isomorphic to 3 x 2n domino tiling as seen in 491. Looked a little at x-and-y weighted coefficients. Also, was interested in something we did in 491 today on counting the number of strings of a given length that follow some pattern. In 491 we saw that the number of binary strings of length n which do not have 2 1's in a row is F_{n+1}. More on this later. Sam: Looked at the coefficients of Fibonacci polynomials of degree n (weighted straight snakes). Abby: Examined the sums of weights of matchings when you take out the four vertices (more empirical validation of the conjecture we established last meeting). Found that on the following graph: a__.__. | | b__c__d where A (all dots) = y^3 +2x^2y, B (no a,b) = x^2+y^2 C (no c,d) = xy D (no a,d) = x^2 E (no b,c) = xy F (no a,b,c,d) = x and therefore AF = BC+DE still holds. Abby also looked at hexagon matchings. __ / \ \__/ / \ \__/ has 3 perfect matchings: __ / \ / \ __ , \ / , / \ \ / \ / __ She found a simple arithmetic progression: H_n = n+1. Emilie: Also examined the hexagons but found a different pattern. Straight hexagon snakes follwed Abby's arithmetic progression but bent snakes followed a Fibonacci progression. This established two theories about hexagonal snakes. In addition, Emilie examined pentagonal snakes. The first observation is that you need an even number of pentagons to have a matching because each pentagon contributes an odd number of vertices. (The first pentagon contributes 5 and each pentagon thereafter shares two of the old vertices, thus contributing 3.) Two pentagons stuck together like so: /\ / \ | | |__| | | | | \ / \/ are really an octogon because the middle edge cannot be used. Paul: Verified the AF = BC + DE conjecture for hexagons -- at least, it seems to be correct. He also essentially replicated Sam's work independently, proving the relationship inductively. Carl: Along with Sam and Paul, also looked at weighted straight snakes. Was amazed by the conciseness of the relation. Reasoned combinatorially. Also looked at hexagons and agrees with Abby that the number of matchings is an arithmetic progression, but is unconvinced of his correctness. This leaves us with two opinions: is the number of hexagon snake matchings purely arithmetic, or is there also a Fibonacci component? John: Had to prepare a calculus exam. Stephen: Also looked at the hexagons but refused to state his opinion as he knew it would carry too much weight. The class attempted to do matchings for three bent hexagons. Emilie and Paul each found five instead of four, which the arithmetic progression rule would have predicted. Their strategy for counting perfect matchings relies on forcing an edge to be matched and then reducing to a smaller case after only a few steps, which Jim dubbed a "divide and conquer" approach. Emilie and Paul go up to the board and depict their findings. For one case, we reduce to the case of one hexagon, and for the other case, two hexagons. (Note that ASCII art makes depicting the matchings somewhat difficult, but hopefully it will be understandable.) __ __/ \ / \ / \__/ / __ \__/ : __ + / \ / \ <- contains two matchings (simple) \__/ \__/ __ __ / \ / \__/ / \ <- contains three matchings (seen earlier in this report) \__/ So, five matchings total. We realized that a blob argument would show us that a left bend and a right bend produce the same result. We would like to exhibit a bijection between square and hexagonal snakes, as if we take a square snake and make a hexagonal one which bends wherever the square one is straight and is straight wherever the square one bends, we should get the same result. We then decided to vote on what to look at next, be it looking at sums of binomial coefficients or what Martin did. We decided to look at what Martin did, perhaps because he seemed to be enthusiastic. Most of the rest of the class was devoted to Martin's explanation of what a regular language is. First, he defined a finite state machine (or finite automaton) M as some tuple: M = (Q, S, d, F, s), where Q is a finite set of states S (Sigma) is our finite alphabet set (the binary alphabet is {0,1}) d: Q x S -> Q is our transition function F, a subset of Q, is our set of final states, and s, a member of Q, is our start state. We can then evaluate some string x in S^* (i.e., the set of all finite strings on the alphabet S) in the following manner: We start in the state s. Then, we look at x. If x is the empty string, we stop where we are. Otherwise, x can be written as x_1y where x_1 is in S and y is a string. (We're popping off the first character of the string x.) We then use d to determine, given where we are and the chracter x_1, where to go. We then look at y the same way we looked at x above. Since each step whittles down our string by one character, this process eventually terminates and we find ourself in some state. We say x is "accepted" by M if the state we find ourself in is in F. Otherwise, x is "rejected". We refer to L, a subset of S^* as a "language". If L is equal to the set of strings accepted by some finite state machine M, we call L a "regular language." Examples of regular languages: * All strings that begin and end with the same letter. * All strings that do not contain two 1's in a row. (We'll call this language L'.) This language is accepted by the following machine: ({1,2,3},{0,1},d,{1,2},1), where d is the following table: 0 1 1 1 2 (1 represents "haven't just seen a one") 2 1 3 (2 represents "have just seen a one, but not two ones") 3 3 3 (3 represents "have seen two ones") We can prove inductively that this machine "works". We can see that there are F_{n+1} strings of length n in L' using the following argument: there is one such empty string (the only empty string), and two strings of length 1 (both 0 and 1), and three of length 2 (00, 01, 10, but not 11) which follow the pattern. Suppose we have some string of length n+2. It follows the pattern if and only if the first character is 0 and the remaining n+1 characters follow the pattern, or the first character is 1, the second character is 0, and the remaining n characters follow the pattern. (The other case would be that the first two characters are both 1, in which case it does not follow the pattern.) Thus, K_{n+2}, the number of strings of length n+2 that follow the pattern, is equal to K_{n+1} + K_n, following the Fibonacci recurrence, aside from the sequence beginning 1, 2 instead of 1, 1. Jim then explained the concept of generating functions, which are algebraic objects that can be thought of as both infinite sequences {a,b,c,d,e,...} and coefficients of polynomials a + bx + cx^2 + dx^3 + ex^4 + ... The number of strings of a given length of L' can be represented by the generating function: 1 + 2x + 3x^2 + 5x^3 + 8x^4 + 13x^5 which can be written as a rational function of x: 1 + x ----------- 1 - x - x^2 There is a theorem which states that for any regular language, the number of strings of a given length can be written as a generating function representable as a rational function of x. On the other hand, if we augment the representation above by using a stack, we give ourself additional expressive power, because now we have the ability to store an arbitrary amount of information (albeit with only the top thing on the stack available at any given time). We call this representation a "pushdown automaton." There is another theorem which states that the number of strings of a given length that a pushdown automaton accepts is equal to an algebraic function, such as __________ \ / 1 \ / -------- \/ 1 - 4x^2 (In fact, this particular algebraic function has the property that the coefficient of x^n in its Taylor expansion around x=0 is just (n choose n/2) when n is even and 0 when n is odd, which in turn equals the number of words of length n containing equal numbers of 0's and 1's. Jim showed us a pushdown automaton that recognizes the equal-numbers-of-0's-and-1's language.)