Published in Discrete Mathematics Letters, this research explores new frontiers in random permutations and interacting particle systems. By extending the classic Hammersley’s process, the authors uncover how statistical "laws of nature" for sequences evolve when considering complex patterns or moving from one-dimensional lines into two-dimensional planes.
Problem Statement: Beyond Ulam’s Problem
At the heart of this research is Ulam’s Problem: determining the length of the longest increasing subsequence (LIS) in a random permutation of numbers from 1 to $n$. It is well-established that this length grows as $2\sqrt{n}$, with fluctuations following the Tracy-Widom distribution—a cornerstone of random matrix theory.
The authors address two significant gaps in the current literature:
- Pattern Avoidance: Investigating the behavior of the longest subsequence that avoids specific patterns, such as $3-2-1$ or $4-3-2-1$.
- Dimensionality: Transitioning Hammersley’s process from a 1D model (where particles appear on a line and "annihilate" neighbors) to a 2D plane with novel interaction rules.
Methodology
The study employs a combination of theoretical proofs and high-performance numerical simulations performed at Bilkent University.
Multi-layer Hammersley Process
To study pattern avoidance, the researchers proposed a system of $k-1$ parallel unit intervals. When a new particle appears in the top layer, it "bumps" the nearest particle to its right down to the next layer. This cascading effect continues until a particle is ejected from the bottom layer. The authors proved (Theorem 2.1) that this multi-layer process exactly mimics the length of the longest $\tau$-avoiding subsequence for monotone patterns, providing a computationally efficient simulation algorithm.
2D Spatial Models
Three new models were introduced within a unit square ($K$), where a new particle at $(u, v)$ "deletes" the closest existing particle within specific geometric regions:
- Model-I: A half-plane defined by a line with slope $m$.
- Model-II: The area outside a circle centered at the origin.
- Model-III: A rectangular region "above and to the right" of the new point.
Key Results and Scaling Laws
Through massive Monte Carlo simulations (up to $10^7$ steps), the authors identified new scaling laws. While the 1D LIS problem scales with $\sqrt{n}$, the 2D models exhibit a growth rate following the form $a(\log n)^b n^c$.
1D Pattern Avoidance Results
For monotone patterns, the simulations provided precise numerical estimates for growth and variance:
- 321-avoiding pattern: The mean number of particles is approximately $4\sqrt{n} - 5.139n^{1/6}$. The standard deviation follows an $n^{1/6}$ scaling.
- 4321-avoiding pattern: The mean grows approximately as $6\sqrt{n} - 9.954n^{1/6}$.
2D Model Insights
Model-III (Rectangular) showed the most robust fit, with the mean growing as $1.020(\log n)^{0.363} n^{0.650}$. Interestingly, across all three 2D models, the standard deviation scaled similarly (roughly $n^{0.26}$ to $n^{0.27}$), suggesting a potential universal "2D Hammersley" distribution.
Conclusion and Future Directions
While the 1D results are supported by theoretical equivalence, the 2D results remain largely empirical. The simulations provide precise exponents (e.g., $c \approx 0.65$), but formal mathematical proofs for these values are still needed. Future work will focus on determining if these 2D processes belong to known universality classes, such as the Kardar-Parisi-Zhang (KPZ) class, which describes various growth processes in nature.
Summary updated