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