The Preisach graph and longest increasing subsequences
Patrik L. Ferrari, Muhittin Tamer Mungan, M. Mert Terzi · Annales de l’Institut Henri Poincaré D Combinatorics Physics and their Interactions · 2022
The Preisach graph is a directed graph associated with a permutation \rho\in\mathcal{S}_N . We give an explicit bijection between its vertices and increasing subsequences of \rho with the property that the length of a subsequence is equal to the degree of nesting of the corresponding vertex inside a hierarchy of cycles and sub-cycles of the graph. As a consequence, the nesting degree of the Preisach graph equals the length of the longest increasing subsequence.