Connected order ideals and \(P\)-partitions

Ben P. Zhou¹

¹Center for Combinatorics Nankai University Tianjin 300071, P. R. China

The electronic journal of combinatorics, Tome 25 (2018) no. 1

Résumé

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$.

Détail

DOI : 10.37236/6463

Classification : 05A15, 06A07
Mots-clés : \(P\)-partition, \(P\)-forest, linear extension, connected order ideal, maximum independent set