0
$\begingroup$

Let $>$ be a linear order relation over a set $A$. Consider the graph $G$ that represent the transitive closure of $>$. Obviously $G$ is directed and acyclic. Given a set of edges $(e_1,e_2,\dots,e_n)$ from $G$, What is the number of linear orders that agrees with the edges?

A linear order $>'$ agrees with edge $e_i=(x,y)$ if $x>' y\iff x>y$.

$\endgroup$
1
$\begingroup$

It depends very heavily on the set of edges chosen. Suppose that $A=[n+1]$, and $\le$ is the usual order.

  • If $e_k=\langle k,k+1\rangle$ for $k\in[n]$, then $\le$ is the only linear order compatible with $\{e_k:k\in[n]\}$.
  • If $e_k=\langle k,n+1\rangle$ for $k\in[n]$, then the only restriction that $\{e_k:k\in[n]\}$ imposes on a linear order on $A$ is that $n+1$ must be its largest element, so there are $n!$ compatible linear orders.
| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

It is in general #P-complete to count the linear extensions of a given partially ordered set. Brightwell and Winkler (1991) give a nice survey. This more recent paper gives a Markov-chain Monte Carlo approximation algorithm.

| cite | improve this answer | |
$\endgroup$

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.