The Preisach graph and longest increasing subsequences
Patrik L. Ferrari
Universität Bonn, GermanyMuhittin Mungan
Universität Bonn, GermanyM. Mert Terzi
LPTMS, CNRS, Université Paris-Saclay, Orsay, France
![The Preisach graph and longest increasing subsequences cover](/_next/image?url=https%3A%2F%2Fcontent.ems.press%2Fassets%2Fpublic%2Fimages%2Fserial-issues%2Fcover-aihpd-volume-9-issue-4.png&w=3840&q=90)
Abstract
The Preisach graph is a directed graph associated with a permutation . We give an explicit bijection between its vertices and increasing subsequences of 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.
Cite this article
Patrik L. Ferrari, Muhittin Mungan, M. Mert Terzi, The Preisach graph and longest increasing subsequences. Ann. Inst. Henri Poincaré Comb. Phys. Interact. 9 (2022), no. 4, pp. 643–657
DOI 10.4171/AIHPD/151