partial DAG and number of linear orders

Question

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$.

Answer 1

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.

Answer 2

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.