Local extrema in random permutations and the structure of longest alternating subsequences

International audience Let $\textbf{as}_n$ denote the length of a longest alternating subsequence in a uniformly random permutation of order $n$. Stanley studied the distribution of $\textbf{as}_n$ using algebraic methods, and showed in particular that $\mathbb{E}(\textbf{as}_n) = (4n+1)/6$ and $\te...

Full description

Bibliographic Details
Main Author: Romik, Dan
Other Authors: Department of Mathematics Davis, University of California Davis (UC Davis), University of California-University of California, Bousquet-Mélou, Mireille and Wachs, Michelle and Hultman, Axel
Format: Conference Object
Language:English
Published: HAL CCSD 2011
Subjects:
Online Access:https://hal.inria.fr/hal-01215067
https://hal.inria.fr/hal-01215067/document
https://hal.inria.fr/hal-01215067/file/dmAO0172.pdf
id ftccsdartic:oai:HAL:hal-01215067v1
record_format openpolar
spelling ftccsdartic:oai:HAL:hal-01215067v1 2023-05-15T16:52:53+02:00 Local extrema in random permutations and the structure of longest alternating subsequences Romik, Dan Department of Mathematics Davis University of California Davis (UC Davis) University of California-University of California Bousquet-Mélou Mireille and Wachs Michelle and Hultman Axel Reykjavik, Iceland 2011 https://hal.inria.fr/hal-01215067 https://hal.inria.fr/hal-01215067/document https://hal.inria.fr/hal-01215067/file/dmAO0172.pdf en eng HAL CCSD Discrete Mathematics and Theoretical Computer Science DMTCS hal-01215067 https://hal.inria.fr/hal-01215067 https://hal.inria.fr/hal-01215067/document https://hal.inria.fr/hal-01215067/file/dmAO0172.pdf info:eu-repo/semantics/OpenAccess ISSN: 1462-7264 EISSN: 1365-8050 Discrete Mathematics and Theoretical Computer Science 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011) https://hal.inria.fr/hal-01215067 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.825-834 longest alternating subsequences permutation statistics random permutation [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] info:eu-repo/semantics/conferenceObject Conference papers 2011 ftccsdartic 2020-12-25T18:15:03Z International audience Let $\textbf{as}_n$ denote the length of a longest alternating subsequence in a uniformly random permutation of order $n$. Stanley studied the distribution of $\textbf{as}_n$ using algebraic methods, and showed in particular that $\mathbb{E}(\textbf{as}_n) = (4n+1)/6$ and $\textrm{Var}(\textbf{as}_n) = (32n-13)/180$. From Stanley's result it can be shown that after rescaling, $\textbf{as}_n$ converges in the limit to the Gaussian distribution. In this extended abstract we present a new approach to the study of $\textbf{as}_n$ by relating it to the sequence of local extrema of a random permutation, which is shown to form a "canonical'' longest alternating subsequence. Using this connection we reprove the abovementioned results in a more probabilistic and transparent way. We also study the distribution of the values of the local minima and maxima, and prove that in the limit the joint distribution of successive minimum-maximum pairs converges to the two-dimensional distribution whose density function is given by $f(s,t) = 3(1-s)t e^{t-s}$. Pour une permutation aléatoire d'ordre $n$, on désigne par $\textbf{as}_n$ la longueur maximale d'une de ses sous-suites alternantes. Stanley a étudié la distribution de $\textbf{as}_n$ en utilisant des méthodes algébriques, et il a démontré en particulier que $\mathbb{E}(\textbf{as}_n) = (4n+1)/6$ et $\textrm{Var}(\textbf{as}_n) = (32n-13)/180$. A partir du résultat de Stanley on peut montrer qu'après changement d'échelle, $\textbf{as}_n$ converge vers la distribution normale. Nous présentons ici une approche nouvelle pour l'étude de $\textbf{as}_n$, en la reliant à la suite des extrema locaux d'une permutation aléatoire, dont nous montrons qu'elle constitue une sous-suite alternante maximale "canonique''. En utilisant cette relation, nous prouvons à nouveau les résultats mentionnés ci-dessus d'une façon plus probabiliste et transparente. En plus, nous prouvons un résultat asymptotique sur la distribution limite des paires formées d'un minimum et d'un ... Conference Object Iceland Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe)
institution Open Polar
collection Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe)
op_collection_id ftccsdartic
language English
topic longest alternating subsequences
permutation statistics
random permutation
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
spellingShingle longest alternating subsequences
permutation statistics
random permutation
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Romik, Dan
Local extrema in random permutations and the structure of longest alternating subsequences
topic_facet longest alternating subsequences
permutation statistics
random permutation
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
description International audience Let $\textbf{as}_n$ denote the length of a longest alternating subsequence in a uniformly random permutation of order $n$. Stanley studied the distribution of $\textbf{as}_n$ using algebraic methods, and showed in particular that $\mathbb{E}(\textbf{as}_n) = (4n+1)/6$ and $\textrm{Var}(\textbf{as}_n) = (32n-13)/180$. From Stanley's result it can be shown that after rescaling, $\textbf{as}_n$ converges in the limit to the Gaussian distribution. In this extended abstract we present a new approach to the study of $\textbf{as}_n$ by relating it to the sequence of local extrema of a random permutation, which is shown to form a "canonical'' longest alternating subsequence. Using this connection we reprove the abovementioned results in a more probabilistic and transparent way. We also study the distribution of the values of the local minima and maxima, and prove that in the limit the joint distribution of successive minimum-maximum pairs converges to the two-dimensional distribution whose density function is given by $f(s,t) = 3(1-s)t e^{t-s}$. Pour une permutation aléatoire d'ordre $n$, on désigne par $\textbf{as}_n$ la longueur maximale d'une de ses sous-suites alternantes. Stanley a étudié la distribution de $\textbf{as}_n$ en utilisant des méthodes algébriques, et il a démontré en particulier que $\mathbb{E}(\textbf{as}_n) = (4n+1)/6$ et $\textrm{Var}(\textbf{as}_n) = (32n-13)/180$. A partir du résultat de Stanley on peut montrer qu'après changement d'échelle, $\textbf{as}_n$ converge vers la distribution normale. Nous présentons ici une approche nouvelle pour l'étude de $\textbf{as}_n$, en la reliant à la suite des extrema locaux d'une permutation aléatoire, dont nous montrons qu'elle constitue une sous-suite alternante maximale "canonique''. En utilisant cette relation, nous prouvons à nouveau les résultats mentionnés ci-dessus d'une façon plus probabiliste et transparente. En plus, nous prouvons un résultat asymptotique sur la distribution limite des paires formées d'un minimum et d'un ...
author2 Department of Mathematics Davis
University of California Davis (UC Davis)
University of California-University of California
Bousquet-Mélou
Mireille and Wachs
Michelle and Hultman
Axel
format Conference Object
author Romik, Dan
author_facet Romik, Dan
author_sort Romik, Dan
title Local extrema in random permutations and the structure of longest alternating subsequences
title_short Local extrema in random permutations and the structure of longest alternating subsequences
title_full Local extrema in random permutations and the structure of longest alternating subsequences
title_fullStr Local extrema in random permutations and the structure of longest alternating subsequences
title_full_unstemmed Local extrema in random permutations and the structure of longest alternating subsequences
title_sort local extrema in random permutations and the structure of longest alternating subsequences
publisher HAL CCSD
publishDate 2011
url https://hal.inria.fr/hal-01215067
https://hal.inria.fr/hal-01215067/document
https://hal.inria.fr/hal-01215067/file/dmAO0172.pdf
op_coverage Reykjavik, Iceland
genre Iceland
genre_facet Iceland
op_source ISSN: 1462-7264
EISSN: 1365-8050
Discrete Mathematics and Theoretical Computer Science
23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011)
https://hal.inria.fr/hal-01215067
23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. pp.825-834
op_relation hal-01215067
https://hal.inria.fr/hal-01215067
https://hal.inria.fr/hal-01215067/document
https://hal.inria.fr/hal-01215067/file/dmAO0172.pdf
op_rights info:eu-repo/semantics/OpenAccess
_version_ 1766043365568151552