Generalized Random Sequential Adsorption on Sparse Random Graphs

Souvik Dhara, Johan S. H. van Leeuwaarden, Debankur MukherjeearXiv 2016 · arXiv

Abstract

We investigate Random Sequential Adsorption (RSA) on a random graph via the following greedy algorithm: Order the $n$ vertices at random, and sequentially declare each vertex either active or frozen, depending on some local rule in terms of the state of the neighboring vertices. The classical RSA rule declares a vertex active if none of its neighbors is, in which case the set of active nodes forms an independent set of the graph. We generalize this nearest-neighbor blocking rule in three ways and apply it to the Erdős-Renyi random graph. We consider these generalizations in the large-graph limit $n\to\infty$ and characterize the jamming constant, the limiting proportion of active vertices in the maximal greedy set.

Introduction

Random Sequential Adsorption (RSA) is a fundamental mathematical framework used to model irreversible processes, such as particles sticking to a surface or cars parking on a street. In the context of graph theory, the "classical" RSA rule is simple: a vertex becomes "active" if none of its neighbors are already active. This process results in a "greedy independent set."

However, real-world systems—such as wireless networks managing interference or atoms in a Rydberg gas—often follow more nuanced rules. A node might tolerate a certain amount of "noise" from multiple neighbors or operate on different frequencies. This paper extends the classical parking problem to complex, multi-state rules on sparse random graphs, providing a rigorous characterization of the "jamming limit"—the final density of the system—for three generalized models.

Methodology: Exploration Algorithms and Fluid Limits

The authors employ a powerful technique called asymptotic analysis via exploration algorithms. Instead of taking a pre-existing graph and running a process on it, they design algorithms that "reveal" the graph's edges simultaneously with the RSA process.

  1. Exploration Algorithms: By revealing edges only when a vertex is selected, the "unexplored" part of the graph remains statistically uniform (specifically, an Erdős-Rényi random graph). This allows the state of the system to be tracked using a manageable set of variables.
  2. Fluid Limits: As the number of vertices $n$ approaches infinity, the discrete, random steps of the algorithm converge to a smooth, deterministic process. The authors use systems of ordinary differential equations (ODEs) to describe how the proportion of nodes in different states (active, frozen, or at a certain "height") evolves over time.

Generalized RSA Models

The paper characterizes three specific generalizations of the RSA rule:

  • Threshold Model: A node becomes active if it has fewer than $K$ active neighbors and its activation won't cause its neighbors to exceed that same threshold.
  • Tetris Model: Particles "stack" on vertices. A new particle's height is one unit higher than the maximum height of its neighbors, up to a limit $K$.
  • Sequential Frequency Assignment Process (SFAP): A node attempts to take the lowest available "frequency" from $\{1, \dots, K\}$ not used by its neighbors. If all frequencies are occupied, the node is frozen.

Key Results and Insights

The primary contribution of this work is the derivation of "universal jamming constants" (Theorems 2, 4, and 6), which serve as master equations for the limiting densities of the Threshold, Tetris, and SFAP models.

Jamming constants for the Threshold model for various $K$ values.

For the simplest case ($K=1$), the formulas simplify to the well-known result for greedy independent sets: $\frac{1}{c} \log(1+c)$. The results quantitatively show how much "capacity" is gained in a network by relaxing the hard-core constraint. For example, moving from $K=1$ to $K=2$ in the Threshold model significantly increases the fraction of active nodes, especially in sparse regimes.

In the Tetris model, the authors identified a "screening effect" where the density of nodes at higher levels can increase as the graph becomes denser (higher average degree $c$). This occurs because high-level nodes "block" lower levels from being filled, a phenomenon analogous to physical particle deposition.

Discussion and Future Work

While this work provides a rigorous foundation for RSA on Erdős-Rényi graphs, several avenues for future research remain. The current study is limited to graphs where every edge is equally likely. Extending these proofs to Configuration Models or Preferential Attachment graphs would better capture the "heavy-tailed" or community structures found in real-world networks.

Additionally, these models are "greedy"---they make decisions based on local, immediate availability. There remains a significant "optimality gap" between these greedy solutions and the maximum possible $K$-independent set, which is often twice as large. Quantifying this gap remains a major open problem in combinatorial optimization.

Summary updated

Abstract

We investigate Random Sequential Adsorption (RSA) on a random graph via the following greedy algorithm: Order the $n$ vertices at random, and sequentially declare each vertex either active or frozen, depending on some local rule in terms of the state of the neighboring vertices. The classical RSA rule declares a vertex active if none of its neighbors is, in which case the set of active nodes forms an independent set of the graph. We generalize this nearest-neighbor blocking rule in three ways and apply it to the Erdős-Renyi random graph. We consider these generalizations in the large-graph limit $n\to\infty$ and characterize the jamming constant, the limiting proportion of active vertices in the maximal greedy set.
BibTeX
@misc{dhara2016generalized,
  author = {Souvik Dhara and Johan S. H. van Leeuwaarden and Debankur Mukherjee},
  title = {{Generalized Random Sequential Adsorption on Sparse Random Graphs}},
  year = {2016},
  eprint = {1604.03918},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1604.03918},
}
Figure