95-403 Timo Seppalainen
A Microscopic Model for the Burgers Equation and Longest Increasing Subsequences (127K, AMS-TeX) Sep 1, 95
Abstract , Paper (src), View paper (auto. generated ps), Index of related papers

Abstract. We introduce an interacting random process related to Ulam's problem, or finding the limit of the normalized longest increasing subsequence of a random permutation. The process describes the evolution of a configuration of sticks on the sites of the one-dimensional integer lattice. Our main result is a hydrodynamic scaling limit: The empirical stick profile converges to a weak solution of the inviscid Burgers equation under a scaling of lattice space and time. The stick process is an alternative view of Hammersley's particle system recently used by Aldous and Diaconis to give a new solution to Ulam's problem. Along the way to the scaling limit we also produce a solution to this question. The heart of the proof is that individual paths of the stochastic process evolve under a semigroup action which under the scaling turns into the corresponding action for the Burgers equation. This semigroup action for nonlinear scalar conservation laws in one space variable is developed in a separate appendix, where we give an existence result and a uniqueness criterion for solutions of such equations with initial data given by a Radon measure.

Files: 95-403.tex