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

## 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.

• We can apply the cokernel construction to the matrix that appears in the statement of the Lindstrom-Gessel-Viennot lemma, but I assume you are asking for a "natural" construction of this group. – Qiaochu Yuan Sep 3 '10 at 14:23
• I would be happy with that construction too, if one can say anything about the resulting group. (For a rectangular grid graph let's say.) Other questions arising would be, how does it behave under quotients? (Need to bee a bit careful about definitions here, let's say that we are quotienting by an automorphism that leaves the sinks&sources fixed) – Gjergji Zaimi Sep 3 '10 at 15:16
• I don't quite understand what you mean by 'the number of non-intersecting paths'. Do you mean 'the number of non-self-intersecting paths'? Or do you mean 'the maximal cardinality of a set of non-mutually-intersecting paths'? Or something else? – HJRW Sep 3 '10 at 16:21
• Once I have specified $k$ vertices to be the sources and $k$ vertices to be the sinks in the directed graph, the non-intersecting paths I am considering are $k$-tuples of mutually disjoint directed paths connecting a source to a sink. In particular any two paths will have different sources and sinks. – Gjergji Zaimi Sep 4 '10 at 3:20