Functional Graphs and Permutation Graphs¶

Definition 3.7.1 (Permutation Graph)¶

Consider a permutation \(P: p_{1}, p_{2}, p_{3}, ..., p_{n}\) of the numbers 1 to n.

Consider an \(n\)-vertex graph \(G\) whose vertices are numbered from 1 to n.

For each \(1 \le i \le n\), we draw a directed edge from \(i\) to \(p_{i}\). This graph is called a permutation graph, constructed from the permutation \(P\).

For example, consider the permutation \(P: 2, 3, 1, 5, 4, 6\). The graph below is a permutation graph for this permutation:

Theorem 3.7.2¶

Statement: The vertices of a permutation graph are partitioned into a set of cycles.

Proof: For every vertex in a permutation graph, its in-degree and out-degree are exactly one. We know that a directed graph in which the in-degree and out-degree of every vertex are equal to one is partitioned into a set of cycles (why?!)!

Theorem 3.7.3¶

Statement: If two elements in a permutation are swapped, then the number of cycles in its permutation graph changes by exactly one.

Proof: The proof of this theorem is left as an exercise for the reader.