The cycle polynomial of a permutation group

MaRDI QIDQ1700769zbMATH OpenFDO

Authors Peter J. Cameron, Jason Semeraro

Publication date 22 February 2018

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.06954, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i1p14

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

chromatic polynomialpermutation groupsreciprocity theorems

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Graph polynomials (05C31) General theory for finite permutation groups (20B05)

Abstract: The cycle polynomial of a finite permutation group $G$ is the generating function for the number of elements of $G$ with a given number of cycles: [F_G(x) = sum_{gin G}x^{c(g)},] where $c(g)$ is the number of cycles of $g$ on $Omega$. In the first part of the paper, we develop basic properties of this polynomial, and give a number of examples. In the 1970s, Richard Stanley introduced the notion of reciprocity for pairs of combinatorial polynomials. We show that, in a considerable number of cases, there is a polynomial in the reciprocal relation to the cycle polynomial of $G$; this is the orbital chromatic polynomial of $Gamma$ and $G$, where $Gamma$ is a $G$-invariant graph, introduced by the first author, Jackson and Rudd. We pose the general problem of finding all such reciprocal pairs, and give a number of examples and characterisations: the latter include the cases where $Gamma$ is a complete or null graph or a tree. The paper concludes with some comments on other polynomials associated with a permutation group.

Review text

Summary: The cycle polynomial of a finite permutation group \(G\) is the generating function for the number of elements of \(G\) with a given number of cycles: \[ F_G(x) = \sum_{g\in G}x^{c(g)}, \] where \(c(g)\) is the number of cycles of \(g\) on \(\Omega\). In the first part of the paper, we develop basic properties of this polynomial, and give a number of examples. In the 1970s, Richard Stanley introduced the notion of reciprocity for pairs of combinatorial polynomials. We show that, in a considerable number of cases, there is a polynomial in the reciprocal relation to the cycle polynomial of \(G\); this is the \textit{orbital chromatic polynomial} of \(\Gamma\) and \(G\), where \(\Gamma\) is a \(G\)-invariant graph, introduced by the first author, Jackson and Rudd. We pose the general problem of finding all such reciprocal pairs, and give a number of examples and characterisations: the latter include the cases where \(\Gamma\) is a complete or null graph or a tree. The paper concludes with some comments on other polynomials associated with a permutation group.

Recommendations

• scientific article; zbMATH DE number 782052
• Some differential properties of Pólya's cycle indicators
• A generalized form of Pòlya's counting method
• Cycle indices and subgroup lattices
• Fixed point polynomials of permutation groups.

Cites work

• A logical expansion in mathematics
• Fixed point polynomials of permutation groups.
• scientific article; zbMATH DE number 3468860 (Why is no real title available?)
• scientific article; zbMATH DE number 1261512 (Why is no real title available?)
• scientific article; zbMATH DE number 1033382 (Why is no real title available?)
• Orbit-counting polynomials for graphs and codes
• Set-Transitive Permutation Groups
• Two enumerative results on cycles of permutations

Cited in

(3)

• Quasisymmetric and Schur expansions of cycle index polynomials
• Some differential properties of Pólya's cycle indicators
• Derangements in wreath products of permutation groups

This page was built for publication: The cycle polynomial of a permutation group

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1700769)