Polynomials and the art of counting: some instances of the Cyclic Sieving Phenomenon

Gaiffi, Giovanni ; Iraci, Alessandro

Matematica, cultura e società, Série 1, Tome 2 (2017) no. 2, pp. 225-238.

Riassunto (VO)

Uno dei molti aspetti affascinanti della combinatoria enumerativa Áe quello di trovare contatti fra varie aree della matematica, e di rivelare relazioni insospettate. Il Cyclic Sieving Phenomenon (CSP), introdotto da Reiner, Stanton e White nel 2004, Áe un recente capitolo di ricerca in questo campo. Lo scopo di questo articolo Áe quello di offrire un'introduzione breve ed elementare al CSP attraverso alcuni esempi. In sintesi, il CSP consiste in questo: si parte da un insieme su cui c'eÁ una azione di un gruppo ciclico con n elementi, e si associa in modo naturale a questo insieme un polinomio. Il punto fondamentale Áe che questo polinomio ha una proprieta Á ``magica'': se si valuta nelle radici ennesime dell'unitaÁ, si ottengono dei numeri naturali che contano i punti fissi dell'azione del gruppo ciclico. Nei nostri esempi compariranno molti oggetti combinatori interessanti, legati ai numeri di Catalan, di Kirkman-Cayley e di Narayana, come le triangolazioni e le dissezioni di poligoni regolari, le partizioni non incrociate, le parentesizzazioni di liste e i grafi ad albero con radice.

Abstract

One of the many fascinating aspects of Enumerative Combinatorics is that it often finds contacts between different areas of mathematics, and reveals unsuspected relations. The Cyclic Sieving Phenomenon (CSP), introduced by Reiner, Stanton and White in 2004, is a recent chapter in this field. The purpose of this paper is to give a short and elementary introduction to the CSP by some examples. The gist of the story is that one starts from a set equipped with a cyclic group action, and finds a natural way to associate a polynomial to this set, with the following `magic' property: if one evaluates this polynomial at some suitable roots of 1, one gets nonnegative integers that enumerate the fixed points of the group action. In our examples many interesting combinatorial objects will come into play, like triangulations and dissections of regular polygons, noncrossing partitions, parenthesizations of lists and rooted ordered plane trees.

Bibliographie

[1] Drew Armstrong, Generalized noncrossing partitions and combinatorics of coxeter groups, Mem. Amer. Math. Soc. 202 (2009), no. 949, x+159. MR2561274 | DOI | MR | Zbl

[2] David Bessis and Victor Reiner, Cyclic sieving of noncrossing partitions for complex reflection groups, Ann. Comb. 15 (2011), no. 2, 197-222. MR2813511 | DOI | MR | Zbl

[3] Nachum Dershowitz and Shmuel Zaks, Ordered trees and non-crossing partitions, Discrete mathematics 62 (1986), no. 2, 215-218. | DOI | MR | Zbl

[4] Giovanni Gaiffi, Nested sets, set partitions and Kirkman-Cayley dissection numbers, European J. Combin. 43 (2015), 279-288. MR3266297 | DOI | MR | Zbl

[5] Alessandro Iraci, Cyclic sieving for noncrossing partitions, master degree thesis (2016), https://etd.adm.unipi.it/ t/etd-09262016-145036/.

[6] Oliver Pechenik, Cyclic sieving of increasing tableaux and small Schröder paths, J. Combin. Theory Ser. A 125 (2014), 357-378. MR3207480 | DOI | MR | Zbl

[7] Józef H. Przytycki and Adam S. Sikora, Polygon dissections and Euler, Fuss, Kirkman, and Cayley numbers, J. Combin. Theory Ser. A 92 (2000), no. 1, 68-76. MR1783940 | DOI | MR

[8] Victor Reiner, Equivariant fiber polytopes, Doc. Math. 7 (2002), 113-132 (electronic). MR1911212 | fulltext EuDML | MR

[9] Victor Reiner and Eric Sommers, Weyl group q-Kreweras numbers and cyclic sieving, ArXiv e-prints (2016May), available at 1605.09172.

[10] Victor Reiner, Dennis Stanton and Dennis White, The cyclic sieving phenomenon, J. Combin. Theory Ser. A 108 (2004), no. 1, 17-50. MR2087303 | DOI | MR | Zbl

[11] Victor Reiner, Dennis Stanton and Dennis White, What is... cyclic sieving?, Notices Amer. Math. Soc. 61 (2014), no. 2, 169-171. MR3156682 | DOI | MR | Zbl

[12] Brendon Rhoades, A skein action of the symmetric group on noncrossing partitions, Journal Algebraic Combinatorics (2016), 1-47. | DOI | MR | Zbl

[13] Bruce E. Sagan, The cyclic sieving phenomenon: a survey, Surveys in combinatorics 2011, 2011, pp. 183- 233. MR2866734 | MR | Zbl

[14] Rodica Simion, A type-B associahedron, Adv. in Appl. Math. 30 (2003), no. 1-2, 2-25. Formal power series and algebraic combinatorics (Scottsdale, AZ, 2001). MR1979780 | DOI | MR

[15] Polygon dissections and standard Young tableaux, J. Combin. Theory Ser. A 76 (1996), no. 1, 175-177. MR1406001 | DOI | MR | Zbl

[16] Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. MR1676282 | DOI | MR

[17] Richard P. Stanley, Enumerative combinatorics. Volume 1, Second, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 2012. MR2868112 | MR

[18] Richard P. Stanley, Catalan numbers, Cambridge University Press, New York, 2015. MR3467982 | DOI | MR

[19] John R. Stembridge, On minuscule representations, plane partitions and involutions in complex Lie groups, Duke Math. J. 73 (1994), no. 2, 469-490. MR1262215 | DOI | MR | Zbl

[20] John R. Stembridge, Some hidden relations involving the ten symmetry classes of plane partitions, J. Combin. Theory Ser. A 68 (1994), no. 2, 372-409. MR1297179 | DOI | MR | Zbl

[21] Marko Thiel, A new cyclic sieving phenomenon for Catalan objects, Discrete Math. 340 (2017), no. 3, 426- 429. MR3584829. | DOI | MR | Zbl