Caged subsequences in permutations

arXiv:2608.09770 · math.CO · Submitted 2026-08-10 · Read on arXiv

math.CO

Submitted: 2026-08-10

Updated: 2026-10-29

License: http://creativecommons.org/licenses/by/4.0/

The gist: 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…

Terminology

Abstract

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 π in 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(n 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 papers