On extinction and survival of the Bak-Sneppen model on arbitrary graphs
Serguei Popov, Stanislav Volkov · 2025
Read On extinction and survival of the Bak-Sneppen model on arbitrary graphs by Serguei Popov, Stanislav Volkov (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-15500.txt.
Introduction
Serguei Popov and Stanislav Volkov study life and death of fitness in the Bak-Sneppen evolution model on general graphs. Their twenty twenty-five paper places the classic model, where the least fit site and its neighbors refresh at random, on any bounded-degree graph. The question is how many top-fitness sites persist in the long run.
In the sparse regime, a graph construction tied to percolation bounds the chance a given site sits at top fitness. If long chains cover the graph, the density of top sites has a thin upper tail. In the dense regime, an energy-style argument bounds the count of zero-fitness sites. Both bounds hold evenly across graph shapes.
Catalog record
| CREATOR | Serguei Popov, Stanislav Volkov |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 44 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-15500
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On extinction and survival of the Bak-Sneppen model on arbitrary graphs Serguei Popov, Stanislav Volkov Abstract We study the discrete Bak-Sneppen model introduced in [ 5 ] . We extend their results as well as the non-triviality result of [ 21 ] for a finite segment of ℤ 1 {\mathbb{Z}}^{1} with the periodic boundary condition to a large class of graphs, by using coupling between the Bak-Sneppen model and the oriented percolation in a quadrant. This allows us to avoid dealing with the so-called avalanches, thus simplifying many arguments. Keywords: Bak-Sneppen model, self-organized criticality, oriented percolation. AMS 2010 subject classifications: 60J20, 60K35, 82C22 {}^{~1} Centro de Matemática, University of Porto, Porto, Portugal e-mail: [email protected] {}^{~2} Lund University, Centre for Mathematical Sciences, Lund, Sweden e-mail: [email protected] 1 Introduction and main results A classical Bak-Sneppen model, introduced in [ 1 , 2 ] , is defined as follows. There are N\geq 3 points uniformly spread over a circumference. Each point at discrete time t=0,1,2,\dots possesses a value \eta_{i}(t)\in[0,1] , i\in[N]=\{1,2,\dots,N\} , called fitness ; we assume that at time zero all fitnesses are distinct. At each time t we choose and index j=j(t) such that \eta_{j}(t)=\min_{i\in[N]}\eta_{i}(t) and replace the fitness of site j as well as that of both its nearest neighbours on the circumference by three uniform [0,1] values, drawn independently. Due to continuity of these random variables, we will a.s. never have ties and j is thus defined uniquely. Formally, \eta_{i}(t+1)=\begin{cases}\zeta_{i-j,t},&\text{if }i\in\{j-1,j,j+1\};\\ \eta_{i}(t),&\text{otherwise}\end{cases} with the contention N+1=1 , 1-1=N , and where \zeta_{-1,t},\zeta_{0,t},\zeta_{-1,t} are i.i.d. uniform [0,1] . A long-standing and still unproven conjecture says that as N\to\infty , the asymptotic distribution of \eta_{i}(t) converges to a uniform distribution over the interval [\eta_{c},1] where \eta_{c}\approx 0.66 . A discrete version of the Bak-Sneppen model introduced in [ 5 ] and later studied by [ 20 , 21 , 24 ] allows only two values of fitnesses, namely \eta_{i}(t)\in\{0,1\} , and the fitnesses are drawn from Bernoulli(p) distribution. Of course, in this case, the minimum value may be no longer uniquely defined, and thus one draws j(t) with equal probability for all those j such that \eta_{j}(t)=\min_{i}\eta_{i}(t) (which is typically =0 , except the case when all \eta_{i} s are ones). It is easy to see that when 0<p<1 we obtain an ergodic Markov chain with 2^{N} states. Let \pi(\eta:\eta_{i}=1)=\pi_{N,p}(\eta:\eta_{i}=1)=\lim_{t\to\infty}{\mathbb{P}}(\eta_{i}(t)=1) be the probability 1 1 1 By symmetry, it does not depend on i that site i is in state 1 under the stationary measure. We are interested in describing \pi_{N,p}(\eta:\eta_{i}=1) for very large N . By comparison with e.g. branching process, it is quite easy to see that if p\geq 2/3 then \pi_{N,p}(\eta:\eta_{i}=1)\to 1 as N\to\infty . It is much harder, however, to show that the same does not happen for all p>0 . Eventually, it was shown in [ 21 ] that for small enough p one has \limsup_{N\to\infty}\pi_{N,p}(\eta:\eta_{i}=1)<1 ; the proof in [ 21 ] is quite complicated. The purpose of the current paper is to provide an alternative, and possibly simpler, proof, based on the comparison with oriented percolation, as well as to extend the result to more general graphs. Indeed, it is very easy to define the discrete Bak-Sneppen model on an arbitrary finite connected graph G without loops, by replacing one of the zero fitness by a Bernoulli variable together with fitnesses of all the neighbours in the graph (in the original problem, the underling graph G is just a circle graph with N vertices). We can even extend this model to infinite graphs with uniformly bounded degree . To achieve this, we switch to a continuous-time model, assuming that each vertex x has its own independent Poisson clock with a rate of 1 . When such a clock rings, one of the two things happens. If the fitness of x is 1 , nothing happens (except when there are no zero fitnesses anywhere on the graph). If the fitness of x is 0 , the fitness of x and each of its neighbours y\sim x is replaced by an independent Bernoulli( p ) variable. In case of a finite graph, the embedded Markov chain coincides with the Bak-Sneppen model described above. For convenience, from now on we will work only with the continuous time version of the model even in case of finite graphs. While one of the first conjectures regarding the distribution of fitness in the continuous model remains open, there are numerous results for related models. In [ 12 ] the authors studied the model without geometric interactions. The Bak-Sneppen evolution model on a regular hypercubic lattice in high dimensions was studied in [ 7 ] . A local barycentric version of the process was studied in [ 17 ] . The hydrodynamic limit of the Bak-Sneppen branching diffusion was obtained in [ 9 , 10 ] . For other recent and related results on the Bak-Sneppen model see [ 4 , 6 , 16 , 11 , 20 ] and references therein. Let G be a finite connected graph without loops or repeated edges. Let d be the maximum degree of a vertex. For x\in G , we refer to x\cup\{y:y\sim x\} as the neighbourhood of x . Definition 1.1 . We say that (x_{1},\ldots,x_{n}) is a self-avoiding path , if x_{j}\sim x_{j+1} for all j=1,\ldots,n-1 , and all sites in the path are distinct. Further, we say that a self-avoiding path (x_{1},\ldots,x_{n}) is a chain , if the neighbourhoods of x_{i} and x_{j} do not intersect whenever j-i\geq 3 . Let \ell(G) be the length of the longest chain in G ; also, let \ell_{x}(G) be the length of the longest chain containing x . Note that, for uniformly bounded-degree graphs, it is straightforward to obtain that \ell_{x}(G) grows at least logarithmically in |G| . Also, observe that the shortest (in the sense of the graph distance) path between two distinct sites x and y is a chain. 2 2 2 Indeed, if it were not a chain, it is not difficult to see that one would be able to construct a shorter path. Let \pi denote the stationary distribution for our (continuous-time) Markov chain. We now state our first result, which says that ones become “locally improbable” if the parameter p is small. Theorem 1.2 . For a given d there exists a function g_{d}:[0,1]\to[0,1] with the property g_{d}(p)\to 0 as p\downarrow 0 , such that for any finite connected graph G of maximal degree d and for any x\in G we have (for the Bak-Sneppen with parameter p ) \pi(\eta:\eta_{x}=1)<g_{d}(p). Next, we state a “concentration of measure” result, which says that, under some additional conditions, in the small- p regime, the stationary measure of the set of configurations with “too many” 1 s converges to zero very quickly as the graph size goes to infinity. For a configuration \eta , let \bar{\eta}=|G|^{-1}\sum_{x\in G}\eta_{x} be the proportion of 1 s in the configuration. Theorem 1.3 . Assume that G (of maximal degree d ) can be covered by K chains, each of size at least \ell . Then there exists a function \tilde{g}_{d}:[0,1]\to[0,1] with the property \tilde{g}_{d}(p)\to 0 as p\downarrow 0 , such that \pi\big(\eta:\bar{\eta}_{x}\geq\tilde{g}_{d}(p)\big)\leq c_{1}Ke^{-c_{2}\ell}. While Theorem 1.3