The Complexity of the Partial Order Dimension Problem - Closing the Gap

Stefan Felsner, Irina Mustata, Martin Pergel

The dimension of a partial order $P$ is the minimum number of linear orders whose intersection is $P$. There are efficient algorithms to test if a partial order has dimension at mo…