Problem 1648

Let's call a simple graph good, if we can assign a direction to the edges such that for any two vertices $v, u$ with $v \to u$, if there's a vertex $w$ with $u \to w$, then there is necessarily a directed edge from $v$ to $w$.
Lemma. A graph is divisibility if and only if it's a good graph.
*Proof.*
* Let $G$ be a divisibility graph and let $n(v)$ denote the number written on vertex $v$. For any pair of vertices like $(v, u)$ where there's an edge between $v$ and $u$, we direct the edge from $v$ to $u$ if $n(v) \mid n(u)$ and otherwise, we direct the edge from $u$ to $v$. Now if for any three vertices $u, v, w$ we have $u \to v, v \to w$, it means $n(u) \mid n(v) \mid n(w)$, thus $n(u) \mid n(w)$ which means $u \to w$, so $G$ is a good graph.

* Let $G$ be a good graph with $n$ vertices. Using induction on $n$, we'll show that $G$ is a divisibility graph. For $n = 1$ the claim is obvious. Now assume the claim for $n = k - 1$. Now consider a good graph with $n = k$ vertices. Note that a good graph cannot have a cycle. Because a cycle $v_1 \to v_2 \to \dots \to v_t \to v_1$, means $v_1 \to v_t$ is also an edge of the directed graph. So the graph is not a simple graph, which is a contradiction. Thus, there is no cycle in $G$. Let $v$ be a vertex of $G$ with in-degree of zero (such vertex exists since $G$ does not have a cycle). The graph $G - \{v\}$ is a good graph with $k-1$ vertices, so by induction, it is also a divisibility graph where $n(u)$ is the number associated with vertex $u$. Now set $n(v) = p$ such that for all $u \in G - \{v\}$ we have $p \nmid n(u)$. Now change the numbers written on the vertices of $G - \{v\}$ in a way that for any vertex $u \neq v$ where $v \to u$, the new associated number is $n'(u) = p \cdot n(u)$. Now $G$ with given numbers is easily shown to be a divisibility graph.

So in order to solve the problem, we need to show that a graph is a permutation graph if and only if itself and its complement are good graphs. Let $G$ be a permutation graph. Let $(v, u)$ be an edge of this graph where $v, u$ are labeled by $i, j$. We direct the edge from $v$ to $u$ if $i < j, \pi(j) < \pi(i)$. It is easy to see that this directed version of $G$ implies $G$ is a good graph. Now for the complement of $G$, call it $\bar{G}$, for any two numbers $i, j$ labeled on vertices $v, u$, we direct an edge from $v$ to $u$ if $i < j, \pi(i) < \pi(j)$. Again, it is quite simple to see that by this directed version of $\bar{G}$, we can conclude that $\bar{G}$ is also a good graph. Now for the other part, we need another lemma.

Lemma. Let $G$ be a graph with $n$ vertices such that both $G$ and its complement, $\bar{G}$, are good graphs. Label the vertices of these graphs by $1, 2, \dots, n$. Then there is an arrangement of the vertices, such that in both $G$ and $\bar{G}$, all vertices are towards the same direction. (Meaning if vertices are respectively labeled as $v_1, \dots, v_n$, for any $i, j$ where $v_i \to v_j$, we have $i < j$.)
*Proof.* Let $G$ be a graph as described. Since $G$ does not contain a cycle, then it is possible to arrange the vertices in a way that all edges are towards the same direction. Of all valid directed versions of $G$, consider the one such that of all the valid directions of $\bar{G}$, the directed version of $\bar{G}$ has the minimum number of edges towards the opposite direction of the ones in $G$. We will prove that this minimum number is zero. Assume the contrary, that even considering a direction version of $\bar{G}$ with minimum number of backward edges, there is still a backward edge. Let's focus on graph $\bar{G}$. Consider an edge where the distance between its vertices is minimal. Let this edge be $v_k \to v_t$. We claim that $v_k, v_t$ are adjacent vertices, otherwise there's a vertex $v_s$ that $v_s \not\to v_t$ and $v_k \not\to v_s$.
$$\left. \begin{array}{l} \text{if } v_t \to v_s \\ v_k \to v_t \end{array} \right\} \bar{G} \text{ is good} \implies v_k \to v_s \\ \left. \begin{array}{l} \text{if } v_s \to v_k \\ v_k \to v_t \end{array} \right\} \bar{G} \text{ is good} \implies v_s \to v_t$$
Both conclusions are impossible, therefore $v_t \not\to v_s, v_s \not\to v_k$, which means in $G$ we must have $v_t \to v_s, v_s \to v_k$, and since $G$ is good, $v_t \to v_k$. Which means in $\bar{G}$ we cannot have an edge between $v_t, v_k$, a contradiction. So $v_k, v_t$ must be adjacent vertices. Since there is no edge between $v_k, v_t$ in $G$, switching their position will not cause any difference to the way we directed the $G$, that all edges are towards the same direction. But, it reduces the number of edges in $\bar{G}$ that are facing backwards by at least one, a contradiction, since we considered a direction of $\bar{G}$ where it has the minimum number of such edges. Hence the lemma.

Now using the latest lemma, consider an arrangement of the vertices such that any edge of both $G, \bar{G}$ are towards the same direction, meaning if $v_i \to v_j$, then $i < j$. Now consider a permutation $\pi$ where $\pi(i) = i - 1 + d^+(v_i) - d^-(v_i) \ge 0$ where $d^+(v), d^-(v)$ are out-degree and in-degree of vertex $v$ respectively. Now we will show that $G$ is a permutation graph, using the permutation $\pi$ as described. We need to show that for any two indices $i < j$, we have $v_i \to v_j$ if and only if $\pi(i) > \pi(j)$. First assume that $v_i \to v_j$. Define the sets $A, B, C$ as
$$\begin{align*} A &:= \{v_k \mid k < i, v_k \to v_i\} \\ B &:= \{v_k \mid i < k < j, v_i \not\to v_k\} \\ C &:= \{v_k \mid j < k, v_i \not\to v_k\} \end{align*}$$
Since both $G, \bar{G}$ are good, we have
$$\begin{align*} \forall v_k \in A : v_k \to v_i \to v_j &\implies v_k \to v_j \\ \forall v_k \in B : v_i \not\to v_k, v_i \to v_j &\implies v_k \to v_j \\ \forall v_k \in C : v_i \not\to v_k, v_i \to v_j &\implies v_j \not\to v_k \end{align*}$$
(The second and third lines are concluded because otherwise, considering $\bar{G}$, we would have $v_i \not\to v_j$.) So we have
$$\left\{ \begin{array}{l} d^-(v_j) \ge |A| + |B| + 1 = d^-(v_i) + |B| + 1 \\ d^+(v_i) \ge d^+(v_j) + ((j - i - 1) - |B|) + 1 \\ \qquad j > i \end{array} \right.$$
$$\begin{aligned} & \implies \pi(i) - \pi(j) \\ &= (i-j) + (d^{+}(v_i) - d^{+}(v_j)) + (d^{-}(v_j) - d^{-}(v_i)) \\ & \geq (i-j) + ((j-i) - |B|) + (|B| + 1) = 1 > 0. \end{aligned}$$
Now if $v_i \not\to v_j$, define these following sets
$$\begin{aligned} D &:= \{v_k \mid k < i, v_k \not\to v_i\} \\ E &:= \{v_k \mid i < k < j, v_i \to v_k\} \\ F &:= \{v_k \mid j < k, v_i \to v_k\} \end{aligned}$$
Again, we have
$$\begin{aligned} \forall v_k \in D : v_k \not\to v_i \not\to v_j &\implies v_k \not\to v_j \\ \forall v_k \in E : v_i \to v_k, v_i \not\to v_j &\implies v_k \not\to v_j \\ \forall v_k \in F : v_i \not\to v_j, v_i \not\to v_k &\implies v_j \to v_k \end{aligned}$$
So we conclude
$$\left\{ \begin{array}{l} d^{+}(v_i) = |E| + |F| \\ d^{+}(v_j) \ge |F| \\ d^{-}(v_j) \le ((i-1) - |D|) + ((j-i-1) - |E|) \\ d^{-}(v_i) + |D| = i-1 \\ j > i \end{array} \right.$$
$$\begin{aligned} & \implies \pi(i) - \pi(j) \\ &= (i-j) + (d^{+}(v_i) - d^{+}(v_j)) + (d^{-}(v_j) - d^{-}(v_i)) \\ & \le (i-j) + (|E|) + ((j-i-1) - |E|) = -1 < 0. \end{aligned}$$
Hence, the given permutation $\pi$ leads to the conclusion that $G$ is a permutation graph. So the claim of the problem is finally deduced. ■