The Preisach graph and longest increasing subsequences
From MaRDI portal
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.
Recommendations
Cites work
- A variational problem for random Young tableaux
- An extension of Schensted's theorem
- Commentary on ``Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem by David Aldous and Persi Diaconis
- Discrete orthogonal polynomial ensembles and the Plancherel measure
- Hammersley's interacting particle process and longest increasing subsequences
- scientific article; zbMATH DE number 1191614 (Why is no real title available?)
- scientific article; zbMATH DE number 3630761 (Why is no real title available?)
- Hysteresis and phase transitions
- Level-spacing distributions and the Airy kernel
- Longest Increasing and Decreasing Subsequences
- Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
- On the distribution of the length of the longest increasing subsequence of random permutations
- Permutations, matrices, and generalized Young tableaux
- Realization of arbitrary hysteresis by a low-dimensional gradient flow
- The longest increasing subsequence in a random permutation and a unitary random matrix model
- The structure of state transition graphs in systems with return point memory. I. General theory
Cited in
(2)
This page was built for publication: The Preisach graph and longest increasing subsequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2693181)
