G-parking functions and tree inversions
Tóm tắt
A depth-first search version of Dhar’s burning algorithm is used to give a bijection between the parking functions of a graph and labeled spanning trees, relating the degree of the parking function with the number of inversions of the spanning tree. Specializing to the complete graph solves a problem posed by R. Stanley.
Tài liệu tham khảo
M. Baker and S. Norine: Riemann-Roch and Abel-Jacobi theory on a finite graph, Adv. Math. 215 (2007), 766–788.
M. Baker and F. Shokrieh: Chipring games, potential theory on graphs, and spanning trees, J. Combin. Theory Ser. A 120 (2013), 164–182.
J. S. Beissinger: On external activity and inversions in trees, J. Combin. Theory Ser. B 33 (1982), 87–92.
N. L. Biggs: Chipring and the critical group of a graph, J. Algebraic Combin. 9 (1999), 25–45.
V. Chvatal and P. L. Hammer: Aggregation of inequalities in integer programming, in: Studies in integer programming (Proc. Workshop, Bonn, 1975), 145–162, Ann. of Discrete Math., Vol. 1. North-Holland, Amsterdam, 1977.
R. Cori and Y. Le Borgne: The sand-pile model and Tutte polynomials, Adv. in Appl. Math. 30 (2003), 44–52, Formal power series and algebraic combinatorics (Scottsdale, AZ, 2001).
D. Dhar: Theoretical studies of self-organized criticality, Phys. A 369 (2006), 29–70.
I. M. Gessel: Enumerative applications of a decomposition for graphs and digraphs, Discrete Math. 139 (1995), 257–271, Formal power series and algebraic combinatorics (Montreal, PQ, 1992).
I. M. Gessel and B. E. Sagan: The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions, Electron. J. Combin., 3(2):Research Paper 9, 1996. The Foata Festschrift.
A. Guedes de Oliveira and M. Las Vergnas: Parking functions and labeled trees, Sém. Lothar. Combin. 65 (2010/12), Art. B65e, 10.
M. D. Haiman: Conjectures on the quotient ring by diagonal invariants, J. Algebraic Combin. 3 (1994), 17–76.
A. E. Holroyd, L. Levine, K. Meszaros, Y. Peres, J. Propp and D. B. Wilson: Chipring and rotor-routing on directed graphs, in: In and out of equilibrium. 2, volume 60 of Progr. Probab., 331–364. Birkhlauser, Basel, 2008.
S. Hopkins and D. Perkinson: Bigraphical arrangements, To appear in Trans. Amer. Math. Soc.; eprint, arXiv:1212.4398, 2012.
A. G. Konheim and B. Weiss: An occupancy discipline and applications, SIAM J. Applied Math. 14 (1966), 1266–1274.
G. Kreweras: Une famille de polyn omes ayant plusieurs propriétésénumeratives, Period. Math. Hungar. 11 (1980), 309–320.
D. J. Lorenzini: Arithmetical graphs, Math. Ann. 285 (1989), 481–501.
D. J. Lorenzini: Anite group attached to the Laplacian of a graph, Discrete Math. 91 (1991), 277–282.
N. V. R. Mahadev and U. N. Peled: Threshold graphs and related topics, volume 56 of Annals of Discrete Mathematics, North-Holland Publishing Co., Amsterdam, 1995.
C. Merino Lopez: Chipring and the Tutte polynomial, Ann. Comb. 1 (1997), 253–259.
J.-C. Novelli and J.-Y. Thibon: Hopf algebras and dendriform structures arising from parking functions, Fund. Math. 193 (2007), 189–241.
A. Postnikov and B. Shapiro: Trees, parking functions, syzygies, and deformations of monomial ideals, Trans. Amer. Math. Soc. 356 (2004), 3109–3142 (electronic).
H. Shin: A new bijection between forests and parking functions, eprint, arXiv:0810.0427, 2008.
R. P. Stanley: An introduction to hyperplane arrangements, in: Geometric combinatorics, volume 13 of IAS/Park City Math. Ser., 389–496, Amer. Math. Soc., Providence, RI, 2007.