Séminaire Lotharingien de Combinatoire, 80B.80 (2018), 12 pp.
Thomas Browning, Max Hopkins, and Zander Kelley
Doppelgangers: the Ur-Operation and Posets of Bounded Height
Abstract.
In the early 1970s, 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 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. The full version of this paper may be found at
https://arxiv.org/abs/1710.10407.
Received: November 14, 2017.
Accepted: February 17, 2018.
Final version: April 1, 2018.
The following versions are available: