Integrability of graph combinatorics via random walks and heaps of dimers. (English) Zbl 1459.05300
Summary: 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.
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
Keywords:
classical integrability; topology and combinatorics; exact results; random graphs; networksReferences:
| [1] | Brézin E, Itzykson C, Parisi G and Zuber J-B 1978 Planar diagrams Commun. Math. Phys.59 35 · Zbl 0997.81548 · doi:10.1007/BF01614153 |
| [2] | Fokas A, Its A and Kitaev A 1991 Discrete Painlevé equations and their appearance in quantum gravity Commun. Math. Phys.142 313 · Zbl 0742.35047 · doi:10.1007/BF02102066 |
| [3] | Kazakov V 1985 Bilocal regularization of models of random surfaces Phys. Lett. B 150 282 · doi:10.1016/0370-2693(85)91011-1 |
| [4] | David F 1985 Planar diagrams, two-dimensional lattice gravity and surface models Nucl. Phys. B 257 45 · doi:10.1016/0550-3213(85)90335-9 |
| [5] | Ambjorn J, Durhuus B and Fröhlich J 1985 Diseases of triangulated random surface models and possible cures Nucl. Phys. B 257 433 · doi:10.1016/0550-3213(85)90356-6 |
| [6] | Kazakov V, Kostov I and Migdal A 1985 Critical properties of randomly triangulated planar random surfaces Phys. Lett. B 157 295 · doi:10.1016/0370-2693(85)90669-0 |
| [7] | See for instance Di Francesco P, Ginsparg P and Zinn-Justin J 1995 2D gravity and random matrices Phys. Rep.254 1 and references therein · doi:10.1016/0370-1573(94)00084-G |
| [8] | see also Eynard B 2000 Random Matrices(Saclay Lecture Notes) available at http://www-spht.cea.fr/cours-ext/en/lectures_notes.shtml |
| [9] | Schaeffer G 1998 Conjugaison d’arbres et cartes combinatoires aléatoires PhD Thesis Université Bordeaux I available at http://www.lix.polytechnique.fr/∼schaeffe/Biblio |
| [10] | Schaeffer G 1997 Bijective census and random generation of Eulerian planar maps Electron. J. Combin.4 R20 · Zbl 0885.05076 |
| [11] | Bouttier J, Di Francesco P and Guitter E 2002 Census of planar maps: from the one-matrix model solution to a combinatorial proof Nucl. Phys. B 645 477 [cond-mat/0207682] · Zbl 0999.05052 · doi:10.1016/S0550-3213(02)00813-1 |
| [12] | Bouttier J, Di Francesco P and Guitter E 2003 Geodesic distance in planar graphs Nucl. Phys. B 663 535 [cond-mat/0303272] · Zbl 1022.05022 · doi:10.1016/S0550-3213(03)00355-9 |
| [13] | Bouttier J, Di Francesco P and Guitter E 2003 Statistics of planar maps viewed from a vertex: a study via labeled trees Nucl. Phys. B 675 631 [cond-mat/0307606] · Zbl 1027.05021 · doi:10.1016/j.nuclphysb.2003.09.046 |
| [14] | see also 2003 Random trees between two walls: Exact partition function J. Phys. A: Math. Gen.36 12349 [cond-mat/0306602] · Zbl 1051.82010 |
| [15] | Viennot X 1986 Heaps of pieces 1: basic definitions and combinatorial lemmas Combinatoire énumérative(Lect. Notes in Math. vol 1234) ed G Labelle and P Leroux (New York: Springer) pp 321-350 · Zbl 0618.05008 · doi:10.1007/BFb0072524 |
| [16] | Bousquet-Mélou M and Rechnitzer A 2002 Lattice animals and heaps of dimers Discrete Math.258 235 · Zbl 1009.05038 · doi:10.1016/S0012-365X(02)00352-7 |
| [17] | Di Francesco P and Guitter E 2002 Critical and multicritical semi-random (1+d)-dimensional lattices and hard objects in d dimensions J. Phys. A: Math. Gen.35 897 · Zbl 0993.82026 |
| [18] | Bouttier J, Di Francesco P and Guitter E 2004 Planar maps as labeled mobiles Electron. J. Combin.11 (1) R69 · Zbl 1060.05045 |
| [19] | Cori R and Vauquelin B 1981 Planar maps are well labeled trees Can. J. Math.33 1023 · Zbl 0415.05020 · doi:10.4153/CJM-1981-078-2 |
| [20] | Arquès D 1986 Les hypercartes planaires sont des arbres très bien étiquetés Discrete Math.58 11 · Zbl 0602.05023 · doi:10.1016/0012-365X(86)90182-2 |
| [21] | Marcus M and Schaeffer G Une bijection simple pour les cartes orientables http://www.lix.polytechnique.fr/∼schaeffe/Biblio/ |
| [22] | Bousquet-Mélou M and Schaeffer G 2000 Enumeration of planar constellations Adv. Appl. Math.24 337 · Zbl 0955.05004 · doi:10.1006/aama.1999.0673 |
| [23] | Di Francesco P 2003 Geodesic distance in planar graphs: an integrable approach Ramanujan J. at press [math.CO/0506543] · Zbl 1079.05040 |
| [24] | Jimbo M and Miwa T 1983 Solitons and infinite dimensional Lie algebras Publ. RIMS, Kyoto Univ.19 943 equation (2.12) · Zbl 0557.35091 · doi:10.2977/prims/1195182017 |
| [25] | Grammaticos B, Nijhoff F and Ramani A 1999 Discrete Painlevé equations The Painlevé Property, One Century Later(CRM series in Math. Phys.) ed R Conte (New York: Springer) pp 413-516 · Zbl 1014.39013 · doi:10.1007/978-1-4612-1532-5_7 |
| [26] | Bousquet-Mélou M 2005 Limit laws for embedded trees. Applications to the integrated superBrownian excursion Preprint math.CO/0501266 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
