zbMATH — the first resource for mathematics

Algebraic potential theory on graphs. (English) Zbl 0892.05033
This paper covers ideas from several areas of mathematics. They include random walks, the Picard group, exchange rate networks, chip-firing games, cohomology, and the conductance of an electrical network. The linking threads are the discrete Laplacian on a graph and the solution of the associated Dirichlet problem.
The first part of the paper develops the traditional potential theory with real coefficients in a coherent way. The basic properties of the incidence operator $$D$$ lead to an orthogonal decomposition of the cochain space, and the projections onto its component subspaces are described explicitly. One of the projections has a canonical factorisation, $$P=XD$$, where $$X$$ can be defined explicitly in graph-theoretical terms. This allows the well-known, but hitherto somewhat mysterious, ‘matrix-tree’ theory to be developed quite naturally in an algebraic framework.
The second part is devoted to applications of the fundamental theory. The relationship between electrical network theory and random walks is simply a manifestation of the fact that both topics can be expressed as Dirichlet problems on a graph. The theory of the canonical factorisation, and the consequent matrix-tree formulae, are used to solve the basic questions in these topics. Other applications, such as handicapping in tournaments and exchange rate networks, are discussed within the same framework.
The third part is devoted to potential theory with integer coefficients. Recent work has established that classical objects of algebraic geometry, such as the Picard group and the Jacobian, are analogues of groups which arise naturally in the theory of integer lattices associated with graphs. The theory is described here using the same techniques as those developed for the real case, which illuminates a number of fundamental results. The basic fact is that the determinants of certain lattices are equal to the tree number of the graph, and this is shown to be related to the factorisation $$P=XD$$. An apparently unrelated topic, chip-firing games on graphs, leads to a set of critical configurations which is in bijective correspondence with the set of spanning trees, and the relationship with the Picard group is made explicit. It follows that the set of critical configurations has a natural group structure.
Certain algebraic and arithmetical invariants of graphs are discussed within this framework. The tree number $$\kappa$$ occurs in the expression for the projection $$P$$, and then reappears at almost every new turn of the theory. It is shown that the underlying object is not $$\kappa$$ itself, but an abelian group of order $$\kappa$$. According to the general theory of abelian groups, it has a direct sum decomposition into subgroups, the orders of which are its invariant factors, and it turns out that the invariant factors are finer invariants of the graph than $$\kappa$$ itself. Other invariants are the effective conductances between vertices of the graph; in particular, the minimum effective conductance. In the case of distance-regular graphs these are shown to be determined by the intersection numbers, whereas the invariant factors are not.
Finally, there is a brief discussion of potential theory with general coefficients, where the invariant factors turn up again.
Reviewer: N.Biggs (London)

MSC:
 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.) 05C99 Graph theory
Full Text: