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

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.