|
|||||
 |
|
|
|
|
|
|
|
Box-ball
systems and RSK recording tableaux
Marisa Cofie, Olivia Fugikawa, Emily Gunawan, Madelyn Stewart and David Zeng |
|
Vol. 19 (2026), No. 3, 361–392
|
Abstract |
|
A box-ball system (BBS) is a discrete dynamical system consisting of balls in an infinite strip of boxes. During each BBS move, the balls take turns jumping to the first empty box, beginning with the smallest-numbered ball. The one-line notation of a permutation can be used to define a BBS state. This paper proves that the Robinson–Schensted (RS) recording tableau of a permutation completely determines the dynamics of the box-ball system containing the permutation. Every box-ball system eventually reaches steady state, decomposing into solitons. We prove that the rightmost soliton is equal to the first row of the RS insertion tableau and it is formed after at most one BBS move. This fact helps us compute the number of BBS moves required to form the rest of the solitons. First, we prove that if a permutation has an L-shaped soliton decomposition then it reaches steady state after at most one BBS move. Permutations with L-shaped soliton decompositions include noncrossing involutions and column reading words. Second, we make partial progress on the conjecture that every permutation on objects reaches steady state after at most BBS moves. Furthermore, we study the permutations whose soliton decompositions coincide with standard tableaux; we conjecture that they are closed under consecutive pattern containment and that the RS recording tableaux belonging to such permutations are counted by the Motzkin numbers. |
Keywords
box-ball systems, soliton cellular automata, Young
tableaux, Robinson–Schensted–Knuth correspondence, dual
Knuth equivalence, Greene's theorem, Schensted's theorem
|
Mathematical Subject Classification
Primary: 05A05, 05A17
Secondary: 37B15
|
Milestones
Received: 5 August 2023
Revised: 27 December 2024
Accepted: 15 January 2025
Published: 12 June 2026
Communicated by Jim Haglund
|
Authors |
| Marisa Cofie | |
| Department of Mathematics University of California Los Angeles, CA United States |
|
| Olivia Fugikawa | |
| Yale University New Haven, CT United States |
|
| Emily Gunawan | |
| Department of Mathematics and
Statistics University of Massachusetts Lowell, MA United States |
|
| Madelyn Stewart | |
| Yale University New Haven, CT United States |
|
| David Zeng | |
| Yale University New Haven, CT United States |
|
| © 2026 MSP (Mathematical Sciences Publishers). |
