2017/10/28 by Thomas Browning, Browning, Thomas, Max Hopkins +3 · 1 citation
Mathematics · Computer Science · #Advanced Combinatorial Mathematics #Mathematics and Applications #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.1710.10407
In the early 1970's, Richard Stanley and Kenneth Johnson introduced and laid the groundwork for studying the order polynomial of partially ordered sets (posets). Decades later, Hamaker, Patrias, Pechenik, and Williams introduced the term "doppelgangers": equivalence classes of posets under the equivalence relation given by equality of the order polynomial. We provide necessary and sufficient conditions on doppelgangers through application of both old and novel tools, including new recurrences and the Ur-operation: a new generalized poset operation. In addition, we prove that the doppelgangers of posets P of bounded height |P|-k may be classified up to systems of k diophantine equations in 2O(k2) time, and similarly that the order polynomial of such posets may be computed in O(|P|) time.