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.
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.
@article{RUMI_2017_1_2_2_225_0,
author = {Giovanni Gaiffi and Alessandro Iraci},
title = {Polynomials and the art of counting: some instances of the Cyclic Sieving Phenomenon},
journal = {Matematica, Cultura e Societ\`a. Rivista dell'Unione Matematica Italiana},
volume = {2},
year = {2017},
pages = {225-238},
mrnumber = {3700592},
language = {it},
url = {http://dml.mathdoc.fr/item/RUMI_2017_1_2_2_225_0}
}
Gaiffi, Giovanni; Iraci, Alessandro. Polynomials and the art of counting: some instances of the Cyclic Sieving Phenomenon. Matematica, Cultura e Società. Rivista dell'Unione Matematica Italiana, Tome 2 (2017) pp. 225-238. http://gdmltest.u-ga.fr/item/RUMI_2017_1_2_2_225_0/
[1] , Generalized noncrossing partitions and combinatorics of coxeter groups, Mem. Amer. Math. Soc.202 (2009), no. 949, x+159. MR2561274 | MR 2561274 | Zbl 1191.05095
[2] and , Cyclic sieving of noncrossing partitions for complex reflection groups, Ann. Comb. 15 (2011), no. 2, 197-222. MR2813511 | MR 2813511 | Zbl 1268.20041
[3] and , Ordered trees and non-crossing partitions, Discrete mathematics 62 (1986), no. 2, 215-218. | MR 863045 | Zbl 0646.05004
[4] , Nested sets, set partitions and Kirkman-Cayley dissection numbers, European J. Combin.43 (2015), 279-288. MR3266297 | MR 3266297 | Zbl 1301.05031
[5] , Cyclic sieving for noncrossing partitions, master degree thesis (2016), https://etd.adm.unipi.it/ t/etd-09262016-145036/.
[6] , Cyclic sieving of increasing tableaux and small Schröder paths, J. Combin. Theory Ser. A125 (2014), 357-378. MR3207480 | MR 3207480 | Zbl 1295.05265
[7] and , Polygon dissections and Euler, Fuss, Kirkman, and Cayley numbers, J. Combin. Theory Ser. A 92 (2000), no. 1, 68-76. MR1783940 | MR 1783940
[8] , Equivariant fiber polytopes, Doc. Math.7 (2002), 113-132 (electronic). MR1911212 | MR 1911212
[9] and , Weyl group q-Kreweras numbers and cyclic sieving, ArXiv e-prints (2016May), available at 1605.09172.
[10] , and , The cyclic sieving phenomenon, J. Combin. Theory Ser. A 108 (2004), no. 1, 17-50. MR2087303 | MR 2087303 | Zbl 1052.05068
[11] , and , What is... cyclic sieving?, Notices Amer. Math. Soc. 61 (2014), no. 2, 169-171. MR3156682 | MR 3156682 | Zbl 1338.05012
[12] , A skein action of the symmetric group on noncrossing partitions, Journal Algebraic Combinatorics (2016), 1-47. | MR 3591372 | Zbl 1355.05280
[13] , The cyclic sieving phenomenon: a survey, Surveys in combinatorics 2011, 2011, pp. 183- 233. MR2866734 | MR 2866734 | Zbl 1233.05028
[14] , 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 | MR 1979780
[15] Polygon dissections and standard Young tableaux, J. Combin. Theory Ser. A 76 (1996), no. 1, 175-177. MR1406001 | MR 1406001 | Zbl 0859.05075
[16] , 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 | MR 1676282
[17] , Enumerative combinatorics. Volume 1, Second, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 2012. MR2868112 | MR 2868112
[18] , Catalan numbers, Cambridge University Press, New York, 2015. MR3467982 | MR 3467982
[19] , On minuscule representations, plane partitions and involutions in complex Lie groups, Duke Math. J.73 (1994), no. 2, 469-490. MR1262215 | MR 1262215 | Zbl 0805.22006
[20] , Some hidden relations involving the ten symmetry classes of plane partitions, J. Combin. Theory Ser. A 68 (1994), no. 2, 372-409. MR1297179 | MR 1297179 | Zbl 0809.05007
[21] , A new cyclic sieving phenomenon for Catalan objects, Discrete Math.340 (2017), no. 3, 426- 429. MR3584829. | MR 3584829 | Zbl 1351.05235