An official website of the United States government
A box-ball system (BBS) is a discrete dynamical system consisting of n 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 n objects reaches steady state after at most n-3 BBS moves. Furthermore, we study the permutations whose soliton decompositions are standard; 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.
more »
« less
Box-ball systems and RSK tableaux
A box-ball system is a collection of discrete time states. At each state, we have a collection of countably many boxes with each integer from 1 to n assigned to a unique box; the remaining boxes are considered empty. A permutation on n objects gives a box-ball system state by assigning the permutation in one-line notation to the first n boxes. After a finite number of steps, the system will reach a so-called soliton decomposition which has an integer partition shape. We prove the following: if the soliton decomposition of a permutation is a standard Young tableau or if its shape coincides with its Robinson–Schensted (RS) partition, then its soliton decomposition and its RS insertion tableau are equal. We study the time required for a box-ball system to reach a steady state. We also generalize Fukuda’s single-carrier algorithm to algorithms with more than one carrier.
more »
« less
- Award ID(s):
- 1950543
- PAR ID:
- 10413736
- Date Published:
- Journal Name:
- Séminaire lotharingien de combinatoire
- Volume:
- 85B
- ISSN:
- 1286-4889
- Page Range / eLocation ID:
- 14
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The box-ball systems are integrable cellular automata whose long-time behavior is characterized by soliton solutions, with rich connections to other integrable systems such as the Korteweg-de Vries equation. In this paper, we consider a multicolor box-ball system with two types of random initial configurations and obtain sharp scaling limits of the soliton lengths as the system size tends to infinity. We obtain a sharp scaling limit of soliton lengths that turns out to be different from the single color case as established in [LLP20]. A large part of our analysis is devoted to studying the associated carrier process, which is a multi-dimensional Markov chain on the orthant, whose excursions and running maxima are closely related to soliton lengths. We establish the sharp scaling of its ruin probabilities, Skorokhod decomposition, strong law of large numbers, and weak diffusive scaling limit to a semimartingale reflecting Brownian motion with explicit parameters. We also establish and utilize complementary descriptions of the soliton lengths and numbers in terms of the modified Greene-Kleitman invariants for the box-ball systems and associated circular exclusion processes.more » « less
-
Abstract The box-ball systems are integrable cellular automata whose long-time behavior is characterized by soliton solutions, with rich connections to other integrable systems such as the Korteweg-de Vries equation. In this paper, we consider a multicolor box-ball system with two types of random initial configurations and obtain sharp scaling limits of the soliton lengths as the system size tends to infinity. We obtain a sharp scaling limit of soliton lengths that turns out to be more delicate than that in the single color case established in [LLP20]. A large part of our analysis is devoted to studying the associated carrier process, which is a multidimensional Markov chain on the orthant, whose excursions and running maxima are closely related to soliton lengths. We establish the sharp scaling of its ruin probabilities, Skorokhod decomposition, strong law of large numbers and weak diffusive scaling limit to a semimartingale reflecting Brownian motion with explicit parameters. We also establish and utilize complementary descriptions of the soliton lengths and numbers in terms of modified Greene-Kleitman invariants for the box-ball systems and associated circular exclusion processes.more » « less
-
For each fully commutative permutation, we construct a “boolean core,” which is the maximal boolean permutation in its principal order ideal under the right weak order. We partition the set of fully commutative permutations into the recently defined crowded and uncrowded elements, distinguished by whether or not their RSK insertion tableaux satisfy a sparsity condition. We show that a fully commutative element is uncrowded exactly when it shares the RSK insertion tableau with its boolean core. We present the dynamics of the right weak order on fully commutative permutations, with particular interest in when they change from uncrowded to crowded. In particular, we use consecutive permutation patterns and descents to characterize the minimal crowded elements under the right weak order.more » « less
-
We focus on simulation optimization algorithms that are designed to accommodate noisy black-box functions on mixed integer/continuous domains. There are several approaches used to account for noise which include aggregating multiple function replications from sample points and a newer method of aggregating single replications within a “shrinking ball.” We examine a range of algorithms, including, simulated annealing, interacting particle, covariance-matrix adaption evolutionary strategy, and particle swarm optimization to compare the effectiveness in generating optimal solutions using averaged function replications versus a shrinking ball approximation. We explore problems in mixed integer/continuous domains. Six test functions are examined with 10 and 20 dimensions, with integer restrictions enforced on 0%, 50%, and 100% of the dimensions, and with noise ranging from 10% to 20% of function output. This study demonstrates the relative effectiveness of using the shrinking ball approach, demonstrating that its use typically enhances solver performance for the tested optimization methods.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
