Connected Order Ideals and $P$-Partitions

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 Feray and Reiner in their study of the fundamental generating function $F_P(\textbf{x})$ associated with $P$-partitions. Based on this bijection, in the cases when $P$ is naturally labeled we show that $F_P(\textbf{x})$ 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 Feray and Reiner's nice formula of $F_P(\textbf{x})$ 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$.