Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Permutations with sh ...
Conference paper

Permutations with short monotone subsequences

Dan Romik (1)
(1) Mathematical Sciences Research Institute
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2004
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Proceedings
DOI
10.46298/dmtcs.3421
License
https://about.hal.science/hal-authorisation-v1
Indicators
651
Views
502
Downloads

Permutations with short monotone subsequences

Dan Romik (1)
(1) Mathematical Sciences Research Institute
Abstract
We consider permutations of $1,2,...,n^2$ whose longest monotone subsequence is of length $n$ and are therefore extremal for the Erdős-Szekeres Theorem. Such permutations correspond via the Robinson-Schensted correspondence to pairs of square $n \times n$ Young tableaux. We show that all the bumping sequences are constant and therefore these permutations have a simple description in terms of the pair of square tableaux. We deduce a limit shape result for the plot of values of the typical such permutation, which in particular implies that the first value taken by such a permutation is with high probability $(1+o(1))n^2/2$.
Keywords
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • Robinson-Schensted correspondence
  • Erdős-Szekeres theorem
  • limit shape
Cited by

Source: OpenCitations

  • Saturation problems in the Ramsey theory of graphs, posets and point sets

    arXiv (Cornell University)

    Authors : Gábor Damásdi ORCID, Balázs Keszegh ORCID, David Malec ORCID, Casey Tompkins ORCID, Zhiyu Wang ORCID, Oscar Zamora ORCID

    Journal reference : Volume 95, 2021, pp. 103321

    DOI : 10.1016/j.ejc.2021.103321

  • On increasing subsequences of minimal Erdös-Szekeres permutations

    Acta Mathematica Sinica English Series

    Authors : Zhong Gen Su ORCID

    Journal reference : Volume 27, 2011, pp. 1573-1580

    DOI : 10.1007/s10114-011-8653-6

  • Large Deviation Principle for Random Permutations

    International Mathematics Research Notices

    Authors : Jacopo Borga ORCID, Sayan Das ORCID, Sumit Mukherjee ORCID, Peter Winkler ORCID

    Journal reference : Volume 2024, 2023, pp. 2138-2191

    DOI : 10.1093/imrn/rnad096

  • The feasible region for consecutive patterns of permutations is a cycle polytope

    Algebraic Combinatorics

    Authors : Jacopo Borga ORCID, Raul Penaguiao ORCID

    Journal reference : Volume 3, 2020, pp. 1259-1281

    DOI : 10.5802/alco.135

  • A determinantal point process approach to scaling and local limits of random Young tableaux

    Authors : Jacopo Borga ORCID, Cédric Boutillier ORCID, Valentin Féray ORCID, Pierre-Loïc Méliot

    Journal reference : Volume 53, 2025, pp.

    DOI : 10.1214/24-aop1706

  • The skew Brownian permuton: A new universality class for random constrained permutations

    Proceedings of the London Mathematical Society

    Authors : Jacopo Borga ORCID

    Journal reference : Volume 126, 2023, pp. 1842-1883

    DOI : 10.1112/plms.12519

  • Erdős–Szekeres theorem for cyclic permutations

    Involve a Journal of Mathematics

    Authors : Éva Czabarka, Zhiyu Wang

    Journal reference : Volume 12, 2018, pp. 351-360

    DOI : 10.2140/involve.2019.12.351

  • Baxter permuton and Liouville quantum gravity

    Probability Theory and Related Fields

    Authors : Jacopo Borga ORCID, Nina Holden, Xin Sun ORCID, Pu Yu ORCID

    Journal reference : Volume 186, 2023, pp. 1225-1273

    DOI : 10.1007/s00440-023-01193-w

  • Second Class Particles and Limit Shapes of Evacuation and Sliding Paths for Random Tableaux

    FIZ-Karlsruhe (eLiBM)

    Authors : Maślanka, Śniady

    Journal reference : Volume , 2022, pp.

    DOI : 10.25537/dm.2022v27.2183-2273
Preview
Loading PDF preview...