A permutation can be represented geometrically by placing it above the trivial (sorted) permutation, and drawing a line segment between the two copies of each permuted element. The intersection graph of these line segments is called a permutation graph; it has an edge for every pair of elements whose order is swapped by the permutation.
The permutation graph is bipartite (as it is in this example) exactly when the permutation that it comes from has no three elements whose ordering is reversed; that is, when it avoids the pattern 321. In this case, we can describe the permutation more succinctly with a convenient textual representation. For a permutation of n elements, look at the tops and bottoms of the line segments in each of the n positions in left to right order, and write down one of the five symbols ">", "/", "\", "<", or "|" to match the orientations of the two segment endpoints in each position. In this example, for instance, in the first position (with a 3 on top and a 1 on the bottom) both endpoints are of segments that extend rightward, matching the orientation of the top and bottom points in the symbol ">", so we would write a ">" in this position. The notation for the permutation 312479568 given in the example would be ">/<|>></<". You can recover the line segments that this string describes (and therefore also the permutation that we started with) by drawing segments that connect the top and bottom points of each vertical bar, the ith rightward-pointing endpoint on the top to the ith leftward-pointing endpoint on the bottom, and the ith leftward-pointing endpoint on the top to the ith rightward-pointing endpoint on the bottom.( Read more...Collapse )