A model of random sequential adsorption on a ladder graph

Tomislav Došlić, Mate Puljiz, Stjepan Šebek, Josip Žubrinić

TL;DR

Researchers have derived the first closed-form analytical solutions for Random Sequential Adsorption (RSA) on a two-row ladder graph with a variable "blockade range" $b$. By comparing the "dynamic" process of sequential deposition to a "static" analysis of all possible jammed states, they prove that the two approaches yield fundamentally different results, providing new insights into the behavior of trapped Rydberg atoms used in quantum simulation.

What Problem Does This Paper Address?

Imagine you are trying to park cars on a street, but every driver insists on leaving at least two empty spaces between them and the next car. Eventually, the street reaches a "jammed" state where no more cars can fit, even though the street isn't technically full. This is the essence of Random Sequential Adsorption (RSA).

While RSA has been studied extensively on one-dimensional lines (the "car parking problem") and two-dimensional planes, analytical solutions for intermediate structures—like a two-row "ladder" graph—are rare. The authors tackle this gap, specifically looking at a model where an object (like an excited atom) can only be placed if it is at least $b$ units away from any other object.

This isn't just a mathematical curiosity; it mimics the "blockade effect" in Rydberg atoms. In quantum computing, if one atom is excited to a high-energy Rydberg state, it prevents its neighbors within a certain radius from being excited. Understanding the density of these excitations is crucial for scaling up quantum simulators.

Methods

The paper analyzes the system using two distinct lenses:

  1. The Dynamic Model: This follows the actual process of deposition. Objects are added one by one at random until no more can fit. The authors use recursive relations to describe the expected number of excited atoms and then apply generating functions to transform these recursions into a differential equation. Solving this yields a closed-form expression for the "jamming limit" (the final density of objects).
  2. The Equilibrium (Static) Model: This ignores the "how" and looks only at the "what." It considers the set of all possible jammed configurations and assumes they are all equally likely. The authors use a renewal approach to build a bivariate generating function that counts these configurations. From this, they derive a complexity function (or configurational entropy) to find the density at which the number of possible states is maximized.

By comparing these two, they test the Edwards hypothesis—the idea that the final state of a granular or jammed system is independent of the dynamics that created it.

Datasets

As a theoretical paper in mathematical physics, this work does not use external empirical datasets. Instead, it defines a theoretical framework based on a two-row square ladder graph of length $L$ and validates its analytical findings through numerical simulations and comparisons to known 1D limits (like Rényi’s car-parking constant).

Key Insights and Ideas

  • The Edwards Hypothesis Fails: The most significant takeaway is that the dynamic jamming limit and the static equilibrium density are not the same. The way you reach a jammed state matters.
  • The "Unfriendly Seating" Analogy: The authors relate the $b=1$ case to the "unfriendly theater seating" problem (where people refuse to sit next to each other), a concept that gained unexpected relevance during the COVID-19 pandemic for social distancing modeling.
  • Convergence to the Continuum: As the blockade range $b$ becomes very large, the dynamic model on the ladder graph converges to Rényi’s car-parking constant ($\approx 0.7476$).
  • The $b \to \infty$ Divergence: Interestingly, while the dynamic model converges to a specific constant as $b$ grows, the static model's scaled density converges to 1. This means that as the blockade range increases, the "history" of how the atoms were excited becomes even more dominant in determining the final density.

Key Results

  • Analytical Formulas: The authors provide explicit, closed-form integrals for the jamming limit $\rho_\infty^b$ for any integer $b \geq 1$.
  • Quantitative Comparison: For $b=1$ (nearest neighbor exclusion), the dynamic density is $\approx 0.8161$, while the equilibrium density is $\approx 0.7236$.
  • Scaling Behavior: The paper demonstrates that scaling the density by $2b$ allows for a direct comparison between different blockade ranges, revealing that the system's behavior stabilizes for large $b$.

Limitations and Future Work

The primary limitation is the geometry: the results are strictly for a two-row ladder. The authors acknowledge that moving to $m > 2$ rows (a "theater" of seats) is significantly harder because the graph no longer neatly decomposes into independent subgraphs after a single excitation.

Future directions include: * Extending the analysis to $m$-row graphs using Monte Carlo approximations or new analytical tricks. * Exploring non-integral blockade ranges (e.g., using Euclidean distance instead of graph distance), which would more accurately model physical Rydberg atoms. * Applying the model to other geometries, such as the hexagonal lattices found in certain quantum materials.

Summary updated

Abstract

Abstract In random sequential adsorption (RSA), objects are deposited on a substrate randomly, irreversibly, and sequentially. Attempts of deposition that lead to an overlap with previously deposited objects are discarded. The process continues until the system reaches a jammed state when no further additions are possible. We analyze a class of RSA models on a two-row square ladder graph in which landing on an empty site in a graph is allowed when at least b neighboring sites in the graph are unoccupied ( <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"> <mml:mrow> <mml:mi>b</mml:mi> <mml:mo>∈</mml:mo> <mml:mrow> <mml:mi mathvariant="double-struck">N</mml:mi> </mml:mrow> </mml:mrow> </mml:math> ). In this paper we complement this typical way of studying RSA models by analyzing also the structure of the set of all jammed states in a static way, disregarding the dynamics that led to a particular jammed state. In both considered settings (dynamic and static) we provide explicit expressions for key statistics that describe the average proportion of the substrate covered by deposited objects, and then we comment on significant differences between the two settings. We illustrate all of our findings through a toy model for ensembles of trapped Rydberg atoms with blockade range b .
BibTeX
@article{doslic2024model,
  author = {Tomislav Došlić and Mate Puljiz and Stjepan Šebek and Josip Žubrinić},
  title = {{A model of random sequential adsorption on a ladder graph}},
  journal = {Journal of Physics A Mathematical and Theoretical},
  year = {2024},
  doi = {10.1088/1751-8121/ad909c},
}

Loading related content...

Figure