Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 PermutationGraph

Source Notebook

Compute the permutation graph of a permutation

Contributed by: Wolfram Staff (original content by Sriram V. Pemmaraju and Steven S. Skiena)

ResourceFunction["PermutationGraph"][p]

gives the permutation graph for the permutation p.

Details and Options

Vertices of a permutation graph represent the elements of a permutation; edges represent pairs of elements that are inversions in the permutation.
ResourceFunction["PermutationGraph"] accepts the same options as Graph.

Examples

Basic Examples (1) 

A permutation Graph of a permutation:

In[1]:=
g = ResourceFunction["PermutationGraph"][{4, 3, 5, 1, 2}, VertexLabels -> "Name"]
Out[1]=

Properties and Relations (3) 

GraphComplement gives the permutation graph of the reverse permutation p:

In[2]:=
p = RandomPermutation[7] // PermutationList
Out[2]=
In[3]:=
gr1 = GraphComplement[ ResourceFunction["PermutationGraph"][p, VertexLabels -> "Name"]]
Out[3]=
In[4]:=
gr2 = ResourceFunction["PermutationGraph"][Reverse[p], VertexLabels -> "Name"]
Out[4]=
In[5]:=
IsomorphicGraphQ[gr1, gr2]
Out[5]=

The number of inversions in a permutation can be computed by the resource function InvesionCount and is equal to the number of edges in its permutation graph:

In[6]:=
p = RandomPermutation[10] // PermutationList
Out[6]=
In[7]:=
{ResourceFunction["InversionCount"][p], EdgeCount[ResourceFunction["PermutationGraph"][p]]}
Out[7]=

Every clique in a permutation graph corresponds to a decreasing sequence in the corresponding permutation:

In[8]:=
p = RandomPermutation[10] // PermutationList
Out[8]=
In[9]:=
g = ResourceFunction["PermutationGraph"][p];
In[10]:=
Reverse /@ FindClique[g, Infinity, All]
Out[10]=

A maximum-size clique corresponds to one of the longest decreasing sequences:

In[11]:=
FindClique[g]
Out[11]=
In[12]:=
HighlightGraph[g, %, VertexSize -> Medium, VertexLabels -> "Name"]
Out[12]=

Version History

  • 1.0.0 – 07 July 2020

Related Resources

License Information