I was wondering if there was a necessary and sufficient condition such that we can give an orientation to a simple connected graph so that it represents a partial order.
More precisely, the directed graph must have the following properties :
For any $a$, $b$, $c$ vertices of the directed graph :
- If there is an directed edge from $a$ to $b$, and from $b$ to $c$, then there is an directed edge from $a$ to $c$.
- If there is an directed edge from $a$ to $b$, there is no directed edge from $b$ to $a$.
- There is no directed edge from $a$ to $a$.
Because we begin with a simple graph, the conditions 2 and 3 are always respected, no matter what orientation of the graph we choose.
We can easily find some graphs such that no orientation gives a partial order. For example, we can see directly that a cycle of odd length and greater than $3$ has no such orientation, and so that if there is an embedding of a such cycle in a graph, this graph has no such orientation.
But it’s not the only examples, because we have also this one :
Because the node 3 is connected to the node 2, but not to the node 1 and the node 5, although the node 2 is connected to the node 1 and the node 5, all the directed edges which contains 2 must either go from 2 to the others, or from the others to 2. We can do the same reasoning for 1 and for 5. But we can’t assure that property for 1, 2 and 5 at the same time, therefore we can’t find the wanted orientation. If we add edges between the nodes 3, 4 and 6, it stays impossible.
There is a simple sufficient condition, such that a graph has the wanted orientation. If the graph contains no odd cycle, it is bipartite, with subsets $U$ and $V$. We define that all edges between $U$ and $V$ are directed from $U$ to $V$, and so the property 1 is respected. But this condition is not necessary : a cycle of length $3$ is orientable in a partial order. Moreover, any complete graph is orientable in a partial order : for $K_n$, we enumarate the vertices, and we set that the edge between $a$ and $b$, with $a < b$, goes from $a$ to $b$. If an edge goes from $a$ to $b$ and an other edge from $b$ to $c$, we have directly that there is an edge from $a$ to $c$.
Is there a necessary and sufficient condition on the graph, which assures that it is orientable in a partial order ?