Parking Function

Petrullo と Senato [PS08] や Gorsky ら [GG] によると, parking function は 1960年代に Konheim と Weiss [KW66] により導入されたものらしい。 その論文の最後の section に, a parking problem として, 気まぐれな奥さんを乗せた車の縦列駐車問題への応用が書かれているので, それがこの parking function という名前の由来のようである。 定義は, 例えば Postnikov と Shapiro の [PS04] などにある。 縦列駐車との関係は, Beck らの [Bec+] の §1.1 の説明が分かりやすい。

古典的には parking function は, ラベル付けられた有限集合を頂点に持つ tree の数, つまり完全グラフの spanning tree の数を数えるものである。 これは Kreweras [Kre80] の結果のようである。 完全グラフを一般のグラフ や quiver \(G\) にした \(G\)-parking function も定義されている。

• \(G\)-parking function

そしてそれらについても spanning tree の個数を数えるものであることが, Gabrielov [Gab93] により示されている。

Parking function は様々なものに関係があり, 興味深い。Benson とTetali の [BCT] や Gorsky らの [GG] によると, 以下のものに関係がある。

• 統計物理における sandpile model
• chip-firing game
• グラフに対する Riemann-Roch の定理の類似
• Tutte polynomial
• vertex operator [Dot09]
• noncrossing partition [Sta97]
• complex hypersurface singularity [GG]
• Shi arrangement

Sandpile model については, AMS の Notices に Levine と Propp の解説 [LP10] がある。 グラフの不変量として, sandpile group という Abel群も定義される。

• sandpile group

他にも, 対称群の表現との関係が重要のようである。 Haiman は, [Hai98; Hai02] で parking function や Catalan number やその一般化の categorification とも言うべき対称群の表現を構成している。

• Haiman の parking function module

Parking function の集合に braid群 が作用することも知られている。Gorsky と Gorsky [GG] が complex hypersurface singularity との関連で発見した。

このように, 古典的な parking function は \(A\)型の root系に深く関係している。 それをより一般の Coxeter system に拡張しようとしたものとして, Armstrong と Reiner と Rhoades の [ARR15] がある。

代数的な構造としては, combinatorial Hopf algebra を作ることもできる。 Novelli と Thibon の [NT; NT07] である。

Shi arrangement との関係を拡張したものとして, グラフ \(G\) から \(G\)-parking function と関係のある hyperplane arrangement を作っている, HopkinsとPerkinsonの結果 [HP16] などがある。

References

[ARR15]

Drew Armstrong, Victor Reiner, and Brendon Rhoades. “Parking spaces”. In: Adv. Math. 269 (2015), pp. 647–706. arXiv: 1204.1760. url: http://dx.doi.org/10.1016/j.aim.2014.10.012.

[BCT]

Brian Benson, Deeparnab Chakrabarty, and Prasad Tetali. \(G\)-Parking Functions, Acyclic Orientations and Spanning Trees. arXiv: 0801.1114.

[Bec+]

Matthias Beck et al. Parking functions, Shi arrangements, and mixed graphs. arXiv: 1405.5587.

[Dot09]

Vladimir Dotsenko. “Parking functions and vertex operators”. In: Selecta Math. (N.S.) 14.2 (2009), pp. 229–245. arXiv: 0809.3683. url: http://dx.doi.org/10.1007/s00029-008-0067-7.

[Gab93]

Andrei Gabrielov. “Abelian avalanches and Tutte polynomials”. In: Phys. A 195.1-2 (1993), pp. 253–274. url: http://dx.doi.org/10.1016/0378-4371(93)90267-8.

[GG]

Evgeny Gorsky and Mikhail Gorsky. A braid group action on parking functions. arXiv: 1112.0381.

[Hai02]

Mark Haiman. “Vanishing theorems and character formulas for the Hilbert scheme of points in the plane”. In: Invent. Math. 149.2 (2002), pp. 371–407. arXiv: math/0201148. url: http://dx.doi.org/10.1007/s002220200219.

[Hai98]

Mark Haiman. “\(t,q\)-Catalan numbers and the Hilbert scheme”. In: Discrete Math. 193.1-3 (1998). Selected papers in honor of Adriano Garsia (Taormina, 1994), pp. 201–224. url: http://dx.doi.org/10.1016/S0012-365X(98)00141-1.

[HP16]

Sam Hopkins and David Perkinson. “Bigraphical arrangements”. In: Trans. Amer. Math. Soc. 368.1 (2016), pp. 709–725. arXiv: 1212.4398. url: https://doi.org/10.1090/tran/6341.

[Kre80]

G. Kreweras. “Une famille de polynômes ayant plusieurs propriétés énumeratives”. In: Period. Math. Hungar. 11.4 (1980), pp. 309–320. url: http://dx.doi.org/10.1007/BF02107572.

[KW66]

Alan G. Konheim and Benjamin Weiss. “An Occupancy Discipline and Applications”. In: SIAM Journal on Applied Mathematics 14.6 (Nov. 1966), pp. 1266–1274.

[LP10]

Lionel Levine and James Propp. “What is \(\dots \) a sandpile?” In: Notices Amer. Math. Soc. 57.8 (2010), pp. 976–979.

[NT]

Jean-Christophe Novelli and Jean-Yves Thibon. A Hopf algebra of parking functions. arXiv: math/0312126.

[NT07]

Jean-Christophe Novelli and Jean-Yves Thibon. “Hopf algebras and dendriform structures arising from parking functions”. In: Fund. Math. 193.3 (2007), pp. 189–241. url: http://dx.doi.org/10.4064/fm193-3-1.

[PS04]

Alexander Postnikov and Boris Shapiro. “Trees, parking functions, syzygies, and deformations of monomial ideals”. In: Trans. Amer. Math. Soc. 356.8 (2004), 3109–3142 (electronic). arXiv: math/0301110. url: http://dx.doi.org/10.1090/S0002-9947-04-03547-0.

[PS08]

P. Petrullo and D. Senato. “An instance of umbral methods in representation theory: the parking function module”. In: Pure Math. Appl. (PU.M.A.) 19.2-3 (2008), pp. 105–115. arXiv: 0807.4840.

[Sta97]

Richard P. Stanley. “Parking functions and noncrossing partitions”. In: vol. 4. 2. The Wilf Festschrift (Philadelphia, PA, 1996). 1997, Research Paper 20, approx. 14. url: http://www.combinatorics.org/Volume_4/Abstracts/v4i2r20.html.