The Preisach graph and longest increasing subsequences (Q2693181)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The Preisach graph and longest increasing subsequences |
scientific article |
Statements
The Preisach graph and longest increasing subsequences (English)
0 references
17 March 2023
0 references
Summary: 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.
0 references
permutations
0 references
longest increasing subsequence
0 references
0 references
0 references
0 references
0 references