SEVENTH MEETING (10/15/02; notes taken by Anton) The following people should take special notice (you have something you need to do): Dan Z Inna Dean Jen Anton took notes. Dan Zaharopol will take notes next time. Anna took attendance "When talking, remind everyone of your name" Gabriel reserved Loker Coffeehouse for Tuesdays and Thursdays 3-5pm ... we'll soon know if we're meeting there this Thursday. Jim got a tax-exemption number for Inna from the department. Inna will burn DVDs of the math 192 videos. Discuss http://jamespropp.org/bilinear/domino What were the typos that were found? Dean and Jen will email Jim about errors in papers. In general, the note-taker should make sure that such details get recorded. More generally, if there's anything that the note-taker doesn't understand, part of her or his job is to make the speaker repeat it and/or explain it more clearly and/or promise to send an email that explains it. GOOD STUFF: A Polynomial-time Algorithm for Detecting Tileability of Polyhexes via Trihexes Good reference: math.wisc.edu/~propp/articles.html "A Pedestrian Approach to a Method of Conway, or, A Tale of Two Cities" Its in the middle of the "Tiling" section. Given a region, the problem of deciding whether it can be tiled with certain tiles is NP complete. That is, there is no way to determine in polynomial time whether the region is tileable (unless P=NP, which is unlikely). Trial and error is about the only thing to do. However, if we fix the tiles and ask "can this region be tiled with these tiles?" there are often algorithms that can answer this question in polynomial time. We would like to have such an algorithm for detecting tileability of polyhexes (regions consisting of hexagons stuck together along the edges) by trihexes. We consider two types of trihexes: linear: __ / \ \__/ / \ \__/ / \ \__/ and triangular: __ / \__ \__/ \ / \__/ \__/ There are two problems that we are interested in: 1. What regions can be tiled with just linear trihexes? 2. What regions can be tiled with a mix of linear and triangular trihexes? One requirement for a region to be tileable by these tiles is that when its faces are 3-colored (where we use some symmetrical 3-coloring of the entire plane, with the property that no adjacent hexagons have the same color; coloring two adjacent hexagons determines a coloring), each color must appear equally often because the colors appear equally often in the tiles: __ /Gr\__ \ /Bl\__ /Re\ Re\ \ /Gr __/ /Bl\__/ \__/ This is akin to the fact that any region tileable by dominoes must have the same number of black and white squares when it is properly colored with the two colors. This is because every domino covers one white square and one black square. However, this color condition is clearly not sufficient. There are regions that satisfy the color condition, but are not tileable. For example, the following figure is not tileable with dominoes, though it satisfies the color condition: __ |Bl| __|__|__ |Bl|Wh|Bl| |__|__|__| |Bl| |__| |Wh| __|__|__ |Wh|Bl|Wh| |__|__|__| |Wh| |__| And there are examples of hexagonal regions that satisfy that color condition that cannot be tiled by our trihexes. Anna asks, "what if we have a triangular region instead of a hexagonal or square one?" Such as: ________ /\ /\ /\ /__\/__\/__\ /\ /\ /\ /\ /__\/__\/__\/__\ \ /\ /\ /\ / \/__\/__\/__\/ \ /\ /\ / \/__\/__\/ Then we could use rhombus tiles (made up of two triangles each). Then the color condition would be that if the triangles are colored by the colors black and white, the region must have the same number of black triangles as white triangles since every rhombus covers a black and a white triangle. Note that in the square and triangular grid cases tiled by dominoes and rhombuses, we can make a bijection between tilings and perfect matchings of a related graph, given by taking a vertex for each square or triangle and connecting adjacent vertices. The graph in the square case is o | o--o--o | o | o | o--o--o | o and in the triangular case is o--o / \ o--o o--o / \ / \ o o--o o \ / \ / o--o o--o (rotated by 90 degrees because of ASCII-graphics constraints) / \ / \ o o--o o \ / \ / o--o o--o \ / o--o And we have algorithms to determine if a graph has a perfect matching. Unfortunately, there is no such bijection of tilings to perfect matchings if you are tiling with trihexes. There is a promising idea: height functions! Consider a tiling of the triangular region above (ignore the numbers for now): 0____1___2 /\ \ \ 1/ \___\___\1 /\ / / /\ 2/ \/___/___/ \0 \ / /\ \ / \/___/ \___\/ 1\ \ / /1 \___\/___/ 0 1 2 Notice that if you sit and look at it for a while, it looks three dimensional. This feeling that some points are closer to you than others can be made precise by agreeing on which directions take you further into the page (screen) and which bring you out. One such choice is in out \ / out--- ---in / \ in out Under this choice, the points on the boundary of the region labeled "0" are those which are most "inside" the page (screen) and the ones labeled "2" are the most "out", ie the closest to you. We can associate to the boundary of the region a "word" which tells you how you move up and down as you move around the boundary. For example, if we start at the right-most "0" above and travel around counter-clockwise, we move up-up-down-down-up-up-down-down-up-up-down-down, so this is our boundary word. Conway and Lagarias did work with these boundary words. Once we have a "height" assigned to each point on the boundary (these heights are the numbers labeling the tiling above), we can look at the highest point on the boundary (or one of the highest). We can take a "bite" out of our region by removing the would-be tile that covers the area around the highest point. In the triangular region example, we might "bite" off the left-most point (at height 2): 0____1___2 0____1___2 /\ /\ /\ /\ /\ /\ 1/__\/__\/__\1 1/__\/__\/__\1 /\ /\ /\ /\ \ /\ /\ /\ 2/__\/__\/__\/__\0 becomes \/__\/__\/__\0 \ /\ /\ /\ / 0/\ /\ /\ / \/__\/__\/__\/ /__\/__\/__\/ 1\ /\ /\ /1 1\ /\ /\ /1 \/__\/__\/ \/__\/__\/ 0 1 2 0 1 2 This results in a smaller region, to which we apply the same procedure until we have "eaten" the whole thing. This gives us a tiling of the original region (every tile that we "bit off" at some point is in the tiling). In this example, the resulting tiling is 0____1___2 /\ \ \ 1/ \___\___\1 /\ /\ \ \ 2/ \/ \___\___\0 \ /\ / / / \/ \/___/___/ 1\ / / /1 \/___/___/ 0 1 2 Perhaps we could define similar height functions for trihex tilings of hexagonal regions and get a similar algorithm. Another tool that could be useful is the fact that the difference between triangular trihexes of one orientation and triangular trihexes of the other orientation is fixed, that is, __ __ ( / \__ ) ( __/ \ ) number ( \__/ \ ) minus number ( / \__/ ) equals some of ( / \__/ ) of ( \__/ \ ) constant ( \__/ ) ( \__/ ) (where the constant dpends only on the region being tiled). In particular, if this difference is not zero (it is enough to find one tiling in which it is not zero), then we know that ANY tiling of that region with straight and triangular trihexes MUST have some triangular trihexes. Another thing to think about is how to move around from one tiling to another. That is, what moves or switches can we do to one tiling to get another valid tiling? For example, part of a tiling may be two linear trihexes. We can replace them by two triangular trihexes of opposite orientation: __ __ / \__ / \__ \__ \__ \ \__ / \__ \ becomes / __/ \ \__ \__/ \__/ / \__ \ \__ \ \__/ \__/ There are similar moves for dominoes and rhombuses: __ __ _____ | | | | | | | | becomes |_____| | | | | | |__|__| |_____| ____ ____ /\ \ / /\ / \___\ becomes /___/ \ \ / / \ \ / \/___/ \___\/ Gale-Robinson Polynomials and Their Combinatorial Meaning A 1-dimensional recurence is a recurence in which you can put all of your terms in a line and say "the nth term is such-and-such formula in the earlier terms" A 2-dimensional recurence is a recurence in which you can put your terms in a 2-dimensional array and say "this term is this-and-that formula in the terms above this one" For example, the number frieze . . . a b c d . . . . . . e f g . . . . . . h i . . . . . . j . . . where we define h = (ef+1)/b , i = (fg+1)/c , j = (hi+1)/f , etc. is a 2-dimensional recurence. A 3-dimensional recurence is a recurence in which you can put your terms in a 3-dimensional array and say "this term is that-and-such formula in the terms below this one" For example, the octahedron and cube recurrences, where the value at the top vertex is determined by some formula involving the values on the other vertices, are 3-dimensional recurences. Often, in order to give a combinatorial meaning to a recurrence, you have to look in dimensions higher than the dimension of the reccurence. Consider the (2-dimensional) reccurence g_n*g_(n-a) = g_(n-i)*g_(n-a+i) + g_ (n-j)*g_(n-a+j) for some integers a>i>j. This satisfies the Laurent property, ie g_n can be written as a laurent polynomial in the initial terms g_1 through g_a. One can construct a graph G_(a,i,j,n) such that the number of perfect matchings of G_(a,i,j,n) is g_n where g_1 through g_a are all 1. If we fix a, i, j, and let n vary, we get "pinecone graphs" However, the construction of the pinecone graphs does not explain observed patterns when a, i, and j have a common factor. For example, let a=8, i=2, and j=4, then we get the sequence 1 1 1 1 1 1 1 1 2 2 3 3 7 7 ... which is just a doubled copy of 1 1 1 1 2 3 7 ... which is the Somos-4 sequence, where a=4, i=1, and j=2. If we add another term to the reccurence to get the 3-dimensional reccurence g_n*g_(n-a) = g_(n-i)*g_(n-a+i) + g_(n-j)*g_(n-a+j) + g_(n-k)*g_(n-a+k) then the sequence satisfies integrality (the terms are integers) only if a,i,j, and k obey certain relations. If we add a fourth term to the right hand sum to get the 4-dimensional reccurence g_n*g_(n-a) = g_(n-i)*g_(n-a+i) + g_(n-j)*g_(n-a+j) + g_(n-k)*g_(n-a+k) + g_ (n-r)*g_(n-a+r) then integrality breaks down. Is there some reason that the third dimension is the limit for integrality to hold (and hence the limiting dimension in which we can find combinatorial interpretations of the sequences)?