For a finite poset $S=\{x_1,\cdots,x_n\}$, there are $k$ ordering relations $x_{k_0}>x_{k_1}$ ($k_0\neq k_1$) that generate all the ordering of the poset $S$. Now we want to make $(S,\geq)$ a totally ordered set that respect the $k$ ordering relations by adding new relations compatible with the $k$ existing ones. How many ways to do that exist?

Edited: What if we know all the orderings of the poset (as opposed to just the generators)? Also a formula is more appropriate than an algorithm here.

Example: $S={a,b,c,d}$. There are 2 relations $a>b$, $b>d$ that generate all relations of the poset. In order to make $S$ a totally ordered set there are 4 ways which is determined by where to put $c$ in this example.

Another idea to think about this is...how many ways we have to order $n$ elements when some elements must be before others while any pair of adjacent elements unrestricted by ordering relations commute. Then how many ways can we order the $n$ elements?

  • 2
    $\begingroup$ I think, if in your example you were instead given the relations $a>b$ and $a>d$, there would be 8 ways. So its impossible to say from $n$ and $k$ alone. $\endgroup$ – Achilles Aug 6 '15 at 21:40
  • $\begingroup$ I know...perhaps I should add a stronger condition, namely all the orderings that have to be respected is known.. $\endgroup$ – Ying Zhou Aug 6 '15 at 21:44

Your second question, counting the number of linear (total) ordering extensions of a given partially ordered set, is #P-hard, meaning that probably no fast (polynomial time) algorithm exists to do it, in terms of the input size (which is $O(\log^2 n)$ if you have $n$ elements to order). However there are some heuristic approaches available online in software form to do this, you can look up "enumerating linear extensions of posets." Your first question is ill-posed as pointed out by a comment, because the number of elements and the number of ordering relations does not determine the number of total linear ordering extensions, even if you assume your initial set of ordering relations is in minimal presentation, i.e. no relations are redundant.

  • $\begingroup$ Thank you very much! Well I mentioned all these generating relations (as opposed to just the number of them). Also it is better to have a formula than an algorithm here.. $\endgroup$ – Ying Zhou Aug 6 '15 at 22:26
  • 1
    $\begingroup$ @YingZhou The fact that the counting problem is #P-hard means that if you DID have some formula for counting linear extensions that could be computed in a reasonable (polynomial) amount of time in terms of the length of the initial set of ordering relations input, then all arbitrary #P problems could be solved much faster than previously believed, and you (or whoever else gave you the answer) would be famous for showing it. Any computeable formula you get will most likely be way too complicated to evaluate in all but the simplest of cases and harder than polynomial time to evaluate in general. $\endgroup$ – user2566092 Aug 6 '15 at 22:48

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.