A simple graph is called "divisibility", if it's possible to put distinct numbers on its vertices such that there is an edge between two vertices if and only if number of one of its vertices is divisible by another one. A simple graph is called "permutationary", if it's possible to put numbers $1,2,...,n$ on its vertices and there is a permutation $ \pi $ such that there is an edge between vertices $i,j$ if and only if $i>j$ and $\pi(i)< \pi(j)$ (it's not directed!) Prove that a simple graph is permutationary if and only if its complement and itself are divisibility. Proposed by Morteza Saghafian .
Problem
Source: Iranian TST 2018, first exam day 2, problem 6
Tags: combinatorics, graph theory
08.04.2018 22:02
Say a finite simple graph $G$ is skeletal if there is a partial order $\leqslant$ on the vertices of $G$ with an edge between $v_1$ and $v_2$ iff $v_1$ and $v_2$ are comparable. (That is, if $v_1\leqslant v_2$ or $v_2\leqslant v_1$). Claim: All skeletal graphs are "divisibility" and visa versa. Proof: Well-known, see, for example, this post $\Box$ Now, consider some permutation $\pi:\{1,2,\dots,n\}\to\{1,2,\dots,n\}$. Observe that the relations $i<_{*} j\iff i<j\text{ and }\pi(i)<\pi(j)$ and $i<^{*} j\iff i<j\text{ and }\pi(i)>\pi(j)$ over the elements of $\{1,2,\dots,n\}$ both give rise to partial orders on said set. It follows that if a graph $G$ is "permutationary", then both $G$ and $\overline{G}$ are skeletal, and are thus both "divisibility." Alternatively, suppose there is some $G$ for which both $G$ and $\overline{G}$ are "divisibility" (and thus one for which both of the aforementioned graphs are skeletal). By definition we have partial orders $\leqslant_{*},\leqslant^{*}$ (irrespectively) over the vertices of $G$ such that for any two vertices $v_1,v_2$, exactly one of $$v_1\leqslant_{*} v_2\text{ or }v_2\leqslant_{*} v_1$$And $$v_1\leqslant^{*} v_2\text{ or }v_2\leqslant^{*} v_1$$Holds. In particular, we may define a total order $\leq$ on the set of vertices of $G$ by simply "combining" the data of $\leqslant_{*}$ and $\leqslant^{*}$. (One may show that no "contradictions" can possibly arise as we define our relations.) Identify the vertices of $G$ with the elements of $\{1,2,\dots,n\}$ in accordance with $\leq$. Now let $S_0=\{1,2,\dots,n\}$, and construct the permutation $\pi:\{1,2,\dots,n\}\to\{1,2,\dots,n\}$ inductively as follows: Define $\pi(i)$ to be the $k^{\text{th}}$ smallest element of $S_{i-1}$ where $k=1+|\{i\in \{1,2,\dots,n\}:1<^{*}i\}|$ and $S_i=S_{i}\setminus\{\pi(i)\}$, iterating the algorithm until $S_n=\emptyset$ is reached. It can be shown that $G$ is the "permutation" graph corresponding to $\pi$, as desired $\blacksquare$
18.03.2019 16:26
This problem appeared as Lemma $3.51$ and Theorem $3.6$ ($(1) \Leftrightarrow (3)$) in B.Dushnik and E.W.Miller's article Partially order sets in 1941. Let me summarize the key points below: (the red words "check" remind us that we omit the details) $1).$ Definition: A finite simple graph $G$ is called a "partial order" graph if there exists a partial order $\preceq$ on $V(G)$ such that for any two distinct vertices $v,v'$, we have $vv' \in E(G)$ if and only if $v$ and $v'$ are comparable in $\preceq$ (i.e. $v \preceq v'$ or $ v' \preceq v$). (as rafayaashary1's definition "skeletal". by the way, literally we should call $G$ a "partial orderable" graph and call $(G,\preceq)$ a "partial ordered" graph) $2)$ Easy Fact 1: a simple graph $G$ is a "divisibility" graph if and only if it is a "partial order" graph. $3)$ Easy Fact 2: if $G$ is a "permutationary" graph with the permutation $\pi$ and $V(G) = \{1,2,\cdots,n\}$. We define two relations $\preceq_1$ and $\preceq_2$ as $$i \preceq_1 j \text{\quad if and only if \quad } i \leq j \text{\quad and \quad } \pi(i) \geq \pi(j)$$$$i \preceq_2 j \text{\quad if and only if \quad } i \leq j \text{\quad and \quad } \pi(i) \leq \pi(j)$$then it can be checked that both $(G, \preceq_1)$ and $(\overline{G}, \preceq_2)$ are "partial order" graphs. So $G$ is a "permutationary" graph $\Rightarrow$ both $G$ and $\overline{G}$ are "partial order" graphs. $4)$ Easy But Trivial Fact If $(G, \preceq_1)$ and $(\overline{G}, \preceq_2)$ are both "partial order" graph. Define two relations $\preceq$ and $\preceq'$ as follows, for any two distinct vertices $v,v' \in V(G)$, $$v \preceq v' \text{\quad if and only if \quad } (v \preceq_1 v' \text{\quad or \quad } v \preceq_2 v')$$$$v \preceq' v' \text{\quad if and only if \quad } (v \preceq_1 v' \text{\quad or \quad } v' \preceq_2 v)$$Then both $\preceq$ and $\preceq'$ are total orders. (This is the lemma 3.51, it need some work to check the transitivity and they are indeed total orders.) Now, since $\preceq$ is a total order, we can lable $V(G)$ as $$v_1 \prec v_2 \cdots \prec v_n.$$Since $\preceq'$ is another total order, we can list vertices in another way, i.e. there exists a permutation $\pi$ on $\{ 1,2,\cdots,n \}$ such that $$v_{\pi^{-1}(n)} \prec' v_{\pi^{-1}(n-1)} \prec' \cdots \prec' v_{\pi^{-1}(1)}.$$We can check that $(G,\pi)$ is a "permutationary" graph. So $G$ and $\overline{G}$ are both "partial order" graph $\Rightarrow$ $G$ is a "permutationary" graph. (This is theorem 3.61 presented in our terminology.) A personal note: I discussed this problem with teachers and students at Xuejun High School in September, 2018.
18.08.2020 20:41
Quite a nice problem! First, suppose the graph is permutationary, and suppose the permutation is given by $\pi$. We can label the vertex $i$ by $2^i 3^{n-\pi(i)}$ to show that the graph is divisibility, and we can label by $2^i 3^{\pi(i)}$ to show that the complement of the graph is divisibility. Now, we show that if the graph $G$ and its complement are divisibility, then it is permutationary. Fix the labelings of $G$ and its complement with distinct positive integers satisfying the divisibility conditions. Let $T$ be a tournament on the vertex set of $G$ defined as follows: draw $i\to j$ if the label of $i$ divides the label of $j$ in either $G$ or the complement, depending on which one contains the edge $ij$. The main claim is as follows. Claim: The tournament $T$ is acylic. Proof: Label the edge $i\to j$ red if it is in $G$, and black otherwise. Suppose for sake of contradiction that $T$ had a (directed) cycle. Consider a cycle of minimal length. Note that if the cycle has two consecutive edge of the same color, say $a\to b$ and $b\to c$, then we must also have the edge $a\to c$. This makes the cycle shorter, which contradicts minimality. Thus, the cycle alternates red and black. Consider a portion of the cycle $z\to a\to b\to c\to d$, where $za$ is black, $ab$ is red, $bc$ is black, and $cd$ is red. Now, we must have $a\to c$, otherwise we get a smaller cycle. If $ac$ is red, then we get $a\to d$ which makes the cycle shorter, and if it is black, then we get $z\to c$, which makes the cycle shorter. Thus, in all cases, the cycle can be made shorter, which is the desired contradiction. $\blacksquare$ Thus, we can assign each vertex of $T$ a label from $1$ through $n$ such that $i\to j$ if and only if $i<j$. Now, change the original divisibility labeling of $G$ from $x$ to $N/x$ where $N$ is the lcm of all the labels. This switches all the red arrows in $G$, but the claim still holds. Consider the similar labeling of the vertices using $1$ through $n$. Let the label of the vertex originally labeled $i$ be $\pi(i)$. It is easy to see that $\pi$ has an inversion $ij$ if and only if $ij$ is an edge in $G$, so we're done.
20.02.2021 02:26
20.02.2021 04:35
good job