The Preisach graph and longest increasing subsequences
Annales de l’Institut Henri Poincaré D, Tome 9 (2022) no. 4, pp. 643-657.
Le texte intégral des articles récents est réservé aux abonnés de la revue. Consultez l'article sur le site de la revue.

The Preisach graph is a directed graph associated with a permutation ρ∈𝒮 N . 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.

Accepté le :
Publié le :
DOI : 10.4171/aihpd/151
Classification : 05-XX, 82-XX
Mots-clés : Permutations, longest increasing subsequence, graphs 
@article{AIHPD_2022__9_4_643_0,
     author = {Ferrari, Patrik L. and Mungan, Muhittin and Terzi, M. Mert},
     title = {The {Preisach} graph and longest increasing subsequences},
     journal = {Annales de l{\textquoteright}Institut Henri Poincar\'e D},
     pages = {643--657},
     volume = {9},
     number = {4},
     year = {2022},
     doi = {10.4171/aihpd/151},
     mrnumber = {4525142},
     zbl = {1509.05080},
     language = {en},
     url = {http://archive.numdam.org/articles/10.4171/aihpd/151/}
}
TY  - JOUR
AU  - Ferrari, Patrik L.
AU  - Mungan, Muhittin
AU  - Terzi, M. Mert
TI  - The Preisach graph and longest increasing subsequences
JO  - Annales de l’Institut Henri Poincaré D
PY  - 2022
SP  - 643
EP  - 657
VL  - 9
IS  - 4
UR  - http://archive.numdam.org/articles/10.4171/aihpd/151/
DO  - 10.4171/aihpd/151
LA  - en
ID  - AIHPD_2022__9_4_643_0
ER  - 
%0 Journal Article
%A Ferrari, Patrik L.
%A Mungan, Muhittin
%A Terzi, M. Mert
%T The Preisach graph and longest increasing subsequences
%J Annales de l’Institut Henri Poincaré D
%D 2022
%P 643-657
%V 9
%N 4
%U http://archive.numdam.org/articles/10.4171/aihpd/151/
%R 10.4171/aihpd/151
%G en
%F AIHPD_2022__9_4_643_0
Ferrari, Patrik L.; Mungan, Muhittin; Terzi, M. Mert. The Preisach graph and longest increasing subsequences. Annales de l’Institut Henri Poincaré D, Tome 9 (2022) no. 4, pp. 643-657. doi : 10.4171/aihpd/151. http://archive.numdam.org/articles/10.4171/aihpd/151/

Cité par Sources :