Cyclic sieving phenomenon in non-crossing connected graphs

International audience A non-crossing connected graph is a connected graph on vertices arranged in a circle such that its edges do not cross. The count for such graphs can be made naturally into a q-binomial generating function. We prove that this generating function exhibits the cyclic sieving phen...

Full description

Bibliographic Details
Main Author: Guo, Alan
Other Authors: Department of Mathematics Durham, Duke University Durham, Bousquet-Mélou, Mireille and Wachs, Michelle and Hultman, Axel
Format: Conference Object
Language:English
Published: HAL CCSD 2011
Subjects:
non-crossing connected graphs
Lagrange inversion
cyclic sieving phenomenon
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Lagrange
Iceland
Online Access:https://hal.inria.fr/hal-01215104
https://hal.inria.fr/hal-01215104/document
https://hal.inria.fr/hal-01215104/file/dmAO0139.pdf
Description
Summary:International audience A non-crossing connected graph is a connected graph on vertices arranged in a circle such that its edges do not cross. The count for such graphs can be made naturally into a q-binomial generating function. We prove that this generating function exhibits the cyclic sieving phenomenon, as conjectured by S.-P. Eu. Un graphe connexe dont les sommets sont disposés sur un cercle est sans croisement si ses arêtes ne se croisent pas. Nous démontrons une conjecture de S.-P. Eu affirmant que la fonction génératrice q-binomiale dénombrant de tels graphes exhibe le phénomène du crible cyclique.

Similar Items