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

learn more… | top users | synonyms

1
vote
0answers
17 views

Reliability polynomial of Cartesian produt of graphs

The all-terminal reliability $R(p)$ of a graph is the probability that the graph remains connected after edges fail independently with probability $p$. Similar the two-terminal reliability ...
0
votes
0answers
36 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
163 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
21 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
1answer
24 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
37 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
252 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
100 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
109 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
91 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
134 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 ...
1
vote
0answers
142 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
191 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
120 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
193 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
144 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
106 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
270 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
60 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
222 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. ...
19
votes
1answer
551 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 ...