Percolation theory describes the behavior of connected clusters in a random graph.

learn more… | top users | synonyms

0
votes
0answers
31 views

Percolation Theory Basics: Open cluster size decay (Square Lattice)

I am trying to learn some stuff about percolation. On wiki (http://en.wikipedia.org/wiki/Percolation_theory) it says: "when $p<p_{c}$, the probability that a specific point (for example, the ...
15
votes
1answer
157 views

The Gaussian moat problem and its extension to other rings in $\mathbb{C}$, $\mathbb{H}$ and $\mathbb{O}$

One of my favourite open problems in number theory, an area in which I enjoy only as a hobbyist, is the Gaussian moat problem, namely "Is it possible to walk to infinity in $\mathbb{C}$, taking ...
1
vote
0answers
19 views

Percolation in a finite, 2D rectangular grid

Images: I'd like some hints to the ??? pointed out as well as how to approach the case in which the X,Y are opposite corners. P.S. This is a problem which I came up with after a conversation with ...
0
votes
0answers
19 views

Total number of nodes in critical Galton-Watson process

Consider the following critical Galton-Watson process: initially there is a population of $Z(0) = z_0$. The distribution of children for each node follows a binomial law, with maximum value $d$; i.e. ...
1
vote
0answers
36 views

The probability that two adjacent vertices are connected with percolation probability $p = 1/2$.

I realise there is already a question on this matter, but I wasn't entirely satisfied with the answer given so that's why I am opening a new question. So the problem is to find the probability that ...
14
votes
1answer
236 views

The problem of the most visited point.

Represents the set $R_{n\times n}=\{1,2,\ldots, n\}\times\{1,2,\ldots, n\} $ as a rectangle of $n$ by $n$ as points in the figures below for exemple. How to calculate the number of circuits that visit ...
6
votes
1answer
97 views

Colored path in a randomly colored grid

A friend of mine asked this question a while ago which I couldn't find any appropriate answer for it. I'd appreciate any comment or help. If one colors each unit square with black/white of an $m ...
9
votes
0answers
101 views

Size of connected regions on a randomly-colored infinite chessboard

Consider an infinite chessboard where each square is colored white with probability $p$ and black with probability $1-p$. Suppose without loss of generality that the square at $(0,0)$ is white. We ...
0
votes
0answers
50 views

Cluster size distribution function on the 2D Bethe Lattice

The cluster size distribution function n(s,p) is the number of clusters of size s at occupation probability p per unit cell of a lattice. On a 2D Bethe lattice, this evaluates to $$ n(s,p) = ...
5
votes
0answers
87 views

Percolation and number of phases in the 2D Ising model.

Update. As my previous figure had conceptual mistakes I decided to change the picture to another, more instructive After a long time I came back to try to understand an article on the Ising ...
1
vote
0answers
133 views

A spaceship travelling to infinity while avoiding star collisions

Consider placing countably infinitely many points labeled $S_i$ randomly over $\mathbb{R}^2$, with asymptotic density points/area $ยต$. Then, what is the largest $r$ such that we can find a a ...
0
votes
0answers
82 views

How to calculate expectation of fraction of vertices connect to edge of $[-n,n]^d \cap \mathbb{Z}^d$.

heres my problem: Let $B(n) = [-n,n]^d \cap \mathbb{Z}^d$, and consider bond percolation with probability $p \in [0,1]$. Define $X_n$ as the fraction of vertices of $B(n)$ which are connected to the ...
1
vote
0answers
134 views

How is percolation defined and measured in social networks?

From the wikipedia article on percolation it appears that the theory is applicable to graphs in general, and this presentation describes the theory nicely. This review article on complex networks ...
10
votes
2answers
185 views

Edge percolation on $\mathbb{Z}^2$: probability that two neighbouring vertices are connected?

I'm considering edge percolation on $\mathbb{Z}^2$ with parameter $p$, so that edges are present with probability $p$. Is it known how to express the probability $P(p)$ that $(0,0)$ is in the same ...
3
votes
0answers
61 views

2-dimensional percolation and a random graph

Imagine turning the square grid defined by $\mathbb{N}^2$ in the plane into a directed graph. The vertices are $\mathbb{N}^2$ and for each vertex $(x,y)$, there is an edge pointing from it to $(x+1, ...
7
votes
0answers
117 views

Take an m x n grid, and in each box pick two opposite corners at random to connect. What can be said about the resulting pattern?

Inspired by the upcoming book 10 PRINT CHR$(205.5+RND(1)); : GOTO 10 by Nick Montfort et al., whose title derives from this particular example of emergent behavior. Here's an example: (Note that ...
3
votes
0answers
185 views

Does Kolmogorov 0-1 law apply to every translation invariant event?

Let $\Lambda$ be a lattice in $\mathbb{R}^d$, $d \ge 2$, thought of as an infinite graph. In percolation theory we consider properties random subgraphs of $\Lambda$. In site percolation $\Lambda^s_p$ ...
3
votes
0answers
59 views

percolation - number of cycles around the origin

I try to study Percolation Theory by "A mini course on percolation theory" of Jeffrey E. Steif. I am very curios about Exercise 2.4. Show that the number of cycles around the origin of length n is ...
2
votes
1answer
139 views

Percolation theory BK inequality

Let $X_1,\cdots X_n$ i.i.d bernoulli(p) r'v's Let $A = \sum_{i=1}^nX_i \geq l$, and $B= \sum_{i=1}^n X_i \geq k$ Then $A \circ B = \sum_{i=1}^nX_i \geq l+k$ (disjoint occurance of A, B) Im ...
1
vote
0answers
105 views

Branching process question

(Cross-posted from mathoverflow Q 93609) I am trying to analyze the following branching process. We start with a root (level 0) node. Each surviving node has two children, each of which may or may ...
2
votes
0answers
71 views

algebraic connectivity of the giant component [closed]

In percolation theory there is this idea of a giant component, and I am curious what is known about its algebraic connectivity. I looked on google but I was not able to find anything particularly ...
1
vote
1answer
267 views

Translation Invariant Random Variable (Percolation)

I'm currently studying the uniqueness of the infinite cluster in supercritical percolation. In the proof the rv $N$ counts the number of infinite clusters on the infinite 2-D square lattice. The claim ...
2
votes
0answers
58 views

Percolation and hopping, has it been described?

This ultimately relates to a physics question, but It wasn't getting any answers, on physics.stackexchange. As it crosses the boundaries of each subject I was advised to post it here: Has a system ...
3
votes
0answers
217 views

2d Brownian motion hitting a point

Let $\Omega\subset \mathbb C$ be a simply connected domain, $\tau = \exp(2\pi\mathrm i/3)$ and $a(\alpha),a(\tau\alpha),a(\tau^2\alpha)$ are some accessible points of $\Omega$. In this paper by S. ...
18
votes
1answer
546 views

How to create mazes on the hyperbolic plane?

I'm interested in building maze-like structures on the [5, 4] tiling of the hyperbolic plane, where by maze-like I mean something akin to a spanning tree of the underlying lattice: a subgraph of the ...