CONNECTIVITY OF ALTERNATING SIGN TRIANGLES

The octahedron recurrence is given by the initial conditions $f_{i,j,k}=x_{i,j,k}$ for $k=-1,0$ and

An alternating sign matrix is a square matrix that satisfies:

1. 1.

   all entries are $-1,0,\text{ or }1$,

2. 2.

   every row and column has sum $1$,

3. 3.

   in every row and column the non-zero entries alternate in sign.

In [1], Robbins and Rumsey found that the exponents of the $x_{i,j,k}$ in any monomial in $f_{i_{0},j_{0},k_{0}}$ formed an alternating sign matrix. In [2], the following theorem about alternating sign matrices was proven:

In [3], James Propp introduced another recurrence called the cube recurrence, which is given by $f_{i,j,k}=x_{i,j,k}$ for $i+j+k=-1,0,1$ and

In [4], Carroll and Speyer introduced a combinatorial object that describe the cube recurrence called grove, which will be defined rigorously in section 2. Carroll and Speyer proved that $f_{0,0,0}$ is a sum of Laurent monomials in the variables $x_{i,j,k}$, and they observed that, in each monomial, the exponents of $x_{i,j,k}$ form an alternating sign triangles. Some properties of alternating sign triangles can be found in [5].

In this paper, we will prove the following theorem, analogous to theorem 1, for alternating sign triangles:

Acknowledgments. I thank Pavlo Pylyavskyy for introducing me to this topic and for his helpful suggestions and continuous support.

In [4], Carroll and Speyer defined groves as follows.

Define the lower cone of any $(i,j,k)\in\mathbb{Z}^{3}$ to be

Let $\mathcal{L}\subseteq\mathbb{Z}^{3}$ be a subset such that, whenever $(i,j,k)\in\mathcal{L},C(i,j,k)\subseteq\mathcal{L}$. Let $\mathcal{U}=\mathbb{Z}^{3}-\mathcal{L}$, and define the set of initial conditions

We also define a rhombus to be any set of the form

In addition, define the edges of each rhombus to be the pairs

Now suppose that $N$ is a cutoff for $\mathcal{I}$. Let $\mathcal{G}$ be a graph whose vertices are the points in $\mathcal{I}$ and edges are the edges of all rhombi occurring in $\mathcal{I}$. We define an $\mathcal{I}$-grove within radius $N$ to be a subgraph $G\subseteq\mathcal{G}$ with the following properties:

• •

  (Completeness) the vertex set of $G$ is all of $\mathcal{I}$;

• •

  (Complementarity) for every rhombus, exactly one of its two edges occurs in $G$;

• •

  (Compactness) for every rhombus all of whose vertices satisfy $i+j+k<-N$, the short edge occurs in $G$;

• •

  (Connectivity) every component of $G$ contains exactly one of the following sets of vertices, and conversely, each such set is contained in some component:

  • –

    $\left\{(0,p,q),(p,0,q)\right\},\left\{(p,q,0),(0,q,p)\right\}$, and $\left\{(q,0,p),(q,p,0)\right\}$ for all $p,q$ with $0>p>q$ and $p+q\in\{-N-1,-N-2\}$;

  • –

    $\left\{(0,p,p),(p,0,p),(p,p,0)\right\}$ for $2p\in\{-N-1,-N-2\}$;

  • –

    $\left\{(0,0,q)\right\},\left\{(0,q,0)\right\}$, and $\left\{(q,0,0)\right\}$ for $q\leq-N-1$.

Carroll and Speyer also proved a bijection between groves and simplified groves. A simplified grove within radius $N$, where $N$ is a cutoff for $\mathcal{I}$ and furthermore is odd, is a subgraph $G^{\prime}$ of $\mathcal{G}$ satisfying:

• •

  (Vertex set) the vertex set of $G^{\prime}$ is $\{(i,j,k)\in\mathcal{I}\text{ | }i+j+k\equiv 0\text{ mod }2;i+j+k\geq-N-1\}$;

• •

  (Acyclicity) $G^{\prime}$ is acyclic;

• •

  (Connectivity) every component of $G^{\prime}$ contains exactly one of the following sets of vertices, and conversely, each such set is contained in some component:

  • –

    $\left\{(0,p,q),(p,0,q)\right\},\left\{(p,q,0),(0,q,p)\right\}$, and $\left\{(q,0,p),(q,p,0)\right\}$ for $p,q$ with $0>p>q$ and $p+q=-N-1$;

  • –

    $\left\{(0,\frac{-N-1}{2},\frac{-N-1}{2}),(\frac{-N-1}{2},0,\frac{-N-1}{2}),(\frac{-N-1}{2},\frac{-N-1}{2},0)\right\}$;

  • –

    $\left\{(0,0,-N-1)\right\},\left\{(0,-N-1,0)\right\}$, and $\left\{(-N-1,0,0)\right\}$.

For our convenience, we will redefine a simplified grove of size $n$ to be a graph $G$ satisfying:

• •

  (Vertex set) the vertex set of $G$ is $\{{(i,j)\in\mathbb{Z}^{2}\mid\lvert i+j\rvert\leq n,j\leq 0,i+j\equiv n\bmod{2}}\}$;

• •

  (Acyclicity) $G$ is acyclic;

• •

  (Connectivity) the boundary vertices can be partitioned into the following sets so that each component of $G$ contains exactly one set, and conversely, each set is contained in some component:

  • –

    $\{(-n,0)\},\{(n,0)\}$ and $\{(0,-n)\}$,

  • –

    (west pairs) $\{(-i,0),(\frac{-n-i}{2},\frac{-n+i}{2})\}$ for $0<i<n,i\equiv n\bmod{2}$,

  • –

    (east pairs) $\{(i,0),(\frac{n+i}{2},\frac{-n+i}{2})\}$ for $0<i<n,i\equiv n\bmod{2}$,

  • –

    (south pairs) $\{(-n+i,-i),(n-i,-i\}$ for $\frac{n}{2}<i<n$,

  • –

    (middle triplet) $\{(0,0),(-\frac{n}{2},-\frac{n}{2}),(\frac{n}{2},-\frac{n}{2})\}$ if $n$ is even.

It can be checked that this new definition gives the same set of simplified groves as Carroll’s. We also define a upward triangle of size $i$ to be a triangle whose vertices are $(a,b),(a-i,b-i),(a+i,b-i)$. Similarly, define an downward triangle of size $i$ to be a triangle whose vertices are $(a,b),(a-i,b+i),(a+i,b+i)$. For simplicity, we will refer to downward and upward triangle of size $1$ as downward and upward triangle respectively.

Now assign to each downward triangle a number $1-e$ where $e$ is the number of edges in that triangle. From the acyclicity condition, we have the number of edge in every triangle is less than $3$; hence, the number assigned to each downward triangle is either $-1,0$ or $1$. Define an alternating sign triangle to be a configuration of numbers generated by our process. It can be checked that this definition gives the same set of alternating sign triangles as Carroll’s proposed definition does.

Now we will introduce some definitions that will be useful for our proof. First of all, define the target grove of size n to be the following grove:

We also say two vertices or two edges to be in the same group if they are in the same component in the target grove. Additionally, we define group $W,S,E$ as in Figure 4 as they play an important part in our proof. Next, for every grove $G$, define its difference grove to be the graph in which:

• •

  Edges that appear in $G$ but not in the target grove are colored red.

• •

  Edges that appear the target grove but not in $G$ are colored black.

• •

  Edges that appear in both $G$ and the target grove are colored blue.

Lastly, we define a spin to be one of the following changes:

We also call the middle vertex above the pivot of the spin. It can be seen that spins of type $1,3,5$ does not change the corresponding alternating sign triangles while spins of type $2,4,6$ is equivalent to adding or subtracting one of the three sub-triangles in Theorem 2 to the corresponding alternating sign triangles. It can also be seen that if a grove $G^{\prime}$ can be obtained from another grove $G$ through a sequence of spins, then $G$ can also be obtained from $G^{\prime}$ through a sequence of spins. Hence, instead of proving Theorem 2, we will prove the following theorem:

Before proving Theorem 3, we will make some trivial observations:

We will prove that if there is some black edges in the difference grove, we can reduce the number of black edges.

Case 1: If there is no group with more than one black edge, then, we choose a group with one black edge. Clearly, the path connecting the two boundary vertices of this group must contain a segment of red edges. Moreover, the black edge lies between the two endpoints of the segment. Because there is only one black edge, every vertices in the region bounded by the red segment and the group edges must be in the same component with the group’s vertices. This means that we can move the black edge to one of the endpoints of the red segment and then, with the endpoint as the pivot, spin the red edge to the place of the black edge, and the number of black edge is reduced.

Case 2: If there are some groups with more than one black edge, then, we choose one of such groups and consider a pair of consecutive black edges. By observation 1, there have to be at least one red edge between the two black edges. If there is only one red edge, by observation 3, we can move the two black edges to the red edge. Now the shared vertex of the two black edges and the red edge has degree 1; therefore, by observation 2, we can spin with that vertex as the pivot to move the red edge to the place of one of the black edges, and the number of black edges is reduced.

On the other hand, if there are more than one red edge, we consider two adjacent red edges and consider two sub cases:

Case 2a: If the two chosen red edges are connected to the same component, then in the other component, between the two red edges, there must be some black edges since otherwise we will have a cycle. If there is only one black edge, then similar to case 1, we can reduce the number of black edges.

If there are more than one black edge, consider two consecutive ones, then by observation 1, there have to be some red edges between them. Because of our choice of red edges at the beginning of this case, these red edges cannot be connected with our original group; hence, they have to be connected to other groups. If there is only one red edge, then similar as above, we can reduce the number of red edges. If there are more than one red edge, and they are connected to the same group, then we get back to this case. If they are connected to different groups, then we get the following bad scenario, which will be considered last.

Case 2b: If the two chosen red edges are connected to different components, then in at least one of the two other components, there have to be black edges on both sides of the red edge because otherwise the boundaries vertices of the two components will be connected. Then if between the two black edges there are only one red edge, then similar as above, we can reduce to number of black edges. If there are more than one red edge, then we proceed similarly as above. Consider two adjacent red edges, if they are connected to the same component, then we are back to case 2a, else, we are back to this case.

Now let us take a moment to review what we have got. We now know that if we get case 2b, we will either finish, or get back to case 2b again, or get to case 2a. If we get case 2a, we will either finish, or get back to case 2a again, or get to the bad scenario. However, this process cannot go on forever because we only have a finite number of red edges, so the process will eventually stops. Therefore, eventually, we will either finish, or get to the bad scenario. Hence, if we can solve for the bad scenario, the proof is complete.

Now we will show that the bad scenario is actually not that bad. To solve for the bad scenario, we need to see when the bad scenario arises. It arises when we have three groups adjacent to each other, and the only place where that happens is at group $W,E,S$ that we defined earlier. Additionally, it only arises when, in our process, we go from group $W$ to group $E$ and $S$ in case 2a.

Now looking back at our proof, we can see that we use only two types of spins: spins with the pivot having degree one, and spins among vertices in the same component as in case 1. In the first type, which direction we spin does not matter, so we can always spin in, say, clockwise direction. In the second type, notice that one of the endpoints of the red segment is to the left of the black edge, so if we use that endpoint as the pivot, we can spin in the clockwise direction only. Therefore, we have the following stronger theorem of theorem 3:

Now let us define the identity triangle, analogous to identity matrix, to be the following triangle:

Clearly, the target grove gives the identity triangle; therefore, from theorem 4, we have the following theorem:

There are also bijections between alternating sign matrix and some other interesting objects, one of which is the corner-sum matrix, which was introduced in [1]. Corner-sum matrices are matrices in which the last row and last column consist of the numbers from 1 to n (in order), and within each row and column, each entry is either equal to, or one more than, the preceding entry. By adding (or subtracting) the sub-matrix in theorem 1 to an alternating sign matrix, we are increasing (or decreasing) the top left entry of the sub-matrix in the corresponding corner-sum matrix by one.

Another notable object is the monotone triangle, which is a triangular array where row $1,...,n$ has $1,...,n$ entries respectively, the numbers in the bottom row are 1 to n (in order), the numbers in each row are strictly increasing from left to right, and the numbers along diagonals are weakly increasing from left to right (see [3]). Again, by adding (or subtracting) the sub-matrix in theorem 1 to an alternating sign matrix, we are decreasing (or increasing) one entry in the corresponding monotone triangle by one.

Now that we have proven theorem 2 for alternating sign triangle, it is possible that there are objects analogous to corner-sum matrix and monotone triangle for alternating sign triangle. Additionally, these objects may also allow us to give a complete characterization of alternating sign triangles.