Recursive Record Filtering and Longest Decreasing Subsequences

Jackson Zariski; Kaitlin Kratter

arxiv: 2604.23825 · v1 · submitted 2026-04-26 · 🧮 math.CO · math.PR

Recursive Record Filtering and Longest Decreasing Subsequences

Jackson Zariski , Kaitlin Kratter This is my paper

Pith reviewed 2026-05-08 05:42 UTC · model grok-4.3

classification 🧮 math.CO math.PR

keywords disappear-sortlongest decreasing subsequencepermutationsplancherel measureyoung diagramstracy-widom lawrecord filtering

0 comments

The pith

The number of passes in recursive record filtering on a sequence equals the length of its longest decreasing subsequence.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies a recursive record-filtering procedure called Disappear-Sort, in which each pass keeps only the left-to-right records and recurses on the remaining entries until nothing is left. For the non-resampling version applied to a permutation, the procedure's layers form an antichain decomposition of a natural poset on the permutation, so the total passes required equal the length of the longest decreasing subsequence. This identification shows that the expected number of passes for a uniform random permutation equals the expected length of the first column in a Plancherel-random Young diagram. The paper supplies an exact formula for this expectation via the Robinson-Schensted correspondence and then invokes classical Plancherel asymptotics to obtain the growth rate 2 sqrt(n) together with n to the 1/6 Tracy-Widom fluctuations.

Core claim

For any permutation p_n the recursive Disappear-Sort procedure produces layers that constitute an antichain decomposition of the associated poset, hence the number of passes equals L(p_n), the length of the longest decreasing subsequence. When p_n is drawn uniformly at random, the expectation of this quantity coincides with the expected first-column length of the Plancherel-random Young diagram; the Robinson-Schensted correspondence then yields an exact expression in terms of partitions and standard Young tableaux, from which the asymptotics E[D_n] ~ 2 sqrt(n) and Tracy-Widom fluctuations on the n^{1/6} scale follow directly.

What carries the argument

The recursive Disappear-Sort procedure, which retains the left-to-right records of the current sequence in each pass and recurses on the discarded entries.

If this is right

For every permutation the number of Disappear-Sort passes equals its longest decreasing subsequence length.
The expected passes for a uniform random permutation equals the expected first-column length of a Plancherel Young diagram.
An exact formula for the expectation is obtained by summing over partitions weighted by the number of standard Young tableaux.
The expectation grows asymptotically as 2 sqrt(n) with fluctuations of scale n^{1/6} governed by the Tracy-Widom law.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The O(n log n) implementation supplies an efficient algorithm for computing longest decreasing subsequence lengths.
The equivalence may allow other asymptotic properties of Plancherel Young diagrams to be transferred to record-filtering statistics on random sequences.
The same layer decomposition might apply to variants of the procedure on other partial orders.

Load-bearing premise

The layers produced by repeated record filtering form an antichain decomposition of the poset attached to the permutation.

What would settle it

For any explicit permutation, count the passes required by the recursive filtering procedure and compare the count directly with the length of its longest decreasing subsequence.

Figures

Figures reproduced from arXiv: 2604.23825 by Jackson Zariski, Kaitlin Kratter.

**Figure 1.** Figure 1: A Monte Carlo simulation to visualize the exact recurrence fo view at source ↗

**Figure 2.** Figure 2: An example standard Young tableau of shape (3 view at source ↗

**Figure 3.** Figure 3: A Monte Carlo simulation to visualize the exact formula for th view at source ↗

read the original abstract

We consider a recursive record-filtering procedure, which we informally call Disappear-Sort. Let $D_n$ denote the random variable giving the required number of passes in Disappear-Sort to eliminate a sequence of length $n$ sampled as i.i.d. copies of a continuous random variable $X$, where each pass retains the left-to-right records and discards all remaining entries. We show that this procedure admits two natural probabilistic interpretations. For the resampling variant we prove that $d_n=\mathbb{E}[D_n]$ satisfies an exact recurrence involving the unsigned Stirling numbers of the first kind. For the non-resampling variant, we associate to a permutation $p_n\in S_n$ a natural poset and prove that the recursive Disappear-Sort layers form an antichain decomposition of this poset. We deduce that the total number of passes equals $L(p_n)$, where $L(p_n)$ is the length of the longest decreasing subsequence of $p_n$. We then show that for a uniform random permutation of size $n$, the expectation $\mathbb{E}[D_n]$ of this second variant coincides with the expected first-column length of a Plancherel-random Young diagram. Using the Robinson--Schensted correspondence, we obtain an exact formula for this expectation in terms of partitions and standard Young tableaux, and classical Plancherel asymptotics then yield $\mathbb{E}[D_n]\sim 2\sqrt{n}$, with fluctuations on the $n^{1/6}$ scale governed by the Tracy--Widom law derived by Baik, Deift and Johansson. We conclude with an $O(n\log n)$ implementation.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper introduces Disappear-Sort, a recursive record-filtering procedure whose pass count equals the longest decreasing subsequence length on permutations, then recovers the known Plancherel asymptotics as a direct consequence.

read the letter

The core contribution is the equivalence between the number of Disappear-Sort passes and LDS length. For a permutation they define a natural poset where the successive record layers form an antichain decomposition; Mirsky's theorem then forces the pass count to equal the poset height, which is exactly the LDS length. From there the expectation under uniform random permutations matches the expected first column length of a Plancherel Young diagram, and the rest follows from RSK and the Baik-Deift-Johansson limit. They also give an exact recurrence for the resampling variant using unsigned Stirling numbers of the first kind and claim an O(n log n) implementation. That combinatorial identification is new and cleanly executed. The argument relies only on standard poset facts and the classical Plancherel results, with no circularity. The resampling recurrence is a separate but straightforward counting exercise. The soft spot is that the asymptotic and fluctuation statements are not new; they are imported wholesale once the expectation is identified with λ'_1. The paper does not derive any fresh probabilistic information or improve the error terms. The poset construction itself looks routine once stated, so the main novelty sits in noticing that this particular filtering process produces the antichain layers. This is a short, self-contained note that will interest people working on algorithmic interpretations of permutation statistics or on connections between sorting procedures and Young tableaux. It is not reshaping the field, but the link is honest and the proofs use established tools without overclaiming. I would bring it to a reading group for the combinatorial step and would send it to peer review; the central claim is verifiable and the write-up is direct.

Referee Report

1 major / 3 minor

Summary. The manuscript introduces the Disappear-Sort recursive record-filtering procedure and studies the number of passes D_n required to process a length-n sequence. For the resampling variant it derives an exact recurrence for the expectation d_n in terms of unsigned Stirling numbers of the first kind. For the non-resampling variant on a permutation p_n it defines a natural poset on the entries, proves that the successive record layers form an antichain decomposition of this poset, and concludes that the number of passes equals L(p_n), the length of the longest decreasing subsequence. It then shows that for uniform random p_n the expectation E[D_n] equals the expected length of the first column of a Plancherel-random Young diagram, supplies an exact formula via the Robinson-Schensted correspondence and standard Young tableaux, and recovers the asymptotic E[D_n] ∼ 2√n together with n^{1/6}-scale Tracy-Widom fluctuations from the Baik-Deift-Johansson theorem. An O(n log n) implementation is also presented.

Significance. If the central identifications hold, the paper supplies a new algorithmic and probabilistic model for the first-column length of Plancherel-random Young diagrams, directly linking a simple record-filtering process to the length of the longest decreasing subsequence and to the RSK shape. The use of Mirsky's theorem to equate passes with poset height, followed by the symmetry of Plancherel measure and the classical BDJ asymptotics, yields a clean derivation of both exact and asymptotic results. The exact formula in terms of partitions and SYT counts and the efficient implementation are additional strengths that could facilitate further study of permutation statistics.

major comments (1)

[non-resampling variant and poset association] In the section establishing the antichain decomposition for the non-resampling variant, the argument that successive record layers partition the poset into antichains (and hence that the number of layers equals the height) should explicitly verify that each layer is an antichain under the chosen partial order; a short direct argument showing that no two elements retained in the same pass can form a decreasing pair would strengthen the application of Mirsky's theorem.

minor comments (3)

[resampling variant] The recurrence for the resampling variant is stated in terms of unsigned Stirling numbers of the first kind; including the explicit initial conditions and the first few computed values of d_n would make the recurrence easier to verify.
[implementation] The O(n log n) implementation is announced in the abstract and conclusion; the manuscript would benefit from a brief pseudocode listing or a short complexity analysis paragraph to confirm the claimed running time.
[preliminaries] Notation for the poset associated to p_n is introduced only in the non-resampling section; moving a concise definition to the preliminaries would improve readability for readers unfamiliar with the construction.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive recommendation. The suggestion to strengthen the antichain verification is well taken, and we will incorporate a short direct argument in the revised manuscript.

read point-by-point responses

Referee: In the section establishing the antichain decomposition for the non-resampling variant, the argument that successive record layers partition the poset into antichains (and hence that the number of layers equals the height) should explicitly verify that each layer is an antichain under the chosen partial order; a short direct argument showing that no two elements retained in the same pass can form a decreasing pair would strengthen the application of Mirsky's theorem.

Authors: We agree that an explicit verification strengthens the exposition. In the revised version we will insert a short direct argument immediately after defining the poset: suppose two entries a and b are retained in the same pass. By construction of the left-to-right record filter, the later of the two cannot be smaller than the earlier one (otherwise the later entry would have been discarded as non-record). Hence a and b are incomparable in the poset, confirming that each layer is an antichain. This makes the appeal to Mirsky's theorem fully explicit while preserving the existing proof structure. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation uses standard theorems and independent priors

full rationale

The paper proves that Disappear-Sort passes equal the longest decreasing subsequence length by constructing an antichain decomposition of the natural poset on the permutation and invoking Mirsky's theorem (height equals minimum antichain cover). This is a direct combinatorial argument with no definitional loop. The expectation is then identified with the expected first column length of a Plancherel-random Young diagram via the Robinson-Schensted correspondence, a standard bijection. The asymptotic E[D_n] ~ 2√n with Tracy-Widom fluctuations is taken from the independent Baik-Deift-Johansson result on Plancherel measure, which is externally established and not derived from the present construction. No fitted parameters are relabeled as predictions, no self-citations are load-bearing, and no ansatz is smuggled. The chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

Relies on standard combinatorial and probabilistic axioms; the new elements are the definition of Disappear-Sort and the poset.

axioms (3)

standard math The unsigned Stirling numbers of the first kind satisfy the recurrence for the expectation in the resampling variant.
Used for the exact recurrence of d_n.
standard math Robinson-Schensted correspondence maps permutations to pairs of Young tableaux with Plancherel measure.
Central to identifying E[D_n] with first column length.
domain assumption The poset associated to the permutation has the property that Disappear-Sort layers are antichains whose number equals the longest decreasing subsequence length.
This is the key new proof in the paper.

pith-pipeline@v0.9.0 · 5594 in / 1599 out tokens · 66242 ms · 2026-05-08T05:42:09.225991+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

12 extracted references · 8 canonical work pages

[1]

A leader-election procedure using records

Gerold Alsmeyer, Zakhar Kabluchko, and Alexander Marynych. A leader-election procedure using records. The Annals of Probability , 45(6B):4348–4388, November
[2]

doi:10.1214/16-AOP1167

work page doi:10.1214/16-aop1167
[3]

On the distribution of the length of the longest increasing subsequence of random per muta- tions

Jinho Baik, Percy Deift, and Kurt Johansson. On the distribution of the length of the longest increasing subsequence of random per muta- tions. Journal of the American Mathematical Society , 12(4):1119–1178, 1999. doi:10.1090/S0894-0347-99-00307-0

work page doi:10.1090/s0894-0347-99-00307-0 1999
[4]

David and H

Herbert A. David and H. N. Nagaraja. Order Statistics. Wiley-Interscience, 3 edition,
[5]

doi:10.1002/0471722162

ISBN 978-0-471-38926-2. doi:10.1002/0471722162

work page doi:10.1002/0471722162
[6]

J. S. Frame, G. de B. Robinson, and R. M. Thrall. The hook graphs of the symmetric group. Canadian Journal of Mathematics , 6:316–324, 1954. doi:10.4153/CJM-1954-030-1

work page doi:10.4153/cjm-1954-030-1 1954
[7]

B. F. Logan and L. A. Shepp. A variational problem for random Yo ung tableaux. Advances in Mathematics , 26(2):206–222, 1977. ISSN 0001-8708. doi:10.1016/0001-8708(77)90030-5

work page doi:10.1016/0001-8708(77)90030-5 1977
[8]

L. Mirsky. A dual of Dilworth’s decomposition theorem. The American Mathematical Monthly, 78(8):876–877, 1971. doi:10.2307/2316481

work page doi:10.2307/2316481 1971
[9]

Th´ eorie des ´ el´ ements saillants d’une suite d’observations

Alfr´ ed R´ enyi. Th´ eorie des ´ el´ ements saillants d’une suite d’observations. Annales scientiﬁques de l’Universit´ e de Clermont. Math´ ematiques, 8(2):7–13, 1962. URL https://www.numdam.org/item/ASCFM_1962__8_2_7_0/

1962
[10]

G. de B. Robinson. On the representations of the symmetric gro up. American Journal of Mathematics , 60(3):745–760, 1938. doi:10.2307/2371609

work page doi:10.2307/2371609 1938
[11]

Schensted

C. Schensted. Longest increasing and decreasing subsequenc es. Canadian Journal of Mathematics, 13:179–191, 1961. doi:10.4153/CJM-1961-015-3

work page doi:10.4153/cjm-1961-015-3 1961
[12]

A. M. Vershik and S. V. Kerov. Asymptotics of the Plancherel m easure of the symmetric group and the limiting form of Young tableaux. Soviet Mathematics Doklady, 18:527–531, 1977. the electronic journal of combinatorics 30 (2023), #P00 15

1977

[1] [1]

A leader-election procedure using records

Gerold Alsmeyer, Zakhar Kabluchko, and Alexander Marynych. A leader-election procedure using records. The Annals of Probability , 45(6B):4348–4388, November

[2] [2]

doi:10.1214/16-AOP1167

work page doi:10.1214/16-aop1167

[3] [3]

On the distribution of the length of the longest increasing subsequence of random per muta- tions

Jinho Baik, Percy Deift, and Kurt Johansson. On the distribution of the length of the longest increasing subsequence of random per muta- tions. Journal of the American Mathematical Society , 12(4):1119–1178, 1999. doi:10.1090/S0894-0347-99-00307-0

work page doi:10.1090/s0894-0347-99-00307-0 1999

[4] [4]

David and H

Herbert A. David and H. N. Nagaraja. Order Statistics. Wiley-Interscience, 3 edition,

[5] [5]

doi:10.1002/0471722162

ISBN 978-0-471-38926-2. doi:10.1002/0471722162

work page doi:10.1002/0471722162

[6] [6]

J. S. Frame, G. de B. Robinson, and R. M. Thrall. The hook graphs of the symmetric group. Canadian Journal of Mathematics , 6:316–324, 1954. doi:10.4153/CJM-1954-030-1

work page doi:10.4153/cjm-1954-030-1 1954

[7] [7]

B. F. Logan and L. A. Shepp. A variational problem for random Yo ung tableaux. Advances in Mathematics , 26(2):206–222, 1977. ISSN 0001-8708. doi:10.1016/0001-8708(77)90030-5

work page doi:10.1016/0001-8708(77)90030-5 1977

[8] [8]

L. Mirsky. A dual of Dilworth’s decomposition theorem. The American Mathematical Monthly, 78(8):876–877, 1971. doi:10.2307/2316481

work page doi:10.2307/2316481 1971

[9] [9]

Th´ eorie des ´ el´ ements saillants d’une suite d’observations

Alfr´ ed R´ enyi. Th´ eorie des ´ el´ ements saillants d’une suite d’observations. Annales scientiﬁques de l’Universit´ e de Clermont. Math´ ematiques, 8(2):7–13, 1962. URL https://www.numdam.org/item/ASCFM_1962__8_2_7_0/

1962

[10] [10]

G. de B. Robinson. On the representations of the symmetric gro up. American Journal of Mathematics , 60(3):745–760, 1938. doi:10.2307/2371609

work page doi:10.2307/2371609 1938

[11] [11]

Schensted

C. Schensted. Longest increasing and decreasing subsequenc es. Canadian Journal of Mathematics, 13:179–191, 1961. doi:10.4153/CJM-1961-015-3

work page doi:10.4153/cjm-1961-015-3 1961

[12] [12]

A. M. Vershik and S. V. Kerov. Asymptotics of the Plancherel m easure of the symmetric group and the limiting form of Young tableaux. Soviet Mathematics Doklady, 18:527–531, 1977. the electronic journal of combinatorics 30 (2023), #P00 15

1977