Permutation graphs and the weak Bruhat order
Keywords:Permutation, inversion, partially ordered set (poset), permutation graph, weak Bruhat order
Permutation graphs are graphs associated with permutations where edges represent inversions. We study different classes of permutation graphs and isomorphic permutation graphs. A complete answer of a basic isomorphism question is given for trees. A connection to the majorization order for integer partitions is established, in connection with the notion of inversion vectors. Finally, we study special transitivity properties related to inversions of permutations.