Algebraic Potential Theory on Graphs
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.
- Enumerating bases of self-dual matroids
- Chip-firing and the critical group of a graph
- On the critical group of the \(n\)-cube
- Classes of lattices induced by chip firing (and sandpile) dynamics.
- Long time behavior of the transition probability of a random walk with drift on an Abelian covering graph.
- The Alexander polynomial of planar even valence graphs
- The critical group of a threshold graph
- Simplicial networks and effective resistance
- Abelian sandpile model and Biggs-Merino polynomial for directed graphs
- Random walks and diffusion on networks
- Canonical measures on metric graphs and a Kazhdan's theorem
- Chip-firing games, potential theory on graphs, and spanning trees
- The Tutte polynomial as a growth function
- Solving Dirichlet and Poisson problems on graphs by means of equilibrium measures
- Sandpile models and lattices: a comprehensive survey
- The critical group of a line graph
- Lecture on topological crystallography
- Shortest paths in distance-regular graphs
- Jacobian tori associated with a finite graph and its abelian covering graphs
- Kirchhoff index of simplicial networks
- Effective resistance is more than distance: Laplacians, simplices and the Schur complement
- Metric graphs, cross ratios, and Rayleigh's laws
- Counting spanning trees in almost complete multipartite graphs
- Sandpile monomorphisms and limits
- The sandpile group of polygon rings and twisted polygon rings
- A type of generalized mesh-star transformation and applications in electrical networks
- Compatible recurrent identities of the sandpile group and maximal stable configurations
- Tutte's dichromate for signed graphs
- Effective resistances and spanning trees in the complete bipartite graph plus a matching
- Analyzing stable regimes of electrical power systems and tropical geometry of power balance equations over complex multifields
- Sandpiles and dominos
- Locally finite graphs with ends: A topological approach. I: Basic theory
- On the regularity of orientable matroids
- High-dimensional networks and spanning forests
- The sandpile group of a polygon flower
- Families of nested graphs with compatible symmetric-group actions
- Riemann-Roch and Abel-Jacobi theory on a finite graph
- Geometric bijections between spanning trees and break divisors
- Arithmetical structures on graphs
- Potential theory for Schrödinger operators on finite networks
- Synchronization and power sharing for droop-controlled inverters in islanded microgrids
- Determinantal probability measures on Grassmannians
- Divisors on graphs, binomial and monomial ideals, and cellular resolutions
- Distance-regular graphs having the M-property
- Hitting times, cover cost, and the Wiener index of a tree
- Complexity and algorithms for computing Voronoi cells of lattices
- Diffusions on graphs, Poisson problems and spectral geometry
- Arithmetical structures on graphs with connectivity one
- On Laplacian monopoles
- Cryptanalysing the critical group: efficiently solving Biggs's discrete logarithm problem
- On Kirchhoff's theorems with coefficients in a line bundle
- Critical groups of covering, voltage and signed graphs
- The critical group of a clique-inserted graph
- Potential Theory on Distance-Regular Graphs
- Potentials in Undirected Graphs and Planar Multiflows
- The lattice of integral flows and the lattice of integral cuts on a finite graph
- Boundary value problems on finite networks
- Synchronization in complex networks of phase oscillators: a survey
- Algebraic properties of generalized graph Laplacians: resistor networks, critical groups, and homological algebra
- Triangulations of the sphere, bitrades and abelian groups
- Flow and Elastic Networks on the 𝑛-Torus: Geometry, Analysis, and Computation
- Decoding from pooled data: sharp information-theoretic bounds
- Generalizing Kirchhoff laws for signed graphs
- The sandpile group of a thick cycle graph
- Applications of the quantum algorithm for st-connectivity
- A revised model of fluid transport optimization in \textit{Physarum polycephalum}
- Lipschitz-free spaces on finite metric spaces
- Random walks on simplicial complexes and the normalized Hodge 1-Laplacian
- Strongly connected multivariate digraphs
- Phase synchronization between collective rhythms of globally coupled oscillator groups: noiseless nonidentical case
- The distribution of sandpile groups of random graphs
- The critical group of \(K_{m} \times C_{n}\)
- The lattice of integer flows of a regular matroid
- Geometric bijections between spanning subgraphs and orientations of a graph
- Effective operators and their variational principles for discrete electrical network problems
- Metric properties of the tropical Abel-Jacobi map
- Graphs whose critical groups have larger rank
- Simplicial Kirchhoff index of random complexes
- Sandpile groups for cones over trees
- The distribution of sandpile groups of random graphs with their pairings
- The complexity of bidirected reachability in valence systems
- On the sandpile group of the cone of a graph
- Vector spaces of graphs closed under isomorphism
- Simplicial effective resistance and enumeration of spanning trees
- The two lives of the Grassmannian
- A note on Dirichlet, Poisson and Neumann problems on infinite networks
- A characterization of the locally finite networks admitting non-constant harmonic functions of finite energy
- Discrete operators on graphs and networks
- Semi-discrete linear polyharmonic flows of polyhedra
- Transfer current and pattern fields in spanning trees
- On the sandpile group of regular trees
- A collection of results concerning electric resistance and simple random walk on distance-regular graphs
- The critical group of \(K_m \times P_n\)
- Live facial feature extraction
- Potential theory on finite graphs
- Torelli theorem for graphs and tropical curves
- Critical groups for homeomorphism classes of graphs
This page was built for publication: Algebraic Potential Theory on Graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4354177)