Variations on Hammersley's interacting particle process

Arda Atalik, H. S. Melihcan Erol, Gökhan Yildirim, Mustafa YilmazarXiv 2021 · arXiv

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:

  1. Pattern Avoidance: Investigating the behavior of the longest subsequence that avoids specific patterns, such as $3-2-1$ or $4-3-2-1$.
  2. 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.
Mean and Standard Deviation for the 321-avoiding pattern process, showing the fit to the derived power laws.
  • 4321-avoiding pattern: The mean grows approximately as $6\sqrt{n} - 9.954n^{1/6}$.
Mean growth for the 4321-avoiding pattern process as a function of n.

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

BibTeX
@misc{atalik2021variations,
  author = {Arda Atalik and H. S. Melihcan Erol and Gökhan Yildirim and Mustafa Yilmaz},
  title = {{Variations on Hammersley's interacting particle process}},
  year = {2021},
  eprint = {2106.11186},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2106.11186},
}
Figure