Permutation graphs and the weak Bruhat order

Abstract

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.