Is there a group whose cardinality counts non-intersecting paths?

Question

Introduction

Graphs are not only important combinatorial objects, but also related to many topological/algebraic structures. In this question I am going to talk about various group structures with combinatorial flavor that one can relate to a graph. In what follows all graphs are connected.

The first example that comes to mind is the fundamental group of a graph when viewed as a topological space. This is a free group and the information it carries is the Euler characteristic, or in simpler words the difference between the number of edges and vertices.

The second example is the critical group of a graph (also called the Sandpile group, Picard group and Jacobian group by different authors) which we can denote as $\mathcal{K}(G)$ for a graph $G$. If we let $L(G)$ be the Laplacian of $G=(V,E)$ this group is nothing more than just $$\mathcal{K}(G) := \mathbb{Z}^{V}/L(G)\mathbb{Z}^{V}$$ so maybe another name for it should be "Laplacian cokernel". By Kirchhoff's theorem the order of $\mathcal{K}(G)$ is precisely the number of spanning trees of $G$. A similar situtation occurs when we consider directed graphs instead. The nice thing about this group is that it behaves nicely under quotients. This means that if one has an automorphism $\phi$ of $G$ then $\mathcal{K}(G/\phi)$ is a subgroup of $\mathcal{K}(G)$. This is not hard to prove without using the critical group itself, see my answer here. The bad thing here is that it is impossible to put a "natural" bijection between $\mathcal{K}(G)$ and the set of spanning trees of $G$, however this is asking for too much.

A last example is that one can do something similar in the case of perfect matchings for planar bipartite graphs, and get Kasteleyn cokernels. Here one considers the Kasteleyn matrix instead of the Laplacian, and in some cases can give the group structure explicitly, for example G. Kuperberg in that paper shows that the Kasteleyn-Percus cokernel of the Aztec diamond is $\mathbb{Z}/2\mathbb{Z}\oplus\mathbb{Z}/4\mathbb{Z}\oplus\cdots\oplus\mathbb{Z}/2^{n}\mathbb{Z}$.

Question

Can we construct a group whose cardinality counts the number of non-intersecting paths in a directed graph which start and end in specified sources and sinks? Can we say anything about the structure of such a group and have they been studied before? I am particularly interested in subgraphs of $\mathbb{Z}^2$. Also any comments regarding the philosophy of counting objects by passing through a group structure first, are welcome.

Motivation

A positive answer to this question might help in giving a combinatorial proof to this question (see Qiaochu's comment for example). It would be interesting in general to study the subgroup structure of this (hypothetical) group in general.

Answer 1

Hi Gjergji. First, when there is a Gessel-Viennot matrix to count non-intersecting lattice paths, there is also a Gessel-Viennot cokernel. This will happen when the graph is planar and when the sources are all "on the left" and the sinks are all "on the right". Otherwise, if you can't find an integer matrix whose determinant counts the families of lattice paths or whatever, then there is no particular reason to believe in a cokernel.

Second, the Gessel-Viennot determinant is not essentially different from the Kasteleyn-Percus determinant. Every planar non-intersecting lattice path problem can be expressed as a planar perfect matching problem for a modified graph, and the Kasteleyn-Percus matrix reduces to the Gessel-Viennot matrix in a predictable way. In particular, the cokernels are the same. This is explained in my paper that you cite.

Third, even the tree group of a planar graph is not all that different from either Gessel-Viennot cokernel or the Kasteleyn cokernel. Again, you can modify a planar, bipartite graph to turn the matchings into trees. The tree group is more general in the sense that it does not require planarity.

---

Actually, although the Gessel-Viennot method is a very nice and very important result, it is something of a social accident that it is (or has at times been) much more popular than the Kasteleyn method in enumerative combinatorics circles. Kasteleyn published in mathematical physics journals, and his work was known but not widely known among combinatorialists until the 1990s. Then, he published a more complicated Pfaffian expression that applies to non-bipartite graphs, and this was only simplified by Percus in the bipartite case. (Although this simplification is easy.) Then, although Kasteleyn-Percus determinants explain and generalize Gessel-Viennot determinants, the matrices are larger and the more condensed Gessel-Viennot form can look more convenient for explicit calculations. Then too, unless you are studying cokernels, you might not need to know that Gessel-Viennot matrices can come from Kasteleyn-Percus matrices.

On the other hand, there are some things that Gessel-Viennot matrices do not easily show you. Three examples: (1) The same Kasteleyn-Percus matrix may have more than one Gessel-Viennot reduction, which will then have the same cokernel. (2) The minors of a Kasteleyn-Percus matrix give you edge probabilities, a fact which has been used to great effect by Rick Kenyon. (3) You may have to discard symmetry to write down the Gessel-Viennot matrix, which can make it more difficult to analyze matchings that are invariant under a group action.