Noncrossing Partitions

集合 \(\{1,\ldots ,n\}\) を円周上に順に等間隔で並べたものの partition で, 凸包 が互いに交わらないものを noncrossing partition という。Ingalls と Thomas の [IT09] によると, Kreweras の [Kre72] で導入された概念らしい。

これは \(A_{n-1}\)型の real central arrangement と関係があり, より一般の Coxeter group に対しても noncrossing partition の集合を定義できる。Armstrong の [Arm09] によると, Brady と Watt の [BW02] と Bessis の [Bes03] で定義されたようである。

Catalan number という数と深い関係にある。

• Catalan number

Noncrossing partition とそれに関連した事柄については, 次の website を見るとよい。Open problem のリストや解説がある。

• Braid Groups, Clusters and Free Probability
• Associahedra and Noncrossing Partitions

表現論の視点からの survey として Ringel の [Rin16] がある。

Armstrong は, [Arm09] でその一般化 (高次化) を考えている。 Bessiss と Reiner は [BR11] で, cyclic sieving phenomenon という 組み合せ論的構造について考えている。

• cyclic sieving phenomenon

Ingalls と Thomas の [IT09] は, cluster algebra などとの関係を, hereditary algebra の表現論の視点から説明しようという試みである。

• Dynkin diagram に対する cluster algebra の cluster と noncrossing partition の対応

彼らは, より一般に finite acyclic quiver に対し, 様々なデータの間の一対一対応を示していて興味深い。

円周上に配置された点を互いに交わらない tree で結んだ noncrossing forest も考えられている。

• noncrossing forest

Kluge [Klu12] は, cyclic sieving phenomena を持つことを示している。

円上に配置された集合 \(\{1,\ldots ,n\}\) の分割ではなく, 多角形の分割として調べることも行なわれている。 例えば, Conley と Ovsienko の [CO23] など。 そのような分割は, そこでは dissection と呼ばれているが, 凸多角形の dissection は Monsky の意味の dissection もあるので注意が必要である。

• 凸多角形の互いに交わらない対角線による dissection

References

[Arm09]

Drew Armstrong. “Generalized noncrossing partitions and combinatorics of Coxeter groups”. In: Mem. Amer. Math. Soc. 202.949 (2009), pp. x+159. arXiv: math/0611106. url: http://dx.doi.org/10.1090/S0065-9266-09-00565-1.

[Bes03]

David Bessis. “The dual braid monoid”. In: Ann. Sci. École Norm. Sup. (4) 36.5 (2003), pp. 647–683. arXiv: math/0101158. url: http://dx.doi.org/10.1016/j.ansens.2003.01.001.

[BR11]

David Bessis and Victor Reiner. “Cyclic sieving of noncrossing partitions for complex reflection groups”. In: Ann. Comb. 15.2 (2011), pp. 197–222. arXiv: math/0701792. url: http://dx.doi.org/10.1007/s00026-011-0090-9.

[BW02]

Thomas Brady and Colum Watt. “\(K(\pi ,1)\)’s for Artin groups of finite type”. In: Geom. Dedicata 94 (2002), pp. 225–250. url: http://dx.doi.org/10.1023/A:1020902610809.

[CO23]

Charles H. Conley and Valentin Ovsienko. “Counting quiddities of polygon dissections”. In: Math. Intelligencer 45.3 (2023), pp. 256–262. arXiv: 2202.00269. url: https://doi.org/10.1007/s00283-022-10180-3.

[IT09]

Colin Ingalls and Hugh Thomas. “Noncrossing partitions and representations of quivers”. In: Compos. Math. 145.6 (2009), pp. 1533–1562. arXiv: math/0612219. url: http://dx.doi.org/10.1112/S0010437X09004023.

[Klu12]

Stefan Kluge. “The cyclic sieving phenomenon for non-crossing forests”. In: Electron. J. Combin. 19.3 (2012), Paper 1, 11. arXiv: 1106.0992.

[Kre72]

G. Kreweras. “Sur les partitions non croisées d’un cycle”. In: Discrete Math. 1.4 (1972), pp. 333–350. url: https://doi.org/10.1016/0012-365X(72)90041-6.

[Rin16]

Claus Michael Ringel. “The Catalan combinatorics of the hereditary Artin algebras”. In: Recent developments in representation theory. Vol. 673. Contemp. Math. Amer. Math. Soc., Providence, RI, 2016, pp. 51–177. arXiv: 1502.06553. url: https://doi.org/10.1090/conm/673/13490.