Integrability of graph combinatorics via random walks and heaps of dimers

P. Di Francesco, E. Guitter

Research output: Contribution to journalArticlepeer-review


We investigate the integrability of the discrete non-linear equation governing the dependence on geodesic distance of planar graphs with inner vertices of even valences. This equation follows from a bijection between graphs and blossom trees and is expressed in terms of generating functions for random walks. We construct explicitly an infinite set of conserved quantities for this equation, also involving suitable combinations of random walk generating functions. The proof of their conservation, i.e. their eventual independence on the geodesic distance, relies on the connection between random walks and heaps of dimers. The values of the conserved quantities are identified with generating functions for graphs with fixed numbers of external legs. Alternative equivalent choices for the set of conserved quantities are also discussed and some applications are presented.

Original languageEnglish (US)
Pages (from-to)29-62
Number of pages34
JournalJournal of Statistical Mechanics: Theory and Experiment
Issue number9
StatePublished - Sep 1 2005
Externally publishedYes


  • Classical integrability
  • Exact results
  • Networks
  • Random graphs
  • Topology and combinatorics

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Statistics and Probability
  • Statistics, Probability and Uncertainty


Dive into the research topics of 'Integrability of graph combinatorics via random walks and heaps of dimers'. Together they form a unique fingerprint.

Cite this