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
    0 references
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references