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

learn more… | top users | synonyms

1
vote
1answer
23 views

$k$ points of contact for percolation

In Grimmett's book on percolation near the beginning of Ch. 7, he summarizes the plan of proof of the result on percolation of slabs. We are in $\mathbb{Z}^d, d\ge2$, with his usual notation that ...
1
vote
1answer
42 views

What may be the number of connected components of this randomly generated topological space?

I hope there exists some answer to this but I am not very good in probability so i do not know how to tackle this problem. It's contemporary-art related so it might not have a good answer. ...
1
vote
2answers
26 views

Translation invariant event in percolation theory in $\mathbb{Z}^d$

At my probability theory proseminar I had a speech about the percolation theory and one of the topics I presented was the uniqueness of an infinite open cluster in Bernoulli bond percolation in ...
0
votes
0answers
47 views

Bond percolation probability on a Bethe lattice

I derived the bond-percolation probability for a Bethe lattice and my result disagrees with a seemingly reputable reference by Albert & Barabasi (see below). I would be happy if somebody could ...
1
vote
1answer
54 views

Percolation over the integers [closed]

Imagine a simple undirected graph with a countably infinite number of vertices, each labeled with an unique integer $v \in \mathbb{Z}$. Connect the vertices by edges randomly such that Each vertex ...
4
votes
2answers
35 views

amenable groups versus amenable graphs

In operator algebras, one is often concerned with amenable groups, defined by one of many equivalent conditions. http://en.wikipedia.org/wiki/Amenable_group#Equivalent_conditions_for_amenability In ...
0
votes
1answer
21 views

Generalized percolation problem

Consider a simple site percolation problem on, for example, a 2D square lattice. Each vertex is randomly either there or not with some probability. If two neighbouring vertices are present, then the ...
6
votes
0answers
51 views

Number of circuits that surround the square.

Consider a grid $G$ in the $\mathbb{R}^2$ plane formed by the points $(x,y)$ with integer coordinates i.e. $G=\{(x,y)\in\mathbb{R}^2: x\in\mathbb{Z},\;y\in\mathbb{Z} \}$. For $n>0$ let $B_n$ square ...
3
votes
1answer
76 views

Books on random permutations

I'm looking for books or introductory/expository articles about random permutations, in particular with regards to their cycle structure. EDIT: I forgot to mention that I'm especially interested in ...
0
votes
0answers
59 views

How to calculate the critical density estimation for “continuum” percolation model in “3D space” when we have “spatial correlation”?

I want to approximately estimate the critical density (lower bound for density) of balls in a cube to make sure that the upper and lower surfaces of the cube will be connected to each other through ...
0
votes
0answers
18 views

How many closed paths of length n are circling 0 on the square lattice?

The context is that i am studying a course on percolation and we use a very large bound which is $n * 3^n$. Is there a better one? Thanks
0
votes
0answers
40 views

Supercritical bond percolation on a square lattice in constrained geometry

Consider bond percolation on the square lattice (with, as usual, set of vertices ${(x,y):\; x,y \in Z}$ with parameter $p>1/2$. Let $\alpha>0$ and let A be the event that there is an infinite ...
0
votes
0answers
67 views

First-hitting probability for the 2D critical site percolation on triangular lattice

Consider critical site percolation on the triangular lattice with mesh-size $\delta$. Let $D$ be the domain $H\backslash[0;i]$ where $H$ is the complex upper half plane. Compute the probability $$ ...
1
vote
0answers
25 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
1answer
82 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 ...
20
votes
2answers
398 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
57 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
66 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
53 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 ...
18
votes
1answer
444 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
155 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 ...
12
votes
0answers
139 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 ...
6
votes
0answers
117 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
138 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
1answer
259 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
246 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
74 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, ...
8
votes
0answers
147 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
299 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
81 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
186 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
124 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 ...
1
vote
1answer
349 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
65 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
256 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. ...
21
votes
1answer
660 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 ...