Perturbation theory for exactly solvable combinatorial problems

The research direction is stated as: “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.” The question concerns last-passage models whose site waiting times have geometric laws, but it does not specify a family of perturbed probability distributions, the observable and scaling to be studied, or how the perturbation is to approach zero. Those choices are needed to turn the direction into a precise limit problem. Deift, Some Open Problems in Random Matrix Theory and the Theory of Integrable Systems (2007)

Background

The direction reflects a gap between detailed asymptotics for special combinatorial models and the broader question of robustness under changes to their probability laws. In directed last-passage percolation, one maximizes the sum of site weights over up/right lattice paths. For geometric weights, Johansson’s representation identifies the passage-time distribution, up to a translation, with the largest particle of a discrete orthogonal polynomial ensemble. This algebraic structure helps connect the model’s fluctuations with random-matrix limits; for general discrete weights, analogous ensemble universality does not by itself provide a percolation interpretation. Deift, Some Open Problems in Random Matrix Theory and the Theory of Integrable Systems (2007) Limiting distribution of last passage percolation models

Deift posed perturbation theory for exactly solvable combinatorial problems as Problem 13 in 2007, placing it alongside longest-increasing-subsequence, tiling, and last-passage questions. The motivating concern was that known asymptotic analyses depended strongly on special weight laws, including geometric and exponential waiting times. Thus the proposed perturbation asks not merely whether passage-time limits exist, but whether random-matrix fluctuation behavior survives when the solvable structure is changed. Deift, Some Open Problems in Random Matrix Theory and the Theory of Integrable Systems (2007) Limiting distribution of last passage percolation models

Known results

For exactly solvable last-passage models, geometric and exponential weights are among the special cases for which Tracy–Widom asymptotics are established. The geometric model’s discrete-ensemble representation explains one source of that solvability. These results provide the unperturbed benchmark, but do not establish stability under an arbitrary small change of the weight distribution. Limiting distribution of last passage percolation models

A broader, but geometrically restricted, universality theorem is available for directed site percolation. If the site weights are independent and identically distributed with mean $\mu$, variance $\sigma^2>0$, and finite fourth moment, then for any fixed $s\in\mathbb{R}$ the last-passage time $L^l(N,k)$ satisfies

$$\lim_{N,k\to\infty}\mathbb{P}\!\left(\frac{L^l(N,k)-\mu(N+k-1)-2\sigma\sqrt{Nk}}{\sigma k^{-1/6}N^{1/2}}\le s\right)=F_{GUE}(s),$$

provided $k=o(N^\alpha)$ for an exponent $\alpha<3/14$. For Gaussian site weights under the same moment conditions, the stated range extends to $\alpha<3/7$. This establishes random-matrix fluctuations for general weight laws in thin rectangles, not for a small perturbation of geometric weights in an unspecified scaling regime. A GUE Central Limit Theorem and Universality of Directed First and Last Passage Site Percolation