All Questions
Tagged with random-graphs percolation
12 questions
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 ...
- 269
2
votes
2
answers
183
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{...
1
vote
0
answers
88
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....
- 1,068
1
vote
1
answer
265
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}...
- 640
1
vote
1
answer
198
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 ...
- 649
1
vote
1
answer
94
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 ...
- 1,633
2
votes
1
answer
97
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.
- 131
1
vote
1
answer
188
views
KPZ relation $\chi = 2 \xi -1$ in a random geometric graph
If I have $n$ points uniformly distributed on the surface of a torus, and form a graph by adding an edge between pairs whenever they are within a unit distance (induced by the Euclidean metric), I ...
- 640
0
votes
0
answers
80
views
Not exactly directed percolation
Is the following problem known/well-studies? I'm looking for references or a name that I can look up.
I start with $N$ cell, each one divides into two cells, each one of the new cells either dies ...
- 371
13
votes
0
answers
509
views
First passage percolation on a random geometric graph in the large connectivity limit
Let $V_\rho\subset\mathbb{R}^2$ be a point set in the plane obtained from a Poisson process of density $\rho$. The random geometric graph $G_\rho$ is obtained from $V_\rho$ by connecting points that ...
- 3,927
6
votes
1
answer
2k
views
Probability of two vertices to be connected in G(n,p)
A question I asked at math.SE without elliciting an answer.
Let $G(n,p)$ be an Erdős–Rényi graph on $n$ vertices. Is there an explicit expression for the probability $P_{n,p}(u,v)$ that two fixed (...
- 656
4
votes
0
answers
617
views
Expected number of components with multiple cycles in a subgraph of a square lattice
Short version
Is there an understanding of the emergence and subsequent disappearance of components with zero, one, or more cycles in a random subgraph of a square or cubic lattice, as the edge-...
- 1,414