Questions tagged [percolation]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
5 votes
0 answers
82 views

The uniform odd and even subgraph of $\mathbb{Z}^2$

Given a (first finite and later infinite) graph $G =(V,E)$ the uniform even graph is the uniform probability measure on the set of spanning even subgraphs. That is subgraphs (V, E') with $E' \subset E$...
Frederik Ravn Klausen's user avatar
2 votes
0 answers
69 views

Multi-scale 3- and 5-arm exponents for critical planar percolation

Consider critical site percolation on the planar triangular lattice. Denote by $A_j(m,n)$ the event that there are $j$ arms (paths from the inner boundary to the outer boundary) of alternating colour ...
Julius's user avatar
  • 301
2 votes
0 answers
98 views

The fluctuations of a random path

Suppose I have a $n \times n$ square grid and for each square, I assign 1 with probability $\frac{1}{2}$ and 0 with probability $\frac{1}{2}$. On the boundary, I put 1s on the lower half and 0s on the ...
Frederik Ravn Klausen's user avatar
13 votes
1 answer
938 views

A disc contains many random points. Each point is connected to its nearest neighbor. What is the expectation of average cluster size?

A disc contains $n$ independent uniformly distributed points. Each point is connected by a line segment to its nearest neighbor, forming clusters of connected points. For example, here are $20$ random ...
Dan's user avatar
  • 2,341
0 votes
0 answers
25 views

Do finite components get smaller as supercritical random graphs with an arbitrary degree sequence get denser?

I asked this question a few weeks ago on MSE but did not receive any responses so I am going to ask a related but more specific question here. First some notation. Let $\mathbb{G} = \mathbb{G}(n,\...
deej's user avatar
  • 21
1 vote
0 answers
45 views

Locality and restriction properties for self-avoiding and loop-erasing random walks

This question has been cross-posted from math.stackexchange.com : https://math.stackexchange.com/questions/4742746/locality-and-restriction-properties-for-self-avoiding-and-loop-erasing-random-wa I ...
Testcase's user avatar
  • 541
1 vote
0 answers
31 views

Crossing a slightly longer box in Bernoulli percolation

Consdier critical Bernoulli bond percolation on $\mathbb{Z}^2$. Given $a, b \in \mathbb{N}$ denote by $p(a,b)$ the probability that there is an open left-right crossing in the box $[0,a]\times [0,b]$....
Julius's user avatar
  • 301
3 votes
0 answers
161 views

Topology of level sets for meromorphic function

Let $F$ be a meromorphic function on $\mathbb{C}$. I consider the "level set" $$E_\varepsilon=\{z:|F(z)|\leq\varepsilon\}.$$ My objective is to find conditions under which $E_\varepsilon$ ...
kaleidoscop's user avatar
  • 1,268
3 votes
0 answers
66 views

The boundary between infinite clusters connected by closed and open bonds

In the following, I'll heuristically describe a boundary between two infinite clusters arising in percolation on the triangular lattice. I expect this concept has been well-studied before. My hope is ...
user196574's user avatar
6 votes
1 answer
108 views

What's the minimum ratio of positive cells such that the player has a positive probability to reach the boundary of a large random map?

A map with $(2n-1)$ rows and $(2n-1)$ columns of square cells is generated randomly as follows: the value of each cell is chosen from {1, -1} randomly and independently with probability {$p$, $1-p$}. ...
Y. Yang's user avatar
  • 83
6 votes
1 answer
206 views

Origin of the term "connective constant"

Let $G$ be a vertex-transitive locally finite graph and $c_n$ the number of self-avoiding walks in $G$ starting from some fixed vertex $v_0$. One can easily see that $c_{m+n} \leq c_m c_n$ and hence ...
Salini Mendisi's user avatar
4 votes
1 answer
228 views

Percolation: at what length scale do we see it?

Consider classical bond percolation on $\mathbb{Z}^d$. Each edge is included with probability $p$ and deleted with probability $1-p$. As is well known, there is a $p_c(d) \in (0,1)$ such that $p>...
Scott Armstrong's user avatar
0 votes
0 answers
52 views

Can I explore the infinite cluster of Bernoulli percolation in $\mathbb{Z}^2$?

In Bernoulli percolation on the square lattice $\mathbb{Z}^2$ every edge is kept with a probability $q$ and erased with probability $1-q$. It is classical that whenever $q > \frac{1}{2}$ there is ...
Frederik Ravn Klausen's user avatar
1 vote
0 answers
26 views

How slowly can one be absorbed in the absorbing phase of the directed percolation universality class?

In absorbing state transitions on a lattice, one often considers "active" and "inactive" sites, with update rules describing how activity spreads or decays. When the lattice sites ...
user196574's user avatar
6 votes
2 answers
403 views

Infinite clusters for loopless percolation

I feel like this is maybe an incredibly trivial problem, and I'm just missing something. I may also be describing a well-known model that I cannot find the name for, so any comment/suggestion is ...
PeaBrane's user avatar
  • 213
0 votes
0 answers
69 views

Likelihood ratio of non-trivial cycles in an inhomogeneous random square lattice graph embedded on a toroidal surface

Consider a square lattice (random) graph $G$ embedded on a toroidal surface. Each edge $(i, j)$ of the graph has an associated likelihood probability $p_{ij}$. The probabilities $p_{ij}$ come from a ...
Sanchayan Dutta's user avatar
2 votes
2 answers
159 views

Which infinite random graphs with percolation threshold $p_c=0$ are transient?

I am interested in long-range percolation models with heavy-tailed degree distributions such as DHH13, GLM21, Y6. The simplest example is scale-free percolation in which vertices are elements $\mathbb{...
Christian Mönch's user avatar
1 vote
0 answers
87 views

In percolation on a lattice, how is "infected" status correlated for points in a region around the origin?

Consider independent bond percolation on $\mathbb{Z}^2$, with $p>p_c$ so that the process is supercritical. For any site $x$ let $Y_x$ be the indicator of $x$ belonging to the infinite open cluster....
Ben Golub's user avatar
  • 1,058
9 votes
2 answers
445 views

Are there more paths exiting a box in $\mathbb{Z}^2$ to the right if I remove some edges to the left

Suppose that I am given the graph $G = (V,E)$ where $V = \{ 1, 2, \dots 2N+1 \} \times \{ 1, 2, \dots 2N+1 \} $ and there is an edge between two vertices $(n,m)$ and $(n',m')$ if and only if $\vert n-...
Frederik Ravn Klausen's user avatar
9 votes
2 answers
1k views

An elementary question in bond percolation

Consider a locally finite, connected graph and "bond (edge) percolation" on this graph. Each edge is open with probability $p.$ There is a parameter $\alpha$, $0<\alpha<1.$ The ...
Konstantin Sonin's user avatar
1 vote
0 answers
59 views

Existence of a bigeodesic in last passage percolation is $0$-$1$ event

On the bottom of page two of This paper, the authors remark the following: '...by translation invariance and ergodicity, we know that existence of a bigeodesic is a $0−1$ event and hence it follows ...
Raghav's user avatar
  • 361
1 vote
1 answer
299 views

Understanding the wrapping criterion in percolation theory

Context: When studying percolation in finite sized systems, there exist various definitions and criteria for determining when a given system is percolating, i.e., given a definition for connectivity, ...
user929304's user avatar
2 votes
0 answers
158 views

Ask for some reference about isoperimetric constant on Voronoi diagrams?

Given a Poisson point process $\mathcal{P}$ in $\mathbb{R}^2$, the $\textbf{Voronoi cells}$ of a point $p\in \mathcal{P}$ is defined by $$V(x):=\{y\in \mathbb{R}^2: \|x-y\|=\min_{x'\in \mathcal{P}}\|x'...
Hermi's user avatar
  • 276
1 vote
1 answer
243 views

Continuum percolation in 1d

What is known about continuum percolation in 1d? By this, I mean, for $d \in \mathbb{N}$, the Poisson-Boolean model of disks of radius $r_0 \in \mathbb{R}$ with centres arranged randomly in $[0,1]^{d}...
apg's user avatar
  • 612
3 votes
0 answers
76 views

super-critical percolation on $\mathbb{Z}^2$, number of corners in a directed open path

Define the planar percolation where each unit edge is open with probability $p$ very close to $1$. Looking at the event where there exists a directed open path between $(0,0)$ and $(n,n)$. This event ...
Xiao's user avatar
  • 425
0 votes
0 answers
119 views

Ask for some percolation reference textbook

I try to learn Bernoulli percolation recently. Could anyone provide some lecture notes or textbooks to enter this field? Thanks.
Hermi's user avatar
  • 276
3 votes
1 answer
178 views

Bernoulli percolation, infinite path from (0,0) in a "cone"

Look at Bernoulli percolation on $\mathbb{Z}^2$ with $p> p_c$ ($p$ can be arbitrarily close to 1). I am interested in the probability that there exists an infinite cluster starting at $(0,0)$ and ...
Xiao's user avatar
  • 425
5 votes
1 answer
282 views

Random walk on the hypercube with deleted edges

Let $G$ be the $n$-dimensional boolean hypercube, i.e. the graph on $\{0,1\}^n$ where two vertices are adjacent iff they differ on exactly one coordinate. Consider a graph $G'$ obtained by deleting a ...
RandomWalker's user avatar
3 votes
1 answer
153 views

Does the union of two percolation measures satisfying the (FKG) inequality still satisfy (FKG)?

Let a percolation measure be a measure on $\{0,1\}^n$. We have a natural partial order on $\{0,1\}^n$ given by comparing all coordinates. An event $A$ is called increasing if for all $ \omega \in A $ ...
Frederik Ravn Klausen's user avatar
6 votes
0 answers
117 views

What can be said about percolation clusters after deleting a positive fraction of edges in general?

Start with a bond-percolation process just above criticality, say $p=1/2+\varepsilon$ on the graph $\mathbb Z^2$ with $\varepsilon>0$. Sample $D\in\{0,1\}^E$ from an independent product measure ...
user507474's user avatar
3 votes
1 answer
2k views

Understanding Finite Size Scaling in Percolation Theory

Fundamental results in percolation theory are all based on the assumption that the system sizes are infinite, as the spanning/percolating cluster is by definition an infinitely sized cluster that ...
user929304's user avatar
8 votes
0 answers
151 views

Pursuit-evasion with many slow pursuers

Question: Suppose that intelligent pursuers with speed $v<1$ are randomly scattered on the plane with area density $1/r$  ($r>0$ is distance from the origin). If you start at the origin ...
Dmytro Taranovsky's user avatar
1 vote
1 answer
173 views

Figuring out a consistent definition for the percolation backbone

In the context of percolation, e.g., bond/site percolation, random graph connectivity in 2-3 dimensions, etc., once the percolation threshold is reached, that is the system is spanned by an infinite ...
user929304's user avatar
1 vote
1 answer
286 views

Percolation critical exponent $\nu$ does not depend on neighborhood connectivity. Does this follow from the universality principle?

I read the Wikipedia article on Percolation critical exponents. It says: In the context of the physical and mathematical theory of percolation, a percolation transition is characterized by a set of ...
Sanchayan Dutta's user avatar
10 votes
0 answers
349 views

Riemann–Hilbert-type problem

Let $P$ be a fixed pentagon in the hyperbolic plane $\mathbb H^2$ with all the angles equal to $\pi / 3$. Let $w_1, w_2, \dots, w_5$ be the sides of $P$ going in the counterclockwise order. We are ...
Misha's user avatar
  • 121
1 vote
1 answer
92 views

What is the expected distance between the sides of a random subgraph of the grid?

Let $G$ be the $n \times n$ grid, in which each vertex is connected to the vertices above it, below it and on either side. Let $G_p$ be the random subgraph of $G$ obtained by keeping each edge with ...
Zur Luria's user avatar
  • 1,603
6 votes
0 answers
246 views

Gaussian square-free moat

Is there a sequence $\{z_n\}_{n=1}^\infty$ of distinct square-free Gaussian integers with $$\sup_{n \geq 1} |z_{n+1} - z_n| < \infty ?$$ For the analogous problem with Gaussian primes instead, ...
Pablo's user avatar
  • 11.2k
2 votes
0 answers
101 views

Percolation-type question involving phase transition for graded acyclic directed graph

Let $G$ be an acyclic directed graph with $MN$ vertices arranged into $M$ generations of $N$ vertices each. We stipulate that edges may only go from generation $j$ to generation $j+1$, so there are $(...
physmath121's user avatar
1 vote
0 answers
50 views

Vertical and horizontal percolation on heterogeneous honeycomb lattice

I have a regular honeycomb lattice where a bond in the unit cell aligns with $(1,0)$; call this the horizontal direction. Each horizontal bond in the lattice is open with probability $p$ and each "...
fuser0909's user avatar
1 vote
0 answers
88 views

Percolation and diameter of graph

Is the critical probability in percolation and diameter of graph related. I guess larger the diameter higher the probability. Is there any result like this? By critical probability I mean the ...
K. Lakshmanan's user avatar
0 votes
0 answers
113 views

How to mathematically justify the "sampling" over only $100$ random matrices to estimate percolation thresholds?

As mentioned in the textbook "Introduction to Percolation Theory" (Chapter 4) by Stauffer et al., the variation of spanning cluster percolation probability $\Pi$ in a finite $L < \infty$ square ...
user avatar
2 votes
1 answer
87 views

Generalization: (The "number" of) smaller sized clusters in large random binary matrices follow a descending order. Why?

This is a sequel to the question: Why is number of single cell clusters always greatest in a random matrix? In their answer, @Aaron Meyerowitz came up with a nice strategy to prove why the number of ...
user avatar
3 votes
1 answer
175 views

Why is number of single cell clusters always greatest in a random matrix?

Consider a large $N\times N$ square lattice, where each cell has a probability $p$ of being "occupied" (let's call denote them as "black") and a probability $1-p$ of being empty (let's denote them as "...
user avatar
6 votes
0 answers
116 views

Length of optimal play in Hex as a function of size

Consider Hex on an $n \times n$ board without a swap rule, so that the first player wins. Assume the first player tries to minimize the length of the game, and the second player tries to maximize the ...
Geoffrey Irving's user avatar
1 vote
1 answer
112 views

Probability for a group of stones to live on an infinite Go board

Suppose on an infinite two dimensional Go board the tengen is occupied by a black stone, and every other grid point is occupied by a black stone, or a white stone, or nothing, with probability 1/3 ...
Fan Zheng's user avatar
  • 5,109
1 vote
1 answer
153 views

Does there exist any analogous result for site percolation?

This is a sequel to the question: Proof and interpretation of the following percolation theory result for $n\times n$ square grid In the paper: The Birth of the Infinite Cluster:Finite-Size Scaling ...
user avatar
2 votes
1 answer
380 views

Proof and interpretation of the following percolation theory result for $n\times n$ square grid

While I was discussing this question with @JamesMartin, he mentioned a result here that: In a $n\times n$ finite square grid, if $p\geq p_c+\epsilon$, such that $\epsilon>0$ and $p_c$ is the ...
user avatar
2 votes
1 answer
95 views

References on the structure of bond percolation on the (finite) 2D-grid in the sub-critical regime (e.g p=1/10)

Would appreciate references to the most up-to-date results for the structure of bond percolation on the (finite) 2D-grid in the sub-critical regime (e.g, $p=1/10$). Thank you.
user17282's user avatar
  • 131
0 votes
0 answers
80 views

How to calculate the exact probability $p$ at which maxima occurs in the curves in an infinite system?

I'm writing with respect to this paper: Khatun, Dutta, and Tarafdar - "Islands in Sea" and "Lakes in Mainland" phases and related transitions simulated on a square lattice Here's a ...
user avatar
2 votes
0 answers
101 views

Is this correct: Inflection points of Euler number graph in Island-Mainland transition correspond to spanning cluster site percolation threshold?

I'm writing with respect to the paper Khatun, Dutta, and Tarafdar - "Islands in Sea" and "Lakes in Mainland" phases and related transitions simulated on a square lattice. Here's a link to a PDF ...
user avatar