Recursive Record Filtering and Longest Decreasing Subsequences

Jackson Zariski; Kaitlin Kratter

arxiv: 2604.23825 · v2 · pith:TTEMSF66new · 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-07-01 09:14 UTC · model grok-4.3

classification 🧮 math.CO math.PR

keywords disappear-sortlongest decreasing subsequenceplancherel measureyoung diagramsrobinson-schensted correspondencetracy-widom lawrecord filteringpermutations

0 comments

The pith

Disappear-Sort on a permutation requires exactly as many passes as 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 defines Disappear-Sort as repeated passes that keep only left-to-right records and discard everything else until nothing remains. It examines the number of passes D_n both when the underlying sequence is resampled each time and when it is not. For the non-resampling case applied to a permutation, the procedure is shown to produce layers that decompose an associated poset into antichains, so the total passes equal the length of the longest decreasing subsequence. This identification makes the expected value of D_n for a uniform random permutation identical to the expected length of the first column of a Plancherel-random Young diagram. The Robinson-Schensted correspondence supplies an exact formula for this expectation, and known Plancherel asymptotics then give the growth rate 2 sqrt(n) together with n to the one-sixth Tracy-Widom fluctuations.

Core claim

For any permutation p_n the recursive Disappear-Sort procedure performs exactly L(p_n) passes, where L(p_n) denotes the length of the longest decreasing subsequence, because its successive record layers constitute an antichain decomposition of the natural poset on the permutation. Consequently the expectation E[D_n] over uniform random permutations equals the expected first-column length of a Plancherel-random Young diagram; the Robinson-Schensted correspondence yields an explicit formula for this quantity in terms of partitions and standard Young tableaux, from which the classical Plancherel limit theorems imply E[D_n] ∼ 2√n with fluctuations of scale n^{1/6} governed by the Tracy-Widom law

What carries the argument

The poset naturally associated to a permutation whose successive left-to-right record layers form an antichain decomposition whose number of layers equals the longest decreasing subsequence length.

If this is right

E[D_n] admits an exact formula as a sum over partitions and standard Young tableaux.
The resampling variant of the procedure satisfies a recurrence involving the unsigned Stirling numbers of the first kind.
The procedure admits an O(n log n) implementation.
Classical Plancherel limit theorems apply directly to give the asymptotic E[D_n] ∼ 2√n with Tracy-Widom fluctuations.

Where Pith is reading between the lines

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

The same record-filtering construction supplies a direct combinatorial model for the first-column statistic on Plancherel-random diagrams.
Variants of the filtering rule may correspond to other classical permutation statistics that also admit Plancherel interpretations.
The O(n log n) implementation gives a practical method for computing longest decreasing subsequence lengths on arbitrary sequences.

Load-bearing premise

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

What would settle it

For small n, compute the average number of Disappear-Sort passes over all n! permutations and check whether it equals the average first-column length taken over all partitions of n weighted by the square of the number of standard Young tableaux of that shape divided by n!.

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

Disappear-Sort gives a new record-filtering view that equals longest decreasing subsequence length via antichain layers, then recovers the known Plancherel first-column expectation.

read the letter

The main takeaway is that the authors introduce Disappear-Sort, a recursive left-to-right record filter, and prove that the non-resampling version requires exactly L(p_n) passes on a permutation, where L is the longest decreasing subsequence length. They do this by showing the successive layers form an antichain decomposition of a natural poset on the sequence. From there the Robinson-Schensted correspondence immediately identifies the expectation under uniform random permutations with the expected first-column length of a Plancherel-random Young diagram, so the classical 2√n asymptotic and Tracy-Widom fluctuations follow at once. They also give an exact recurrence for the resampling variant using unsigned Stirling numbers of the first kind and close with an O(n log n) implementation.

The procedure and the antichain identification are the genuinely new pieces; everything after that is a direct consequence of standard external results. The paper keeps the argument economical and does not overclaim novelty for the asymptotics.

The load-bearing step is the claim that the recursive layers are antichains and that their number equals the height of the poset. The abstract states this is proved, but that is the only place where a gap could appear. If the decomposition argument is correct, the rest is routine and the soundness is high. No circularity or invented objects show up.

The work is aimed at people who already care about permutation statistics, record processes, or probabilistic combinatorics. A reader who wants a new algorithmic or filtering interpretation of LDS length will find it useful; someone outside that circle will not miss much. The citation pattern is appropriate and leans on the right classical sources.

I would send it to peer review. The new procedure and the poset claim are concrete enough that referees can check them directly, and the paper is short enough that the review burden stays reasonable.

Referee Report

0 major / 2 minor

Summary. The paper defines Disappear-Sort, a recursive procedure that filters left-to-right records in passes until the sequence is eliminated. For the resampling variant, it derives an exact recurrence for the expected number of passes d_n using unsigned Stirling numbers of the first kind. For the non-resampling variant applied to a permutation p_n, it defines a natural poset and proves that the layers form an antichain decomposition, so that the number of passes is exactly the length L(p_n) of the longest decreasing subsequence. Consequently, for uniform random permutations, E[D_n] equals the expected length of the first column of a Plancherel-random Young diagram. An exact formula is given in terms of partitions and standard Young tableaux, and classical asymptotics yield E[D_n] ∼ 2√n with Tracy-Widom fluctuations on the n^{1/6} scale. An O(n log n) implementation is provided.

Significance. This provides a new interpretation of the Plancherel first-column length via a simple record-filtering procedure and connects it directly to longest decreasing subsequences. The exact formula and the derivation of the asymptotics from the Robinson-Schensted correspondence and Baik-Deift-Johansson results are strengths. The O(n log n) implementation is a practical contribution. The use of standard combinatorial tools is appropriately leveraged.

minor comments (2)

The abstract refers to 'the resampling variant' and 'the non-resampling variant' but the main text should clearly define these variants early on for reader clarity.
The complexity claim of O(n log n) for the implementation should include a brief justification or reference to the data structure used.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript and for recommending acceptance. We are pleased that the connections to the Plancherel measure, longest decreasing subsequences, and the O(n log n) implementation were viewed as strengths.

Circularity Check

0 steps flagged

No significant circularity; derivation relies on external theorems

full rationale

The paper proves directly that Disappear-Sort layers form an antichain decomposition of the associated poset, yielding D_n = L(p_n) by explicit argument rather than by definition or fit. It then invokes the standard Robinson-Schensted correspondence (external, not by these authors) to equate the expectation under uniform random permutations with the expected first-column length under Plancherel measure, followed by classical asymptotics. No self-citation is load-bearing, no parameter is fitted and renamed as a prediction, and no ansatz or uniqueness claim reduces to prior work by the same authors. The central identification is established by proof against an external benchmark.

Axiom & Free-Parameter Ledger

0 free parameters · 3 axioms · 0 invented entities

The paper relies on standard facts about left-to-right records in continuous i.i.d. sequences, the definition of the poset associated to a permutation, the Robinson-Schensted correspondence, and classical Plancherel asymptotics. No free parameters are introduced; no new entities are postulated.

axioms (3)

domain assumption Left-to-right records in i.i.d. continuous sequences are well-defined and the filtering process terminates after finitely many passes.
Invoked in the definition of D_n and the two variants.
domain assumption The layers produced by recursive record filtering form an antichain decomposition of the permutation poset.
Central step that equates number of passes to longest decreasing subsequence length.
standard math Robinson-Schensted correspondence maps uniform random permutations to Plancherel-random Young diagrams.
Used to equate E[D_n] with expected first-column length.

pith-pipeline@v0.9.1-grok · 5825 in / 1709 out tokens · 23204 ms · 2026-07-01T09:14:47.414271+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

12 extracted references

[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]

��
[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. ��

1999
[4]

David and H

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

��

ISBN 978-0-471-38926-2. ��
[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. ��

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. ��

1977
[8]

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

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 ��

1962
[10]

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

1938
[11]

Schensted

C. Schensted. Longest increasing and decreasing subsequenc es. Canadian Journal of Mathematics, 13:179–191, 1961. ��

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. 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]

��

[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. ��

1999

[4] [4]

David and H

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

[5] [5]

��

ISBN 978-0-471-38926-2. ��

[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. ��

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. ��

1977

[8] [8]

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

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 ��

1962

[10] [10]

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

1938

[11] [11]

Schensted

C. Schensted. Longest increasing and decreasing subsequenc es. Canadian Journal of Mathematics, 13:179–191, 1961. ��

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. 15

1977