2
$\begingroup$

Consider a set of $n$ points $x_1, \dots, x_n$ such that none are equal i.e. $x_i = x_j \Rightarrow i = j$.

Now consider a partial ordering (this may not be the correct term to use in this case) represented by a set $S$ e.g.

$$ S = \{x_1 < x_2, x_2 < x_3 \} $$

My question is, how can we find the total number of actual orderings of our points that satisfy the partial ordering represented by $S$?

For example in the 3D case the ordering given by the above $S$ uniquely defines the actual order of the points $x_1 < x_2 < x_3$. However if instead

$$ S = \{x_1 < x_2, x_1 < x_3 \}, $$

there are now 2 possible actual orderings, $x_1 < x_2 < x_3$ and $x_1 < x_3 < x_2$.

I noticed that these partial orderings can be represented by directed acyclic graphs. I then thought that there would be a fairly simple combinatorial approach to counting the total orderings possible satisfying one of these DAGs (in a sense, the DAG constrains the set of all possible orderings). However I kept running into special cases where any algorithm I came up with would break down.

$\endgroup$
3
$\begingroup$

This is the problem of counting linear extensions.

The short answer is that there's no polynomial-time algorithm unless P=NP, and in fact under a weaker assumption. A recent paper studying this problem is https://www.ijcai.org/proceedings/2017/74 - it has a good introduction and references.

$\endgroup$
  • $\begingroup$ Not only did this answer my question, but that paper is exactly the sort of further thing I was looking for. $\endgroup$ – rwolst Oct 18 '17 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.