PreprintCC BY 4.0arXiv
Caged subsequences in permutations
Abstract
Given a sequence a:=(a1,…,an) of reals, a subsequence b=(ai1,…,aik) is said to be "caged" if the largest and smallest among the members of b are ai1 and aik, though not necessarily in that order. In this paper, we consider the problem of maximal caged sequences in permutations π∈ Sn. We also consider the same problem for a random permutation, both when the permutation is chosen uniformly at random and also when it is picked uniformly at random from among the permutations of rectangular shape, via the RSK correspondence. We also give a O(nlog n) time algorithm to obtain these maximal caged sequences. In addition, we propose a randomized linear time algorithm that gives the length of the maximal caged sequence up to the factor of (1−o(1)).
Related
- Recurrences for permutations with long increasing subsequences
- The longest increasing subsequences of Luce permutations and permutons
- Quotients of L1 by subsequences of the Haar system have cotype 2
- A Non-commutative Individual Ergodic Theorem Along Sparse Random Subsequences
- Longest increasing subsequences of dyadic-type chaotic orbits
BibTeX
@misc{balachandran2026caged,
title = {{Caged subsequences in permutations}},
author = {Niranjan Balachandran and Omkar Ramdas and Umesh Shankar},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.09770},
eprint = {2608.09770},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.09770},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Caged subsequences in permutations
AU - Niranjan Balachandran
AU - Omkar Ramdas
AU - Umesh Shankar
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2608.09770
UR - https://arxiv.org/abs/2608.09770
AB - Given a sequence a:=(a_1,…,a_n) of reals, a subsequence b=(a_i_1,…,a_i_k) is said to be "caged" if the largest and smallest among the members of b are a_i_1 and a_i_k, though not necessarily in that order. In this paper, we consider the problem of maximal caged sequences in permutations π∈ S_n. We also consider the same problem for a random permutation, both when the permutation is chosen uniformly at random and also when it is picked uniformly at random from among the permutations of rectangular shape, via the RSK correspondence. We also give a O(nlog n) time algorithm to obtain these maximal caged sequences. In addition, we propose a randomized linear time algorithm that gives the length of the maximal caged sequence up to the factor of (1−o(1)).
ER -