Function Repository Resource:

PermutationGraph

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]:=
 Out[1]=

Properties and Relations (3)

GraphComplement gives the permutation graph of the reverse permutation p:

 In[2]:=
 Out[2]=
 In[3]:=
 Out[3]=
 In[4]:=
 Out[4]=
 In[5]:=
 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]:=
 Out[6]=
 In[7]:=
 Out[7]=

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

 In[8]:=
 Out[8]=
 In[9]:=
 In[10]:=
 Out[10]=

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

 In[11]:=
 Out[11]=
 In[12]:=
 Out[12]=

Version History

• 1.0.0 – 07 July 2020