Chip-firing games, potential theory on graphs, and spanning trees

被引：59

作者：

Baker, Matthew ^{[1
]}

Shokrieh, Farbod ^{[1
]}

机构：

[1] Georgia Inst Technol, Atlanta, GA 30332 USA

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES A | 2013年 / 120卷 / 01期

基金：

美国国家科学基金会;

关键词：

Chip-firing; Potential theory; Energy pairing; Reduced divisors; Matrix-tree theorem; Random spanning trees; PARKING FUNCTIONS; MODEL;

D O I：

10.1016/j.jcta.2012.07.011

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We study the interplay between chip-firing games and potential theory on graphs, characterizing reduced divisors (G-parking functions) on graphs as the solution to an energy (or potential) minimization problem and providing an algorithm to efficiently compute reduced divisors. Applications include an "efficient bijective" proof of Kirchhoffs matrix-tree theorem and a new algorithm for finding random spanning trees. The running times of our algorithms are analyzed using potential theory, and we show that the bounds thus obtained generalize and improve upon several previous results in the literature. (C) 2012 Elsevier Inc. All rights reserved.

引用

页码：164 / 182

页数：19

共 46 条

[1] THE RANDOM-WALK CONSTRUCTION OF UNIFORM SPANNING-TREES AND UNIFORM LABELED TREES
ALDOUS, DJ
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 1990, 3 (04) : 450 - 465
[2] REFLECTION SEQUENCES
ALON, N
KRASIKOV, I
PERES, Y
[J]. AMERICAN MATHEMATICAL MONTHLY, 1989, 96 (09) : 820 - 823
[3] [Anonymous], 1998, GRAD TEXT M
[4] The lattice of integral flows and the lattice of integral cuts on a finite graph
Bacher, R
delaHarpe, P
Nagnibeda, T
[J]. BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE, 1997, 125 (02): : 167 - 198
[5] SELF-ORGANIZED CRITICALITY
BAK, P
TANG, C
WIESENFELD, K
[J]. PHYSICAL REVIEW A, 1988, 38 (01): : 364 - 374
[6] Riemann-Roch and Abel-Jacobi theory on a finite graph
Baker, Matthew
Norine, Serguei
[J]. ADVANCES IN MATHEMATICS, 2007, 215 (02) : 766 - 788
[7] Baker M, 2006, CONTEMP MATH, V415, P15
[8] BEN-ISRAEL A., 2003, CMS BOOKS MATH OUVRA, V15
[9] G-parking functions, acyclic orientations and spanning trees
Benson, Brian
Chakrabarty, Deeparnab
Tetali, Prasad
[J]. DISCRETE MATHEMATICS, 2010, 310 (08) : 1340 - 1353
[10] The Tutte polynomial as a growth function
Biggs, N
[J]. JOURNAL OF ALGEBRAIC COMBINATORICS, 1999, 10 (02) : 115 - 133

← 1 2 3 4 5 →