Nonlinear Exchange Dynamics for Independent Sets
Abstract
In recent years, nonlinear dynamics derived from kinetic theory have gained attention in the context of sampling configurations of spin systems such as the Ising model. We focus on nonlinear dynamics for the hard-core model, a canonical spin system with hard constraints that specifies a distribution over independent sets in a graph, weighted by their sizes. We explore two distinct types of nonlinear dynamics: the mean-field dynamics, which preserves the density (or average size) of independent sets, and the single-site dynamics, which preserves the marginal vector (i.e., the occupancy probabilities of the vertices). These dynamics are natural stochastic processes for sampling from the hard-core model with a specified density or marginal vector, respectively, both of which are canonical instances of maximum entropy distributions that have been studied in various contexts. In contrast to linear Markov chains, there is a significant lack of a fundamental theoretical framework for nonlinear dynamics. We develop foundational theoretical tools for analyzing nonlinear dynamics within the context of the hard-core model. We establish almost linear convergence of both the mean-field and single-site dynamics at sufficiently low density through novel coupling arguments. We also establish exponential decay of relative entropy for the mean-field dynamics all the way up to the critical density. Additionally, we design new algorithms for sampling from the hard-core distribution with either a specified density or a specified marginal vector. These algorithms are based on a related linear Markov chain, called the particle-system dynamics and inspired by the so-called Kac's program, that approximates the associated nonlinear dynamics. As we demonstrate in the paper, they are comparable in time complexity, but simpler to implement, than traditional approaches based on learning parameter values.
Related
- Large independent sets via neighborhood block dynamics, Glauber dynamics, and local occupancy
- Two problems about bases and independent sets in free groups
- Lifting for N-independent sets in II1 factors
- Variance of random greedy independent sets in triangle-free graphs
- Random independent sets and local sparsity
BibTeX
@misc{minab2026nonlinear,
title = {{Nonlinear Exchange Dynamics for Independent Sets}},
author = {Mehrad Abbaszadeh Minab and Pietro Caputo and Zongchen Chen and Mario Morellini and Alistair Sinclair},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.29016},
eprint = {2607.29016},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.29016},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Nonlinear Exchange Dynamics for Independent Sets
AU - Mehrad Abbaszadeh Minab
AU - Pietro Caputo
AU - Zongchen Chen
AU - Mario Morellini
AU - Alistair Sinclair
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2607.29016
UR - https://arxiv.org/abs/2607.29016
AB - In recent years, nonlinear dynamics derived from kinetic theory have gained attention in the context of sampling configurations of spin systems such as the Ising model. We focus on nonlinear dynamics for the hard-core model, a canonical spin system with hard constraints that specifies a distribution over independent sets in a graph, weighted by their sizes. We explore two distinct types of nonlinear dynamics: the mean-field dynamics, which preserves the density (or average size) of independent sets, and the single-site dynamics, which preserves the marginal vector (i.e., the occupancy probabilities of the vertices). These dynamics are natural stochastic processes for sampling from the hard-core model with a specified density or marginal vector, respectively, both of which are canonical instances of maximum entropy distributions that have been studied in various contexts. In contrast to linear Markov chains, there is a significant lack of a fundamental theoretical framework for nonlinear dynamics. We develop foundational theoretical tools for analyzing nonlinear dynamics within the context of the hard-core model. We establish almost linear convergence of both the mean-field and single-site dynamics at sufficiently low density through novel coupling arguments. We also establish exponential decay of relative entropy for the mean-field dynamics all the way up to the critical density. Additionally, we design new algorithms for sampling from the hard-core distribution with either a specified density or a specified marginal vector. These algorithms are based on a related linear Markov chain, called the particle-system dynamics and inspired by the so-called Kac's program, that approximates the associated nonlinear dynamics. As we demonstrate in the paper, they are comparable in time complexity, but simpler to implement, than traditional approaches based on learning parameter values.
ER -