The Relation of Graphs to Totally Nonnegative Matrices and the Temperley-Lieb Algebra
REU Spring/Summer
May-Aug 2002
Michal Ostrowski
Under direction of Mark Skandera
University of Michigan
Abstract. We discuss an alternate method of generating a particular graph based on a specific arrangement of vertices as it relates to the Temperle-Lieb algebra. We characterize the graph produced and describe certain properties thereof.
1. Introduction
A totally nonnegative matrix is defined as a matrix all of whose minors are nonnegative. That is, taking the determinant of any square submatrix yields a nonnegative number. For example the matrix is a totally nonnegative matrix.
A planar network is a planar acyclic directed graph G with 2n specific boundary vertices labeled counter-clockwise as s1, …, sn, tn, …, t1. (See also [4].) An example of a planar network is figure 1.2.
The path matrix of a planar network G is A = [aij] where aij represents the number of paths from sI to tj in G. The path matrix for the planar network in Figure 1.2 is represented by the matrix A = . According to both Lindström [5] and Karlin and McGregor [4] the path matrix of a planar network is always a totally nonnegative matrix. Essentially the converse is true according to Skandera [10, Thm. 1.2] with contributions by Brenti [1], Fallat, Gekhtman, Johnson [2], Fomin, Zelevinsky [3], and Lusztig [6].
A fact known about totally nonnegative matrices is that ∆{12},{12}∆{3},{3} ≤ ∆{13},{13}∆{2},{2} for sizes greater than three. Skandera [10, Thm. 3.2] generalizes this by letting I,J be n-element subsets of [2n] so that . Also according to Skandera [10, Obs. 2.3, Corr. 3.4] we have if and only if a certain subset of the nth Temperley-Lieb algebra corresponding to I, is contained in the subset of Tn corresponding to J,. For more current research see [3] Fomin and Zelevinsky.
2. Mike Ostrowski Algorithm
The Temperley-Lieb algebra, Tn, is a set of all graphs of non-crossing lines on 2n vertices arranged in two columns of n vertices each. Half of the dots are black and the other half are white. Connecting these dots by all possible combinations of non-crossing lines creates the elements of Tn. One way of creating a base structure for the Temperley-Lieb elements given a particular arrangement of dots is to apply the Left-Right algorithm. A different arrangement of dots is used for this algorithm. The dots are arranged in a 2n-gon, such that two vertices lie at the top, the leftmost of which is v1. The remaining vertices are labeled counter-clockwise. Label this diagram, D.
1. An edge is drawn between each white vertex, vn if vn+1 is black.
2. Once all of the vertices were examined this way, they are taken out of consideration and step 1 is repeated for the remaining vertices.
3. Step 2 is repeated until all vertices have a degree of one, that is they have one edge.
4. Next, steps 1 through 3 are repeated on the same D with no edges drawn considering each white vertex vn and the vertex vn-1.
5. The two resulting graphs are overlaid and the resulting graph, G, will have all vertices of degree two. Note that each component with two vertices and one edge, the edge is considered double.
The Mike Ostrowski algorithm poses an alternate method to producing a graph, G, given a diagram, D.
1. Given the diagram D, draw and edge between all vertices vn and vn+1 if they are of different colors.
2. For all paths with an even number of vertices (vn, …, vm) connect vn-1 to vm+1.
3. If any component is made to be a continuous path such that all vertices on the component have degree two remove that component from consideration.
4. For all remaining even-length paths consisting of consecutive vertices, draw an edge between the next vn-j and vm+j where vn-j and vm+j have degree less than two and if there is an edge present at the vertex vn-j or vm+j it does not connect and vertices between vn and vn-j nor between vm and vm+j.
5. Repeat steps 3 and 4 until all vertices of all components have degree equal to two. Note that if a component has two vertices and by any previous step has a second edge drawn connecting the two vertices it is to be considered as having degree two for both vertices.
Claim 2.1: Given the same D this algorithm creates the same G as the Left-Right algorithm.
Proof: Consider the paths created in step 1 of the Mike Ostrowski algorithm. Note that if this path has a length of two (connecting two vertices) then it will be an exact duplicate of an edge created in step 1 or 4.1. Now consider a path of odd length created in step 1 of the Mike Ostrowski algorithm. This path will be equivalent to an equal number of paths created from step 1 and 4.1 of the Left-Right algorithm. Note that if the first vertex is black then every other connection starting from the first will have been created by step 1 of the Left-Right algorithm since the black vertex vn-1 will be directly to the left of a white vertex vn. Note that the remaining paths will have been created by step 4.1 of the Left-Right algorithm since the vertex vn will be directly to the left of a black vertex vn+1. If the first vertex is white, then the first chain and every other will have been created in step 1 of the Left-Right algorithm and the rest in step 4.1 because of the same reasoning. If the path created in step 1 of the Mike Ostrowski algorithm is of even length, then there will no longer be an equal number of edges created in steps 1 and 4.1 of the Left-Right algorithm but the same reasoning would justify the paths creation.
Now consider the edges created in step 2 of the Mike Ostrowski algorithm. Note that these edges correspond to those created in 2 or 4.2 depending on the color of the first vertex vn. That is because when even-length paths are considered under the Mike Ostrowski algorithm, then the first and last edge (from vn to vn+1 and from vm to vm-1) will both be created under the same step 1 or 4.1 of the Left-Right algorithm. The same reasoning follows for step 4 of the Mike Ostrowski algorithm, since the qualifications placed on the vertices to be connected ensure that this step mirrors the Left-Right algorithm. The requirement that the edge has degree less than two ensures that it is a valid point to have any edge created. The next requirement that if an edge is present at the vertex vn-j or vm+j it does not connect and vertices between vn and vn-j nor between vm and vm+j ensures that in the Left-Right algorithm the vertex was not connected to another in a previous iteration of step 1 or 4.1.
The first step of the Mike Ostrowski algorithm yields a number of interesting results.
Observation 2.2: Note that as a result of the first step of the Mike Ostrowski algorithm all consecutive vertices of alternating color are connected by edges into maximal paths.
Proof: By the definition of the algorithm, this is true.
Lemma 2.3: Every path can be reduced to length one or two for the purposes of counting vertices and edges.
Proof: Note every edge connects two vertices, one of each color. Thus, every even path will contain a number of black-white pairs. We consider the endpoints as crucial, since they define the orientation of the path, and they can be considered as one pair. The other paths between the endpoints must also be in pairs, and their removal will not change the overall structure of the diagram. The odd paths likewise contain any number of black-white pairs, with an extra black or white vertex. This is the crucial vertex, since both endpoints will be of its color. Thus all black-white pairs can be removed from the odd chain without altering the essence of the graph G.
Observation 2.4: As a result of the first step of the Mike Ostrowski algorithm the number of even chains will be even as will the number of odd chains when the total number of paths exceeds one.
Proof: Realize that for the D to be a valid diagram for the Temperley-Lieb algebra, there must be an equal number of black and white vertices. First, assume that there are zero odd chains. Every maximal path ends in one white vertex and one black vertex. By Lemma 2.3, we can reduce the even length chains to just one white vertex and one black vertex. Therefore, in order for the count to add up, each path must have a second to maintain an even number of both white and black vertices. Note similarly that every odd chain added to D can be treated as a single black or white vertex. Note then that every odd chain must be balanced by a second of the opposite color.
Proposition 2.5: The Mike Ostrowski algorithm will never create a bow-tie shape. That is two edges of a single component of G will never cross.
Proof: In step 1 of the Mike Ostrowski algorithm, all maximal chains are created. In order for a bow-tie shape to exist, the vertices at the ends of these maximal chains on each side of the cross must be off like color on both the top and bottom. Assume this orientation, if it does not fit, rotate G so that it does. Thus if vn is black, vn+i is also black, but vn+i+j and vn+i+j+k are both white, as in figure 2.1.
Note that in this layout there must be an odd number of vertices between vn and vn+i and between vn+i+j and vn+i+j+k and an even number between vn+i and vn+i+j and between vn and vn+i+j+k. This means that as a result of step 1 there may be at least one odd length path and any even number of even paths between vn and vn+i. If only even chains are present, every other chain will end up in one component and the rest in the second as a result of step 2. If there are only odd chains present, there must be an equal number on each side to maintain a equal number of each color of vertices. Further, each vertex vn+m and vn+i+j+k-m will be connected by an edge up to and including vn+i and vn+i+j and finally vn and vn+i+j+k will be connected.
Lemma 2.6: An edge connecting two maximal odd-length paths of consecutive vertices will never cross another doing the same.
Proof: By Lemma 2.3 we can consider all of the maximal odd-length paths of consecutive vertices as a single vertex. Label the edges (vm, vn) and (vj, vk) so that the vertices oriented clockwise are vj, vm, vk, and vn. Let vj and vm be white, thus vk and vn will be black. Thus, there must be at least one even length path between vj and vn and at least one between vm and vk. Label the first vertex belonging to the even length path closest to vm vm′ , the last vertex of the even length path closest to vk vk′ , the first vertex of the even length path closest to vn vn′ , and the last vertex of the even length path closest to vj vj′ as in figure 2.2.
Thus by the second step of the Mike Ostrowski algorithm, vm will connect to the first black vertex clockwise on a path not connected to vm′. vk will connect to the first white vertex counter-clockwise on a path not connected to vk′. vn will connect to the first white vertex clockwise on a path not connected to vn′. vj will connect to the first black vertex counter-clockwise on a path not connected to vj′. Thus we see that the formerly crossing paths cannot occur.
Lemma 2.7: From the completed graph G, any number of components may be removed. Both what was removed and what remains will be valid graphs G′ and G″.
Proof: A component is composed of any combination of odd and even maximal paths consisting of consecutive vertices and edges connecting these paths. Thus we must acknowledge two cases: that even length paths may be removed and that odd paths must be removed.
First consider a component A consisting of only even length edges. Consider each path, vn…vm, and note that vn and vm are of different color. Note also that since they are part of a maximal path of consecutive vertices then vn+1 is the same color as vn and vm-1 is the same color as vm. Note also that vn+1 and vm-1 will be connected by an edge as a result of step 2. Thus if the path between vn and vm were to be removed, the vertices vn+1 and vm-1 will become consecutive vertices in the new diagram and will thus be connected by an edge.
Now add into A any even number of maximal odd length paths created in step 1 connecting consecutive vertices. Note that the vertices to either side of these odd length paths will be the same color as the extra vertex in that path, thus allowing the removal of the path without affecting the vertices directly before and after it. Now due to Lemma 2.6, any pair of these odd length paths can be removed without affecting the orientation of the remaining graph as long as the pair is in one component.
Now note that if one component can be removed from G we can repeat this process with the one component removed to produce a new graph G′ with any number of the original components removed. Note that if we return to G and remove all components that were in G′ we obtain a graph G″ which contains all of the components that were removed from G to obtain G′.
Observation 2.8: The indices of the endpoints of any edge of G differ by an odd number.
Proof: Consider the first step of the Mike Ostrowski algorithm. Note that all of the edges thus created connect consecutive vertices (vi and vi+1) a difference in the indices of 1. Note that the indices of the vertices connected in step 2 also differ by an odd number since the vertices are vi-1 and vi+2n+2 for n ≥ 0. Likewise for step 4, the vertices straddle an even length path and the same number of vertices to either end of it.