Perturbation theory for exactly solvable combinatorial problems
Statement
The asymptotic behavior of a variety of combinatorial problems has now been analyzed in great detail. Here we have in mind Ulam's problem for the length of the longest increasing subsequence, the tiling problem for the Aztec diamond, the hexagon tiling problem, and the last passage percolation problem, amongst many others. In all cases, in an appropriate scaling limit, the statistical fluctuations in the systems at hand are described by random matrix theory. The asymptotic analysis, however, depends in a critical, and rigid way, on the underlying probability measures for the systems. For example, the analysis of the last passage percolation problem requires the waiting time at each site to be either geometrically or exponentially distributed (Johansson): if the statistics of the waiting times is neither geometric nor exponential, the analysis fails completely. What happens if the geometric distribution, say, is slightly perturbed? The challenge here is to develop an effective perturbation theory for such systems. One expects that the random matrix behavior of the fluctuations should persist. Related work on this problem has been done by Baik-Suidan and Bouchard-Martin (cf. Problem 10).
Record
- Source
- Added
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.