Permutation graphs and the weak Bruhat order

Authors

DOI:

https://doi.org/10.26493/2590-9770.1536.8db

Keywords:

Permutation, inversion, partially ordered set (poset), permutation graph, 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.

Published

2023-02-27

Issue

Section

Articles