Geodesic
The Preisach graph and longest increasing subsequences
Annales de l’Institut Henri Poincaré D, Tome 9 (2022) no. 4, pp. 643-657.

Voir la notice de l'article provenant de la source Numdam

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
Keywords: 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/articles/10.4171/aihpd/151/

Cité par Sources :