Order polynomials and Pólya's enumeration theorem.

zbMATH Open1309.06003arXiv1310.0838MaRDI QIDQ405267FDOQ405267

Authors: Katharina Jochemko 

Publication date: 4 September 2014

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

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.

Full work available at URL: https://arxiv.org/abs/1310.0838

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

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

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)

Cites Work

• A course in combinatorics.
• Acyclic orientations of graphs
• Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen
• Ordered structures and partitions
• Quotients of Peck posets
• The chromatic polynomial of an unlabeled graph
• Orbital Chromatic and Flow Roots
• Title not available (Why is that?)
• Equivariant Ehrhart theory

Cited In (22)

• The chromatic quasisymmetric class function of a digraph
• The Combinatorial Significance of a Theorem of Pólya
• Title not available (Why is that?)
• Title not available (Why is that?)
• The odd-valued chromatic polynomial of a signed graph
• An invariant theory approach to graph enumeration
• 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
• A generalized form of Pòlya's counting method
• Generating polynomial orderings
• Title not available (Why is that?)
• Arithmetic of marked order polytopes, monotone triangle reciprocity, and partial colorings
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)