2017/06/18 by Levine, Lionel, Lyu, Hanbaek, Pike, John · 1 citation
#37K40 #60F05 #Cellular Automata and Lattice Gases (nlin.CG) #Combinatorics (math.CO) #Exactly Solvable and Integrable Systems (nlin.SI) #FOS: Mathematics #FOS: Physical sciences #Pattern Formation and Solitons (nlin.PS) #Probability (math.PR)
paper · doi:10.48550/arxiv.1706.05621
In this paper, we consider the soliton cellular automaton introduced in [Takahashi 1990] with a random initial configuration. We give multiple constructions of a Young diagram describing various statistics of the system in terms of familiar objects like birth-and-death chains and Galton-Watson forests. Using these ideas, we establish limit theorems showing that if the first n boxes are occupied independently with probability p∈(0,1), then the number of solitons is of order n for all p, and the length of the longest soliton is of order log n for p<1/2, order √(n) for p=1/2, and order n for p>1/2. Additionally, we uncover a condensation phenomenon in the supercritical regime: For each fixed j≥ 1, the top j soliton lengths have the same order as the longest for p≤ 1/2, whereas all but the longest have order at most log n for p>1/2. As an application, we obtain scaling limits for the lengths of the kth longest increasing and decreasing subsequences in a random stack-sortable permutation of length n in terms of random walks and Brownian excursions.