Permutation graphs and the weak Bruhat order
DOI:
https://doi.org/10.26493/2590-9770.1536.8dbKeywords:
Permutation, inversion, partially ordered set (poset), permutation graph, weak Bruhat orderAbstract
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.