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

Giovanni Gaiffi; Alessandro Iraci

Matematica, Cultura e Società. Rivista dell'Unione Matematica Italiana (2017)

  • Volume: 2, Issue: 2, page 225-238
  • ISSN: 2499-751X

Abstract

top
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.

How to cite

top

Gaiffi, Giovanni, and Iraci, Alessandro. "Polynomials and the art of counting: some instances of the Cyclic Sieving Phenomenon." Matematica, Cultura e Società. Rivista dell'Unione Matematica Italiana 2.2 (2017): 225-238. <http://eudml.org/doc/290413>.

@article{Gaiffi2017,
abstract = {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.},
author = {Gaiffi, Giovanni, Iraci, Alessandro},
journal = {Matematica, Cultura e Società. Rivista dell'Unione Matematica Italiana},
language = {ita},
month = {8},
number = {2},
pages = {225-238},
publisher = {Unione Matematica Italiana},
title = {Polynomials and the art of counting: some instances of the Cyclic Sieving Phenomenon},
url = {http://eudml.org/doc/290413},
volume = {2},
year = {2017},
}

TY - JOUR
AU - Gaiffi, Giovanni
AU - Iraci, Alessandro
TI - Polynomials and the art of counting: some instances of the Cyclic Sieving Phenomenon
JO - Matematica, Cultura e Società. Rivista dell'Unione Matematica Italiana
DA - 2017/8//
PB - Unione Matematica Italiana
VL - 2
IS - 2
SP - 225
EP - 238
AB - 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.
LA - ita
UR - http://eudml.org/doc/290413
ER -

References

top
  1. ARMSTRONG, DREW, Generalized noncrossing partitions and combinatorics of coxeter groups, Mem. Amer. Math. Soc.202 (2009), no. 949, x+159. MR2561274 Zbl1191.05095MR2561274DOI10.1090/S0065-9266-09-00565-1
  2. BESSIS, DAVID and REINER, VICTOR, Cyclic sieving of noncrossing partitions for complex reflection groups, Ann. Comb.15 (2011), no. 2, 197-222. MR2813511 Zbl1268.20041MR2813511DOI10.1007/s00026-011-0090-9
  3. DERSHOWITZ, NACHUM and ZAKS, SHMUEL, Ordered trees and non-crossing partitions, Discrete mathematics62 (1986), no. 2, 215-218. Zbl0646.05004MR863045DOI10.1016/0012-365X(86)90120-2
  4. GAIFFI, GIOVANNI, Nested sets, set partitions and Kirkman-Cayley dissection numbers, European J. Combin.43 (2015), 279-288. MR3266297 Zbl1301.05031MR3266297DOI10.1016/j.ejc.2014.08.028
  5. IRACI, ALESSANDRO, Cyclic sieving for noncrossing partitions, master degree thesis (2016), https://etd.adm.unipi.it/ t/etd-09262016-145036/. 
  6. PECHENIK, OLIVER, Cyclic sieving of increasing tableaux and small Schröder paths, J. Combin. Theory Ser. A125 (2014), 357-378. MR3207480 Zbl1295.05265MR3207480DOI10.1016/j.jcta.2014.04.002
  7. PRZYTYCKI, JÓZEF H. and SIKORA, ADAM S., Polygon dissections and Euler, Fuss, Kirkman, and Cayley numbers, J. Combin. Theory Ser. A92 (2000), no. 1, 68-76. MR1783940 MR1783940DOI10.1006/jcta.1999.3042
  8. REINER, VICTOR, Equivariant fiber polytopes, Doc. Math.7 (2002), 113-132 (electronic). MR1911212 MR1911212
  9. REINER, VICTOR and SOMMERS, ERIC, Weyl group q-Kreweras numbers and cyclic sieving, ArXiv e-prints (2016May), available at 1605.09172. 
  10. REINER, VICTOR, STANTON, DENNIS and WHITE, DENNIS, The cyclic sieving phenomenon, J. Combin. Theory Ser. A108 (2004), no. 1, 17-50. MR2087303 Zbl1052.05068MR2087303DOI10.1016/j.jcta.2004.04.009
  11. REINER, VICTOR, STANTON, DENNIS and WHITE, DENNIS, What is... cyclic sieving?, Notices Amer. Math. Soc.61 (2014), no. 2, 169-171. MR3156682 Zbl1338.05012MR3156682DOI10.1090/noti1084
  12. RHOADES, BRENDON, A skein action of the symmetric group on noncrossing partitions, Journal Algebraic Combinatorics (2016), 1-47. Zbl1355.05280MR3591372DOI10.1007/s10801-016-0701-y
  13. SAGAN, BRUCE E., The cyclic sieving phenomenon: a survey, Surveys in combinatorics 2011, 2011, pp. 183- 233. MR2866734 Zbl1233.05028MR2866734
  14. SIMION, RODICA, 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 MR1979780DOI10.1016/S0196-8858(02)00522-5
  15. Polygon dissections and standard Young tableaux, J. Combin. Theory Ser. A 76 (1996), no. 1, 175-177. MR1406001 Zbl0859.05075MR1406001DOI10.1006/jcta.1996.0099
  16. STANLEY, RICHARD P., 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 MR1676282DOI10.1017/CBO9780511609589
  17. STANLEY, RICHARD P., Enumerative combinatorics. Volume 1, Second, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 2012. MR2868112 MR2868112
  18. STANLEY, RICHARD P., Catalan numbers, Cambridge University Press, New York, 2015. MR3467982 MR3467982DOI10.1017/CBO9781139871495
  19. STEMBRIDGE, JOHN R., On minuscule representations, plane partitions and involutions in complex Lie groups, Duke Math. J.73 (1994), no. 2, 469-490. MR1262215 Zbl0805.22006MR1262215DOI10.1215/S0012-7094-94-07320-1
  20. STEMBRIDGE, JOHN R., Some hidden relations involving the ten symmetry classes of plane partitions, J. Combin. Theory Ser. A 68 (1994), no. 2, 372-409. MR1297179 Zbl0809.05007MR1297179DOI10.1016/0097-3165(94)90112-0
  21. THIEL, MARKO, A new cyclic sieving phenomenon for Catalan objects, Discrete Math.340 (2017), no. 3, 426- 429. MR3584829. Zbl1351.05235MR3584829DOI10.1016/j.disc.2016.09.006

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.