Connected order ideals and P-partitions

zbMATH Open1391.05037arXiv1609.05471MaRDI QIDQ1753036FDOQ1753036

Authors: Ben P. Zhou 

Publication date: 25 May 2018

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

Abstract: Given a finite poset $P$, we associate a simple graph denoted by $G_P$ with all connected order ideals of $P$ as vertices, and two vertices are adjacent if and only if they have nonempty intersection and are incomparable with respect to set inclusion. We establish a bijection between the set of maximum independent sets of $G_P$ and the set of $P$-forests, introduced by F'eray and Reiner in their study of the fundamental generating function $F_P(extbfx)$ associated with $P$-partitions. Based on this bijection, in the cases when $P$ is naturally labeled we show that $F_P(extbfx)$ can factorise, such that each factor is a summation of rational functions determined by maximum independent sets of a connected component of $G_P$. This approach enables us to give an alternative proof for F'eray and Reiner's nice formula of $F_P(extbfx)$ for the case of $P$ being a naturally labeled forest with duplications. Another consequence of our result is a product formula to compute the number of linear extensions of $P$.

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

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

Recommendations

• \(P\)-partition generating function equivalence of naturally labeled posets
• \(P\)-partition generating function equivalence of naturally labeled posets
• Partially ordinal sums and \(P\)-partitions
• \(P\)-partitions and quasisymmetric power sums
• On \(P\)-partitions related to ordinal sums of posets

zbMATH Keywords

maximum independent setlinear extension\(P\)-partition\(P\)-forestconnected order ideal

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorics of partially ordered sets (06A07)

Cites Work

• Title not available (Why is that?)
• Counting linear extensions
• Permutohedra, Associahedra, and Beyond
• Faces of generalized permutohedra
• q-hook length formulas for forests
• Ordered structures and partitions
• \(p\)-partitions revisited
• Linear extension sums as valuations on cones
• A historical survey of P-partitions

Cited In (1)

• Connectedness of a variety generated by an order ideal on the punctured spectrum

Uses Software

• SageMath

This page was built for publication: Connected order ideals and \(P\)-partitions

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