Caged subsequences in permutations
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality