Order polynomials and Pólya's enumeration theorem.

MaRDI QIDQ405267zbMATH OpenFDO

Authors Katharina Jochemko

Publication date 4 September 2014

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

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

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

group actionspartially ordered setsgraph coloringsorder preserving mapsPólya enumeration

Mathematics Subject Classification ID

Graph polynomials (05C31) Combinatorial identities, bijective combinatorics (05A19) Coloring of graphs and hypergraphs (05C15) Combinatorics of partially ordered sets (06A07) Group actions on combinatorial structures (05E18) Algebraic aspects of posets (06A11)

Abstract: P'olya's enumeration theorem is concerned with counting labeled sets up to symmetry. Given a finite group acting on a finite set of labeled elements it states that the number of labeled sets up to symmetry is given by a polynomial in the number of labels. We give a new perspective on this theorem by generalizing it to partially ordered sets and order preserving maps. Further we prove a reciprocity statement in terms of strictly order preserving maps generalizing a classical result by Stanley (1970). We apply our results to counting graph colorings up to symmetry.

Recommendations

• A generalized form of Pòlya's counting method
• An invariant theory approach to graph enumeration
• Pólya's Theorem and Its Progeny
• scientific article; zbMATH DE number 1890128
• scientific article; zbMATH DE number 815883

Cites work

• scientific article; zbMATH DE number 3341135 (Why is no real title available?)
• A course in combinatorics.
• Acyclic orientations of graphs
• Equivariant Ehrhart theory
• Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen
• Orbital Chromatic and Flow Roots
• Ordered structures and partitions
• Quotients of Peck posets
• The chromatic polynomial of an unlabeled graph

Cited in

(22)

• The chromatic quasisymmetric class function of a digraph
• The Combinatorial Significance of a Theorem of Pólya
• scientific article; zbMATH DE number 4006278 (Why is no real title available?)
• scientific article; zbMATH DE number 1389217 (Why is no real title available?)
• An invariant theory approach to graph enumeration
• The odd-valued chromatic polynomial of a signed graph
• Polya enumeration theorems in algebraic geometry
• A recursion of the Pólya polynomial for the symmetric group
• Numerical algorithm for Pólya enumeration theorem
• Effective Poset Inequalities
• Chromatic quasisymmetric class functions of linearized combinatorial Hopf monoids
• Generating polynomial orderings
• A generalized form of Pòlya's counting method
• scientific article; zbMATH DE number 1890128 (Why is no real title available?)
• Arithmetic of marked order polytopes, monotone triangle reciprocity, and partial colorings
• scientific article; zbMATH DE number 6118169 (Why is no real title available?)
• scientific article; zbMATH DE number 205337 (Why is no real title available?)
• scientific article; zbMATH DE number 1557805 (Why is no real title available?)
• Double posets and the antipode of QSym
• Chromatic quasisymmetric class functions for combinatorial Hopf monoids
• Representations, characters, and counting colourings under symmetry
• Double posets and the antipode of QSym

This page was built for publication: Order polynomials and Pólya's enumeration theorem.

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